一种基于近似EMD的DBSCAN改进算法

• 作者: 张宏兵 汤九斌 陆建峰
• 来源期刊: 山东大学学报：工学版
• 学科: 工学
• 关键词: 聚类 DBSCAN算法 近似EMD 高维数据
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 机器学习与数据挖掘
• 页码范围: 35-40
• 分类号: TP311
• 语种: 中文

摘要

DBSCAN（density—based spatial clustering of applications with noise）算法是基于密度的经典聚类算法，但是该算法应用于高维数据时，常用距离函数不能很好地反映出数据点之间的关系，从而可能导致聚类簇不够精确。如果能在高维空间中采用合适的距离度量，将会改善聚类结果。针对上述问题，提出利用近似EMD（earth mover’s distance，堆土机距离）作为距离测度，通过迭代搜索的方法找出所有直接密度可达对象实现聚类。实验结果表明：在高维文本数据的聚类中，和原来算法相比，改进算法的正确率提高了6％，两者在时间上相差不大；而对低维的Iris数据，改进算法通过EMD改善了实体间的相似性度量，减少了划分为噪声点的数据点个数，平均正确率提高了10％。实验结果表明了改进算法对高维数据的有效性，并可以改善聚类性能。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陆建峰	南京理工大学计算机科学技术学院	77	1217	17.0	33.0
2	汤九斌		3	12	2.0	3.0
3	张宏兵	南京理工大学计算机科学技术学院	1	6	1.0	1.0