Clustering Uncertain Data Using Voronoi Diagrams

Ben Kao, Sau Dan Lee, David W. Cheung, Wai-Shing Ho, K. F. Chan

Abstract

We study the problem of clustering uncertain objects whose locations are described by probability density functions (pdf). We show that the UK-means algorithm, which generalises the k-means algorithm to handle uncertain objects, is very inefficient. The inefficiency comes from the fact that UK-means computes expected distances (ED) between objects and cluster representatives. For arbitrary pdf's, 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 calculation. These techniques are analytically proven to be more effective than the basic bounding-box-based technique previous known in the literature. We conduct experiments to evaluate the effectiveness of our pruning techniques and to show that our techniques significantly outperform previous methods.
BibTeX
@inproceedings{kao2008clustering,
  author = {Ben Kao and Sau Dan Lee and David W. Cheung and Wai-Shing Ho and K. F. Chan},
  title = {{Clustering Uncertain Data Using Voronoi Diagrams}},
  booktitle = {ICDM},
  year = {2008},
  doi = {10.1109/icdm.2008.31},
}

Loading related content...

Figure