Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization

ABSTRACT

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, "Age" and "Balance" are two numeric attributes, and "CardLoan" is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form((Age, Balance) ∈ P) ⇒ (CardLoan = Yes),which implies that bank customers whose ages and balances fall in a planar region P tend to use card loan with a high probability. We consider two classes of regions, rectangles and admissible (i.e. connected and x-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for gain, support, and confidence, respectively. We have implemented the algorithms for admissible regions, and constructed a system for visualizing the rules.

REFERENCES

• ACKT96: Tetsuo Asano , Danny Z. Chen , Naoki Katoh , Takeshi Tokuyama, Polynomial-time solutions to image segmentation, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.104-113, January 28-30, 1996, Atlanta, Georgia, United States
• AGI+92: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• AIS93a: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• AIS93b: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• AKM+87: A. Aggarwal, M. Klawe, S. Moran, P. Shot, and R. Wilbur. Geometric applications of a matrixsearching algorithm. Algorithmica, 2:209-233, 1987.
• AS94: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• Ben84: Jon Bentley. Programming pearls. Communications of the A CM, 27(27):865-871, September 1984.
• BFOS84: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
• FHLL93: Paul Fischer , Klaus-Uwe Höffgen , Hanno Lefmann , Tomasz Luczak, Approximations with Axis-Aligned Rectangles (Extended Abstract), Proceedings of the 9th International Symposium on Fundamentals of Computation Theory, p.244-255, August 23-27, 1993
• FMMT96a: Takeshi Fukuda , Yasuhido Morimoto , Shinichi Morishita , Takeshi Tokuyama, Mining optimized association rules for numeric attributes, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-191, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237708]
• FMMT96b: Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, and Takeshi Tokuyama. Data mining using two-dimensional optimized association rules: Scheme, algorithms, and visualization. In Technical Report, IBM Tokyo Research Laboratory, 1996.
• GJ77: M.R. Garey and D. S. Johnson. The rectilinear steiner tree problem is np complete. SIAM J. Appl. Math, 32:836-834, 1977.
• HCC92: Jiawei Han , Yandong Cai , Nick Cercone, Knowledge Discovery in Databases: An Attribute-Oriented Approach, Proceedings of the 18th International Conference on Very Large Data Bases, p.547-559, August 23-27, 1992
• KKS94: Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Supporting Data Mining of Large Databases by Visual Feedback Queries, Proceedings of the Tenth International Conference on Data Engineering, p.302-313, February 14-18, 1994
• MAR96: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• NH94a: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• NH94b: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• NKT89: G. L. Nemhauser , A. H. G. Rinnooy Kan , M. J. Todd, Optimization, Elsevier North-Holland, Inc., New York, NY, 1989
• PCY95: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• PS91: G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. In Knowledge Discovery in Databases, pages 229-248, 1991.
• PSF91: Gregory Piateski , William Frawley, Knowledge Discovery in Databases, MIT Press, Cambridge, MA, 1991
• Qui86: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• Qui93: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• SA96: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• SAD+93: Michael Stonebraker , Rakesh Agrawal , Umeshwar Dayal , Erich J. Neuhold , Andreas Reuter, DBMS Research at a Crossroads: The Vienna Update, Proceedings of the 19th International Conference on Very Large Data Bases, p.688-692, August 24-27, 1993

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Verification