Approximation algorithms for clustering uncertain data

ABSTRACT

There is an increasing quantity of data with uncertainty arising from applications such as sensor network measurements, record linkage, and as output of mining algorithms. This uncertainty is typically formalized as probability density functions over tuple values. Beyond storing and processing such data in a DBMS, it is necessary to perform other data analysis tasks such as data mining. We study the core mining problem of clustering on uncertain data, and define appropriate natural generalizations of standard clustering optimization criteria. Two variations arise, depending on whether a point is automatically associated with its optimal center, or whether it must be assigned to a fixed cluster no matter where it is actually located.

For uncertain versions of k-means and k-median, we show reductions to their corresponding weighted versions on data with no uncertainties. These are simple in the unassigned case, but require some care for the assigned version. Our most interesting results are for uncertain k-center, which generalizes both traditional k-center and k-median objectives. We show a variety of bicriteria approximation algorithms. One picks O(kε--¹log²n) centers and achieves a (1 + ε) approximation to the best uncertain k-centers. Another picks 2k centers and achieves a constant factor approximation. Collectively, these results are the first known guaranteed approximation algorithms for the problems of clustering uncertain data.

REFERENCES

• 1: C. Aggarwal and P. S. Yu. Framework for clustering uncertain data streams. In IEEE International Conference on Data Engineering, 2008.
• 2: David Arthur , Sergei Vassilvitskii, k-means++: the advantages of careful seeding, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1027-1035, January 07-09, 2007, New Orleans, Louisiana
• 3: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , Vinayaka Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, v.33 n.3, p.544-562, 2004 [doi>10.1137/S0097539702416402]
• 4: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 5: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 7: M. Chau, R. Cheng, B. Kao, and J. Ngai. Uncertain data mining: An example in clustering location data. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
• 8: Graham Cormode , Minos Garofalakis, Sketching probabilistic data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247513]
• 9: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007 [doi>10.1007/s00778-006-0004-3]
• 10: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.
• 11: J. C. Dunn. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Journal of Cybernetics, 3:32--57, 1973.
• 12: M. Dyer and A. Frieze. A simple heuristic for the p-center problem. Operations Research Letters, 3:285--288, 1985.
• 13: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, page 226, 1996.
• 14: Dan Feldman , Morteza Monemizadeh , Christian Sohler, A PTAS for k-means clustering based on weak coresets, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247072]
• 15: T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38(2-3):293--306, 1985.
• 16: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 17: S. Har-Peled. Geometric approximation algorithms. http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/book.pdf, 2007.
• 18: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 19: D. Hochbaum and D. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180--184, May 1985.
• 20: Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
• 21: Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007413]
• 22: T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265565]
• 23: Stavros G. Kolliopoulos , Satish Rao, A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem, Proceedings of the 7th Annual European Symposium on Algorithms, p.378-389, July 16-18, 1999
• 24: Amit Kumar , Yogish Sabharwal , Sandeep Sen, A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 25: J. B. MacQueen. Some method for the classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Structures, pages 281--297, 1967.
• 26: Wang Kay Ngai , Ben Kao , Chun Kit Chui , Reynold Cheng , Michael Chau , Kevin Y. Yip, Efficient Clustering of Uncertain Data, Proceedings of the Sixth International Conference on Data Mining, p.436-445, December 18-22, 2006 [doi>10.1109/ICDM.2006.63]
• 27: Rina Panigrahy , Sundar Vishwanathan, An O(log*n) approximation algorithm for the asymmetric p-center problem, Journal of Algorithms, v.27 n.2, p.259-268, May 1, 1998 [doi>10.1006/jagm.1997.0921]
• 28: 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:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms

Keywords:
clustering, probabilistic data