使用強韌叢集演算法的叢集整合技術

Robust clustering for cluster ensemble

石耿維(Keng-Wei Shih)

指導教授 ： 王才沛

國立交通大學/資訊學院/多媒體工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00917

摘要

本論文研究目的在於探討強韌的叢集演算法（robust clustering）應用在叢集整和（cluster ensemble）技術上的分析。叢集整合演算法包括三個主要的部份：1.產生個別分群的叢集演算法、2.將個別分群用一個資料結構來整合各結果、3.如何由這個整合的資料結構來得出最終的分群。第一部份我們將使用強韌叢集演算法（robust clustering）做分群，本論文中將會使用NC（Noise Clustering）及PFCM（Possibilistic Fuzzy c-Means Clustering）作為個別分群的叢集演算法，第二部份我們將使用代表資料點兩兩關係的co-association矩陣來紀錄各個叢集後的結果，第三部份接著再從co-association矩陣中利用階層式叢集演算法（hierarchical agglomerative clustering algorithm）找出最終分群結果並去除雜訊。最終分群的結果好壞會利用NMI（normalized mutual information）做最後分析。測試的資料中我們會用各種資料，包涵高斯、曲線，分析各種叢集演算法後的結果，有雜訊和無雜訊對叢集整合的影響，以及從最後階層樹中分析出最終的分群數目。

關鍵字

強韌叢集 ； 雜訊叢集 ； 模糊 ； 雜訊 ； 叢集整合

並列摘要

In this paper, we discuss using robust clustering for cluster ensembles. Cluster ensemble algorithms include three main parts: (1) Generate clusters by applying different clustering algorithms; (2) combine multiple results as a data structure; (3) find the clustering result from data structure. In the first part, we use robust clustering algorithm to generate multiple clustering results. Robust clustering algorithms used include noise clustering (NC) and possibilistic fuzzy c-means clustering (PFCM). In the second part, we use co-association matrix to organize clusters. In the third part, we discard noises from the co-association matrix and then use hierarchical agglomerative clustering algorithm to find the final cluster. The quality of combination results can be evaluated with normalized mutual information (NMI). The data sets, used for testing include Gaussian and half rings with or without noise.

並列關鍵字

robust clustering ； noise clustering ； fuzzy ； noise ； outlier ； cluster ensemble ； possibilistic

參考文獻

[1] R.N. Dave, "Characterization and detection of noise in clustering", Pattern Recognition Letters, vol. 12, pp. 657-664, 1991.

[2] R. Krishnapuram and J.M. Keller, "A possibilistic approach to clustering", IEEE. Trans. Fuzzy Systems, vol. 1, pp. 98-110, 1993.

[3] M. Barni, V. Cappellini, and A. Mecocci, "Comments on 'A Possibilistic Approach to Clustering' ", IEEE Trans. Fuzzy Systems, vol. 4, pp. 393-396, 1996.

[4] Pal, N.R., Pal, K., Keller, J.M., Bezdek, J. C., "A possibilistic fuzzy c-means clustering algorithm." IEEE Trans. Fuzzy Systems vol. 13, pp. 517- 530. 2005

[6] Y. Hong, S. Kwong, Y. Chang, and Q. Ren, "Unsupervised data pruning for clustering of noisy data", Knowledge-Based Systems, vol. 21, pp. 612-616, 2008.