穩健式聚類演算法

A Robust Possibilistic Clustering Algorithm

賴建佑(Chien-Yo Lai)

指導教授 ： 楊敏生

中原大學/理學院/應用數學研究所/博士(2010年)

https://doi.org/10.6840/cycu201000388

摘要

Krishnapuram and Keller 於1993年提出可能性c-均值(Possibilistic c-means, PCM)演算法，藉由鬆綁模糊c-均值(Fuzzy c-means, FCM)演算法中資料點隸屬各類的隸屬度總和為1的限制，使離群值的影響力變小，群心的估計值更為穩健，因此，若配合適當的起始值和參數值，PCM會是一個尋找眾數的好方法，然而適當的起始值之選取以及必須給定群數仍舊是PCM演算法的兩大難題。在本篇論文中，我們利用PCM演算法中，若給定過多群心會發生群心重疊的現象，我們提出了一個穩健式聚類演算法，利用群心重疊的性質，且為避免起始群心之選取問題，使用所有資料點當起始群心，採合併相近群之方式，根據資料自身結構得到不錯的分類結果，我們提出了一套穩健式聚類演算法稱之為自動合併可能性聚類法(Automatic merging　possibilistic clustering method, AM-PCM)。

關鍵字

可能性分類 ； 模糊c均值 ； 穩健性 ； 可能性c隸屬度 ； 模糊c分割 ； 自動合併

並列摘要

Krishnapuram and Keller (1993) first proposed a possibilistic approach to clustering, called possibilistic c-means (PCM), by relaxing the constraint in fuzzy c-means (FCM) that the memberships of a data point across classes sum to 1. The PCM algorithm has a tendency to produce coincident clusters. This can be a merit of PCM as a good mode-seeking algorithm if initials and parameters are suitably chosen. However, the performance of PCM heavily depends on the selection of parameters and initializations. In this paper, for solving these parameters and initializations selection problems, we propose a new scheme of PCM, called an automatic merging possibilistic clustering method (AM-PCM). The proposed AM-PCM algorithm first uses all data points as initial prototypes and then automatically merges these surrounding points around each cluster mode such that it can self-organize data groups according to the original data structure.

並列關鍵字

Fuzzy c-means ； Automatic merging ； Fuzzy c-partitions ； Possibilistic clustering ； Robustness ； Possibilistic c-memberships

參考文獻

[2] M. Barni, V. Cappellini, and A. Mecocci, “Comments on ‘A Possibilistic Approach to Clustering,’” IEEE Trans. Fuzzy Systems, vol. 4, pp. 393-396, Aug. 1996.

[3] J.C. Bezdek, “Cluster validity with fuzzy sets,” J. Cybernet., vol. 3, pp. 58-73, 1974.

[4] J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, New York: Plenum Press, 1981.

[6] R.N. Dave, “Validating fuzzy partition obtained through c-shells clustering,” Pattern Recognition Letters, vol. 17, pp. 613-623, 1996.

[7] J.C. Dunn, “A fuzzy relative of the ISODATA process and its use in detecting compact, well-separated clusters,” J. Cybernetics, vol. 3, pp. 32-57, 1974.