Learning classification rules by randomized iterative local search

by Chisholm, Michael (Michael

Learning easily understandable decision rules from examples is one of the classic

problems in machine learning. Most learning algorithms for this problem employ some variation

of a greedy separate-and-conquer algorithm. In this paper, we describe a system called LERILS

that learns highly accurate and comprehensible rules from examples using a randomized iterative

local search inspired by algorithms like WalkSat and simulated annealing. We compare its

performance to C4.5, RIPPER, and CN2 on 11 data sets from the UCI machine learning

repository. We show that LERILS can outperform C4.5 most of the time and sometimes it can

even best RIPPER. While its accuracy is comparable to CN2, its rules are shorter and fewer, and

hence are more human-comprehensible.