Abstract:  As an extension of traditional data mining, uncertain data clustering gets wide interest of researchers. Uncertain data clustering is equivalent to a combinatorial optimization problem, and researchers usually solve it by using heuristic algorithms. As we known, the existence heuristic clustering algorithms for uncertain data, such as UK-Means and UK-Medoids, are easy to understand and to implement, but these algorithm also have the initialization sensitivity problem which affecting the clustering quality severely. In this paper, we propose an approximate backbone based heuristic clustering algorithm APPGCU (APProximate backbone guided heuristic clustering algorithm for uncertain data). In this algorithm, we first do P times sampling on the original dataset, and run UK-Medoids on the P sampled datasets to get P sub-optimal solutions; then get the approximate backbone from the P sub-optimal solutions, and extract the initialization cluster center; eventually, re-run UK-Medoids with the initialization, get the solution by a heuristic search. The experiments on synthetic and standard UCI uncertain datasets demonstrate that APPGCU gets better clustering results than existing heuristic clustering algorithms, and improves the quality of clustering results.