Fuzzy Partition Clustering Algorithms Based on Alternative Mahalanobis Distances

基於選擇性馬氏距離之模糊分割聚類演算法

10.6773/JRMS.200812.0002

劉湘川(Hsiang-Chuan Liu)

G-K演算法 ； Liu演算法 ； FCM-AM ； PCM-AM ； FPCM-AM ； G-K algorithm ； Liu-algorithm ； FCM-AM ； PCM-AM ； FPCM-AM

測驗統計年刊

16期_上（2008 / 12 / 01）

13 - 31

英文

眾所周知之模糊分割聚類演算法大都為基於歐式距離之方法，只能辨識同為超球形之數據類，Gustafson & Kessel (1979)推廣歐式距離至馬氏距離，提出G-K演算法是基於馬氏距離之模糊分割聚類演算法，兼可搜索超橢球形數據類等，但是各聚類之超體積須有先驗訊息，否則只能考慮各聚類之超體積為相同之情況，且當任一聚類之維度大於該聚類樣本點數時，該聚類之估計模糊共變數矩陣可能為非滿秩，其逆矩陣會產生奇異值問題，也是G-K演算法所未考慮之議題，本文針對上述兩種缺失，在目標函數中引進各聚類共變數矩陣之調整因子及一選擇性全域分散矩陣，刪除G-K演算法之共變數矩陣行列式之限制條件，並採用特徵向量減維法，而得改善之推廣新演算法，簡稱「Liu演算法」，進而應用「Liu演算法」，將基於歐式距離之三種常用模糊分割聚類演算法；「模糊C平均法(FCM)」，「可能性C平均法(PCM)」，及「模糊可能性C平均法(FPCM)」，分別推廣至基於不同選擇性馬式距離之三種模糊分割聚類演算法，對應簡記為「選擇性馬氏模糊C平均法(FCM-AM)」，「選擇性馬氏可能性C平均法(PCM-AM)」，「選擇性馬氏模糊可能性C平均法(FPCM-AM)」。

The well-known fuzzy partition clustering algorithms are mainly based on Euclidean distance measure for partitioning, which can only be used for the clusters in the data set with the same super-spherical shape distribution. Instead of using Euclidean distance measure, Gustafson & Kessel (1979) proposed the G-K algorithm which employs the Mahalanobis distance. It is a fuzzy partition clustering algorithm which can be used for the clusters in the data set with different geometrical shapes. However, without the prior information of the shape volume for each class, the G-K algorithm can only be utilized for the clusters with the same volume in the data set. In other words, if any dimension of a class is greater than the number of samples in the class, the estimated covariance matrix of that class may not be fully ranked. Hence, the algorithm will induce the singular problem for the inverse covariance matrix. This is an important issue need be addressed when we use the G-K algorithm for clustering. To overcome the issues, a new solution is proposed. A regulating factor of the covariance matrix for each class and the alternative global scatter matrix are added in the objective function, besides, the constraint of the determinant of the covariance matrices used in the G-K algorithm is removed. This new proposed algorithm is called Liualgorithm. Based on the proposed Liu-algorithm, three well known fuzzy partition clustering algorithms using Euclidean distance measure; the Fuzzy C-Means (FCM), the Possibility C-Means (PCM), and the Fuzzy Possibility C-Means (FPCM), are extended by using the local and global Mahalanobis distance. They will be called the Fuzzy C-Means based on Alternative Mahalanobis distances (FCM-AM), the Possibility C-Means based on Alternative Mahalanobis distances (PCM-AM), the Fuzzy Possibility C-Means based on Alternative Mahalanobis distances (FPCM-AM), respectively.

1. Bezdek, J. C.(1981).Pattern Recognition with Fuzzy Objective Function Algorithms.NY:Plenum Press.
2. Dunn, J. C.(1973).A fuzzy relative of the isodata process and its use in detecting compact, well-separated clusters.J. Cybern,3(3),32-57.
3. Gustafson, D. E.,Kessel, W. C.(1979).Fuzzy clustering with a fuzzy covariance matrix.Proc. IEEE Conf. Decision Contr.,San Diego, CA:
4. Liu, H. C.,Yih J. M.,Wu, B. B.,Liu S. W.(2008).Fuzzy c-mean algorithm based on complete Mahalanobis distances.2008 International Conferences on Machine Learning and Cybernetics,Kuming, China:
5. Liu, H. C.,Yih, J. M.,Liu, S. W.(2007).Fuzzy c-mean algorithm based on Mahalanobis distances and better initial values.INFORMATION SCIENCES 2007, Proceedings of the 10th joint conferences, Salt Lake City, Utah, USA
6. Liu, H. C.,Yih, J. M.,Sheu, T. W.,Liu, S. W.(2007).A new fuzzy possibility cmean algorithm based on unsuppervise Mahalanobis distances.Proceedings of International conference on Machine Learning and Cybernetics 2007
7. Pal, N. R.,Pal, K.,Bezdek, J. C.(1993).A possibilistic approach to clustering.IEEE Transactions on Fuzzy Systems,1(2),98-110.
8. Pal, N. R.,Pal, K.,Bezdek, J. C.(1997).A mixed c-mean clustering model.Proceedings of the Sixth IEEE International conference on Fuzzy System