Density biased sampling: an improved method for data mining and clustering

ABSTRACT

Data mining in large data sets often requires a sampling or summarization step to form an in-core representation of the data that can be processed more efficiently. Uniform random sampling is frequently used in practice and also frequently criticized because it will miss small clusters. Many natural phenomena are known to follow Zipf's distribution and the inability of uniform sampling to find small clusters is of practical concern. Density Biased Sampling is proposed to probabilistically under-sample dense regions and over-sample light regions. A weighted sample is used to preserve the densities of the original data. Density biased sampling naturally includes uniform sampling as a special case. A memory efficient algorithm is proposed that approximates density biased sampling using only a single scan of the data. We empirically evaluate density biased sampling using synthetic data sets that exhibit varying cluster size distributions finding up to a factor of six improvement over uniform sampling.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: P.S Bradley, Usama Fayyad, and Cory Reina. Scaling clustering algorithms to large databases. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD- 98), pages 9-15, New York City, New York, August 1998. AAAI Press.
• 3: P.S Bradley, Usama Fayyad, and Cory Reina. Scaling EM (expectation maximization) clustering to large databases. Technical Report MSR-TR-98- 35, Microsoft Research, Redmond, WA, November, 1998.
• 4: Chris Buckley, Mandar Mitra, Janet Walz, and Clarie Cardie. Using clustering and superconcepts within SMART: TREC 6. In Sixth Text REtrieval Conference (TREC-6), Gaithersburg, Maryland, November 1997. National Institute of Standards and Technology (NIST), United States Department of Commerce.
• 5: Christos Faloutsos , H. V. Jagadish, On B-Tree Indices for Skewed Distributions, Proceedings of the 18th International Conference on Very Large Data Bases, p.363-374, August 23-27, 1992
• 6: Christos Faloutsos , Yossi Matias , Abraham Silberschatz, Modeling Skewed Distribution Using Multifractals and the `80-20' Law, Proceedings of the 22th International Conference on Very Large Data Bases, p.307-317, September 03-06, 1996
• 7: Usama M. Fayyad, Cory A. Reina, and Paul S. Bradley. Initialization of iterative refinement clustering algorithms. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), pages 194-198, New York City, New York, August 1998. AAAI Press.
• 8: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
• 9: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, ACM SIGMOD Record, v.27 n.2, p.73-84, June 1998
• 10: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 11: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 12: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 13: Bernardo A. Huberman, Peter L. T. Pirolli, James E. Pitkow, and Rajan M. Lukose. Strong regularities in world wide web surfing. Science, 280(5360):95-97, April 3 1998.
• 14: Najmeh Joze-Hkajavi and Kenneth Salem. Twophase clustering of large datasets. Technical Report CS-98-27, Department of Computer Science, University of Waterloo, November 1998.
• 15: Jeremy Kepner, Xiaohui Fan, Neta Buhcall, James Gunn, Robert Lupton, and Ghohung Xu. An automated cluster finder: the adaptive matched filter. The Astrophysics Journal, 517, 1999.
• 16: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 17: Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, ACM SIGMOD Record, v.19 n.2, p.375-386, Jun. 1990
• 18: Edie Rasmussen, Clustering algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 19: Brian D. Ripley. Spatial Statistics. John Wiley & Sons, 1981.
• 20: Manfred Schroeder. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, 1991.
• 21: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 22: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 23: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, ACM SIGMOD Record, v.25 n.2, p.103-114, June 1996
• 24: G.K. Zipf. Human Behavior and Principle of Least Effort: An Introduction to Human Ecology. Addison Wesley, Cambridge, Massachusetts, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing

General Terms:
Design, Theory, Verification