Voronoi-diagram-based Clustering for Uncertain Data

Speaker: Paul CHAN Kai Fong

Abstract

We study the problem of clustering of uncertain data by Voronoi-diagram-based approach. In our model, each uncertain object may have an irregular uncertainty region in two-dimensional space. The probability density function (pdf) is defined over the uncertainty region. To cluster uncertain objects, the partition-based clustering methods assign the object to its nearest cluster representative using expected distance. Expected distance computation is expensive as it require integration operation. One approach to cluster uncertain objects is MinMax-based approach. The MinMax-based use the lower and upper distance bound the prune clusters. We propose the Voronoi-diagram-based approach to cluster uncertain objects. Uncertain objects are indexed by R-tree. Voronoi diagram is constructed to determine the nearest cluster representative. The Voronoi diagram and the bisectors of cluster representatives are used to prune clusters and avoid the number of expected distance computations. We made a preliminary study to determine the difference between two approaches. Experimental results show that the Voronoi-diagram-based approach is efficient for clustering uncertain data.