基于密度敏感距离和模糊划分的改进FCM算法

doi:10.11896/jsjkx.210700042

摘要/Abstract

摘要： 传统的模糊C均值(Fuzzy C-means,FCM)算法对噪声数据敏感,并且在迭代过程中因仅考虑了距离因素,故使用欧氏距离进行距离度量,这会导致只考虑样本点之间的局部一致性特征,而忽略全局一致性特征的问题,为此,提出了一种基于密度敏感距离和模糊划分的改进FCM算法。首先在建立相似度矩阵时使用密度敏感距离替代欧氏距离来进行计算,然后在聚类过程中引入模糊熵作为约束条件,推导出新的聚类中心和具有高斯分布特性的隶属度计算公式。此外,针对传统FCM算法随机选取初始聚类中心可能导致聚类结果不稳定的问题,根据聚类中心点周围样本点比较密集以及聚类中心点之间距离较远两个原则,结合密度敏感距离来选取初始聚类中心点。最后通过实验对比表明,与传统FCM聚类算法及其派生算法相比,改进算法不仅具有更高的聚类性能和抗噪性,且收敛速度也显著提高。

关键词: 初始聚类中心, 隶属度, 密度敏感距离, 模糊C均值聚类, 模糊熵

Abstract: The traditional fuzzy C-means(FCM) algorithm is sensitive to noise data and only considers the distance factor in the iterative process.Therefore,the use of Euclidean distance for distance measurement will result in only considering the local consistency feature between sample points,while ignoring the global consistency feature.To solve these problems,an improved FCM algorithm based on density sensitive distance and fuzzy partition is proposed.First,the density sensitive distance is used to replace the Euclidean distance in the calculation of the similarity matrix,and then fuzzy entropy is introduced as a constraint condition in the clustering process to derive the new clustering center and the membership calculation formula with Gaussian distribution characteristics.In addition,in view of the problem that the traditional FCM algorithm randomly selects the initial clustering center may cause the clustering result to be unstable,according to the two principles of denser sample points around the cluster center point and longer distance between the cluster center points,combined with the density sensitive distance to select the initial cluster center point.Finally,the experimental comparison proves that the improved algorithm not only has higher clustering perfor-mance and anti-noise,but also significantly improves the convergence speed compared with the traditional FCM clustering algorithm and its derivative algorithm.

Key words: Density sensitive distance, Fuzzy C-means clustering, Fuzzy entropy, Initial cluster center, Membership

中图分类号:

TP391.9

毛森林, 夏镇, 耿新宇, 陈剑辉, 蒋宏霞. 基于密度敏感距离和模糊划分的改进FCM算法[J]. 计算机科学, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042

MAO Sen-lin, XIA Zhen, GENG Xin-yu, CHEN Jian-hui, JIANG Hong-xia. FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition[J]. Computer Science, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042

参考文献

[1] YANG L,CAO X D,CHEN Y H,et al.Research on Integrated Application of Enterprise Distributed Database Based on MAS on CIAgent Platform[J].Journal of Intelligent Systems,2007(3):73-78.
[2] LAOHAKIAT S,SA-ING V.An incremental density-basedclustering framework using fuzzy local clustering[J].Information Sciences,2021,547:404-426.
[3] GOSAIN A,DAHIYA S.Performance analysis of various fuzzy clustering algorithms:a review[J].Procedia Computer Science,2016,79:100-111.
[4] ASKARI S.Fuzzy C-Means clustering algorithm for data with unequal cluster sizes and contaminated with noise and outliers:Review and development[J/OL].Expert Systems with Applications,2021,165.https://www.sciencedirect.com/science/article/pii/S0957417420306679?via%3Dihub.
[5] LIAO S Y,ZHANG J F,LIU A Q.Fuzzy C-means Clustering Algorithm Based on Fuzzy Entropy Constraint[J].Small Microcomputer System,2014,35(2):379-383.
[6] LIU X Y,ZHANG X F,MA Y,et al.DTI Image Segmentation Algorithm Based on Improved Spatial Fuzzy Clustering[J].Chinese Journal of Biomedical Engineering,2018,37(4):394-403.
[7] MEMON K H,MEMON S,QURESHI M A,et al.Kernel possibilistic fuzzy c-means clustering with local information for image segmentation[J].International Journal of Fuzzy Systems,2019,21(1):321-332.
[8] CHEN H P,SHEN X J,LONG J W,et al.Fuzzy clustering algorithm for automatically determining the number of clusters[J].Electronic Journal,2017,45(3):687-694.
[9] LEI X X,OUYANG H L,XU L J.Kernel-Distance-Based Intuitionistic Fuzzy c-Means Clustering Algorithm and Its Application[J].Pattern Recognition and Image Analysis,2019,29(S6):592-597.
[10] TOLENTINO J A,GERARDO B D,MEDINA R P.Enhanced manhattan-based clustering using fuzzy C-means algorithm[C]//International Conference on Computing and Information Technology.Cham:Springer,2018:126-134.
[11] GUEORGUIEVA N,VALOVA I,GEORGIEV G.M&MFCM:fuzzy c-means clustering with mahalanobis and minkowski distance metrics[J].Procedia Computer Science,2017,114:224-233.
[12] CHAIRA,TAMALIKA.A novel intuitionistic fuzzy C meansclustering algorithm and its application to medical images[J].Applied Soft Computing,2011,11(2):1711-1717.
[13] ZHU L,WANG S T,DENG Z H.Research on generalized fuzzy C-means clustering algorithm with improved fuzzy partitions[J].Journal of Computer Research and Development,2009,46(5):814.
[14] SHI W F,SHANG L.Determining Clustering Number of FCM Algorithm Based on DTRS[J].Computer Science,2017,44(9):45-48,66.
[15] TAO X,WANG R,CHANG R,et al.Spectral clustering algorithm using density-sensitive distance measure with global and local consistencies[J].Knowledge-Based Systems,2019,170:26-42.
[16] QING M,SUN X M.A New Clustering Validity Function:FuzzyEntropy of Fuzzy Partition[J].Journal of Intelligent Systems,2015,10(1):75-80.
[17] ZHANG S J,ZHAO H C.Study on the optimal number of clus-tering and the algorithm of selecting the initial clustering center point[J].Computer Application Research,2017,34(6):1617-1620.
[18] WANG Z H,WANG S Y,DU H.An improved fuzzy C-means clustering algorithm based on density sensitive distance[J].Computer Engineering,2021,47(5):88-96,103.
[19] FAN J L,WU C M.Clustering validity function based on fuzzy entropy[J].Pattern Recognition and Artificial Intelligence,2001,14(4):390-394.
[20] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J/OL].Science,2014,344(6191).https://www.hindawi.com/journals/mpe/2017/5060842/.
[21] ZHANG Q,CHEN H M,FENG Y F.Overlapping Community Detection Method Based on Rough Sets and Density Peaks[J].Computer Science,2020,47(5):72-78.
[22] SHANG F H,JIAO L C,HI J R,et al.Fast affinity propagation clustering:A multilevel approach[J].Pattern Recognition,2011,45(1):474-486.
[23] RAMIREZ E H,BRENA R,MAGATTI D,et al.Topic model validation[J].Neurocomputing,2011,76(1):125-133.

相关文章 15

[1]	乔颖婧, 高保禄, 史瑞雪, 刘璇, 王朝辉. 融合Tamura纹理特征的改进FCM脑MRI图像分割算法 Improved FCM Brain MRI Image Segmentation Algorithm Based on Tamura Texture Feature 计算机科学, 2021, 48(8): 111-117. https://doi.org/10.11896/jsjkx.200700003
[2]	张毛银, 郑婷婷, 郑婉容. 基于指数加权的区间直觉模糊熵及其应用 Interval-valued Intuitionistic Fuzzy Entropy Based on Exponential Weighting and Its Application 计算机科学, 2019, 46(10): 229-235. https://doi.org/10.11896/jsjkx.180901738
[3]	夏扬波, 杨文忠, 张振宇, 王庆鹏, 石研. 一种移动无线传感器网络的节点位置预测方法 Node Position Prediction Method for Mobile Wireless Sensor Networks 计算机科学, 2018, 45(8): 113-118. https://doi.org/10.11896/j.issn.1002-137X.2018.08.020
[4]	贾伟,华庆一,张敏军,陈锐,姬翔,王博. 基于改进粒子群优化的移动界面模式聚类算法 Mobile Interface Pattern Clustering Algorithm Based on Improved Particle Swarm Optimization 计算机科学, 2018, 45(4): 220-226. https://doi.org/10.11896/j.issn.1002-137X.2018.04.037
[5]	范建平,薛坤,吴美琴. 基于直觉模糊熵的交叉评价方法 Cross Evaluation Method Based on Intuitionistic Fuzzy Entropy 计算机科学, 2018, 45(2): 280-286. https://doi.org/10.11896/j.issn.1002-137X.2018.02.048
[6]	王宏杰,师彦文. 结合初始中心优化和特征加权的K-Means聚类算法 K-Means Clustering Algorithm Based on Initial Center Optimization and Feature Weighted 计算机科学, 2017, 44(Z11): 457-459. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.097
[7]	李凯,顾丽凤,胡少方. 引入调整项的模糊孪生支持向量机 Regularized Fuzzy Twin Support Vector Machine 计算机科学, 2017, 44(8): 260-264. https://doi.org/10.11896/j.issn.1002-137X.2017.08.044
[8]	邢文凯,高雪霞,侯小毛,翟萍. 云计算环境下的模糊解耦能效优化算法研究 Research on Fuzzy Decoupling Energy Efficiency Optimization Algorithm in Cloud Computing Environment 计算机科学, 2017, 44(12): 75-79. https://doi.org/10.11896/j.issn.1002-137X.2017.12.015
[9]	池云仙,赵书良,罗燕,赵骏鹏,高琳,李超. 基于特征隶属度的文本分类相似性度量方法 Similarity Measure for Text Classification Based on Feature Subjection Degree 计算机科学, 2017, 44(11): 289-296. https://doi.org/10.11896/j.issn.1002-137X.2017.11.044
[10]	汪琼枝,郑文曦,王道然. 应用近似模糊熵的不完备信息系统属性约简 Attribute Reduction Algorithm for Incomplete Information Systems Based on Approximate Fuzzy Entropy 计算机科学, 2016, 43(Z6): 81-82. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.018
[11]	苏丁为,周创明,王毅. 基于直觉模糊熵的粒子群多目标优化 Particle Swarm Algorithm for Multi-objective Optimization Based on Intuitionistic Fuzzy Entropy 计算机科学, 2016, 43(8): 262-266. https://doi.org/10.11896/j.issn.1002-137X.2016.08.053
[12]	王黎明,姜琴,张卓. 基于属性消减的模糊概念格渐进式构造算法 Incremental Algorithm for Constructing Fuzzy Concept Lattices Based on Attributes Decrement 计算机科学, 2016, 43(8): 216-222. https://doi.org/10.11896/j.issn.1002-137X.2016.08.044
[13]	薛占熬,朱泰隆,薛天宇,刘杰,王楠. 基于直觉模糊集的三支决策模型 Model of Three-way Decision Theory Based on Intuitionistic Fuzzy Sets 计算机科学, 2016, 43(6): 283-288. https://doi.org/10.11896/j.issn.1002-137X.2016.06.056
[14]	苏丁为,王毅,周创明. 基于直觉模糊熵的改进粒子群算法求解WTA问题 Improved Particle Swarm Optimization Algorithm for Solving Weapon-target Assignment Problem Based on Intuitionistic Fuzzy Entropy 计算机科学, 2016, 43(12): 255-259. https://doi.org/10.11896/j.issn.1002-137X.2016.12.046
[15]	杨霁琳,秦克云. 模糊信息系统中基于OWA算子的模糊粗糙集模型 Fuzzy Rough Set Model Based on OWA Operator in Fuzzy Information System 计算机科学, 2016, 43(12): 84-87. https://doi.org/10.11896/j.issn.1002-137X.2016.12.014

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed