Approximate Backbone Guided Heuristic Clustering Algorithm For Uncertain Data

In recent year, clustering uncertain data gets a widespread concern. It is of great importance in research and practical implementation. Uncertain data cluste-ring is a classic NP-hard problem. Researchers usually treat the uncertain data clus-tering problem as a combinatorial optimization problem, and propose some heu-ristic clustering algorithms to solve it. In this problem, as a heuristic algorithm, UK-Medoids and UK-Means algorithm were proposed for its high efficiency. They are both devide based uncertain data clustering. However, UK-Medoids and UK-Me ans are sensitive to the initial cluster center. To solve this problem, we propose an approximate backbone based algorithm to find cluster center for devide based unce-rtain data clustering algorithms, named APPGCU(APProximate backbone Guided heuristic Clustering algorithm for Uncertain data). The main idea of our algorithm is as follows:make M times random sampling on the uncertain dataset; then, use UK-Medoids to do clust-ering on the sampled datasets. and get M local optimal results; then get intersection on the M local optimal results to get approxim-ate backbone, and then get initial clu-ster center from the approximate backbone. Based on the initial cluster center, rerun UK-Medoids on the original uncertain dat-aset, and get the better clustering result. Experiment results show that the APPG-CU can solve the sensitivity problem to initial cluster center of UK-Medoids, and can get better clustering results.