模糊聚类分析及其在数字图像处理中的应用
|
摘要
模糊C均值聚类算法(FCM)是非监督模式分类的主要方法之一,在模式识别中有着重要的地位。但现实生活中存在着大量的先验知识,大量的样本带有已知的信息,如何充分利用这些先验知识进行聚类成为人们研究的一个热点。本论文首先重新正确阐述了半监督聚类问题,对先验知识进行了分类描述,对半监督聚类问题研究现状作了回顾,主要研究了半监督FCM算法。在特征加权FCM算法基础上,将先验知识加入到其最优问题中,得到一种新的半监督特征加权FCM算法。该问题的求解可通过HPR乘子法解决,但是由于HPR乘子法是针对一般带有约束条件的非线性最优问题而言的,算法中引入了较多中间变量,计算复杂度比较高。本文通过恰当的变量替换和HPR乘子法的思想,得到了半监督特征加权FCM算法的新的求解方法。该算法与原FCM算法相比,没有增加变量个数,从而其运算速度影响不大。通过IRIS数据实验,得出该算法不仅深化了半监督FCM算法的讨论范围,而且计算复杂度相对不大。相对于已有的半监督FCM算法有长足的改善,同时也为全监督FCM算法提供了思想方法。
图像分割是图像处理中的一项基本内容,也是一门重要的图像技术。通过实验发现,将半监督特征加权FCM算法用到图像分割中,能取得较好的分割效果;手写数字识别也是图像处理和模式识别领域中较成功的研究课题之一。通过实验发现,将半监督特征加权FCM算法用到手写数字识别中,能取得较好的识别效果。
Fuzzy C-means clustering algorithm (FCM) is an important method of unsupervised pattern classification, and has an important position in pattern recognition. But in real life, there are a lot of known knowledge, and a large number of samples have known information, how to take full advantage of the known information of cluster become a hotspot of research.
In this paper, first of all, we re-elaborate the issue of the semi-supervised clustering, and describe the known knowledge by class, and discusse the research status of the semi-supervised clustering. Based on the feature weighted FCM algorithm, the known knowledge is added to the optimal problem, we get a new feature weighted FCM algorithm with semi-supervision. The problem can be solved by HPR algorithm, but HPR algorithm is suitable for the general nonlinear optimal question with constraint conditions, and is added a lot of middle variables, so make the computational complexity higher. In view of this, throng appropriate variable substitution and the thought of HPR algorithm, we obtain the new algorithm to solve the feature weighting FCM algorithm with semi-supervision. Compared with the original FCM algorithm, the number of variables of the new algorithm is not increased, thus there is little effect on its speed of operation. IRIS data experiment shows that the new algorithm not only deepens the discussion scope of the semi-supervised FCM algorithm, but also makes the computation complexity little. Compared with the existing semi-supervised FCM algorithm, the new algorithm has greater improvement, and provides a way of thinking for the FCM algorithm with supervision.
Image segmentation is an essential element in image processing, but also an important imaging technology. Through experiments we found that the feature weighted FCM algorithm with semi-supervision can achieve better results in image segmentation; handwritten numeral recognition is the more successful one research topic in the field of image processing and pattern recognition. Through experiments found that the feature weighted FCM with semi-supervised can obtain a better recognition effect in handwritten numeral recognition.
图像分割是图像处理中的一项基本内容,也是一门重要的图像技术。通过实验发现,将半监督特征加权FCM算法用到图像分割中,能取得较好的分割效果;手写数字识别也是图像处理和模式识别领域中较成功的研究课题之一。通过实验发现,将半监督特征加权FCM算法用到手写数字识别中,能取得较好的识别效果。
Fuzzy C-means clustering algorithm (FCM) is an important method of unsupervised pattern classification, and has an important position in pattern recognition. But in real life, there are a lot of known knowledge, and a large number of samples have known information, how to take full advantage of the known information of cluster become a hotspot of research.
In this paper, first of all, we re-elaborate the issue of the semi-supervised clustering, and describe the known knowledge by class, and discusse the research status of the semi-supervised clustering. Based on the feature weighted FCM algorithm, the known knowledge is added to the optimal problem, we get a new feature weighted FCM algorithm with semi-supervision. The problem can be solved by HPR algorithm, but HPR algorithm is suitable for the general nonlinear optimal question with constraint conditions, and is added a lot of middle variables, so make the computational complexity higher. In view of this, throng appropriate variable substitution and the thought of HPR algorithm, we obtain the new algorithm to solve the feature weighting FCM algorithm with semi-supervision. Compared with the original FCM algorithm, the number of variables of the new algorithm is not increased, thus there is little effect on its speed of operation. IRIS data experiment shows that the new algorithm not only deepens the discussion scope of the semi-supervised FCM algorithm, but also makes the computation complexity little. Compared with the existing semi-supervised FCM algorithm, the new algorithm has greater improvement, and provides a way of thinking for the FCM algorithm with supervision.
Image segmentation is an essential element in image processing, but also an important imaging technology. Through experiments we found that the feature weighted FCM algorithm with semi-supervision can achieve better results in image segmentation; handwritten numeral recognition is the more successful one research topic in the field of image processing and pattern recognition. Through experiments found that the feature weighted FCM with semi-supervised can obtain a better recognition effect in handwritten numeral recognition.
引文
进,或者做进一步的研究;
2.进行全监督的模糊聚类研究。
[1] Zadeh L A. Fuzzy sets.Information and Control, 8(1965):338~353
[2]闵珊华,贺仲雄.懂一点模糊数学.北京:中国青年出版社, 1985
[3]王士同,夏祖勋,陈剑夫.模糊数学在人工智能中的应用。北京:机械工业出版社,1991
[4] Bezdek J C. A review of probabilistic, fuzzy, and neutral model for pattern recognition. J. Intell. Fuzzy Syst, 1996(1):1~25
[5] Droodchi M, Reza A M, Nonlinear smoothing of signals by applying fuzzy clustering to local points. In Porc. 1996 ACM Symposium on Applied Computing, Philadelphia, PA. 1996:18~20
[6]朱剑英.应用模糊数学方法的若干关键问题及处理方法.模糊系统与数学, 1992, 11(2): 57~63
[7] Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC.1974,4(3):310~313
[8]丁斌.动态Fuzzy图最大树聚类分析.数值计算和计算机应用, 1992,2:157~159
[9] Backer E. Jain A K. A clustering performance measure based on fuzzy set decomposition. IEEE Trans. PAMI, 1981, 3(1):66~74
[10]高新波.模糊聚类分析及其应用.西安电子科技大学出版社,西安.2004.1
[11] Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC, 1974, 4(3): 310~313
[12] Bezdek J C. Pattern Recogition with Fuzzy Objective Function Algorithms. Plenum Press, New York, 1981
[13]姜琴,甘海涛. FCM算法中参数确定方法的探讨.武汉工业学院学报. 2009, 28(1):42~44
[14] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[15] Basu, S., Banerjee, A., and Mooney, R. 2002. Semi-supervised clustering by seeding. Proceedings of the Int. Conference on Machine Learning, pp. 19–26
[16] Nigam, K, McCallum, A, Thrun, S, and Mitchell, T. 2000. Text classification
from labeled and unlabeled documents using Expectation-Maximization. Machine Learning, 39(2/3):103–134
[17] Klinkenberg, R. 2001. Using labeled and unlabeled data to learn drifting concepts.Proceedings of the Workshop on Learning from Temporal and Spatial Data, pp. 16–24
[18] Blum, A., Lafferty, J., Rwebangira, M, and Reddy, R. 2004. Cluster kernels for semi-supervised learning. Proceedings of the 21th International Conference on Machine Learning, pp. 92–100
[19] Zhu, X. Kandola, J. Ghahramani, Z. and Lafferty, J. 2005. Nonparametric transforms of graph kernels for semi-supervised learning. Advances in Neural Information Processing Systems, 17:1641–1648
[20] W Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.No.3, pp.13-20, 1985
[21] Amine M.Bensaid, Lawrence O.Hall, James C.Bezdek and Laurence P.Clarke. Partially Supervised Clustering For Image Segmentation. Pattern Recognition, Vol.29, No5, pp.859-871, 1996
[22] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[23] ABDELHAMID BOUCHACHIA, WITOLD PEDRYCZ. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 12, 47-78, 2006
[24] Witold Pedrycz, George Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004), 1339-1349
[25]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,Vol.17,No4.2000年
[26] Bensaid A M, Hall L Q, Bezdek J C. et al. Partially supervised clustering for image segmentation. Pattern Recognition, 1996, 29(5)859~871
[27] Mohammed Benkhalifa, Amine Bensaid, Abdelhak Mouradi. Text Categorization using the Semi-Supervised Fuzzy c-Means Algorithm. Fuzzy Information Processing Society. 561– 565, 1999
[28]薛毅.最优化原理与方法.北京:北京工业大学出版社,2004,8
[29]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社, 2004,1
[30]何坚勇.最优化方法.北京:清华大学出版社, 2007, 1
[31]万仲平,费浦生.优化理论与方法.武汉:武汉大学出版社, 2004 ,6
[32] Xiaojun Tong, Qin Jiang, Haitao Gan, Shan Zeng, Kai Zhao. Research on the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm. CDABES2008. 8: 677~682from labeled and unlabeled documents using Expectation-Maximization. Machine Learning, 39(2/3):103–134
[17] Klinkenberg, R. 2001. Using labeled and unlabeled data to learn drifting concepts.Proceedings of the Workshop on Learning from Temporal and Spatial Data, pp. 16–24
[18] Blum, A., Lafferty, J., Rwebangira, M, and Reddy, R. 2004. Cluster kernels for semi-supervised learning. Proceedings of the 21th International Conference on Machine Learning, pp. 92–100
[19] Zhu, X. Kandola, J. Ghahramani, Z. and Lafferty, J. 2005. Nonparametric transforms of graph kernels for semi-supervised learning. Advances in Neural Information Processing Systems, 17:1641–1648
[20] W Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.No.3, pp.13-20, 1985
[21] Amine M.Bensaid, Lawrence O.Hall, James C.Bezdek and Laurence P.Clarke. Partially Supervised Clustering For Image Segmentation. Pattern Recognition, Vol.29, No5, pp.859-871, 1996
[22] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[23] ABDELHAMID BOUCHACHIA, WITOLD PEDRYCZ. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 12, 47-78, 2006
[24] Witold Pedrycz, George Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004), 1339-1349
[25]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,Vol.17,No4.2000年
[26] Bensaid A M, Hall L Q, Bezdek J C. et al. Partially supervised clustering for image segmentation. Pattern Recognition, 1996, 29(5)859~871
[27] Mohammed Benkhalifa, Amine Bensaid, Abdelhak Mouradi. Text Categorization using the Semi-Supervised Fuzzy c-Means Algorithm. Fuzzy Information Processing Society. 561– 565, 1999
[28]薛毅.最优化原理与方法.北京:北京工业大学出版社,2004,8
[29]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社, 2004,1
[30]何坚勇.最优化方法.北京:清华大学出版社, 2007, 1
[31]万仲平,费浦生.优化理论与方法.武汉:武汉大学出版社, 2004 ,6
[32] Xiaojun Tong, Qin Jiang, Haitao Gan, Shan Zeng, Kai Zhao. Research on the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm. CDABES2008. 8: 677~682
2.进行全监督的模糊聚类研究。
[1] Zadeh L A. Fuzzy sets.Information and Control, 8(1965):338~353
[2]闵珊华,贺仲雄.懂一点模糊数学.北京:中国青年出版社, 1985
[3]王士同,夏祖勋,陈剑夫.模糊数学在人工智能中的应用。北京:机械工业出版社,1991
[4] Bezdek J C. A review of probabilistic, fuzzy, and neutral model for pattern recognition. J. Intell. Fuzzy Syst, 1996(1):1~25
[5] Droodchi M, Reza A M, Nonlinear smoothing of signals by applying fuzzy clustering to local points. In Porc. 1996 ACM Symposium on Applied Computing, Philadelphia, PA. 1996:18~20
[6]朱剑英.应用模糊数学方法的若干关键问题及处理方法.模糊系统与数学, 1992, 11(2): 57~63
[7] Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC.1974,4(3):310~313
[8]丁斌.动态Fuzzy图最大树聚类分析.数值计算和计算机应用, 1992,2:157~159
[9] Backer E. Jain A K. A clustering performance measure based on fuzzy set decomposition. IEEE Trans. PAMI, 1981, 3(1):66~74
[10]高新波.模糊聚类分析及其应用.西安电子科技大学出版社,西安.2004.1
[11] Dunn J C. A graph theoretic analysis of pattern classification via Tamura’s fuzzy relation. IEEE Trans. SMC, 1974, 4(3): 310~313
[12] Bezdek J C. Pattern Recogition with Fuzzy Objective Function Algorithms. Plenum Press, New York, 1981
[13]姜琴,甘海涛. FCM算法中参数确定方法的探讨.武汉工业学院学报. 2009, 28(1):42~44
[14] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[15] Basu, S., Banerjee, A., and Mooney, R. 2002. Semi-supervised clustering by seeding. Proceedings of the Int. Conference on Machine Learning, pp. 19–26
[16] Nigam, K, McCallum, A, Thrun, S, and Mitchell, T. 2000. Text classification
from labeled and unlabeled documents using Expectation-Maximization. Machine Learning, 39(2/3):103–134
[17] Klinkenberg, R. 2001. Using labeled and unlabeled data to learn drifting concepts.Proceedings of the Workshop on Learning from Temporal and Spatial Data, pp. 16–24
[18] Blum, A., Lafferty, J., Rwebangira, M, and Reddy, R. 2004. Cluster kernels for semi-supervised learning. Proceedings of the 21th International Conference on Machine Learning, pp. 92–100
[19] Zhu, X. Kandola, J. Ghahramani, Z. and Lafferty, J. 2005. Nonparametric transforms of graph kernels for semi-supervised learning. Advances in Neural Information Processing Systems, 17:1641–1648
[20] W Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.No.3, pp.13-20, 1985
[21] Amine M.Bensaid, Lawrence O.Hall, James C.Bezdek and Laurence P.Clarke. Partially Supervised Clustering For Image Segmentation. Pattern Recognition, Vol.29, No5, pp.859-871, 1996
[22] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[23] ABDELHAMID BOUCHACHIA, WITOLD PEDRYCZ. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 12, 47-78, 2006
[24] Witold Pedrycz, George Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004), 1339-1349
[25]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,Vol.17,No4.2000年
[26] Bensaid A M, Hall L Q, Bezdek J C. et al. Partially supervised clustering for image segmentation. Pattern Recognition, 1996, 29(5)859~871
[27] Mohammed Benkhalifa, Amine Bensaid, Abdelhak Mouradi. Text Categorization using the Semi-Supervised Fuzzy c-Means Algorithm. Fuzzy Information Processing Society. 561– 565, 1999
[28]薛毅.最优化原理与方法.北京:北京工业大学出版社,2004,8
[29]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社, 2004,1
[30]何坚勇.最优化方法.北京:清华大学出版社, 2007, 1
[31]万仲平,费浦生.优化理论与方法.武汉:武汉大学出版社, 2004 ,6
[32] Xiaojun Tong, Qin Jiang, Haitao Gan, Shan Zeng, Kai Zhao. Research on the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm. CDABES2008. 8: 677~682from labeled and unlabeled documents using Expectation-Maximization. Machine Learning, 39(2/3):103–134
[17] Klinkenberg, R. 2001. Using labeled and unlabeled data to learn drifting concepts.Proceedings of the Workshop on Learning from Temporal and Spatial Data, pp. 16–24
[18] Blum, A., Lafferty, J., Rwebangira, M, and Reddy, R. 2004. Cluster kernels for semi-supervised learning. Proceedings of the 21th International Conference on Machine Learning, pp. 92–100
[19] Zhu, X. Kandola, J. Ghahramani, Z. and Lafferty, J. 2005. Nonparametric transforms of graph kernels for semi-supervised learning. Advances in Neural Information Processing Systems, 17:1641–1648
[20] W Pedrycz. Algorithms of Fuzzy Clustering with Partial Supervision. Pattern recognition letters.No.3, pp.13-20, 1985
[21] Amine M.Bensaid, Lawrence O.Hall, James C.Bezdek and Laurence P.Clarke. Partially Supervised Clustering For Image Segmentation. Pattern Recognition, Vol.29, No5, pp.859-871, 1996
[22] W Pedrycz and Waletzky. Fuzzy clustering with partial supervision. IEEE Transactions on Systems Man and Cybernetics, B 27(5):787–795, 1997
[23] ABDELHAMID BOUCHACHIA, WITOLD PEDRYCZ. Data Clustering with Partial Supervision. Data Mining and Knowledge Discovery, 12, 47-78, 2006
[24] Witold Pedrycz, George Vukovich. Fuzzy clustering with supervision. Pattern Recognition 37(2004), 1339-1349
[25]窦葳,黄昕,杨伟松.监督FCM分割MRI颅脑组织探讨.中国医学物理学杂志,Vol.17,No4.2000年
[26] Bensaid A M, Hall L Q, Bezdek J C. et al. Partially supervised clustering for image segmentation. Pattern Recognition, 1996, 29(5)859~871
[27] Mohammed Benkhalifa, Amine Bensaid, Abdelhak Mouradi. Text Categorization using the Semi-Supervised Fuzzy c-Means Algorithm. Fuzzy Information Processing Society. 561– 565, 1999
[28]薛毅.最优化原理与方法.北京:北京工业大学出版社,2004,8
[29]唐焕文,秦学志.实用最优化方法.大连:大连理工大学出版社, 2004,1
[30]何坚勇.最优化方法.北京:清华大学出版社, 2007, 1
[31]万仲平,费浦生.优化理论与方法.武汉:武汉大学出版社, 2004 ,6
[32] Xiaojun Tong, Qin Jiang, Haitao Gan, Shan Zeng, Kai Zhao. Research on the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm. CDABES2008. 8: 677~682