Three Geometric Approaches for representing Decision Rules in a Supervised Learning System

Three Geometric Approaches for representing Decision Rules in a Supervised Learning System Jesús Aguilar, José Riquelme y Miguel Toro Departamento de Lenguajes y Sistemas Informáticos. Facultad de Informática y Estadística. Universidad de Sevilla. E-mail: {aguilar, riquelme, mtoro}@lsi.us.es This paper describes a system for learning rules based on different geometric representations. The method uses a genetic algorithm (GA) to find out decision rules according to one of the three possible shapes: hyperrectangles, rotated hyperrectangles and hyperellipses. These geometric representation are internally codified as individuals of the population of the GA. The result is a decision queue (DQ) for each representation. It means that the obtained rules must be applied in specific order. With this policy, the number of rules may be reduced because the rules could be one inside of another. The user decides what representation provides the best accuracy and what produces the smaller number of rules. Sometimes, the linguistic interpretation of the rule set –with few rulesis more important than the exact classification of an unseen example –with too many rules-. Therefore, the system offers an ideal tool to select the best solutions oriented to our particular problem. In previous works [1,3], we presented a system to classify databases by using hyperrectangles (axisparallel). This system used a GA to search the best solutions and produced a hierarchical set of rules. The hierarchy follows that an example will be classified by the i-rule if it does not satisfy the conditions of the i-1 precedent rules. The rules are sequentially obtained until the space is totally covered. The behavior is similar to a queue, for that reason we have given the name decision queue (DQ) to the produced rule set. This concept is based on the k-DL, the set of decision lists with conjunctive clauses of size at most k at each decision [4]. DQ is based on DL. Really, DQ is a DL-generalization because it permits codifying functions fi of continuous attributes and the values vi can belong to any set. DQ presents the following structure: If conditions Then class Else If conditions Then class Else If conditions Then class ............................................ Else “unknown class” The experiments described in this section are from UCI Repository. DATABAS C4.5 AXIS-PARALLEL ROTATED HYPERREC. HYPERELLIPTICAL #RULES ERROR #RULES ERROR #RULES ERROR #RULES ERROR IRIS 4.4 6.3 3.4 7.47 3.6 4.83 4.2 5.6 PIMA 77.6 28.4 20.0 27.2 17.4 26.35 7.4 26.8 CANCER 5.2 13.8 2.2 4.24 2.2 5.38 2.6 5.0 Table. Databases (number of examples, dimension, number of classes). The number of rules is reduced with regard to other systems, like C4.5 [2], and improves the flexibility to construct a classifier varying the relaxing coefficient. References: [1] Aguilar, J., Riquelme, J. and Toro, M. A Tool to obtain a Hierarchical Qualitative Set of Rules from Quantitative Data. Lectures Notes in Artificial Intelligence 1415. pp 336-346. Springer-Verlag, 1998. [2] Quinlan, J. R. C4.5: programs for Machine Learning. Morgan Kaufmann Pub.,1993. [3] Riquelme J. and Aguilar, J. Revista Iberoamericana de Inteligencia Artificial nº 5. A GA-based Tool to obtain a Hierarchical Classifier for Supervised Learning. (in spanish) pp 38-43, 1998. [4] Rivest, R.L. Learning Decision Lists. Machine Learning, 87. pp. 229-246.