Establishing the foundations of data mining
Edward L. Robertson, Mehmet Dalkılıç · 2000
The main contribution of this dissertation establishes a bridge between data and two well-studied areas: Rough Sets and Information Theory. There are two main parts. The first part establishes a coherent framework for data mining. Observing that data mining depends on two partitions, the classifier and the estimator, we define the classifier/estimator (CE) framework. The classifier indicates the target of the data mining investigation. The classifier may be difficult to express from the data instance or may involve an “oracle” beyond the extant data. The estimator is typically simply expressible using the data instance. The degree to which the estimator refines the classifier partition can be used to measure how well the data instance matches the concept being investigated. The CE framework is shown to generalize a variety of data mining and database concepts, including rough sets, functional dependency, multivalued dependency, and association rules. Furthermore, the CE framework suggests a wider range of data mining questions. Additionally, the CE framework is shown to naturally express qualitative and quantitative measures and allows a question to be posed at a number of different conceptual scopes from local to global interests. The second part uses the tools of information theory to examine and reason about the information content of the attributes within a relation instance. For two sets of attributes X and Y, an information dependency measure (InD measure) characterizes the uncertainty remaining about the values for the set Y when the values for the set X are known. A variety of arithmetic inequalities (InD inequalities) are shown to hold among InD measures; InD inequalities hold in any relation instance. Numeric constraints (InD constraints) on InD measures, consistent with the InD inequalities, can be applied to relation instances. Remarkably, functional and multivalued dependencies correspond to setting certain constraints to zero, with Armstrong's axioms shown to be consequences of the arithmetic inequalities applied to constraints. As an analog of completeness, for any set of constraints consistent with the inequalities, we may construct a relation instance that approximates these constraints within any positive e. InD measures suggest many valuable applications in areas such as data mining.