基于区间阴影集的密度峰值聚类算法
|
摘要
为了减小模糊集及其诱导的经典阴影集之间存在的较大的不确定性差异,文中基于模糊熵提出阴影集模型——区间阴影集.由此提出基于区间阴影集的密度峰值聚类算法,优化经典密度峰值聚类算法的噪声检测策略.改进算法在原二支聚类结果的基础上摒弃原有检测策略,引入区间阴影集模型,并转化为三支聚类结果,达到噪声检测的目的.在经典人工数据集、UCI数据集上的对比实验表明,文中算法能将数据集中对象更合理地分配到相应类簇,对噪声数据具有良好的鲁棒性.
To narrow the discrepancy between a fuzzy set and its induced shadowed set, a shadowed set model, interval shadowed set, is proposed based on fuzzy entropy. Grounded on the interval shadowed set model, an improved density peak clustering algorithm is proposed to optimize the noise detection strategy of the classical algorithm. To detect the noise, the two-way clustering result of classical algorithm is transformed into three-way clustering result by introducing interval shadowed set model. Finally, comparison experiments on classical artificial datasets and UCI datasets show that the improved algorithm distributes the objects of any dimension and scale more reasonably to the corresponding clusters, and it has good robustness to noise data.
To narrow the discrepancy between a fuzzy set and its induced shadowed set, a shadowed set model, interval shadowed set, is proposed based on fuzzy entropy. Grounded on the interval shadowed set model, an improved density peak clustering algorithm is proposed to optimize the noise detection strategy of the classical algorithm. To detect the noise, the two-way clustering result of classical algorithm is transformed into three-way clustering result by introducing interval shadowed set model. Finally, comparison experiments on classical artificial datasets and UCI datasets show that the improved algorithm distributes the objects of any dimension and scale more reasonably to the corresponding clusters, and it has good robustness to noise data.
引文
[1] ZADEH L A.Fuzzy Sets.Information and Control,1965,8(3):338-353.
[2] PEDRYCZ W.Shadowed Sets:Representing and Processing Fuzzy Sets.IEEE Transactions on Systems,Man,and Cybernetics(Cybernetics),1998,28(1):103-109.
[3] PEDRYCZ W.Shadowed Sets:Bridging Fuzzy and Rough Sets // INUIGUCHI M,WU W Z,CORNELISC,et al.,eds.Rough Fuzzy Hybridization.Singapore,Singapore:Springer,1999:179-199.
[4] PEDRYCZ W.Granular Computing with Shadowed Sets // Proc of the International Workshop on Rough Sets,Fuzzy Sets,Data Mi-ning,and Granular-Soft Computing.Berlin,Germany:Springer,2005:23-32.
[5] PEDRYCZ W.Interpretation of Clusters in the Framework of Sha-dowed Sets.Pattern Recognition Letters,2005,26(15):2439-2449.
[6] PEDRYCZ W.From Fuzzy Sets to Shadowed Sets:Interpretation and Computing.International Journal of Intelligent Systems,2009,24(1):48-61.
[7] DENG X F.Three-Way Classification Models.Ph.D.Dissertation.Regina,Canada:University of Regina,2015.
[8] DENG X F,YAO Y Y.Decision-Theoretic Three-Way Approximations of Fuzzy Sets.Information Sciences,2014,279:702-715.
[9] TAHAYORI H,SADEGHIAN A,PEDRYCZ W.Induction of Sha-dowed Sets Based on the Gradual Grade of Fuzziness.IEEE Transactions on Fuzzy Systems,2013,21(5):937-949.
[10] GRZEGORZEWSKI P.Fuzzy Number Approximation via Shadowed Sets.Information Sciences,2013,225:35-46.
[11] MITRA S,PEDRYCZ W,BARMAN B.Shadowed c-means:Integrating Fuzzy and Rough Clustering.Pattern Recognition,2010,43(4):1282-1291.
[12] 郭晋华,苗夺谦,周杰.基于阴影集的粗糙聚类阈值选择.计算机科学,2011,38(10):209-210,227.(GUO J H,MIAO D Q,ZHOU J.Shadowed Sets Based Threshold Selection in Rough Clustering.Computer Science,2011,38(10):209-210,227.)
[13] YU H.A Framework of Three-Way Cluster Analysis // Proc of the International Joint Conference on Rough Sets.Berlin,Germany:Springer,2017:300-312.
[14] YU H,ZHANG C,WANG G Y.A Tree-Based Incremental Overlapping Clustering Method Using the Three-Way Decision Theory.Knowledge-Based Systems,2016,91:189-203.
[15] WANG P X,YAO Y Y.CE3:A Three-Way Clustering Method Based on Mathematical Morphology.Knowledge-Based Systems,2018,155:54-65.
[16] RODRIGUEZ A,LAIO A.Machine Learning:Clustering by Fast Search and Find of Density Peaks.Science,2014,344(6191):1492-1496.
[17] WANG S L,WANG O K,LI C Y,et al.Clustering by Fast Search and Find of Density Peaks with Data Field.Chinese Journal of Electronics,2016,25(3):397-402.
[18] XU J,WANG G Y,DENG W H.DenPEHC:Density Peak Based Efficient Hierarchical Clustering.Information Sciences,2016,373(12):200-218.
[19] 谢娟英,高红超,谢维信.K近邻优化的密度峰值快速搜索聚类算法.中国科学(信息科学),2016,46(2):258-280.(XIE J Y,GAO H C,XIE W X.Clustering by Fast Search and Find of Density Peaks Based the Optimization of K-nearest Neighbors.Scientia Sinica(Informations),2016,46(2):258-280.)
[20] XIE J Y,GAO H C,XIE W X,et al.Robust Clustering by Detecting Density Peaks and Assigning Points Based on Fuzzy Weighted K-nearest Neighbors.Information Sciences,2016,354:19-40.
[21] DU M J,DING S F,JIA H J.Study on Density Peaks Clustering Based on k-Nearest Neighbors and Principal Component Analysis.Knowledge-Based Systems,2016,99:135-145.
[22] ZHANG W K,LI J.Extended Fast Search Clustering Algorithm:Widely Density Clusters,No Density Peaks.Computer Science,2015,5(7):1-18.
[23] 张文开.基于密度的层次聚类算法研究.硕士学位论文.合肥:中国科学技术大学,2015.(ZHANG W K.Research on Density-Based Hierarchical Clustering Algorithm.Master Dissertation.Hefei,China:University of Science and Technology of China,2015.)
[24] MEHMOOD R,BIE R F,DAWOOD H,et al.Fuzzy Clustering by Fast Search and Find of Density Peaks // Proc of the International Conference on Identification,Information,and Knowledge in the Internet of Things.Washington,USA:IEEE,2016:258-261.
[25] ZHANG Y F,CHEN S M,YU G.Efficient Distributed Density Peaks for Clustering Large Data Sets in MapReduce.IEEE Transactions on Knowledge and Data Engineering,2016,28(12):3218-3230.
[26] LIU X C.Entropy,Distance Measure and Similarity Measure of Fuzzy Sets and Their Relations.Fuzzy Sets and Systems,1992,52(3):305-318.
[27] LIANG J Y,CHIN K,DANG C Y,et al.A New Method for Measuring Uncertainty and Fuzziness in Rough Set Theory.International Journal of General Systems,2002,31(4):331-342.
[28] LUCA A D,TERMINI S.A Definition of a Nonprobabilistic Entropy in the Setting of Fuzzy Sets Theory.Information and Control,1972,20(4):301-312.
[29] PAL N R,PAL S K.Entropy:A New Definition and Its Applications.IEEE Transactions on Systems,Man,and Cybernetics,2002,21(5):1260-1270.
[30] YAO Y Y,WANG S,DENG X F.Constructing Shadowed Sets and Three-Way Approximations of Fuzzy Sets.Information Sciences,2017,412/413:132-153.
[31] 张翔,肖小玲,徐光祐.基于样本之间紧密度的模糊支持向量机方法.软件学报,2006,17(5):951-958.(ZHANG X,XIAO X L,XU G Y.Fuzzy Support Vector Machine Based on Affinity among Samples.Journal of Software,2006,17(5):951-958.)
[32] 周德龙,赵志国,潘泉,等.基于模糊集的图像增强算法研究.电子与信息学报,2002,24(7):905-909.(ZHOU D L,ZHAO Z G,PAN Q,et al.An Image Enhancement Algorithm Based on Fuzzy Sets.Journal of Electronics and Information Technology,2002,24(7):905-909.)
[33] 申铉京,刘翔,陈海鹏.基于多阈值Otsu准则的阈值分割快速计算.电子与信息学报,2017,39(1):144-149.(SHEN X J,LIU X,CHEN H P.Fast Computation of Threshold Based on Multi-threshold Otsu Criterion.Journal of Electronics and Information Technology,2017,39(1):144-149.)
[34] FR?NTI P,VIRMAJOKI O.Iterative Shrinking Method for Clus-tering Problems.Pattern Recognition,2006,39(5):761-775.
[35] GIONIS A,MANAILA H,TSAPARAS P.Clustering Aggregation.ACM Transactions on Knowledge Discovery from Data,2007,1(1).DOI:10.1145/1217299.1217303.
[36] VEENMAN C J,REINDERS M J T,BACKER E.A Maximum Variance Cluster Algorithm.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(9):1273-1280.
[37] BEZDEK J C,PAL N R.Some New Indexes of Cluster Validity.IEEE Transactions on Systems,Man,and Cybernetics(Cyberne-tics),1998,28(3):301-315.
[38] 刘解放,王士同,王骏,等.一种具有最优保证特性的贝叶斯可能性聚类方法.电子与信息学报,2017,39(7):1554-1562.(LIU J F,WANG S T,WANG J,et al.Bayesian Possibilistic Clustering Method with Optimality Guarantees.Journal of Electro-nics and Information Technology,2017,39(7):1554-1562.)
[2] PEDRYCZ W.Shadowed Sets:Representing and Processing Fuzzy Sets.IEEE Transactions on Systems,Man,and Cybernetics(Cybernetics),1998,28(1):103-109.
[3] PEDRYCZ W.Shadowed Sets:Bridging Fuzzy and Rough Sets // INUIGUCHI M,WU W Z,CORNELISC,et al.,eds.Rough Fuzzy Hybridization.Singapore,Singapore:Springer,1999:179-199.
[4] PEDRYCZ W.Granular Computing with Shadowed Sets // Proc of the International Workshop on Rough Sets,Fuzzy Sets,Data Mi-ning,and Granular-Soft Computing.Berlin,Germany:Springer,2005:23-32.
[5] PEDRYCZ W.Interpretation of Clusters in the Framework of Sha-dowed Sets.Pattern Recognition Letters,2005,26(15):2439-2449.
[6] PEDRYCZ W.From Fuzzy Sets to Shadowed Sets:Interpretation and Computing.International Journal of Intelligent Systems,2009,24(1):48-61.
[7] DENG X F.Three-Way Classification Models.Ph.D.Dissertation.Regina,Canada:University of Regina,2015.
[8] DENG X F,YAO Y Y.Decision-Theoretic Three-Way Approximations of Fuzzy Sets.Information Sciences,2014,279:702-715.
[9] TAHAYORI H,SADEGHIAN A,PEDRYCZ W.Induction of Sha-dowed Sets Based on the Gradual Grade of Fuzziness.IEEE Transactions on Fuzzy Systems,2013,21(5):937-949.
[10] GRZEGORZEWSKI P.Fuzzy Number Approximation via Shadowed Sets.Information Sciences,2013,225:35-46.
[11] MITRA S,PEDRYCZ W,BARMAN B.Shadowed c-means:Integrating Fuzzy and Rough Clustering.Pattern Recognition,2010,43(4):1282-1291.
[12] 郭晋华,苗夺谦,周杰.基于阴影集的粗糙聚类阈值选择.计算机科学,2011,38(10):209-210,227.(GUO J H,MIAO D Q,ZHOU J.Shadowed Sets Based Threshold Selection in Rough Clustering.Computer Science,2011,38(10):209-210,227.)
[13] YU H.A Framework of Three-Way Cluster Analysis // Proc of the International Joint Conference on Rough Sets.Berlin,Germany:Springer,2017:300-312.
[14] YU H,ZHANG C,WANG G Y.A Tree-Based Incremental Overlapping Clustering Method Using the Three-Way Decision Theory.Knowledge-Based Systems,2016,91:189-203.
[15] WANG P X,YAO Y Y.CE3:A Three-Way Clustering Method Based on Mathematical Morphology.Knowledge-Based Systems,2018,155:54-65.
[16] RODRIGUEZ A,LAIO A.Machine Learning:Clustering by Fast Search and Find of Density Peaks.Science,2014,344(6191):1492-1496.
[17] WANG S L,WANG O K,LI C Y,et al.Clustering by Fast Search and Find of Density Peaks with Data Field.Chinese Journal of Electronics,2016,25(3):397-402.
[18] XU J,WANG G Y,DENG W H.DenPEHC:Density Peak Based Efficient Hierarchical Clustering.Information Sciences,2016,373(12):200-218.
[19] 谢娟英,高红超,谢维信.K近邻优化的密度峰值快速搜索聚类算法.中国科学(信息科学),2016,46(2):258-280.(XIE J Y,GAO H C,XIE W X.Clustering by Fast Search and Find of Density Peaks Based the Optimization of K-nearest Neighbors.Scientia Sinica(Informations),2016,46(2):258-280.)
[20] XIE J Y,GAO H C,XIE W X,et al.Robust Clustering by Detecting Density Peaks and Assigning Points Based on Fuzzy Weighted K-nearest Neighbors.Information Sciences,2016,354:19-40.
[21] DU M J,DING S F,JIA H J.Study on Density Peaks Clustering Based on k-Nearest Neighbors and Principal Component Analysis.Knowledge-Based Systems,2016,99:135-145.
[22] ZHANG W K,LI J.Extended Fast Search Clustering Algorithm:Widely Density Clusters,No Density Peaks.Computer Science,2015,5(7):1-18.
[23] 张文开.基于密度的层次聚类算法研究.硕士学位论文.合肥:中国科学技术大学,2015.(ZHANG W K.Research on Density-Based Hierarchical Clustering Algorithm.Master Dissertation.Hefei,China:University of Science and Technology of China,2015.)
[24] MEHMOOD R,BIE R F,DAWOOD H,et al.Fuzzy Clustering by Fast Search and Find of Density Peaks // Proc of the International Conference on Identification,Information,and Knowledge in the Internet of Things.Washington,USA:IEEE,2016:258-261.
[25] ZHANG Y F,CHEN S M,YU G.Efficient Distributed Density Peaks for Clustering Large Data Sets in MapReduce.IEEE Transactions on Knowledge and Data Engineering,2016,28(12):3218-3230.
[26] LIU X C.Entropy,Distance Measure and Similarity Measure of Fuzzy Sets and Their Relations.Fuzzy Sets and Systems,1992,52(3):305-318.
[27] LIANG J Y,CHIN K,DANG C Y,et al.A New Method for Measuring Uncertainty and Fuzziness in Rough Set Theory.International Journal of General Systems,2002,31(4):331-342.
[28] LUCA A D,TERMINI S.A Definition of a Nonprobabilistic Entropy in the Setting of Fuzzy Sets Theory.Information and Control,1972,20(4):301-312.
[29] PAL N R,PAL S K.Entropy:A New Definition and Its Applications.IEEE Transactions on Systems,Man,and Cybernetics,2002,21(5):1260-1270.
[30] YAO Y Y,WANG S,DENG X F.Constructing Shadowed Sets and Three-Way Approximations of Fuzzy Sets.Information Sciences,2017,412/413:132-153.
[31] 张翔,肖小玲,徐光祐.基于样本之间紧密度的模糊支持向量机方法.软件学报,2006,17(5):951-958.(ZHANG X,XIAO X L,XU G Y.Fuzzy Support Vector Machine Based on Affinity among Samples.Journal of Software,2006,17(5):951-958.)
[32] 周德龙,赵志国,潘泉,等.基于模糊集的图像增强算法研究.电子与信息学报,2002,24(7):905-909.(ZHOU D L,ZHAO Z G,PAN Q,et al.An Image Enhancement Algorithm Based on Fuzzy Sets.Journal of Electronics and Information Technology,2002,24(7):905-909.)
[33] 申铉京,刘翔,陈海鹏.基于多阈值Otsu准则的阈值分割快速计算.电子与信息学报,2017,39(1):144-149.(SHEN X J,LIU X,CHEN H P.Fast Computation of Threshold Based on Multi-threshold Otsu Criterion.Journal of Electronics and Information Technology,2017,39(1):144-149.)
[34] FR?NTI P,VIRMAJOKI O.Iterative Shrinking Method for Clus-tering Problems.Pattern Recognition,2006,39(5):761-775.
[35] GIONIS A,MANAILA H,TSAPARAS P.Clustering Aggregation.ACM Transactions on Knowledge Discovery from Data,2007,1(1).DOI:10.1145/1217299.1217303.
[36] VEENMAN C J,REINDERS M J T,BACKER E.A Maximum Variance Cluster Algorithm.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(9):1273-1280.
[37] BEZDEK J C,PAL N R.Some New Indexes of Cluster Validity.IEEE Transactions on Systems,Man,and Cybernetics(Cyberne-tics),1998,28(3):301-315.
[38] 刘解放,王士同,王骏,等.一种具有最优保证特性的贝叶斯可能性聚类方法.电子与信息学报,2017,39(7):1554-1562.(LIU J F,WANG S T,WANG J,et al.Bayesian Possibilistic Clustering Method with Optimality Guarantees.Journal of Electro-nics and Information Technology,2017,39(7):1554-1562.)