Clustering transactions using large items

ABSTRACT

In traditional data clustering, similarity of a cluster of objects is measured by pairwise similarity of objects in that cluster. We argue that such measures are not appropriate for transactions that are sets of items. We propose the notion of large items, i.e., items contained in some minimum fraction of transactions in a cluster, to measure the similarity of a cluster of transactions. The intuition of our clustering criterion is that there should be many large items within a cluster and little overlapping of such items across clusters. We discuss the rationale behind our approach and its implication on providing a better solution to the clustering problem. We present a clustering algorithm based on the new clustering criterion and evaluate its effectiveness.

REFERENCES

• 1: 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
• 2: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 3: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 4: Peter Cheeseman , John Stutz, Bayesian classification (AutoClass): theory and results, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 5: Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
• 6: M. Ester, H-P Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. KDD 1996
• 7: S. Guba, R. Rastogi, K. Shim. A clustering algorithm for categorical attributes. ICDE 1999
• 8: E.H. Hart, G. Karypis, V. Kumar and B. Mobasher. Clustering based on association rule hypergraphs. SIGMOD workshop on research issues on Data Mining and Knowledge Discovery, 1997
• 9: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 10: L. Kaufman and P.J. Rousseeuw. Finding groups in data: an introduction to cluster analysis, John Wiley 8c Son, 1990
• 11: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 12: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 13: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 14: Xiaowei Xu , Martin Ester , Hans-Peter Kriegel , Jörg Sander, A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.324-331, February 23-27, 1998
• 15: O. Zamir, O. Etzioni, O. Madani and R. M. Karp. Fast and intuitive clustering of web documents. KDD 1997, 287-290
• 16: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory