Reducing UK-Means to K-Means
Authors:
- S. D. LeeSLS. D. Lee
- Ben KaoBKBen Kao
- Reynold ChengRCReynold Cheng
Open Access
- 1 October 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23759232,p. 483-488
Abstract
This paper proposes an optimisation to the UK-means algorithm, which generalises the k-means algorithm to han- dle objects whose locations are uncertain. The location of each object is described by a probability density function (pdf). The UK-means algorithm needs to compute expected distances (EDs) between each object and the cluster repre- sentatives. The evaluation of ED from first principles is very costly operation, because the pdf 's are different and arbi- trary. But UK-means needs to evaluate a lot of EDs. This is a major performance burden of the algorithm. In this pa- per, we derive a formula for evaluating EDs efficiently. This tremendously reduces the execution time of UK-means, as demonstrated by our preliminary experiments. We also il- lustrate that this optimised formula effectively reduces the UK-means problem to the traditional clustering algorithm addressed by the k-means algorithm.Keywords
This publication has 6 references indexed in Scilit:
- Efficient Clustering of Uncertain DataIEEE International Conference on Data Mining (ICDM), 2006
- Classical Mechanics2006
- Hierarchical Density-Based Clustering of Uncertain Data2006
- Uncertain Data Mining: An Example in Clustering Location Data2006
- Density-based clustering of uncertain data2005
- Capturing the Uncertainty of Moving-Object Representations1999