Decision tree based induction of decision lists

Abstract

This paper addresses the problem of using decision lists for building machine learning algorithms. In this work, we first highlight the expressive power of Decision Lists (DL), which were already known to generalize decision trees. We also present ICDL, a new algorithm for learning simple decision lists. This problem – learning low size and high accuracy lists – is, as we prove formally, theoretically hard and calls for the use of heuristics such as CN2, BruteDL or ICDL. Our method is based on an original technique midway between learning rule based procedures and decision trees. ICDL operates in two stages: it first greedily builds a large decision list then prunes it to obtain a smaller yet accurate one, thereby avoiding the drawbacks associated with the first phase alone. Experimental results show the efficiency of our approach by comparing them to the two well-known algorithms CN2 and C4.5. ICDL's time complexity is low. It produces decision lists whose size is far smaller compared to both CN2 and C4.5, and whose accuracy also compares favourably with theirs. Finally, ICDL has the advantage that it can also be used to build decision trees using a CART-like scheme. Thus, our algorithm has the particularity to be able to provide two different types of widely used classifiers, which the user can choose freely.