不确定数据聚类是传统数据挖掘的扩展,具有广泛的应用背景和研究价值,受到研究者们广泛的关注。不确定数据聚类问题属于典型的NP难解问题,并表现出了典型的NP难解问题的特点。通常很难在多项式时间内获得NP难解问题的全局最优解,研究者们经常把聚类问题描述成组合优化问题,并设计启发式聚类算法对不确定数据聚类进行求解。现有的启发式不确定数据聚类算法中,UK-means和UK-Med oids算法都属于基于切割不确定数据聚类算法,它们具有容易理解和实现简单等特点,得到广泛的关注和应用,但同时它们也具有对初始解敏感的缺点,这严重影响了聚类质量。为了解决基于切割的不确定数据算法对初始解敏感的问题,本文深入研究了不确定数据聚类问题表现出的NP难解性质,分析了该问题的解空间的特征,并在近似骨架理论的基础上,提出了一种近似骨架启发式聚类算法APPGCU (APProximate backbone Guided heuristic Clustering algorithm for Uncertain data)。该算法流程如下：首先对原不确定数据集完成M次采样,在采样后的规模较小的M个不确定数据集上分别执行随机初始簇心的UK-Medoids算法得到M个局部最优解；然后通过对M个局部最优解求交集得到近似骨架,并从中提取出初始簇心；最后从初始簇心开始,使用UK-Medoids算法启发式搜索出聚类结果。该算法充分利用了近似骨架在启发式算法设计中表现出的优异性能,根据不确定数据聚类的特点设计了高效聚类算法。在充足的仿真和实际数据集中的实验结果表明,算法APPGCU的聚类结果明显高于现有的不确定数据启发式聚类算法,提高了聚类结果的质量。