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

doi:10.3778/j.issn.1673-9418.2102013

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (9): 2041-2049.DOI: 10.3778/j.issn.1673-9418.2102013

• Database Technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311.13

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.

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

Figures/Tables 13

Fig.1 Clustering results in absence of obstacles in space

Fig.2 Clustering results in presence of obstacles in space

Fig.3 Obstacle space distance

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

Fig.5 Example of theorem 1

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

Fig.7 Example of generalized covering circle

Table 1 UCI laboratory datasets

数据集	样本数目	维数	类别
Iris	150	4	3
Wine	178	13	3
Haberman	306	3	2
Heart	270	13	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

Fig.8 Effect of sample size on accuracy

Fig.9 Effect of obstacles on accuracy

Fig.10 Effect of sample size on CPU response time

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

References 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.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 17

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Lei, WU Runxiu, LI Peiwu, ZHAO Jia. Weighted K-nearest Neighbors and Multi-cluster Merge Density Peaks Clustering Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2163-2176.
[2]	XU Jia, MO Xiaokun, YU Ge, LYU Pin, WEI Tingting. SQL-Detector: SQL Plagiarism Detection Technique Based on Coding Features [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2030-2040.
[3]	ZHAO Liheng, WANG Jian, CHEN Hongjun. Density-Peak Clustering Algorithm on Decentralized and Weighted Clusters Merging [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(8): 1910-1922.
[4]	ZHANG Xiangping, LIU Jianxun, XIAO Qiaoxiang, CAO Buqing. Multidimensional Information-Based Web Service Representation Method [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1561-1569.
[5]	JIANG Yiying, ZHANG Liping, JIN Feihu, HAO Xiaohong. Groups Nearest Neighbor Query of Mixed Data in Spatial Database [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 348-358.
[6]	CHEN Junfen, ZHANG Ming, ZHAO Jiacheng, XIE Bojun, LI Yan. Deep Clustering Algorithm Based on Denoising and Self-Attention [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1717-1727.
[7]	WANG Dagang, DING Shifei, ZHONG Jin. Research of Density Peaks Clustering Algorithm Based on Second-Order k Neighbors [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1490-1500.
[8]	SHEN Xueli, QIN Xinyu. KNN Algorithm of Enhanced Clustering Based on Density Canopy and Deep Feature [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1289-1301.
[9]	FAN Ruidong, HOU Chenping. Robust Auto-weighted Multi-view Subspace Clustering [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(6): 1062-1073.
[10]	BAI Exiang, LUO Ke, LUO Xiao. Peak Density Clustering Algorithm Combining Natural and Shared Nearest Neighbor [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(5): 931-940.
[11]	ZHANG Nini, GE Hongwei. Stable K Multiple-Means Clustering Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(5): 941-948.
[12]	MA Ruiqiang, SONG Baoyan, DING Linlin, WANG Junlu. Dynamic Matrix Clustering Method for Time Series Events [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(3): 468-477.
[13]	XUE Hongyan, QIAN Xuezhong, ZHOU Shibing. Ensemble Clustering Algorithm Based on Weighted Super Cluster [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2362-2373.
[14]	ZHANG Pei, ZHU En, CAI Zhiping. One-Stage Partition-Fusion Multi-view Subspace Clustering Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2413-2420.
[15]	YAO Xiaohong, HUANG Hengjun. Semi-supervised Clustering Method for Non-negative Functional Data [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2438-2448.