Uncertain centroid based partitional clustering of uncertain data
Open Access
- 1 March 2012
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 5 (7) , 610-621
Abstract
Clustering uncertain data has emerged as a challenging task in uncertain data management and mining. Thanks to a computational complexity advantage over other clustering paradigms, partitional clustering has been particularly studied and a number of algorithms have been developed. While existing proposals differ mainly in the notions of cluster centroid and clustering objective function, little attention has been given to an analysis of their characteristics and limits. In this work, we theoretically investigate major existing methods of partitional clustering, and alternatively propose a well-founded approach to clustering uncertain data based on a novel notion of cluster centroid. A cluster centroid is seen as an uncertain object defined in terms of a random variable whose realizations are derived based on all deterministic representations of the objects to be clustered. As demonstrated theoretically and experimentally, this allows for better representing a cluster of uncertain objects, thus supporting a consistently improved clustering performance while maintaining comparable efficiency with existing partitional clustering algorithms.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Metric and trigonometric pruning for clustering of uncertain data in 2D geometric spaceInformation Systems, 2011
- Representing uncertain data: models, properties, and algorithmsThe VLDB Journal, 2009
- Approximation algorithms for clustering uncertain data2008
- Clustering Uncertain Data Via K-Medoids2008
- Efficient Clustering of Uncertain DataIEEE International Conference on Data Mining (ICDM), 2006
- Uncertain Data Mining: An Example in Clustering Location Data2006
- Model-based approximate querying in sensor networksThe VLDB Journal, 2005
- Density-based clustering of uncertain data2005
- A tractable probabilistic model for Affymetrix probe-level analysis across multiple chipsBioinformatics, 2005
- Managing uncertainty in moving objects databasesACM Transactions on Database Systems, 2004