Border-peeling Inspired Globally Central Clustering Algorithm

NAVIGATE

Table of Contents

STATISTICS

Viewed350

Downloads327

Border-peeling Inspired Globally Central Clustering Algorithm

[HTML] PDF下载 (327)

[1]CHENG Mingchang,AO Lan,LIU Liu.Border-peeling Inspired Globally Central Clustering Algorithm[J].Journal of Zhengzhou University (Engineering Science),2024,45(05):86-94.[doi:10.13705/j.issn.1671-6833.2024.02.002]

Copy

Journal of Zhengzhou University (Engineering Science)[ISSN 1671-6833/CN 41-1339/T] Volume: 45 Number of periods: 2024 05 Page number: 86-94 Column: Public date: 2024-08-08

Title:: Border-peeling Inspired Globally Central Clustering Algorithm

Author(s):: CHENG Mingchang¹; AO Lan¹; 2; LIU Liu¹; 3; 4; 1. V. C. & V. R. Key Lab of Sichuan Provence, Sichuan Normal University, Chengdu 610066, China; 2. School of Mathematical Sciences, Sichuan Normal University, Chengdu 610066, China; 3. Geomathematics Key Laboratory of Sichuan Province, Chengdu University of Technology, Chengdu 610059, China; 4. College of Mathematics and Physics, Chengdu University of Technology, Chengdu610059, China

Keywords:: globally central clustering algorithm; border peeling; overlapping; reverse k-nearest neighbors; empirical distribution

CLC:: TP311. 13 TP391

DOI:: 10.13705/j.issn.1671-6833.2024.02.002

Abstract:: The globally central clustering algorithms, such as k-means and spectral clustering, often suffer from theproblem of local optima and difficulty in parameter setting with overlapping and adhesive clusters in the data distribution, which might greatly limits the effectiveness of globally central clustering algorithms in practicalapplications. To address this issue, a border-peeling inspired globally central clustering algorithm was proposed.Firstly, a one-step border peeling method was designed, which defines a locally distance-weighted density according to the reverse k-nearest neighbor relationships between sample points. The density value at the maximal point of thefirst-order difference of the density empirical distribution function was utilized as the threshold to divide the datasetinto boundary and core sets. Then, the traditional globally central clustering algorithms were embedded to clusterthe core set. Benefiting from the significant improvement in the overlapping of the core set, the embedding algorithms could converge to the true cluster centers easily. Finally, a boundary attraction algorithm was proposed,which could progressively amalgamate sample points from the boundary set, utilizing existing reverse k-nearestneighbor relationships, and commencing from the already categorized core set sample points. Compared with thecurrently iterative border peeling algorithms, the proposed algorithm had significant advantages in computational efficiency. There was no additional complex termination conditions but only direct performs boundary partitioning using a threshold. Furthermore, the global approach also exhibited stronger robustness local data densities were different. In the experimental phase, three synthetic datasets and six real-world datasets were used to evaluate the algorithm′s performance, parameter sensitivity, and time consumption, further validating the efficacy and practicalityof this algorithm.

References:: [1] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatialdatabases with noise[C]∥Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Palo Alto: AAAI, 1996: 226-231.
[2] COMANICIU D, MEER P. Mean shift: a robust approach toward feature space analysis[ J] . IEEE Transactions on Pattern Analysis and Machine Intelligence,2002, 24(5) : 603-619.
[3] RODRIGUEZ A, LAIO A. Clustering by fast search andfind of density peaks[ J] . Science, 2014, 344 ( 6191) :1492-1496.
[4] GUO W J, WANG W H, ZHAO S P, et al. Density peakclustering with connectivity estimation [ J ] . Knowledge-Based Systems, 2022, 243: 108501.
[5] CHENG M C, MA T F, LIU Y B. A projection-basedsplit-and-merge clustering algorithm[ J] . Expert Systemswith Applications, 2019, 116: 121-130.
[6] SIERANOJA S, FRÄNTI P. Adapting k-means for graphclustering [ J ] . Knowledge and Information Systems,2022, 64(1) : 115-142.
[7] HUANG J Z, NG M K, RONG H Q, et al. Automatedvariable weighting in k-means type clustering[ J] . IEEETransactions on Pattern Analysis and Machine Intelligence, 2005, 27(5) : 657-668.
[8] ZHANG Y Q, CHEUNG Y M. A new distance metric exploiting heterogeneous interattribute relationship for ordinal-and-nominal-attribute data clustering [ J ] . IEEETransactions on Cybernetics, 2022, 52(2) : 758-771.
[9] 周成龙, 陈玉明, 朱益冬. 粒 K 均值聚类算法[ J] . 计算机工程与应用, 2023, 59(13) : 317-324.
ZHOU C L, CHEN Y M, ZHU Y D. Granular K-meansclustering algorithm[ J] . Computer Engineering and Applications, 2023, 59(13) : 317-324.
[10] 邓秀勤, 郑丽苹, 张逸群, 等. 基于新的距离度量的异构属性数据子空间聚类[ J] . 郑州大学学报( 工学版) , 2023, 44(2) :53-60.
DENG X Q, ZHENG L P, ZHANG Y Q, et al. Subspaceclustering of heterogeneous-attribute data based on a newdistance metric [ J ] . Journal of Zhengzhou University(Engineering Science) , 2023, 44(2) :53-60.
[11] AVERBUCH-ELOR H, BAR N, COHEN-OR D. Borderpeeling clustering[ J] . IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42 ( 7 ) : 1791-1797.
[12] DU M J, WANG R, JI R, et al. ROBP a robust borderpeeling clustering using Cauchy kernel [ J] . InformationSciences, 2021, 571: 375-400.
[13] CAPÓ M, PÉREZ A, LOZANO J A. An efficient splitmerge re-start for the K-means algorithm [ J ] . IEEETransactions on Knowledge and Data Engineering, 2022,34(4) : 1618-1627.
[14] LLOYD S. Least squares quantization in PCM[ J] . IEEETransactions on Information Theory, 1982, 28(2) : 129-137.
[15] SHI J B, MALIK J. Normalized cuts and image segmentation[ J ] . IEEE Transactions on Pattern Analysis andMachine Intelligence, 2000, 22(8) : 888-905.
[16] VON LUXBURG U. A tutorial on spectral clustering[ J] .Statistics and Computing, 2007, 17(4) : 395-416.
[17] ZHA H Y, HE X F, DING C, et al. Spectral relaxationfor K-means clustering[ C]∥Proceedings of the 14th International Conference on Neural Information ProcessingSystems: Natural and Synthetic. Cambridge: MIT, 2001:1057-1064.
[18] ZHANG X L, WANG W, NRVÅG K, et al. K-AP:generating specified K clusters by efficient affinity propagation[ C]∥Proceedings of the 2010 IEEE InternationalConference on Data Mining. Piscataway: IEEE, 2010:1187-1192.
[19] MEILǍ M. Comparing clusterings—an information baseddistance[ J] . Journal of Multivariate Analysis, 2007, 98(5) :873-895.
[20] HUBERT L, ARABIE P. Comparing partitions[ J] . Journal of Classification, 1985, 2:193-218.
[21] VEENMAN C J, REINDERS M J T, BACKER E. Amaximum variance cluster algorithm [ J] . IEEE Transactions on Pattern Analysis and Machine Intelligence,2002, 24(9) : 1273-1280.
[22] GIONIS A, MANNILA H, TSAPARAS P. Clustering aggregation[C]∥ Proceeding of the 21st International Conference on Data Engineering ( ICDE′ 05 ) . Piscataway:IEEE,2005:341-352.
[23] KELLY M, LONGJOHN R, NOTTINGHAM K. The UCImachine learning repository[ DB / OL] . [ 2023 - 06 - 29]https:∥archive. ics. uci. edu / datasets.
[24] ALCALA-FDEZ J, FERNANDEZ A, LUENGO J, et al.KEEL data-mining software tool: data set repository, integration of algorithms and experimental analysis framework[ J] . Journal of Multiple-Valued Logic and Soft Computing, 2011, 17(2 / 3) : 255-287.

Similar References:

Memo

Last Update: 2024-09-02