Efficient clustering of 2D uncertain data using vectors

Speaker: Jackie NGAI Wang Kay

Abstract

We study the problem of clustering data objects whose values are uncertain. 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 uncertain objects of this sort is to apply the UK-means algorithm, which is based on the traditional K-means algorithm. Methods have been used in UK-means to prune out expensive computations that are unnecessary in order to increase UK-means' efficiency. But there is a weakness inherent in those methods in pruning. We study other pruning methods that use vectors to not only address the weakness but also gain other advantages in pruning. Our experimental study shows that such pruning methods are extremely effective. In most cases, they perform twice or more effective in pruning than the current methods do. This leads to much more efficient UK-means algorithms.