基于特征权重的FCM算法研究及应用
|
摘要
模糊C-均值(FCM)聚类算法是非监督模式识别中应用范围最广泛的算法之一。但是传统的FCM算法中,设定样本的各维特征对分类效果的贡献水平是相同的。在实际中,由于特征提取不够完善,使得特征矢量中每维特征对分类的贡献不均匀,聚类中必须考虑各维特征的不同影响。本文提出建立了一种FCM特征权重的自适应算法。在该算法中制定了对聚类有效的两个原则:特征贡献平衡原则和类间分离度最大原则。根据这两个原则,对数据的各维特征进行归一化处理,实现其贡献的平衡性,然后利用特征加权,使得差异性大的特征对分类贡献更大。改进的FCM算法相对于传统的FCM算法有更强的无监督性和自动化,误分率小,得到的聚类原型模式也更接近实际的类中心位置。同时通过结果还可以分析各维特征对分类的贡献程度,有效的进行特征提取和优选,这在实际应用中是非常方便的。
针对基于特征权重的后验FCM学习算法程序化问题,进行了细致的研究。设计思路是利用已知样本集,选取部分作为初始训练样本集,然后通过改进的FCM算法进行多层分类,分类过程中要将相应的因素保存下来,构成分类训练器。程序语言是采用C语言和Matlab语言相结合的方式。
在程序实现过程中,为了使得类间距离足够大,程序实现了贴近度特征转换算法;对于过多的孤立样本,将根据万有引力思想构造的吸收化FCM算法进行了程序化;因为要进行多层循环分类,算法结构主要是采用的递归算法;程序产生的数据采用的线性链表和树形结构保存。
训练完成后,利用测试样本对程序进行了测试,结果显示分类效果良好。
Fuzzy C-means (FCM) clustering algorithm is used most widely in non-supervision of pattern recognition algorithm.But in the traditional FCM algorithm,each feature of the samples plays a uniform contribution for clustering.In fact, due to the feature selection are not perfect,each feature of the feature vector is not uniform for clustering contribution,we have to take into account the different effect of each feature.So we bring forward an adaptive algorithm for the weight of the feature weighted of FCM,In this algorithm, we establish two principles:the principle of the feature contribution balance and the principle of the most separate degree of intra-cluster.Based on this two principles,we normalize each feature to achieve the balance of their contributions,and then,we get the feature weight,make the feature with larger otherness should work more contribution for classification.
The new FCM arithmetic is unsupervised and adaptive compared with the traditional one,and the misclassification percent of the new one is less than the traditional one,and the improved method can also make the center of every sort closer to the actual.At the same time,we can carry the feature extraction and selection effectively with analyzing the contributions of the various features through the results,and in practice,it is very convenient.
Aimed at the program problem of the posterior FCM learning algorithm with the feature weighted,we carried the studying detailedly.The design ideas is selecting the part of the known samples as the initial training sample set,then carrying multi-classification with the FCM algorithm by improving,we need preserve the appropriate factors among the classification process to constitutes a classification trainer.The programming language is combine C language with Matlab language.
In the program implementation process,in order to make the distance between classes large enough,the program achieved the similarity feature transformation algorithm;about so much isolated sample,we make the program of the absorption of FCM algorithm based on the thought of gravity;since the needs for multi- circulation classification,the algorithm structure mainly adopts recursive algorithm;we save process data generated by a linear linked list and tree structure.
After training completed,we checkout the program by using testing samples,and we get a good classification results.
针对基于特征权重的后验FCM学习算法程序化问题,进行了细致的研究。设计思路是利用已知样本集,选取部分作为初始训练样本集,然后通过改进的FCM算法进行多层分类,分类过程中要将相应的因素保存下来,构成分类训练器。程序语言是采用C语言和Matlab语言相结合的方式。
在程序实现过程中,为了使得类间距离足够大,程序实现了贴近度特征转换算法;对于过多的孤立样本,将根据万有引力思想构造的吸收化FCM算法进行了程序化;因为要进行多层循环分类,算法结构主要是采用的递归算法;程序产生的数据采用的线性链表和树形结构保存。
训练完成后,利用测试样本对程序进行了测试,结果显示分类效果良好。
Fuzzy C-means (FCM) clustering algorithm is used most widely in non-supervision of pattern recognition algorithm.But in the traditional FCM algorithm,each feature of the samples plays a uniform contribution for clustering.In fact, due to the feature selection are not perfect,each feature of the feature vector is not uniform for clustering contribution,we have to take into account the different effect of each feature.So we bring forward an adaptive algorithm for the weight of the feature weighted of FCM,In this algorithm, we establish two principles:the principle of the feature contribution balance and the principle of the most separate degree of intra-cluster.Based on this two principles,we normalize each feature to achieve the balance of their contributions,and then,we get the feature weight,make the feature with larger otherness should work more contribution for classification.
The new FCM arithmetic is unsupervised and adaptive compared with the traditional one,and the misclassification percent of the new one is less than the traditional one,and the improved method can also make the center of every sort closer to the actual.At the same time,we can carry the feature extraction and selection effectively with analyzing the contributions of the various features through the results,and in practice,it is very convenient.
Aimed at the program problem of the posterior FCM learning algorithm with the feature weighted,we carried the studying detailedly.The design ideas is selecting the part of the known samples as the initial training sample set,then carrying multi-classification with the FCM algorithm by improving,we need preserve the appropriate factors among the classification process to constitutes a classification trainer.The programming language is combine C language with Matlab language.
In the program implementation process,in order to make the distance between classes large enough,the program achieved the similarity feature transformation algorithm;about so much isolated sample,we make the program of the absorption of FCM algorithm based on the thought of gravity;since the needs for multi- circulation classification,the algorithm structure mainly adopts recursive algorithm;we save process data generated by a linear linked list and tree structure.
After training completed,we checkout the program by using testing samples,and we get a good classification results.
引文
[1]高新波.模糊聚类算法的优化及应用研究:[博士学位论文].西安:西安电子科技大学,1998:1~8
[2]Bezdek J C. A review of probabilistic, fuzzy, and neural models for pattern recognition. J. Intell. Fuzzy Syst. ,1(1996):1~25
[3]高新波.模糊聚类分析及其应用.西安:西安电子科技大学出版社,2004:3~7
[4]何清.模糊聚类分析理论与应用研究进展.模糊系统与数学, 1998, 12(2):89~94
[5]Zadeh L A. Fuzzy sets. Information and Control, 8(1965):338~353
[6]朱剑英.应用模糊数学方法的若干关键问题及处理方法.模糊系统与数学, 1992, 11(2):57~63
[7]陈元谱,尹建伟,董金祥.基于可能性理论的聚类分析.计算机工程与应用, 2003,39(13):85~87
[8]Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC, 1974, 4(3):310~313
[9]Zkim Le. Fuzzy relation compositions and pattern recognition. Inf. Sci. , 1996,89:107~130
[10]Ruspini E H. A new approach to clustering. Inf. Cont. ,1969, 15(1):22~32
[11]J.C. Dunn. Well-separated clusters and the optimal fuzzy partitions. J Cybernet, 1974, 4:95~104
[12] Bezdek J C. Pattern recognition with fuzzy objective function algorithms. New York:Plenum Press, 1981
[13]L. Bobrowski, J.C. Bezdek. C-means clustering with the L1 and∞norms. IEEE Trans. Systems Man and Cybernetics, 1991, 21(3):545~554
[14] H. Frigui. and R. Krishnapuram. A comparison of fuzzy shell clustering methods for the detection of ellipses. IEEE Trans. Fuzzy Systems, 1996, 4 (2):193~217
[15]R. Krishnapuram, H. Frigui, O. Nasraoui. Fuzzy and possibilistic shell clusteringalgorithms and their application to boundary detection and surface approximation. IEEE Trans. Fuzzy Systems, 1995, 3(1):29~60
[16]R.J. Hathaway, Y Hu, Density-weighted fuzzy C-means clustering. IEEE Trans. Fuzzy Systems, 2009, 17(1):243~252
[17]X.Z. Wang, Y.D. Wang, L.J. Wang. Improving fuzzy c-means clustering based on feature-weighted learning. Pattern Recognition Letters, 2004, 25(10):1123~1132
[18]W. Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.1985 (3):13~20
[19]W. Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Trans. Systems Man and Cybernetics, 1997, B27 (5):787~795
[20]A. Bouchachia, W. Pedrycz. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 2006(12):47~78
[21]W. Pedrycz, G. Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004):1339~1349
[22]H.X. Zhang, J. Lu. Semi-supervised fuzzy clustering: A kernel-based approach, Knowledge-Based Systems, 2009, 22(6):477~481
[23]裴继红,范九伦,谢维信.一种新的高效软聚类方法.截集模糊G均值聚类算法.电子学报, 1998, 26(2):83~86
[24]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,2000,17(4):201~202
[25]武小红,周建江.可能性模糊C-均值聚类新算法.电子学报,2008,36(10):1996~200
[26]张慧哲,王坚.基于初始聚类中心选取的改进FCM聚类算法.计算机科学, 2009, 36(6):206~ 209
[27]丁震,胡钟山等.一种基于模糊聚类的图像分割方法.计算机研究与发展, 1997, 34(7):536~541
[28]Gao Xinbo, Xie Weixin. Adavances in theory and applications of fuzzy clustering. Chinese Science Bulletin, 2000, 45(11):961~970
[29]Bezdek J C, Fordon W A. The application of fuzzy set theory to the medical diagnosis. In Advances of Fuzzy Sets and Theories, North-Holland, Amsterdam, 1979:445~461
[30]Sheng Chen, Gibson G J, cowan C F N. Adaptive channel equalization using a polynomial-perceptron structure. Proc. Inst. Elec. Eng. ,1990, 137(5):257~264
[31]Karayiannis N B, Bezdek J C. An integrated approach to fuzzy learning vector quantizatin and fuzzy c-means clustering. IEEE Trans. FS, 1997, 5(4):695~702
[32]Ryoke M, Nakamori Y, Suzuki K. Adaptive fuzzy clustering and fuzzy prediction models. FUZZ-IEEE’95, 1995:2215~2220
[33]Bezdek J C, Castelaz P F. Prototype classification and feature selection with fuzzy sets. IEEE Trans. SMC, 1977, 2(7):87~92
[34]Bezdek J C, Lim G. Classification with multiple prototype. FUZZ-IEEE’96, 1996:626~632
[35]Antonio M D, Skarmeta F G, Martin F. A fuzzy clustering-based rapid prototyping for fuzzy rule-based modeling. IEEE Trans.FS, 1997, 2(5):223~232
[36]Delgado M, Gomez-Skarmeta A F, A fuzzy clustering-based rapid prototyping for fuzzy rule-based modeling. IEEE Trans. FS,1997, 5(2):223~233
[37]Zhang Qiwen, Wang QR, Boyle R.A clustering algorithm for data~ sets with a large number of classes, Pattern recognition, 1991, 4 (24):331~340
[38]Wu Youshou, Ding Xiaoqing. A new clustering method for Chinese character recognition system using artificial neural networks. Chinese J of Electrionies, 1993, 2 (3):1~8
[39]Huang Zezhen, Kuth A .A combined self~ organizing feature map and multi~ layer perception for isolated word recognition. IEEE SP, 1992, 40 (11):2651~2657
[40]刘增良.模糊技术与应用选编.北京:北京航空航天大学出版社, 1997:8~10
[41]Coleman G B, Andrews H C. Image segmentation by clustering. Proc. IEEE, 1979, 5(67):773~785
[42]刘健庄.基于二维直方图的图像模糊聚类分割方法.电子学报,1992 ,20(9):40～46
[43]Trivedi MM, Bezdek J C. Low-level segmentation of aerial image with fuzzy clustering. IEEE SMC , 1986 , 16(4):589～598
[44]Chaudhuri B B, Sarkar N. Texture segmentation using fractal dimension. IEEEPAMI , 1995 , 17 (1) :72～77
[45]Krishnapuram R, Frigui H, Nasraoni O. New fuzzy shell clustering algorithms for boundary detection and pattern recognition. In Proc. SPIE Conf. Robotics and Computer Vision, Boston, 1991, 1607:458~465
[46]曾山.基于模糊聚类算法的手写数字图像识别[硕士学位论文].保存地点:武汉工业学院,2009:1~8
[47]Tong Xiaojun, Jiang Qin, Gan Haitao. Research On the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm[A]. CDABES, 2008,1(1):27~31.
[48]Tong Xiaojun, Zhang Shemin. Similarity and Nearness of Fuzzy Sets. Proceedings of the Fourth International Conference on Machine Learning and Cybemetics, Guangzhou, 2005:2668~2670
[49]边肇祺,张学工.模式识别(第二版).北京:清华大学出版社,2000:176~210
[50]陈望宇,廖芹.基于遗传算法的贝叶斯网络模型研究[J].计算机工程与设计, 2009, (11):2756~2759, 2799
[51]Ripley.模式识别与神经网络.北京:人民邮电出版社,2009:22~32
[2]Bezdek J C. A review of probabilistic, fuzzy, and neural models for pattern recognition. J. Intell. Fuzzy Syst. ,1(1996):1~25
[3]高新波.模糊聚类分析及其应用.西安:西安电子科技大学出版社,2004:3~7
[4]何清.模糊聚类分析理论与应用研究进展.模糊系统与数学, 1998, 12(2):89~94
[5]Zadeh L A. Fuzzy sets. Information and Control, 8(1965):338~353
[6]朱剑英.应用模糊数学方法的若干关键问题及处理方法.模糊系统与数学, 1992, 11(2):57~63
[7]陈元谱,尹建伟,董金祥.基于可能性理论的聚类分析.计算机工程与应用, 2003,39(13):85~87
[8]Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC, 1974, 4(3):310~313
[9]Zkim Le. Fuzzy relation compositions and pattern recognition. Inf. Sci. , 1996,89:107~130
[10]Ruspini E H. A new approach to clustering. Inf. Cont. ,1969, 15(1):22~32
[11]J.C. Dunn. Well-separated clusters and the optimal fuzzy partitions. J Cybernet, 1974, 4:95~104
[12] Bezdek J C. Pattern recognition with fuzzy objective function algorithms. New York:Plenum Press, 1981
[13]L. Bobrowski, J.C. Bezdek. C-means clustering with the L1 and∞norms. IEEE Trans. Systems Man and Cybernetics, 1991, 21(3):545~554
[14] H. Frigui. and R. Krishnapuram. A comparison of fuzzy shell clustering methods for the detection of ellipses. IEEE Trans. Fuzzy Systems, 1996, 4 (2):193~217
[15]R. Krishnapuram, H. Frigui, O. Nasraoui. Fuzzy and possibilistic shell clusteringalgorithms and their application to boundary detection and surface approximation. IEEE Trans. Fuzzy Systems, 1995, 3(1):29~60
[16]R.J. Hathaway, Y Hu, Density-weighted fuzzy C-means clustering. IEEE Trans. Fuzzy Systems, 2009, 17(1):243~252
[17]X.Z. Wang, Y.D. Wang, L.J. Wang. Improving fuzzy c-means clustering based on feature-weighted learning. Pattern Recognition Letters, 2004, 25(10):1123~1132
[18]W. Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.1985 (3):13~20
[19]W. Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Trans. Systems Man and Cybernetics, 1997, B27 (5):787~795
[20]A. Bouchachia, W. Pedrycz. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 2006(12):47~78
[21]W. Pedrycz, G. Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004):1339~1349
[22]H.X. Zhang, J. Lu. Semi-supervised fuzzy clustering: A kernel-based approach, Knowledge-Based Systems, 2009, 22(6):477~481
[23]裴继红,范九伦,谢维信.一种新的高效软聚类方法.截集模糊G均值聚类算法.电子学报, 1998, 26(2):83~86
[24]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,2000,17(4):201~202
[25]武小红,周建江.可能性模糊C-均值聚类新算法.电子学报,2008,36(10):1996~200
[26]张慧哲,王坚.基于初始聚类中心选取的改进FCM聚类算法.计算机科学, 2009, 36(6):206~ 209
[27]丁震,胡钟山等.一种基于模糊聚类的图像分割方法.计算机研究与发展, 1997, 34(7):536~541
[28]Gao Xinbo, Xie Weixin. Adavances in theory and applications of fuzzy clustering. Chinese Science Bulletin, 2000, 45(11):961~970
[29]Bezdek J C, Fordon W A. The application of fuzzy set theory to the medical diagnosis. In Advances of Fuzzy Sets and Theories, North-Holland, Amsterdam, 1979:445~461
[30]Sheng Chen, Gibson G J, cowan C F N. Adaptive channel equalization using a polynomial-perceptron structure. Proc. Inst. Elec. Eng. ,1990, 137(5):257~264
[31]Karayiannis N B, Bezdek J C. An integrated approach to fuzzy learning vector quantizatin and fuzzy c-means clustering. IEEE Trans. FS, 1997, 5(4):695~702
[32]Ryoke M, Nakamori Y, Suzuki K. Adaptive fuzzy clustering and fuzzy prediction models. FUZZ-IEEE’95, 1995:2215~2220
[33]Bezdek J C, Castelaz P F. Prototype classification and feature selection with fuzzy sets. IEEE Trans. SMC, 1977, 2(7):87~92
[34]Bezdek J C, Lim G. Classification with multiple prototype. FUZZ-IEEE’96, 1996:626~632
[35]Antonio M D, Skarmeta F G, Martin F. A fuzzy clustering-based rapid prototyping for fuzzy rule-based modeling. IEEE Trans.FS, 1997, 2(5):223~232
[36]Delgado M, Gomez-Skarmeta A F, A fuzzy clustering-based rapid prototyping for fuzzy rule-based modeling. IEEE Trans. FS,1997, 5(2):223~233
[37]Zhang Qiwen, Wang QR, Boyle R.A clustering algorithm for data~ sets with a large number of classes, Pattern recognition, 1991, 4 (24):331~340
[38]Wu Youshou, Ding Xiaoqing. A new clustering method for Chinese character recognition system using artificial neural networks. Chinese J of Electrionies, 1993, 2 (3):1~8
[39]Huang Zezhen, Kuth A .A combined self~ organizing feature map and multi~ layer perception for isolated word recognition. IEEE SP, 1992, 40 (11):2651~2657
[40]刘增良.模糊技术与应用选编.北京:北京航空航天大学出版社, 1997:8~10
[41]Coleman G B, Andrews H C. Image segmentation by clustering. Proc. IEEE, 1979, 5(67):773~785
[42]刘健庄.基于二维直方图的图像模糊聚类分割方法.电子学报,1992 ,20(9):40～46
[43]Trivedi MM, Bezdek J C. Low-level segmentation of aerial image with fuzzy clustering. IEEE SMC , 1986 , 16(4):589～598
[44]Chaudhuri B B, Sarkar N. Texture segmentation using fractal dimension. IEEEPAMI , 1995 , 17 (1) :72～77
[45]Krishnapuram R, Frigui H, Nasraoni O. New fuzzy shell clustering algorithms for boundary detection and pattern recognition. In Proc. SPIE Conf. Robotics and Computer Vision, Boston, 1991, 1607:458~465
[46]曾山.基于模糊聚类算法的手写数字图像识别[硕士学位论文].保存地点:武汉工业学院,2009:1~8
[47]Tong Xiaojun, Jiang Qin, Gan Haitao. Research On the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm[A]. CDABES, 2008,1(1):27~31.
[48]Tong Xiaojun, Zhang Shemin. Similarity and Nearness of Fuzzy Sets. Proceedings of the Fourth International Conference on Machine Learning and Cybemetics, Guangzhou, 2005:2668~2670
[49]边肇祺,张学工.模式识别(第二版).北京:清华大学出版社,2000:176~210
[50]陈望宇,廖芹.基于遗传算法的贝叶斯网络模型研究[J].计算机工程与设计, 2009, (11):2756~2759, 2799
[51]Ripley.模式识别与神经网络.北京:人民邮电出版社,2009:22~32