障碍空间中Voronoi图优化的反向近邻数聚类算法

doi:10.3778/j.issn.1673-9418.2102013

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (9): 2041-2049.DOI: 10.3778/j.issn.1673-9418.2102013

障碍空间中Voronoi图优化的反向近邻数聚类算法

何云斌(), 刘婉旭, 万静

哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080

收稿日期:2021-02-02 修回日期:2021-06-02 出版日期:2022-09-01 发布日期:2021-06-28
通讯作者: + E-mail: hybha@163.com
作者简介:何云斌（1972—）,男,教授,硕士生导师,主要研究方向为数据库理论与应用。
刘婉旭（1995—）,女,硕士研究生,主要研究方向为数据库理论与应用。
万静（1972—）,女,教授,硕士生导师,主要研究方向为数据库理论与应用、空间数据库。
基金资助:
国家自然科学基金(61872105);黑龙江省教育厅科学技术研究项目(12531z004)

Optimized Number of Reverse Neighbor Clustering Algorithm by Voronoi Diagram in Obstacle Space

HE Yunbin(), LIU Wanxu, WAN Jing

College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

Received:2021-02-02 Revised:2021-06-02 Online:2022-09-01 Published:2021-06-28
About author:HE Yunbin, born in 1972, professor, M.S. super-visor. His research interests include database theory and application.
LIU Wanxu, born in 1995, M.S. candidate. Her research interests include database theory and application.
WAN Jing, born in 1972, professor, M.S. super-visor. Her research interests include database theory and application and spatial database.
Supported by:
National Natural Science Foundation of China(61872105);Science and Technology Research Project of Heilongjiang Provincial Education Department(12531z004)

摘要/Abstract

摘要：

针对现有的障碍空间聚类算法需要人工选取聚类中心及设定阈值等问题,提出了一种障碍空间中Voronoi图优化的反向近邻数聚类算法（OBRK-means）。该算法从聚类中心的选取、离群点的筛选和广义覆盖圆三方面进行讨论和分析。首先,该算法引入Voronoi图来计算反向近邻数,进而确定聚类中心的候选集合;其次,利用Voronoi图和样本点密度进行数据集中离群点的筛选和剪枝;最后,引入广义覆盖圆来进行初始聚类,针对初始聚类结果不精确的问题提出内边界点和外边界点,并在内边界点和外边界点中根据公式分别计算出剔除点和拓展点来提高聚类准确性。理论研究和实验表明,该算法在处理障碍空间中的数据时具有更高的效率,能够得到更好的聚类结果。

关键词: 聚类, Voronoi图, 障碍空间, 反向近邻数

Abstract:

In order to solve the problem that the existing obstacle space clustering algorithm needs to select the clustering center and set the threshold value manually, OBRK-means (obstacle based on nearest K-means) clus-tering algorithm based on Voronoi diagram is proposed. The algorithm is discussed and analyzed from three aspects: the selection of cluster center, the selection of outliers and the generalized coverage circle. Firstly, Voronoi diagram is introduced to calculate the reverse nearest neighbor number to determine the cluster center. Secondly, Voronoi diagram and density of sample points are used to screen and prune outliers in the dataset. Finally, the generalized covering circle is introduced to carry out the initial clustering, and the inner and outer boundary points are proposed to solve the problem that the initial clustering results are not accurate. The exclusion points and expansion points are calculated respectively from the inner and outer boundary points to improve the accuracy of clustering. Theoretical research and experimental results show that the algorithm has higher efficiency in processing data in obstacle space and gets better clustering results.

Key words: clustering, Voronoi diagram, obstacle space, number of reverse neighbor

中图分类号:

TP311.13

何云斌, 刘婉旭, 万静. 障碍空间中Voronoi图优化的反向近邻数聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2041-2049.

HE Yunbin, LIU Wanxu, WAN Jing. Optimized Number of Reverse Neighbor Clustering Algorithm by Voronoi Diagram in Obstacle Space[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2041-2049.

图/表 13

图1 空间中不存在障碍物时的聚类结果

Fig.1 Clustering results in absence of obstacles in space

图2 空间中存在障碍物时的聚类结果

Fig.2 Clustering results in presence of obstacles in space

图3 障碍空间距离

Fig.3 Obstacle space distance

图4 内外边界点、剔除点、拓展点的示例

Fig.4 Example of inner and outer boundary points, culling points and extension points

图5 定理1的示例

Fig.5 Example of theorem 1

图6 障碍物对计算第 k近邻的影响

Fig.6 Influence of obstacles on calculation of k nearest neighbor

图7 广义覆盖圆的示例

Fig.7 Example of generalized covering circle

表1 UCI实验室数据集

Table 1 UCI laboratory datasets

数据集	样本数目	维数	类别
Iris	150	4	3
Wine	178	13	3
Haberman	306	3	2
Heart	270	13	2

表2 算法评测有效性对比

Table 2 Comparison of effectiveness of algorithms

Dataset	Algorithm	F-measure	Silhouette
Iris	OBRK-means	0.891 1	0.798 9
Iris	DBCCOM	0.877 9	0.799 3
Wine	OBRK-means	0.889 7	0.817 5
Wine	DBCCOM	0.876 8	0.802 3
Haberman	OBRK-means	0.878 6	0.687 9
Haberman	DBCCOM	0.865 1	0.655 5
Heart	OBRK-means	0.881 0	0.779 1
Heart	DBCCOM	0.869 7	0.762 1

图8 样本数目对准确率的影响

Fig.8 Effect of sample size on accuracy

图9 障碍物数目对准确率的影响

Fig.9 Effect of obstacles on accuracy

图10 样本数目对CPU响应时间的影响

Fig.10 Effect of sample size on CPU response time

图11 障碍物数目对CPU响应时间的影响

Fig.11 Effect of the number of obstacles on CPU response time

参考文献 17

[1]	谢娟英, 丁丽娟. 完全自适应的谱聚类算法[J]. 电子学报, 2019, 47(5): 1000-1008. DOI
	XIE J Y, DING L J. The true self-adaptive spectral cluste-ring algorithms[J]. Acta Electronica Sinica, 2019, 47(5): 1000-1008.
[2]	安宁, 江思源, 唐晨, 等. 融合单纯形映射与熵加权的聚类方法[J]. 计算机工程与应用, 2020, 56(9): 148-155. DOI
	AN N, JIANG S Y, TANG C, et al. Clustering method by combining simplex mapping and entropy weighting[J]. Computer Engineering and Applications, 2020, 56(9): 148-155.
[3]	BABY V, CHANDRA N S. Distributed threshold k-means clustering for privacy preserving data mining[C]// Procee-dings of the 2016 International Conference on Advances in Computing, Communications and Informatics, Jaipur, Sep 21-24, 2016. Piscataway: IEEE, 2016: 2286-2289.
[4]	CARLSSON G E, MÉMOLI F, RIBEIRO A, et al. Admissi-ble hierarchical clustering methods and algorithms for asym-metric networks[J]. IEEE Transactions on Signal and Infor-mation Processing over Networks, 2017, 3(4): 711-727.
[5]	邢长征, 张园. 基于密度与网格的聚类算法的改进[J]. 计算机工程与应用, 2016, 52(22): 81-85.
	XING C Z, ZHANG Y. Improved clustering algorithm based on density and grid[J]. Computer Engineering and Applica-tions, 2016, 52(22): 81-85.
[6]	CELEUX G, MAUGIS-RABUSSEAU C, SEDKI M. Varia-ble selection in model-based clustering and discriminant ana-lysis with a regularization approach[J]. Advances in Data Analysis and Classification, 2019, 13(1): 259-278. DOI URL
[7]	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI URL
[8]	卢炎生, 娄强. 障碍空间里基于密度的快速聚类算法[J]. 小型微型计算机系统, 2007, 28(11): 1976-1980.
	LU Y S, LOU Q. Fast density-based clustering algorithm con-taining obstacles[J]. Journal of Chinese Computer Systems, 2007, 28(11): 1976-1980.
[9]	李宇涵, 孙冬璞. 基于Voronoi图的障碍不确定数据的聚类算法[J]. 计算机工程与科学, 2016, 38(5): 1031-1038.
	LI Y H, SUN D P. A clustering algorithm of uncertain data with obstacles based on Voronoi diagram[J]. Computer En-gineering & Science, 2016, 38(5): 1031-1038.
[10]	TUNG A K H, HOU J, HAN J W. Spatial clustering in the presence of obstacles[C]// Proceedings of the 17th Interna-tional Conference on Data Engineering, Heidelberg, Apr 2-6, 2001. Washington: IEEE Computer Society, 2001: 359-367.
[11]	陈克平, 周丽华, 王丽珍, 等. 一种带障碍的网格弥散聚类算法DCellO[C]// 第二十一届中国数据库学术会议, 厦门, 2004. 北京: 中国计算机学会, 2004: 462-469.
	CHEN K P, ZHOU L H, WANG L Z, et al. A diffusant clus-tering algorithm based on grid in the presence of obstacles-DCellO[C]// The 21st National Database Conference of China, Oct 14-17, 2004. Beijing: China Computer Federation, 2004: 217-224.
[12]	曹科研, 王国仁, 韩东红, 等. 障碍空间中不确定数据聚类算法[J]. 计算机科学与探索, 2012, 6(12): 1087-1097. DOI
	CAO K Y, WANG G R, HAN D H, et al. Clustering algori-thm of uncertain data in obstacle space[J]. Journal of Fron-tiers of Computer Science and Technology, 2012, 6(12): 1087-1097.
[13]	万静, 崔美玉, 何云斌, 等. 障碍空间中基于Voronoi图的不确定数据聚类算法[J]. 计算机研究与发展, 2019, 56(5): 977-991.
	WAN J, CUI M Y, HE Y B, et al. Uncertain data clustering algorighm based on Voronoi diagram in obstacle space[J]. Journal of Computer Research and Development, 2019, 56(5): 977-991.
[14]	DUHAN N, SHARMA A K. DBCCOM: density based clus-tering with constraints and obstacle modeling[C]// Procee-dings of the 4th International Conference on Contemporary Computing, Noida, Aug 8-10, 2011. Berlin, Heidelberg: Sprin-ger, 2011: 212-228.
[15]	陈智鹏, 杨诗琴. 带障碍物情况下两点间最短距离的求解方法[J]. 计算机工程, 2010, 36(16): 171-173.
	CHEN Z P, YANG S Q. Solution of shortest distance bet-ween two points in presence of obstacles[J]. Computer En-gineering, 2010, 36(16): 171-173.
[16]	陈朝威, 常冬霞. 基于密度差分的自动聚类算法[J]. 软件学报, 2018, 29(4): 935-944.
	CHEN Z W, CHANG D X. Automatic clustering algorithm based on density difference[J]. Journal of Software, 2018, 29(4): 935-944.
[17]	韩心然. 考虑多边形障碍区域的线状需求物流节点选址研究[D]. 北京: 北京交通大学, 2018.
	HAN X R. Research on logistics node location with curved demands considering polygonal obstacles[D]. Beijing: Bei-jing Jiaotong University, 2018.

障碍空间中Voronoi图优化的反向近邻数聚类算法

Optimized Number of Reverse Neighbor Clustering Algorithm by Voronoi Diagram in Obstacle Space

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 17

相关文章 15

编辑推荐

Metrics

[1]	陈磊, 吴润秀, 李沛武, 赵嘉. 加权K近邻和多簇合并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2163-2176.
[2]	许嘉, 莫晓琨, 于戈, 吕品, 韦婷婷. SQL-Detector：基于编码特征的SQL习题抄袭检测技术[J]. 计算机科学与探索, 2022, 16(9): 2030-2040.
[3]	赵力衡, 王建, 陈虹君. 去中心化加权簇归并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(8): 1910-1922.
[4]	叶廷宇, 叶军, 王晖, 王磊. 结合人工蜂群优化的粗糙K-means聚类算法[J]. 计算机科学与探索, 2022, 16(8): 1923-1932.
[5]	张祥平, 刘建勋, 肖巧翔, 曹步清. 融合多维信息的Web服务表征方法[J]. 计算机科学与探索, 2022, 16(7): 1561-1569.
[6]	蒋祎莹, 张丽平, 金飞虎, 郝晓红. 空间数据库中混合数据组最近邻查询[J]. 计算机科学与探索, 2022, 16(2): 348-358.
[7]	陈俊芬, 张明, 赵佳成, 谢博鋆, 李艳. 结合降噪和自注意力的深度聚类算法[J]. 计算机科学与探索, 2021, 15(9): 1717-1727.
[8]	王大刚, 丁世飞, 钟锦. 基于二阶[k]近邻的密度峰值聚类算法研究[J]. 计算机科学与探索, 2021, 15(8): 1490-1500.
[9]	沈学利, 秦鑫宇. 密度Canopy的增强聚类与深度特征的KNN算法[J]. 计算机科学与探索, 2021, 15(7): 1289-1301.
[10]	范瑞东, 侯臣平. 鲁棒自加权的多视图子空间聚类[J]. 计算机科学与探索, 2021, 15(6): 1062-1073.
[11]	柏锷湘, 罗可, 罗潇. 结合自然和共享最近邻的密度峰值聚类算法[J]. 计算机科学与探索, 2021, 15(5): 931-940.
[12]	张倪妮, 葛洪伟. 稳定的K-多均值聚类算法[J]. 计算机科学与探索, 2021, 15(5): 941-948.
[13]	马瑞强, 宋宝燕, 丁琳琳, 王俊陆. 面向时间序列事件的动态矩阵聚类方法[J]. 计算机科学与探索, 2021, 15(3): 468-477.
[14]	薛红艳, 钱雪忠, 周世兵. 超簇加权的集成聚类算法[J]. 计算机科学与探索, 2021, 15(12): 2362-2373.
[15]	张培, 祝恩, 蔡志平. 单步划分融合多视图子空间聚类算法[J]. 计算机科学与探索, 2021, 15(12): 2413-2420.