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

山东大学学报(工学版) ›› 2012, Vol. 42 ›› Issue (4): 35-40.

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

张宏兵¹,陆建峰^1*,汤九斌²

1.南京理工大学计算机科学技术学院, 江苏南京 210094; 2.中国电信江苏公司, 江苏南京 210037

收稿日期:2012-05-06 出版日期:2012-08-20 发布日期:2012-05-06
通讯作者: 陆建峰(1969- ),男,江苏南京人,教授,博士生导师,主要研究方向为人工智能和图像图形技术等. E-mail:lujf@njust.edu.cn E-mail:lujf@njust.edu.cn
作者简介:张宏兵(1987- ),男,江苏东台人,硕士研究生,主要研究方向为文本挖掘. E-mail:iamzhanghongbing@126.com
基金资助:
江苏省自然基金资助项目(BK2009489);江苏省青蓝工程资助项目

An improved DBSCAN algorithm based on the approximate EMD

ZHANG Hong-bing1, LU Jian-feng1*, TANG Jiu-bin2

1. School of Computer Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China;
2. Jiangsu Corporation of China Telecom, Nanjing 210037, China

Received:2012-05-06 Online:2012-08-20 Published:2012-05-06

摘要/Abstract

摘要：

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

关键词: 聚类, DBSCAN算法, 近似EMD, 高维数据

Abstract:

The DBSCAN algorithm is one of the classic clustering algorithms based on the density. When this algorithm was applied to high-dimensional data, the distance measures in common use could not reflect the relationships between instances well, which would lead to the inaccurate clustering. If appropriate distance measures were adopted in high-dimensional space, the clustering result would be improved. To solve the above problem, the approximate EMD (earth mover′s distance) instead of the common distance was used as the distance measure, and the clustering was achieved by finding all densityreachable objects with the method of iterative search. The experimental results showed that the performance of improved algorithm was 6％ higher than that of the original algorithm for the high-dimensional text clustering, while there is no obvious difference in time cost. For low-dimensional Iris data, the proposed algorithm could improve the similarity measure between the instances, reduce the number of data points classified as noise points, and boot the performance with 10％. The experimental results also indicated that the proposed algorithm could reveal its effectiveness for high-dimensional data, and could improve the clustering performance.

Key words: clustering, DBSCAN algorithm, approximate EMD, high-dimensional data

张宏兵1,陆建峰1*,汤九斌2. 一种基于近似EMD的DBSCAN改进算法[J]. 山东大学学报(工学版), 2012, 42(4): 35-40.

ZHANG Hong-bing1, LU Jian-feng1*, TANG Jiu-bin2. An improved DBSCAN algorithm based on the approximate EMD[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(4): 35-40.

参考文献

相关文章 15

[1]	李晓辉,刘小飞,孙炜桐,赵毅,董媛,靳引利. 基于车辆与无人机协同的巡检任务分配与路径规划算法[J]. 山东大学学报 (工学版), 2025, 55(5): 101-109.
[2]	陈素根,赵志忠. 融合局部截断距离及小簇合并的密度峰值聚类[J]. 山东大学学报 (工学版), 2025, 55(2): 58-70.
[3]	王梅,宋凯文,刘勇,王志宝,万达. DMKK-means——一种深度多核K-means聚类算法[J]. 山东大学学报 (工学版), 2024, 54(6): 1-7.
[4]	王丽娟,徐晓,丁世飞. 面向密度峰值聚类的高效相似度度量[J]. 山东大学学报 (工学版), 2024, 54(3): 12-21.
[5]	张鑫,费可可. 基于log鲁棒核岭回归的子空间聚类算法[J]. 山东大学学报 (工学版), 2023, 53(6): 26-34.
[6]	李兆彬,叶军,周浩岩,卢岚,谢立. 变异萤火虫优化的粗糙K-均值聚类算法[J]. 山东大学学报 (工学版), 2023, 53(4): 74-82.
[7]	侯延琛,赵金东. 任意形状聚类的SPK-means算法[J]. 山东大学学报 (工学版), 2023, 53(2): 87-92.
[8]	程业超,刘惊雷. 自适应图正则的单步子空间聚类[J]. 山东大学学报 (工学版), 2022, 52(2): 57-66.
[9]	卢建云,张蔚,李林. 一种基于动态局部密度和聚类结构的聚类算法[J]. 山东大学学报 (工学版), 2022, 52(2): 118-127.
[10]	孟银凤,杨佳宇,曹付元. 函数型数据的分裂转移式层次聚类算法[J]. 山东大学学报 (工学版), 2022, 52(1): 19-27.
[11]	朱恒东, 马盈仓, 代雪珍. 自适应半监督邻域聚类算法[J]. 山东大学学报 (工学版), 2021, 51(4): 24-34.
[12]	朱昌明,岳闻,王盼红,沈震宇,周日贵. 主动三支聚类下的全局和局部多视角多标签学习算法[J]. 山东大学学报 (工学版), 2021, 51(2): 34-46.
[13]	解子奇,王立宏,李嫚. 块对角子空间聚类中成对约束的主动式学习[J]. 山东大学学报 (工学版), 2021, 51(2): 65-73.
[14]	李蓓,赵松,谢志佳,牛萌. 电动汽车虚拟储能可用容量建模[J]. 山东大学学报 (工学版), 2020, 50(6): 101-111.
[15]	董新宇,陈瀚阅,李家国,孟庆岩,邢世和,张黎明. 基于多方法融合的非监督彩色图像分割[J]. 山东大学学报 (工学版), 2019, 49(2): 96-101.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed