Clustering Uncertain Data Using Voronoi Diagrams and R-Tree Index
Authors:
Open Access
- 20 May 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 22 (9) , 1219-1233
Abstract
Abstract-We study the problem of clustering uncertain objects whose locations are described by probability density functions (pdfs). We show that the UK-means algorithm, which generalizes the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (EDs) between objects and cluster representatives. For arbitrary pdfs, expected distances are computed by numerical integrations, which are costly operations. We propose pruning techniques that are based on Voronoi diagrams to reduce the number of expected distance calculations. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previously known in the literature. We then introduce an R-tree index to organize the uncertain objects so as to reduce pruning overheads. We conduct experiments to evaluate the effectiveness of our novel techniques. We show that our techniques are additive and, when used in combination, significantly outperform previously known methods.Keywords
This publication has 26 references indexed in Scilit:
- Approximation algorithms for clustering uncertain data2008
- Reducing UK-Means to K-Means2007
- Efficient Evaluation of Imprecise Location-Dependent Queries2007
- Efficient Clustering of Uncertain DataIEEE International Conference on Data Mining (ICDM), 2006
- Uncertain Data Mining: An Example in Clustering Location Data2006
- Energy-efficient communication protocol for wireless microsensor networks2005
- Density-based clustering of uncertain data2005
- Mixture Model Clustering of Uncertain Data2005
- Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data2004
- Accuracy and Resource Consumption in Tracking and Location Prediction2003