סמינר מחלקתי - המחלקה להנדסת תעשייה

IMPROVEMENTS IN THE CONSTRUCTION OF EFFICIENT DECISION TREES

M.Sc. student - Chavatzelet Tryster

Abstract

In the field of decision trees, most existing trees aim to reduce the classification error. Few decision tree algorithms concentrate their efforts on reducing the weighted average number of tests required to reach classification. Most decision trees work with greedy algorithms that generally give reasonable results, although in many cases, far from the optimal solution. Some attempts have been made to reduce the greediness of these algorithms by incorporating look-ahead functions. These efforts have met with problematic results whereby, in some cases, increasing the look-ahead caused an increase in the weighted average number of tests instead of a decrease. Moreover, these look-ahead functions increase the complexity of the algorithm exponentially.

We propose an alternative algorithm, based on the existing GOTA algorithm as developed by Hartmann et al. (1982) that allows for constant improvement of the weighted average number of tests, without any risk of increasing this measure.  The algorithm builds multiple trees, each one using a one step look-ahead method. The number of trees built depends upon an algorithm parameter supplied by the user, indicating the number of possibilities to be explored at each level of the tree. The algorithm has a more moderate increase in complexity as opposed to the look-ahead functions and, according to numerical results, returned very satisfactory results in a fraction of the time required by standard look-ahead algorithms, eventually converging to the optimal solution.

העבודה התבצעה בהנחיית פרופ' עירד בן-גל.

ההרצאה תתקיים ביום ג', 1.05.12, בשעה 13:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.