Minimizing the Variance of Cluster Mixture Models for Clustering Uncertain Objects

In recent years, there has been a growing interest in clustering uncertain objects. In contrast to traditional, “sharp” data representation models, uncertain objects are modeled as probability distributions defined over uncertainty regions. In this context, a major issue is related to poor efficiency of existing algorithms, mainly due to expensive computation of the distance between uncertain objects. In this work, we propose a novel formulation to the problem of clustering uncertain objects, which allows for reaching accurate solutions by minimizing the variance of the mixture models that represent the clusters to be identified. We define a heuristic, MMVar, which exploits some analytical properties about the computation of variance for mixture models to compute local minima of the objective function at the basis of the proposed formulation. This characteristic allows MMVar to discard any distance measure between uncertain objects and, therefore, to achieve high efficiency. Experiments have shown that MMVar outperforms state-of-the-art algorithms from an efficiency viewpoint, while achieving better average performance in terms of accuracy.