Elon Computing Sciences

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.