Learning classification rules by randomized iterative local search

Graduation date: 2000Learning easily understandable decision rules from examples is one of the classic\ud problems in machine learning. Most learning algorithms for this problem employ some variation\ud of a greedy separate-and-conquer algorithm. In this paper, we describe a system called LERILS\ud that learns highly accurate and comprehensible rules from examples using a randomized iterative\ud local search inspired by algorithms like WalkSat and simulated annealing. We compare its\ud performance to C4.5, RIPPER, and CN2 on 11 data sets from the UCI machine learning\ud repository. We show that LERILS can outperform C4.5 most of the time and sometimes it can\ud even best RIPPER. While its accuracy is comparable to CN2, its rules are shorter and fewer, and\ud hence are more human-comprehensible