基于混合距離學習的魯棒的模糊C均值聚類算法

卞則康，王士同

(江南大學 數字媒體學院，江蘇 無錫 214122)

基于混合距離學習的魯棒的模糊C均值聚類算法

卞則康，王士同

(江南大學 數字媒體學院，江蘇 無錫 214122)

距離度量對模糊聚類算法FCM的聚類結果有關鍵性的影響。實際應用中存在這樣一種場景，聚類的數據集中存在著一定量的帶標簽的成對約束集合的輔助信息。為了充分利用這些輔助信息，首先提出了一種基于混合距離學習方法，它能利用這樣的輔助信息來學習出數據集合的距離度量公式。然后，提出了一種基于混合距離學習的魯棒的模糊C均值聚類算法(HR-FCM算法)，它是一種半監督的聚類算法。算法HR-FCM既保留了GIFP-FCM(Generalized FCM algorithm with improved fuzzy partitions)算法的魯棒性等性能，也因為所采用更為合適的距離度量而具有更好的聚類性能。實驗結果證明了所提算法的有效性。

距離度量；FCM聚類算法；成對約束；輔助信息；混合距離；半監督；GIFP-FCM；魯棒性

聚類分析作為一種重要的數據處理技術已經被廣泛地應用到各種領域，如模式識別、數據挖掘等。在聚類分析中，需要根據數據點之間的相似或相異程度，對數據點進行區分和分類。因此對于不同的數據集，選擇合適的距離度量方式對算法的聚類性能有重要的影響[1]。歐式距離是較為常用的距離度量方式，但其具有以下不足：1)采用歐式距離的方法通常是假設所有變量都是不相關的，并且數據所有維度的方差都為1，所有變量的協方差為0[2]；2)歐式距離僅僅適用于特征空間中的超球結構，對于其他結構的數據集不太理想；3)歐式距離對噪聲比較敏感，聚類結果容易受到噪聲的干擾[3]。因此，歐式距離在實際應用中受到了限制。

針對這些問題，近年來提出了多種距離學習的方法，根據在距離學習過程中是否有先驗的訓練樣本，距離學習可以分為有監督距離學習[4-6]和無監督距離學習[7-8]。在有監督距離學習的方法中，需要借助數據集的輔助信息進行距離學習，其中輔助信息通常以約束對的形式來表示[9]。由數據集輔助信息學習得到的距離函數，可以有效地反映數據集的自身特點，對數據集具有很好的適用性。

在之前的研究中，人們提出了許多利用輔助信息進行距離學習的算法。比如，將距離學習轉化為凸優化問題的方法[4]、相關成分分析法[5]、區分成分分析法等[10]。然而這些方法大多數將目標函數假設在馬氏距離的框架下，本質上來說，針對馬氏距離學習得到的新距離是歐式距離的線性變換，仍然有歐式距離的缺點。在含有輔助信息的數據集中，歐式距離的聚類性能和魯棒性不理想。

因此，本文提出了一種基于混合距離學習的魯棒模糊C均值聚類算法(HR-FCM)。在此算法中，數據集的未知距離被表示成若干候選距離的線性組合，在候選的距離度量中加入了非線性的距離度量。與其他有監督的聚類算法[11-12]不同的是，HR-FCM利用數據集本身含有的少數的輔助信息進行混合距離的學習，相對于歐式距離沒有考慮到數據集本身的特征，利用數據集的輔助信息學習得到的混合距離融合了數據集的一些特征，提高了提高算法的聚類性能和魯棒性。

1 混合距離學習

1.1 混合距離

由于數據集結構特征不同，為了合理地計算不同數據集之間的距離，在距離學習中引入權重已經成為一種常用的方法。本文定義數據集中的混合距離度量的線性組合如下：

由文獻[13]可證式(1)中D(x,y)是一個距離函數。下面將介紹距離學習的過程。

在距離學習中，借鑒文獻[2]的思想，利用最大邊界的框架，優化目標函數：

使用拉格朗日乘子法優化式(2)，其拉格朗日函數為

式中：φi和λ為拉格朗日乘子。則式(3)的KKT條件為

顯然由式(4)無法求得ωi，因此先舍棄ωi非負的條件，則可重新構建新的拉格朗日函數，如式(5)所示：

可以求得

由式(6)可以看出，即使在成功的優化過程下ωi也可能出現負值，由前文看出，在考慮ωi為負的條件下，無法用拉格朗日函數求解。因此，在受到加權中心模糊聚類算法[14]的啟發，可以將ωi改寫為式(7)的形式：

式中：p+表示所有使ωi取正值的i的集合，p-表示無法使ωi取正值的i的集合，使用p+和p-來分別表示集合p+和p-的大小。

對于閾值β，使用梯度下降的方法進行求解，通過求偏導，得到β的梯度如下：

由于集合np+不斷改變，則等式進一步修改為如下形式：

式中：

具體的算法描述如下：

求解集合p+和p-的算法，算法1如下：

求解ω具體算法，算法2步驟如下：

輸出距離權值ω，閾值β。

步驟：

因為高中學生接觸實驗時間少，大多數時間都是啃書本.所以，在實驗時難免手忙腳亂，極易引起安全事故.比如，未按順序加熱試管、組裝儀器，在分液時，未能正確的倒出上下層液體，直接加熱燒杯，在加熱裝有液體的試管時管口指向同學.可見，教師應當做好督促工作，在實驗前認真講解注意點，確保實驗探究安全、成功的結束.此外，也要充分挖掘有限的實驗時間，提高實驗探究的效率.教師可提前設置問題，并讓學生預習書本，了解實驗步驟、注意點.在進入實驗時后，立即組織實驗.

2)計算距離矩陣：D(i,k)，

3)設置迭代步數：t=1，

4)循環，直至收斂：

①更新學習率：γ=1/t,t=t+1

②更新訓練子集：

③計算梯度：

④更新閾值：β′=β-γβJ;

⑤更新集合p+和p-，使用算法1;

至此，通過對訓練集的距離學習，得到的權值ωi，從而得到新的距離函數。通過數據集本身構成的輔助信息學習得到的混合距離，對數據集自身的適應性更高，更有利于聚類效果的改善。

1.2 時間復雜度分析

這個部分主要討論所提算法的時間復雜度，HR-FCM算法的時間復雜度主要討論的是混合距離學習的時間復雜度。總的來說，混合距離學習的最大時間復雜度為O(N2dp)，其中N表示訓練數據集中樣本的個數，d表示樣本的維度，p表示候選距離的個數。算法的主要時間消耗在求解距離矩陣D中，時間復雜度為O(Ndp)。在迭代循環中，每一步都有一個線性的時間復雜度，為O(max(N,np))。

2 基于混合距離學習的魯棒的FCM算法

模糊C均值聚類算法(FCM)，它是一種基于目標函數的聚類算法，是迄今為止應用最廣泛、理論最為完善的聚類算法。傳統的FCM聚類算法使用歐式距離作為距離度量函數導致其聚類性能和魯棒性較差。

針對傳統FCM算法的缺點，近年來研究者們提出了一些改進的FCM算法，例如：基于改進的模糊劃分的模糊C均值聚類算法(IFP-FCM)[15]和基于改進的模糊劃分的泛化的模糊C均值聚類算法(GIFP-FCM)[16]。IFP-FCM算法是由H?ppner和Klawonn提出的一種改進的FCM聚類算法。IFP-FCM算法通過對每個數據增加一個隸屬約束函數，以降低算法對噪聲的敏感性，增加了算法的魯棒性。但是此算法仍然沿用的是傳統的歐式距離作為距離度量，受到IFP-FCM算法的啟發，朱林等提出了GIFP-FCM算法。

在此啟發下，本文提出了一種基于混合距離學習的魯棒的FCM聚類算法，算法描述如下：

使用拉格朗日乘數法對式(12)進行優化，得到新的聚類中心和隸屬函數如式(13)和式(14)：

式(15)是表示樣本與類中心的距離度量公式，當p=2時，式(15)就是傳統的歐氏距離。

本文提出的HR-FCM算法，加入了距離學習的過程，通過距離學習出來的距離度量比傳統的歐式距離更佳適合具有輔助信息的數據集，增加了算法的聚類性能和魯棒性。因此，用新的混合距離D替換式(13)和式(14)中的距離度量dp，得到新的聚類中心公式(16)和隸屬度計算公式(17)；

式中距離度量D的定義如式(18)：

式中：ωi是通過距離學習得到的權值。

算法3 HR-FCM算法

輸入數據矩陣X∈Rd×N，權值向量ω，聚類數目c，閾值ε，模糊指數m，抗噪參數α，最大迭代次數T;

輸出最終的隸屬矩陣U。

步驟：

4)如果‖Ut+1-Ut‖<ε或者t>T,輸出最終的隸屬矩陣，否則t=t+1返回2)。

HR-FCM算法通過使用距離學習得到的新的混合距離代替傳統FCM算法中的歐式距離，進一步增加了算法的抗噪性能。再者，通過數據集本身的輔助信息進行距離的學習的得到的混合距離，比原有的歐式距離更加適合數據集，提高了算法的適用性。HR-FCM算法與傳統的FCM算法相比，具有更佳的聚類性能和魯棒性。

3 實驗研究和分析

本章通過實驗檢測本文提出的HR-FCM算法的聚類性能和魯棒性能。本章的實驗主要分為兩個部分：1)將本文提出的HR-FCM算法與現有的基于歐氏距離的聚類算法作比較，如：FCM、K-means和K-medoids,檢測算法的聚類性能；2)主要是檢測算法的魯棒性能，通過對實驗數據加入不同程度的隨機噪聲，并與FCM算法和GIFP-FCM算法作比較。

3.1 實驗設置和實驗數據

本文的實驗參數設置如下：閾值ε=10-5，最大迭代次數T=300，模糊指數T=300，m∈{1.5,2,3,4},α∈{0.5,0.7,0.9,0.99}。為了實驗結果的公平，重復每次聚類過程20，實驗結果取均值。

實驗中對于候選距離的選取，選擇了基于歐式距離的含有方差的距離分量d1(x,y)，非線性的距離分量d3(x,y),曼哈頓距離分量d2(x,y)。由這3種距離分量線性組合后的混合距離D(x,y)是一個非線性的距離函數。本文預設的3個距離度量如式(19)所示：

本文選取的實驗數據集均來自UCI數據集，數據集細節如表1。由于UCI數據集中沒有約束對形式的輔助信息，需要選取數據集中的一部分帶標簽的數據集構成約束對作為訓練集。其中，擁有相同的類標的樣本點構成正約束對，不同的類標的構成負約束對，選取相同數目的正負約束對進行距離學習。對于本文中的數據集，前6個取10%的數據集構成訓練集，最后兩個取1%的數據集。

在抗噪聲實驗中，在數據集中隨機加入10%和20%的高斯白噪聲(SNR=40 db或者30 db)，分別計算本文提出的HR-FCM算法、傳統FCM聚類算法和GIFP-FCM算法的聚類性能。

表1 數據集信息

3.2 評價方法

為了評估算法的聚類效果，本文采用了一些標準的評價方法，包括歸一化互信息(NMI)[17]和芮氏指數(RI)[18-19],這些將用來評價HR-FCM算法與FCM的聚類效果。

式中：X定義了已知標簽的原始數據，Y定義了對未知標簽的原始數據的聚類結果，I(X,Y)定義了X和Y之間的互信息，H(X)和H(Y)分別代表了X和Y的熵，a定義了X和Y中任意兩個具有相同類標簽并且屬于同一個樣本的數目，b定義了X和Y中任意兩個具有不同標簽并且屬于不同類的樣本的個數，n表示原始樣本的個數。顯而易見，NMI和RI的值都是介于0～1的，NMI和RI的值越大，表示X和Y之間的相似度就越高，即算法的效果越好。

3.3 實驗結果和分析

在第1部分的實驗中，為了檢測算法的聚類性能，設置HR-FCM算法中的抗噪參數α=0，比較使用了混合距離的HR-FCM算法與使用歐氏距離的FCM算法和其他常用的基于歐氏距離的聚類算法，檢測混合距離對聚類性能的影響。選取上述7個數據集作為本次實驗的實驗數據集，每組數據集運行20次，實驗結果選取RI和NMI值的均值，實驗結果如圖1和圖2所示。

第1部分的實驗結果表明：對于小數據集，HR-FCM算法的聚類性能不僅比傳統的基于歐氏距離的FCM聚類算法要好，也比基于歐氏距離的K-mean和K-medoids的聚類算法性能好。對于大樣本數據集，由于樣本數對于FCM聚類算法的影響比K-means 和K-medoids的大，此時，距離度量對于聚類性能的影響力下降，因此，K-means 和K-medoids算法的聚類性能較佳，但是與傳統的FCM聚類算法相比，本文提出的基于混合聚類的HR-FCM算法具有較好的聚類性能，如waveform數據集。

從表2的實驗中還可以得到，對于高維的數據集，4種算法聚類性能都有一定的下降。由于數據維度的增加，單個樣本的信息增加，在這些信息中存在著不同類型的信息，本文提出的混合距離度量函數相比傳統的歐氏距離能夠充分地度量出樣本之間的距離，學習出樣本之間的有效信息，提高算法的聚類性能。對于數據集wdbc和sonar,表2的實驗結果顯示了混合距離的有效性。

表2 聚類算法性能

為了檢測算法在多類樣本數據集中的聚類性能，實驗中也使用了多類樣本數據集vowel。由于多類樣本中，隨著類別的增加，對于樣本之間的距離度量的難度增加，因此算法的聚類性能受到一定的影響，如圖1和圖2中，對于少類別數據集wine,各個算法的RI和NMI值較高，對于多類別數據集vowel，各個算法的指標出現較大幅度的下降。圖1和圖2的實驗結果也表明，對于多樣本數據集，本文提出的HR-FCM算法的聚類性能與其他3種算法的聚類性能都出現了一定的下降，但是本文提出的算法較之其他3種算法的穩定性較高。

(a) vowel

(b) wine 圖1 各數據集的RI值Fig.1 The RI on the different data sets

(a) vowel

(b) wine 圖2 各數據集的NMI值Fig.2 The NMI on the different data sets

在第2部分的實驗中，為了檢測本文算法的魯棒性能，設置了在兩個多類別樣本數據集上的對比實驗，這兩個數據集分別是小樣本量的低維數據集vowel和大樣本量的高維數據集led。本次實驗主要是為了檢測HR-FCM算法與傳統的FCM算法和GIFP-FCM算法在聚類性能和魯棒性能上面的差別，因此本次實驗，比較了3種算法在不同模糊指數的情況下的聚類性能，通過改變噪聲的添加比例，比較算法的魯棒性能。為了進一步檢測HR-FCM算法受抗噪參數的影響，本次實驗設置不同的參數取值，通過比較聚類指標的變化顯示算法的魯棒性的變化。

從表3和表4的結果中容易看出在相同的模糊指數的情況下，HR-FCM算法的聚類性能和魯棒性大多強于傳統的FCM算法。在模糊指數一定的情況下，隨著抗噪參數α的增加，HR-FCM算法的魯棒性越來越強。在加入噪聲后，算法的聚類性能收到了一定的影響，算法的聚類性能下降，FCM聚類算法的聚類性能下降較多。從表4的實驗結果中容易看出，在實驗數據集為大數據集的情況下，本文提出的HR-FCM算法的聚類性能和魯棒性強于傳統的FCM算法。由表3和表4的結果也可以看出本文提出的HR-FCM算法的聚類結果要優于GIFP-FCM算法。由于本文使用混合距離代替傳統的歐氏距離，因此本文的HR-FCM算法的魯棒性能強于GIFP-FCM算法。

綜上所述，對于含有輔助信息的數據集，本文提出的HR-FCM算法由于采用混合距離，使得算法具有較好的適應性，比傳統的使用歐氏距離作為距離度量的FCM算法和GIFP-FCM算法具有更好的聚類性能和魯棒性。

表3 噪聲實驗結果

表4 噪聲實驗結果

4 結束語

在聚類的實際應用中，大多數數據集都含有一定量的輔助信息，這些輔助信息中含有重要的數據特征，但是這些輔助信息在聚類過程中常常被忽略。本文提出了一種利用數據集的輔助信息進行距離學習的方法，進而提出了一種改進的FCM算法HR-FCM。用數據集的輔助信息進行距離學習得到的混合函數，不僅能夠反映出數據集本身的特征，而且比歐式距離更加契合數據集，更加適合于實際應用。在含有輔助信息的數據集中，本文提出的HR-FCM算法具有較好的聚類性能和魯棒性。實驗結果證明了結論。

[1]王駿, 王士同. 基于混合距離學習的雙指數模糊C均值算法[J]. 軟件學報, 2010, 21(8): 1878-1888.

WANG Jun, WANG Shitong. Double indices FCM algorithm based on hybrid distance metric learning[J]. Journal of software, 2010, 21(8): 1878-1888.

[2]WU L, HOI S C H, JIN R, et al. Learning bregman distance functions for semi-supervised clustering[J]. IEEE transactions on knowledge and data engineering, 2012, 24(3): 478-491.

[3]WU K L, YANG M S. Alternative c-means clustering algorithms[J]. Pattern recognition, 2002, 35(10): 2267-2278.

[4]XING E P, NG A Y, JORDAN M I, et al. Distance metric learning, with application to clustering with side-information[J]. Advances in neural information processing systems, 2003, 15: 505-512.

[5]BAR-Hillel A, HERTZ T, SHENTAL N, et al. Learning a mahalanobis metric from equivalence constraints[J]. Journal of machine learning research, 2005, 6(6): 937-965.

[6]郭瑛潔, 王士同, 許小龍. 基于最大間隔理論的組合距離學習算法[J]. 智能系統學報, 2015, 10(6):843-850.

[7]YE J, ZHAO Z, LIU H. Adaptive distance metric learning for clustering[C]//IEEE Conference on Computer Vision and Pattern Recognition. Minneapolis, USA, 2007: 1-7.

[8]WANG X, WANG Y, WANG L. Improving fuzzy c-means clustering based on feature-weight learning[J]. Pattern recognition letters, 2004, 25(10): 1123-1132.

[9]HE P, XU X, HU K, et al. Semi-supervised clustering via multi-level random walk[J]. Pattern recognition, 2014, 47(2): 820-832.

[10]HOI S C H, LIU W, LYU M R, et al. Learning distance metrics with contextual constraints for image retrieval[C]// IEEE Conference on Computer Vision and Pattern Recognition. New York, USA, 2006: 2072-2078.

[11]曾令偉,伍振興,杜文才.基于改進自監督學習群體智能(ISLCI)的高性能聚類算法[J].重慶郵電大學學報: 自然科學版, 2016, 28(1): 131-137.

ZENG Lingwei, WU Zhenxing, DU Wencai. Improved self supervised learning collection intelligence based high performance data clustering approach[J].Journal of Chongqing university of posts and telecommunications: natural science edition,2016, 28(1): 131-137.

[12]程旸，王士同. 基于局部保留投影的多可選聚類發掘算法[J].智能系統學報， 2016, 11(5): 600-607.

CHENG Yang, WANG Shitong. A multiple alternative clusterings mining algorithm using locality preserving projections[J]. CAAI transactions on intelligent systems,2016, 11(5): 600-607.

[13]DUDA R O, HART P E, STORK D G. Pattern classification[M]// Pattern classification. Wiley, 2001:119-131.

[14]MEI J P, CHEN L. Fuzzy clustering with weighted medoids for relational data[J]. Pattern recognition, 2010, 43(5): 1964-1974.

[15]HOPPNER F, KLAWONN F. Improved fuzzy partitions for fuzzy regression models[J]. International journal of approximate reasoning, 2003, 32(2/3): 85-102.

[16]ZHU L, CHUNG F L, WANG S. Generalized fuzzy C-means clustering algorithm with improved fuzzy partitions[J]. IEEE transactions on systems man and cybernetics part B, 2009, 39(3): 578-591.

[17]STREHL A, GHOSH J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. Journal of machine learning research, 2002, 3(3): 583-617.

[18]IWAYAMA M, TOKUNAGA T. Hierarchical Bayesian clustering for automatic text classification[J]. IJCAI, 1996: 1322-1327.

[19]RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the american statistical association, 1971, 66(336): 846-850.

RobustFCMclusteringalgorithmbasedonhybrid-distancelearning

BIAN Zekang， WANG Shitong

(School of Digital Media, Jiangnan University, Wuxi 214122, China)

The distance metric plays a vital role in the fuzzy C-means clustering algorithm. In actual applications, there is a practical scenario in which the clustered data have a certain amount of side information, such as pairwise constraints with labels. To sufficiently utilize this side information, first, we propose a learning method based on hybrid distance, in which side information can be utilized to attain a distance metric formula for the data set. Next, we propose a robust fuzzy C-means clustering algorithm (HR-FCM algorithm) based on hybrid-distance learning, which is semi-supervised. The HR-FCM inherits the robustness of the GIFP-FCM (generalized FCM algorithm with improved fuzzy partitions) and has better clustering performance due to the more appropriate distance metric. The experimental results confirm the effectiveness of the proposed algorithm.

distance metric; FCM clustering algorithm; pairwise constraints;side information; hybrid distance; semi-supervised; GIFP-FCM; robustness

2016-07-23.網絡出版日期2017-04-07.

國家自然科學基金項目(61272210).

卞則康. E-mail：bianzekang@163.com.

10.11992/tis.201607019

http://kns.cnki.net/kcms/detail/23.1538.tp.20170407.1734.004.html

TP181

A

1673-4785(2017)04-0450-09

中文引用格式：卞則康，王士同.基于混合距離學習的魯棒的模糊C均值聚類算法J.智能系統學報， 2017, 12(4): 450-458.

英文引用格式：BIANZekang，WANGShitong.RobustFCMclusteringalgorithmbasedonhybrid-distancelearningJ.CAAItransactionsonintelligentsystems, 2017, 12(4): 450-458.

卞則康,男,1993年生,碩士研究生,主要研究方向為人工智能和模式識別。

王士同，男，1964年生，教授，博士生導師，主要研究方向為人工智能與模式識別。發表學術論文近百篇，其中被SCI、EI檢索50余篇。