Analysis of Structural Clustering Based on Normalized Metric
TANG Xu-Qing1, ZHU Ping1, CHENG Jia-Xing2
1.School of Science, Jiangnan University, Wuxi 214122 2.Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230039
Abstract：On the basis of the ordered granular space, structural clustering (or classification) analysis is proposed based on normalized metric. Firstly, the concept of consistent clustering according to metric is presented, and the research on consistent clustering characteristic of ordered granular space is given. Secondly, structural clustering analysis theory is given based on normalized metric, and the algorithm to obtain its structural clustering is discussed. Thirdly, the research on the determination of the optimal clustering based on ordered granular space is carried out. A method to obtain the optimal clustering is given, and the method is global optimal. Finally, the fusion technology based on structural clusters of normalized metrics is studied by the intersection operation of two normalized metrics. The conclusions provide a comprehensive theory and methodology on structural clustering (or classification) analysis based on metric.
[1] Theodoridis S, Koutroumbas K. Pattern Recognition. 2nd Edition. Amsterdam, Netherlands: Elsevier, 2003 [2] Yang Shuying. Pattern Recognition and Intelligent Computing — Technical Realization of Matlab. Beijing. China: Electronics Industry Press, 2008 (in Chinese) (杨淑莹. 模式识别与智能计算——Matlab技术实现. 北京: 电子工业出版社, 2008) [3] Xu Zongben, Zhang Jiangshe, Zheng Yalin. Bionics in Intelligent Computing: Theory and Algorithms. Beijing, China: Science Press, 2004 (in Chinese) (徐宗本, 张讲社, 郑亚林. 计算智能中的仿生学: 理论与算法. 北京: 科学出版社, 2004) [4] Richard O, Duda P E, Hart D G S. Pattern Classification. 2nd Edition. New York, USA: John Wiley & Sons, 2001 [5] Wu Chengzhong. Introduction of Fuzzy Sets (I). Beijing, China: Beijing Normal University Press, 1989 (in Chinese) (吴承忠. 模糊集引论(上). 北京: 北京师范大学出版社, 1989) [6] Ruspini E H . A New Approach to Clustering. Information and Control, 1969, 15(1): 22-32 [7] He Qing, Li Hongxiang, Xhi Zhongzhi, et al. Fuzzy Clustering Method Based on Perturbation. Computers and Mathematics with Applications, 2003, 46(5/6): 929-946 [8] Lee H S. An Optimal Algorithm for Computing the Max-Min Transitive Closure of a Fuzzy Similarity Matrix. Fuzzy Sets and Systems, 2001, 123(1): 129-136 [9] Liang G S, Chou T Y, Han T C, et al. Cluster Analysis Based on Fuzzy Equivalence Relation. European Journal of Operational Research, 2005, 166(1): 160-171 [10] Liu Baoding, Esogbue A O. Cluster Validity for Fuzzy Criterion Clustering // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Vancouver, Canada, 1995, Ⅴ: 4702-4705 [11] Kamimura H, Kurano M. Clustering by a Fuzzy Metric. Fuzzy Sets and Systems, 2001, 120(2): 249-254 [12] Kim D W, Lee K H, Lee D. Fuzzy Clustering of Categorical Data Using Fuzzy Centroids. Pattern Recognition Letters, 2004, 25(11): 1263-1271 [13] Angelov P. An Approach for Fuzzy Rule-Base Adaptation Using On-line Clustering. International Journal of Approximate Reasoning, 2004, 35(3): 275-289 [14] Devillez A, Billaudel P, Lecolier G V, et al. A Fuzzy Hybrid Hierarchical Clustering Method with a New Criterion Able to Find the Optimal Partition. Fuzzy Sets and Systems, 2002, 128(3): 323-338 [15] Pedrycz W. Collaborative Fuzzy Clustering. Pattern Recognition Letters, 2002, 23(14): 1675-1686 [16] Piangkh O S. Analytically Tractable Case of Fuzzy C-Means Clustering. Pattern Recognition, 2006, 39(1): 35-46 [17] Tsekouras G, Sarimveis H, Kavakli E, et al. A Hierarchical Fuzzy Clustering Approach to Fuzzy Modeling. Fuzzy Sets and Systems, 2005, 150(2): 246-266 [18] Wu K L, Yu Jian, Yang M S, et al. A Novel Fuzzy Clustering Algorithm Based on a Fuzzy Scatter Matrix with Optimality Tests. Pattern Recognition Letters, 2005, 26(5): 639-652 [19] Fu Guoyao. Optimization Methods for Fuzzy Clustering. Fuzzy Sets and Systems, 1998, 93(3): 301-309 [20] Frey B J, Dueck D. Clustering by Passing Messages between Data Points. Science, 2007, 315(5814): 972-976 [21] Yang M S, Ko C H. On a Class of Fuzzy C-Numbers Clustering Procedures for Fuzzy Data. Fuzzy Sets and Systems, 1996, 84(1): 49-60 [22] Hung W L, Yang M S. Fuzzy Clustering on LR-Type Fuzzy Numbers with an Application in Taiwanese Tea Evaluation. Fuzzy Sets and Systems, 2005, 150(3): 561-577 [23] Tang Xuqing, Zhu Ping, Cheng Jiaxing. Cluster Analysis Based on Fuzzy Quotient Space. Journal of Software, 2008, 19(4): 861-868 (in Chinese) (唐旭清,朱 平,程家兴.基于模糊商空间的聚类分析方法. 软件学报, 2008, 19(4): 861-868) [24] Tang Xuqing, Zhu Ping, Cheng Jiaxin. Study on Fuzzy Granular Space Based on Normalized Equicrural Metric. Computer Science, 2008, 35(4): 142-145 (in Chinese) (唐旭清,朱 平,程家兴.基于等腰归一化距离的模糊粒度空间研究.计算机科学, 2008, 35(4): 142-145) [25] Pawlak Z. Rough Sets. International Journal of Computer and Information Science, 1982, 11: 341-356 [26] Zhang Bo, Zhang Ling. The Theory and Application of Problem Solving. Amsterdam, Netherlands: Elsevier Science, 1992 [27] Zhang Ling, Zhang Bo. Theory of Problem Solving and Its Applications — The Theory and Methods of Quotient Space of Granular Computing. 2nd Edition. Beijing, China: Tsinghua University Press, 2007 (in Chinese) (张 铃,张 钹.问题求解理论及应用——商空间粒度计算理论及应用.第2版.北京:清华大学出版社, 2007) [28] Zhang Ling, Zhang Bo. Theory of Fuzzy Quotient Space (Methods of Fuzzy Granular Computing). Journal of Software, 2003, 14(4): 770-776 (in Chinese) (张 铃,张 钹.模糊商空间理论(模糊粒度计算方法). 软件学报, 2003, 14(4): 770-776) [29] Zhang Ling, Zhang Bo. The Structure Analysis of Fuzzy Sets. International Journal of Approximate Reasoning, 2005, 40(12): 92-108 [30]Li Jun, Wang Guojun. Theory of α-Truth Degrees in n-Valued Gdel Propositional Logic. Journal of Software, 2007, 18(1): 33-39 (in Chinese) (李 骏,王国俊.Gdel n值命题逻辑中命题的α-真度理论.软件学报, 2007, 18(1): 33-39) [31] Yao Y Y. Granular Computing: Basic Issues and Possible Solutions // Proc of the 5th Joint Conference on Information Sciences. Atlantic City, USA, 2000, Ⅰ: 186-189 [32] Yao Y Y, Yao J T. Granular Computing as a Basis for Consistent Classification Problems // Proc of the PAKDD Workshop on Foundation of Data Mining. Taipei, China, 2002: 101-106 [33] Bezdek J C, Pal N R. Some New Indexes of Cluster Validity. IEEE Trans on Systems, Man and Cybernetics, 1998, 28(3): 301-315 [34] Gunderson R W. Application of Fuzzy ISODATA Algorithms to Star-Tracker Pointing Systems // Proc of the 7th Triannual World IFAC Congress. Helsinki, Finland, 1978: 1319-1323 [35] Kothari R, Pitts D. On Finding the Number of Clusters. Pattern Recognition Letters, 1999, 20(4): 405-416 [36] Fu Guoyao. Optimization Methods for Fuzzy Clustering. Fuzzy Sets and Systems, 1998, 93(3): 301-309 [37] Trauwert E, Kaufman L, Rousseeuw P. Fuzzy Clustering Algorithms Based on the Maximum Likelihood Principle. Fuzzy Sets and Systems, 1991, 42(2): 213-227 [38] Hardy A. On the Number of Classes. Computational Statistics and Data Analysis, 1996, 23(1): 83-96 [39] Sun Haojun, Wang Shengrui, Jiang Qingshan. FCM-Based Model Selection Algorithms for Determining the Number of Clusters. Pattern Recognition Letters, 2004, 37(10): 2027-2037 [40] Kim D W, Lee K H, Lee D. On Cluster Validity Index for Estimation of Optimal Number of Fuzzy Clusters. Pattern Recognition, 2004, 37(10): 2009-2025 [41] Yu Jian, Cheng Qiansheng. The Search Scope of Optimal Cluster Number in Fuzzy Clustering Method. Science in China: Series E, 2002, 32(2): 274-280 (in Chinese) (于 剑,程乾生.模糊聚类方法中的最佳聚类数的搜索范围.中国科学:E辑, 2002, 32(2): 274-280) [42] Rezaee M R, Lelieveldt B P F, Reiber J H C. A New Cluster Validity Index for Fuzzy C-means. Pattern Recognition Letters, 1998,19(3/4): 237-246 [43] Pal N R, Bezdek J C. On Cluster Validity for the Fuzzy C-Means Model. IEEE Trans on Fuzzy System, 1995, 3(3): 370-379 [44] Backer E, Jain A K. A Clustering Performance Measure Based on Fuzzy Set Decomposition. IEEE Trans on Pattern Analysis and Machine Intelligence, 1981, 3(1): 66-75 [45] Bezdek J C. Cluster Validity with Fuzzy Sets. Cybernetics and Systems, 1974, 3(3): 58-73 [46] Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms. New York, USA: Plenum Press, 1981 [47] Windham M P. Cluster Validity for Fuzzy Clustering Algorithms. Fuzzy Sets and Systems, 1981, 5: 177-185 [48] Bezdek J C. Mathematical Models for Systematics and Taxonomy // Proc of the 8th International Conference on Numerical Taxonomy. San Francisco, USA, 1975: 143-166 [49] Fukuyama Y, Sugeno M. A New Method of Choosing the Number of Clusters for the Fuzzy C-Means Method // Proc of the 5th Fuzzy Systems Symposium. Kyoto, Japan, 1989: 247-250 [50] Xie L X, Beni G. A Validity Measure for Fuzzy Clustering. IEEE Trans on Pattern Analysis and Machine Intelligence, 1991, 13(8): 841-847 [51] Pedrycz W. Collaborative Fuzzy Clustering. Pattern Recognition Letters, 2002, 23(14): 1675-1686 [52] Miyamoto S. Information Clustering Based on Fuzzy Multi-Sets. Information Processing and Management: An International Journal, 2003, 39(2): 195-213
2009, Vol. 22 
