Local bounding technique and its applications to uncertain clustering

Abstract

Clustering analysis is a well studied topic in computer science with a variety of applications in data mining, information retrieval and electronic commerce. However, traditional clustering method can only be applied on data set with exact information. With the emergence of web-based applications in last decade, such as distributed relational database, traffic monitoring system and sensor network, there is a pressing need on handling uncertain data in these analysis tasks. However, no trivial solution over such uncertain data is available on clustering problem, by extending conventional methods.

This dissertation discusses a new clustering framework on uncertain data, Worst Case Analysis (WCA) framework, which estimates the clustering uncertainty with the maximal deviation in the worst case. Several different clustering models under WCA framework are thus presented, satisfying the requirements of different applications, and all independent to the underlying clustering criterion and clustering algorithms. Solutions to these models with respect to k-means algorithm and EM algorithm are proposed, on the basis of Local Bounding Technique, which is a powerful tool on analyzing the impact of uncertain data on the local optimums reached by these algorithms. Extensive experiments are conducted to evaluate the effectiveness and efficiency of the technique in these models with data collected in real applications.