Knowledge Discovery with Second-Order Relations

This paper presents an induction technique that discovers a set of classification rules, from a set of examples, using second-order relations as a representational model. Second-order relations are database relations in which tuples have sets of atomic values as components. Using sets of values, which are interpreted as disjunctions, provides compact representations that facilitate efficient management and enhance comprehensibility. The second-order relational framework is based on theoretical foundations that link relational database theory, machine learning, and logic synthesis. The rule induction technique can be viewed as a second-order relation compression problem in which the original relation, representing training data, is transformed into a second-order relation with fewer tuples by merging tuples in ways that preserve consistency with the training data. This problem is closely related to two-level Boolean function minimization in logic synthesis. We describe a rule-mining system, SORCER, and compare its performance to two state-of-the-art classification systems: C4.5 and CBA. Experimental results based on the average of error rates over 26 data sets show that SORCER, using a simple compression scheme, outperforms C4.5 and is competitive to CBA. Using a slightly more sophisticated compression scheme, SORCER outperforms both C4.5 and CBA.

Authors and Affiliations

1. Institute for Human and Machine Cognition, University of West Florida, Pensacola FL, USA, , , , , , US

   Rattikorn Hewett & John Leuchner

Received 5 October 1999 / Revised 15 February 2001 / Accepted in revised form 10 August 2001

Correspondence and offprint requests to: R. Hewett, Institute for Human and Machine Cognition, University of West Florida, 40 South Alcaniz Street, Pensacola, FL 32501, USA. Email: rhewett@ai.uwf.eduau

Reprints and permissions