PDF《(Extended Abstract)》

In ECML-95: Proceedings of the Eighth European Conference on Machine Learning, Heraklion, Crete, Greece, 1995.

Learning Classification Rules Using Lattices (Extended Abstract) Mehran Sahami Computer Science Department, Stanford University, Stanford, CA 94305, USA Email: sahami@CS.Stanford.EDU Abstract. This paper presents a novel induction algorithm, Rulearner, which induces classification rules using a Galois lattice as an explicit map through the search space of rules. The Rulearner system is shown to compare favorably with commonly used symbolic learning methods which use heuristics rather than an explicit map to guide their search through the rule space. Furthermore, our learning system is shown to be robust in the presence of noisy data. The Rulearner system is also capable of learning both decision lists and unordered rule sets allowing for comparisons of these different learning paradigms within the same algorithmic framework.

1 Introduction Research in rule induction by means of search [MC, 1969;

MI, 1982;

CN, 1989] has been on-going for some time. While some systems, such as Version Spaces, make direct use of the data to be learned during rule induction, such methods are highly sensitive to noisy data. In other systems, the search through the space of rules is guided by heuristics as opposed to using the data to build an explicit map through the space of rules to induce. In this capacity, such algorithms are only data-driven to the extent that the heuristics employed in them make use of the data to be learned. We present the Rulearner system which seeks to combine both the direct use of data with robustness in the presence of noise during the rule induction process. Since the algorithm uses a Galois lattice constructed from training data [OO, 1988] as an explicit guide through the rule space, the algorithm is directly data-driven as it does not simply heuristically fit the training data. Our system is also capable of inducing both an unordered set of classification rules as well as a decision list [RI, 1987]. This allows for the Rulearner system to be used in making direct comparisons between these two learning paradigms within a single algorithmic framework. Several experiments with the Rulearner system are presented comparing it with the commonly used symbolic learning systems C4.5 [QU, 1993] and CN2 [CN, 1989].

2 Lattice Definitions A lattice is defined to be a directed acyclic graph in which any two nodes, u and v, have a unique join (a node higher in the graph to which a u and v are connected by minimal length paths) and a unique meet (a node lower in the graph which is connected to u and v by minimal length paths) ― referred to respectively as least upper bounds and greatest lower bounds in formal mathematics. We also define: Definition 1. The upward closure of node u, denoted UC(u), is the set of all nodes, including u, that can be reached from u following upward arcs in the lattice. Definition 2. The downward closure of a node u, denoted DC(u), is the set of all nodes which contain u in their upward closure. Definition 3. The cover of a node u, denoted Cover(u), is the number of instance nodes in DC(u). Our lattices are defined by representing each training instance by a single node (referred to as an instance node) in the lowest level of the lattice. In the greatest level of the lattice we create a node for every possible feature that an instance in the training set may have (referred to as feature nodes). These two sets of nodes uniquely define a set of internal arcs and nodes which comprise the complete lattice. We use the GRAND algorithm [OO, 1988] for lattice construction in our experiments.