"A Heuristic for Mining Association Rules
In Polynomial Time"
Mathematical and Computer Modelling,
No. 37, pp. 219-233, 2003.
Yilmaz, E., E. Triantaphyllou, J. Chen, and T.W. Liao
Abstract:
Mining association rules from databases has attracted great
interest because of its potentially very practical applications.
Given a database, then the problem of interest is how to mine
association rules (i.e., patterns of consumers' behaviors) in an
efficient and effective way. The databases involved in today's
information society can be very large. Thus, fast and effective
algorithms are needed to mine association rules out of large
databases. Previous approaches may cause an exponential
computing resource consumption. A combinatorial explosion occurs
because existing approaches exhaustively mine all the rules. The
proposed algorithm takes a previously developed approach, called
the Randomized Algorithm 1 (or RA1), and adapts it to mine
association rules out of a database in an efficient way. The RA1
approach was primarily developed for inferring logical clauses
from examples. Numerous computational results suggest that the
new approach is very promising.
Key Words:
Data mining, association rules, algorithm analysis, the one
clause at a time (OCAT) approach, randomized algorithms,
heuristics.