Clustering of Uncertain data by Voronoi-diagram-based approach

Speaker: Paul CHAN Kai Fong

Abstract

We study the clustering of uncertain objects in a Voronoi-diagram-based (VD) approach. Clustering of uncertain objects by MinMax-based (MM) approach are well studied recently. Several extensions to MM approach are proposed, such as Cluster Shift (CS) methods, and anchor point Pre-computation (PC) methods. These methods greatly improve the efficiency of basic MinMax algorithm. In addition, MM approach rely heavily on estimation of tigher distance bounds. If the distance bounds cannot be significantly improved, the methods simply degraded to basic MinMax algorithm. When the degree of uncertainty of objects are very small, MM approach may not perform well. Fortunately, VD approach do not have such limitation. Besides, we proved that VD with bisector pruning is strictly better than basic MinMax method. Several VD methods are proposed. Experimental results show that Voronoi-diagram-based methods outperform MinMax-based methods when degree of objects' uncertainty are small. The hybird of VD methods and CS methods always perform better than that of MM approach.