Advances of the DBLearn System for Knowledge Discovery in Large Databases

1 Introduction

With the rapid growth of the number of databases and the tremendous amounts of data being collected and stored in databases, it is increasingly important to de­ velop software tools for data mining or knowledge discov­ ery in databases [Piatetsky-Shapiro and Frawley, 1991 ; Fayyad et al. , 1995].

Data mining is the extraction of "information" or "knowledge" from data, which helps understanding data in databases and automatic construction of knowledge­ bases from databases.

DBLearn is such a knowledge discovery system pro­ totype, developed in Simon Fraser University between 1989 and 1993 [Cai et al., 1991; Han et al., 1993; 1994]. It discovers characteristic rules and discrimi­ nant rules embedded in relational databases. The ma­ jor features of the system are speed and efficiency in analyzing large databases, interactive knowledge min­ ing, and smooth intergration with commercial relational database systems. Experiments with DBLearn have been performed in NSERC (Natural Science and Engineering

*Research is partially supported by the Nat ural Sciences and Engineering Research Council of Canada under the grant OGP0037230, by the Networks of Centres of Excellence Pro­ gram (with the participation of PRECARN association) un­ der the grant IRIS:HMI-5, and by a research grant from the Hughes Research Laboratories.

• A discriminator discovers a set of discriminant rules from the relevant set(s) of data in a database. A discriminant rule distinguishes the general features of one set of data, called the target class, from some other set(s) of data, called the contrasting class( es).
• An association rule finder discovers a set of asso­ ciation rules (in the form of "At 1\ · · · 1\ A; ---> B1 1\ · · · 1\ Bj'') at multiple concept levels from the relevant set(s) of data in a database. For example, it may find from a large set of transaction data an association rule that if a customer buys (one brand o/) milk, s/he usually buys (another brand o/) bread.

DBMiner offers both graphical and SQL-like interfaces. For example, to characterize Computer Science grants in the NSERC94 database in relevance to discipline and amount categories and the distribution of count% and amount%, the data mining query is as follows.

use NSERC94 characterize "CS_Discipline_Grants" from award A, grant-type G where A.granLcode = G.granLcode and A.disc_code = "Computer" in relevance to disc_code, amount, percentage( count), percentage( amount)

To process this query, the system first obtains the rel­ evant set of data by processing a relational database query, then generalizes the data using an attribute­ oriented induction approach [Cai et al., 1991; Han et al., 1993], and presents different forms of outputs , in­ cluding generalized relations, generalized feature tables, bar/pie charts, generalized rules, to outline the number or amount distribution of computer science (research) grants according to discipline categories (such as theory, AI, database, and so on),

In the development of other functional modules, attribute-oriented induction [Han et al., 1993; Han and Fu, 1995] also plays an essential role . It integrates a machine learning paradigm learning-from-examples [Michalski, 198:3] with set-oriented database operations and substan­ tially reduces the computational complexity of database learning processes.

The system also performs automatic generation of con­ ceptual hierarchies for numerical attributes and dynamic conceptual hierarchy adjustment [Han and Fu, 1994] for all the attributes based on the statistical distribution of the set of relevant data, which produces desirable gener­ alized results.

3 Further development of DBMiner

The DBMiner system is currently being extended in sev­ eral directions as follows.

• Further enhancement of the discovery power and ef­ ficiency for data mining in relational systems [Han and Fu, 1995], including the improvement of rule quality and system performance for the existing functional module, the development of techniques for mining new kinds of rules, etc.
• Integration, maintenance and application. of discov­ ered knowledge, including incremental update of discovered rules, merging of discovered rules into ex­ isting knowledge-bases, intelligent query answering using discovered knowledge, and the construction of multiple layered databases.
• Extension of data mining technique towards ad­ vanced and/or special purpose database systems , including extended-relational, object-oriented, de­ ductive, spatial, temporal, and heterogeneous databases.