Data Mining Using Two-Dimensional Optimized Accociation Rules: Scheme, Algorithms, and Visualization.

@inproceedings{DBLP:conf/sigmod/FukudaMMT96,
  author    = {Takeshi Fukuda and
               Yasuhiko Morimoto and
               Shinichi Morishita and
               Takeshi Tokuyama},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Data Mining Using Two-Dimensional Optimized Accociation Rules:
               Scheme, Algorithms, and Visualization},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {13-23},
  ee        = {http://doi.acm.org/10.1145/233269.233313, db/conf/sigmod/FukudaMMT96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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) in P) => (CardLoan = Yes),

which implies that bank customers whose ages and balances fall in a planar region P tend to use 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.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[ACKT96]

Tetsuo Asano, Danny Z. Chen, Naoki Katoh, Takeshi Tokuyama: Polynomial-Time Solutions to Image Segmentation. SODA 1996: 104-113 BibTeX

[AGI+92]

Rakesh Agrawal, Sakti P. Ghosh, Tomasz Imielinski, Balakrishna R. Iyer, Arun N. Swami: An Interval Classifier for Database Mining Applications. VLDB 1992: 560-573 BibTeX

[AIS93a]

Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Database Mining: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 5(6): 914-925(1993) BibTeX

[AIS93b]

Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993: 207-216 BibTeX

[AKM+87]

Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, Robert E. Wilber: Geometric Applications of a Matrix-Searching Algorithm. Algorithmica 2: 195-208(1987) BibTeX

[AS94]

Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994: 487-499 BibTeX

[Ben84]

Jon Louis Bentley: Algorithm Design Techniques. Commun. ACM 27(9): 865-871(1984) BibTeX

[BFOS84]

Leo Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone: Classification and Regression Trees. Wadsworth 1984, ISBN 0-534-98053-8
BibTeX

[FHLL93]

Paul Fischer, Klaus-Uwe Höffgen, Hanno Lefmann, Tomasz Luczak: Approximations with Axis-Aligned Rectangles (Extended Abstract). FCT 1993: 244-255 BibTeX

[FMMT96a]

Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Mining Optimized Association Rules for Numeric Attributes. PODS 1996: 182-191 BibTeX

[FMMT96b]

...

[GJ77]

M. R. Garey, David S. Johnson: The Rectilinear Steiner Tree Problem in NP Complete. SIAM Journal of Applied Mathematics 32: 826-834(1977) BibTeX

[HCC92]

Jiawei Han, Yandong Cai, Nick Cercone: Knowledge Discovery in Databases: An Attribute-Oriented Approach. VLDB 1992: 547-559 BibTeX

[KKS94]

Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl: Supporting Data Mining of Large Databases by Visual Feedback Queries. ICDE 1994: 302-313 BibTeX

[MAR96]

Manish Mehta, Rakesh Agrawal, Jorma Rissanen: SLIQ: A Fast Scalable Classifier for Data Mining. EDBT 1996: 18-32 BibTeX

[NH94a]

Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155 BibTeX

[NH94b]

Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155 BibTeX

[NKT89]

...

[PCY95]

Jong Soo Park, Ming-Syan Chen, Philip S. Yu: An Effective Hash Based Algorithm for Mining Association Rules. SIGMOD Conference 1995: 175-186 BibTeX

[PS91]

Gregory Piatetsky-Shapiro: Discovery, Analysis, and Presentation of Strong Rules. Knowledge Discovery in Databases 1991: 229-248 BibTeX

[PSF91]

Gregory Piatetsky-Shapiro, William J. Frawley (Eds.): Knowledge Discovery in Databases. AAAI/MIT Press 1991, ISBN 0-262-62080-4
Contents BibTeX

[Qui86]

J. Ross Quinlan: Induction of Decision Trees. Machine Learning 1(1): 81-106(1986) BibTeX

[Qui93]

J. Ross Quinlan: C4.5: Programs for Machine Learning. Morgan Kaufmann 1993, ISBN 1-55860-238-0
BibTeX

[SA96]

Ramakrishnan Srikant, Rakesh Agrawal: Mining Quantitative Association Rules in Large Relational Tables. SIGMOD Conference 1996: 1-12 BibTeX

[SAD+93]

Michael Stonebraker, Rakesh Agrawal, Umeshwar Dayal, Erich J. Neuhold, Andreas Reuter: DBMS Research at a Crossroads: The Vienna Update. VLDB 1993: 688-692 BibTeX

Referenced by

1. Shinichi Morishita, Jun Sese: Traversing Itemset Lattice with Statistical Metric Pruning. PODS 2000: 226-236
2. Laks V. S. Lakshmanan, Raymond T. Ng, Jiawei Han, Alex Pang: Optimization of Constrained Frequent Set Queries with 2-variable Constraints. SIGMOD Conference 1999: 157-168
3. Johannes Gehrke, Venkatesh Ganti, Raghu Ramakrishnan, Wei-Yin Loh: BOAT-Optimistic Decision Tree Construction. SIGMOD Conference 1999: 169-180
4. Rajeev Rastogi, Kyuseok Shim: Mining Optimized Support Rules for Numeric Attributes. ICDE 1999: 206-215
5. Sridhar Ramaswamy, Sameer Mahajan, Abraham Silberschatz: On the Discovery of Interesting Patterns in Association Rules. VLDB 1998: 368-379
6. Yasuhiko Morimoto, Takeshi Fukuda, Hirofumi Matsuzawa, Takeshi Tokuyama, Kunikazu Yoda: Algorithms for Mining Association Rules for Binary Segmentations of Huge Categorical Databases. VLDB 1998: 380-391
7. Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han, Alex Pang: Exploratory Mining and Pruning Optimizations of Constrained Association Rules. SIGMOD Conference 1998: 13-24
8. Rajeev Rastogi, Kyuseok Shim: Mining Optimized Association Rules with Categorical and Numeric Attributes. ICDE 1998: 503-512
9. Banu Özden, Sridhar Ramaswamy, Abraham Silberschatz: Cyclic Association Rules. ICDE 1998: 412-421
10. Takeshi Fukuda, Hirofumi Matsuzawa: Parallel Processing of Multiple Aggregate Queries on Shared-Nothing Multiprocessors. EDBT 1998: 278-292
11. Yasuhiko Morimoto, Hiromu Ishii, Shinichi Morishita: Efficient Construction of Regression Trees with Range and Region Splitting. VLDB 1997: 166-175
12. Sergey Brin, Rajeev Motwani, Craig Silverstein: Beyond Market Baskets: Generalizing Association Rules to Correlations. SIGMOD Conference 1997: 265-276
13. Heikki Mannila: Methods and Problems in Data Mining. ICDT 1997: 41-55
14. Brian Lent, Arun N. Swami, Jennifer Widom: Clustering Association Rules. ICDE 1997: 220-231
15. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Constructing Efficient Decision Trees by Using Optimized Numeric Association Rules. VLDB 1996: 146-155
16. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: SONAR: System for Optimized Numeric AssociationRules. SIGMOD Conference 1996: 553
17. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Mining Optimized Association Rules for Numeric Attributes. PODS 1996: 182-191