Data mining, hypergraph transversals, and machine learning (extended abstract)

Publisher Website
Google Scholar
Abstract
Several data mining problems can be formulated as problems of finding maximally specific sentences that are interesting in a database. We first show that this problem has a close relationship with the hypergraph transversal problem. We then analyze two algorithms that have been previously used in data mining, proving upper bounds on their complexity. The first algorithm is useful when the maximally specific interesting sentences are "small". We show that this al- gorithm can also be used to efficiently solve a special case of the hypergraph transversal problem, improving on previ- ous results. The second algorithm utilizes a subroutine for hypergraph transversals, and is applicable in more general situations, with complexity close to a lower bound for the problem. We also relate these problems to the model of ex- act learning in computational learning theory, and use the correspondence to derive some corollaries.

This publication has 9 references indexed in Scilit: