胡燕
开通时间:..
最后更新时间:..
点击次数:
论文类型:期刊论文
发表时间:2015-01-30
发表刊物:南京大学学报(自然科学版)
收录刊物:PKU、ISTIC、CSCD
卷号:51
期号:1
页面范围:197-205
ISSN号:0469-5097
关键字:NP-难解;启发式算法;近似骨架;不确定数据聚类
摘要:不确定数据聚类是传统数据挖掘的扩展,面对不确定数据聚类,研究者们经常把聚类问题描述成组合优化问题,并设计启发式聚类算法进行求解。现有的启发式聚类算法,如 UK-means 和 UK-Medoids 具有容易理解和实现简单等优点,但初始解敏感问题严重影响了聚类质量。本文在近似骨架理论的基础上,提出了一种近似骨架启发式聚类算法APPGCU(Approximate backbone guided heuristic clustering algorithm for uncertain data)。该算法首先对原数据集完成P次采样,在采样后的规模较小的P 个数据集上分别执行 UK-Medoids 算法得到P 个局部最优解;然后通过对P个局部最优解求交得到近似骨架,并从中提取初始簇心;最后从初始簇心开始,启发式搜索出聚类结果。在仿真和实际数据集中的实验结果表明,算法 APPGCU 的聚类结果明显高于实验对比的启发式聚类算法,提高了聚类质量。