Extending the ID3 Algorithm to Handle Confidence Values

Presentation at Elon Student Undergraduate Research Forum, Spring 2009

Thomas William Porter (Dr. Shannon P. Duvall) Department of Computing Sciences

An expert system is a computer application that performs a task that would otherwise be performed by a human expert. For example, there are expert systems that can diagnose medical illnesses, make financial forecasts, and provide strategy in video games. ID3 is an algorithm that uses inductive inference from examples to create an expert system. For example, given several accounts of a doctor’s diagnosis based on patients’ symptoms, the program can attempt diagnoses of its own. In many real-world applications, some pieces of information could be more relevant or more credible than other pieces of information in a given database. For our medical diagnoses example, a patient may or may not know he has
a symptom or may give irrelevant or imagined symptoms.

A confidence measure is a real number, between 0 and 1, dictating how one piece of information should weigh in making the decision. ID3 in its current form cannot handle this distinction and weighs each piece of information the same, perhaps providing skewed results in the presence of erroneous information. My work uses Bayes’ Theorem to create a new algorithm to handle this measure of confidence. This new algorithm was tested on data sets and compared against the original algorithm and showed to be more effective when in the presence of erroneous information. As a result, the new learning program can be applied to more varied and real-world applications.