Discrete Deterministic Data Mining as Knowledge Compilation

Abstract

In the subfield of data analysis known as Discrete Deterministic Data Mining, notions from Formal Concept Analysis have been used to design a procedure to construct association rules. Empirically, this method has proved effective in practice for certain relevant tasks. We mathematically prove that these methods, rephrased in a Propositional Logic framework, compute the so-called Empirical Horn Approximation, which is a major model of Knowledge Compilation and is well-known to produce very good practical results in several fields of Artificial Intelligence. (This talk represents joint work with J. Baixeries, and appears in the Workshop on Discrete Math and Data Mining at SIAM DM Conference, 2003.) Jose Luis Balcazar is Professor in the department of Llenguatges i Sistemes Informatics at the Universitat Politecnica de Catalunya, Barcelona. Professor Balcazar has research interests in Data Mining, Computational Learning Theory, and Complexity Theory, is the author of many research articles in these areas, and is an author of the well-known books on structural complexity theory (Structural Complexity I and II).