The discovery of association rules from tabular databases comprising nominal and ordinal attributes

Article type: Research Article

Authors: Richards, G.^{; *} | Rayward-Smith, V.J.

Affiliations: School of Information Systems, University of East Anglia, Norwich, NR4 7TJ, UK. Tel.: +44 (0)1603 592308; Fax: +44 (0)1603 593344; E-mail: gr@cmp.uea.ac.uk, vjrs@cmp.uea.ac.uk

Correspondence: [*] Corresponding author.

Abstract: Classification rules are a convenient method of expressing regularities that exist within databases. They are particularly useful when we wish to find patterns that describe a defined class of interest, i.e. for the task of partial classification or “nugget discovery”. In this paper we address the problems of finding classification rules from databases containing nominal and ordinal attributes. The number of rules that can be formulated from a database is usually potentially vast due to the effect of combinatorial explosion. This means that generating all rules in order to find the best rules (according to some stated criteria) is usually impractical and alternative strategies must be used. In this paper we present an algorithm that delivers a clearly defined set of rules, the pc'-optimal set. This set describes the interesting associations in a database but excludes many rules that are simply minor variations of other rules. The algorithm addresses the problems of combinatorial explosion and is capable of finding rules from databases comprising nominal and ordinal attributes. In order to find the pc'-optimal set efficiently, novel pruning functions are used in the search that take advantage of the properties of the pc'-optimal set. Our main contribution is a method of on-the-fly pruning based on exploiting the relationship between pc'-optimal sets and ordinal data. We show that using these methods results in a very considerable increase in efficiency allowing the discovery of useful rules from many databases.

DOI: 10.3233/IDA-2005-9305

Journal: Intelligent Data Analysis, vol. 9, no. 3, pp. 289-307, 2005