"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

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.

Download this paper as a PDF file. (Size = 120 KB)

Visit Dr. Triantaphyllou's homepage.