Academic
Publications
Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space

Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space,10.1016/j.is.2010.09.005,Information Systems,Wang Kay Ngai,Ben

Metric and trigonometric pruning for clustering of uncertain data in 2D geometric space  
BibTex | RIS | RefWorks Download
We study the problem of clustering data objects with location uncertainty. In our model, a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. One method to cluster such uncertain objects is to apply the UK-means algorithm [1], an extension of the traditional K-means algorithm, which assigns each object to the cluster whose representative has the smallest expected distance from it. For arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration of the pdf. We study two pruning methods: pre-computation (PC) and cluster shift (CS) that can significantly reduce the number of integrations computed. Both pruning methods rely on good bounding techniques. We propose and evaluate two such techniques that are based on metric properties (Met) and trigonometry (Tri). Our experimental results show that Tri offers a very high pruning power. In some cases, more than 99.9% of the expected distance calculations are pruned. This results in a very efficient clustering algorithm.11Part of this paper appears in Ngai et al., 2006 [2], in which the algorithms PC and CS were described. The idea of trigonometric pruning (Section 6), most of the empirical performance study (Section 7), discussion (Section 8), and all proofs of theorems (Appendixes), have not been previously published. The new materials amount to about 34 of the current paper.
Journal: Information Systems - IS , vol. 36, no. 2, pp. 476-497, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.