李凱，王亮，周宇飛

（河北大學數(shù)學與計算機學院，河北保定 071002）

基于偶對約束和馬氏距離的半監(jiān)督模糊聚類算法

李凱，王亮，周宇飛

（河北大學數(shù)學與計算機學院，河北保定 071002）

研究了基于偶對約束的半監(jiān)督模糊聚類，將馬氏距離引入到半監(jiān)督模糊聚類SCAPC（semi-supervised fuzzy clustering algorithm with pairwise constraints）中，獲得了一種新的半監(jiān)督模糊聚類目標函數(shù)，通過求解優(yōu)化問題，提出了一種基于偶對約束和馬氏距離的半監(jiān)督模糊聚類算法M-SCAPC（Modified-SCAPC）.針對選擇的標準數(shù)據(jù)集和人工數(shù)據(jù)集，對提出的算法M-SCAPC進行了實驗研究，并與FCM（fuzzy C-means）、AFCC（active fuzzy constrained clustering）和SCAPC算法的聚類性能進行了比較，表明了提出的算法M-SCAPC在收斂速度和正確率方面的有效性.

半監(jiān)督聚類；偶對約束；度量學習；馬氏距離

1 引入馬氏距離的半監(jiān)督聚類算法M-SCAPC

給定一個具有N個樣本的數(shù)據(jù)集X＝｛xi｜i∈｛1，…，N｝｝，假設集合X中的樣本點被分為c個簇S1，S2，…，Sc，并記vk（k∈｛1，…，c｝）表示c個聚類中心，uik表示樣本點xi屬于簇Sk的隸屬度，V和U分別表示由聚類中心構(gòu)成的集合與由隸屬度構(gòu)成的矩陣.

歐氏距離較適用于球形數(shù)據(jù)，然而該度量受樣本間的相關性影響較大，在處理非球形數(shù)據(jù)或高維數(shù)據(jù)時聚類效果較差，同時聚類速度也較慢，而馬氏距離在處理相關性較大的數(shù)據(jù)集時具有較好的效果［6］.針對這種情況，研究了使用馬氏距離的半監(jiān)督聚類，獲得了如下的目標函數(shù)：

下面給出算法M-SCAPC的描述：

1）初始化最大簇數(shù)Cmax，設置簇的閾值e和ε，并初始化簇中心和隸屬度；

2）計算協(xié)方差矩陣Ck和馬氏距離；

3）利用式（3）和（4）分別計算參數(shù)β和參數(shù)α；

4）計算各簇的勢，如果簇的勢小于閾值e，則刪除該簇，并減少相應簇的數(shù)目；

5）根據(jù)式（2）計算新的隸屬度矩陣，使用（5）更新簇中心；

2 實驗結(jié)果和分析

為了驗證算法M-SCAPC的有效性，選擇了UCI中的數(shù)據(jù)集Iris，Diabetes和Wine；同時也人工生成了數(shù)據(jù)集Data，該數(shù)據(jù)集是一個具有3維且包括150個樣本點，其簇數(shù)為3，每個簇包括50個樣本點.實驗中選取e＝7，ε＝0.001，從所有樣本點中選取10對約束樣本點，從而獲得約束點對集M和C集合.

2.1 參數(shù)α和β與迭代次數(shù)的關系

由目標函數(shù)可知，參數(shù)α和β是M-SCAPC算法中決定約束懲罰項的重要程度的參數(shù)，為此通過Iris數(shù)據(jù)集對提出算法進行了實驗研究，隨著迭代次數(shù)的增加，α值先增加后減少，直至α值趨于穩(wěn)定.另外，隨著迭代次數(shù)的增加，β值逐漸減小，并且在迭代的初期，β值比較大，說明聚類還不穩(wěn)定，對勢的影響比較大，隨著迭代的進行，聚類數(shù)和β值都逐漸穩(wěn)定下來.另外，β值也受η0的取值影響，η0的取值將影響最終的聚類數(shù)目和迭代次數(shù)，結(jié)果如表1所示.

表1 η0值對分類數(shù)目和迭代次數(shù)的影響Tab.1 Influence ofη0on the number of clusters and the number of iterations

從表1中可以看出，η0的取值會影響到算法最終的聚類數(shù)目和收斂速度.Iris正確的簇數(shù)為3，但是當給定初始化最大簇數(shù)Cmax＝18和η0取值在［1，2］時，Iris數(shù)據(jù)集的簇數(shù)分別為16，14，13，說明沒有得到正確的簇數(shù)，此時目標函數(shù)迭代21次.當η0取值在［4，5］時，最終聚類數(shù)為3，得到了正確的聚類結(jié)果，并且此時平均迭代次數(shù)為18左右.當η0取值在［7，9］時，算法得到的簇數(shù)是1或2，小于正確的簇數(shù)3，說明此時平衡因子的值太大使競爭超過了正常的范圍，此時的迭代次數(shù)為16次.這表明當η0的值越大，算法的迭代次數(shù)越小，實驗結(jié)果表明，當η0在［4，5］取值時會有比較好的聚類結(jié)果.

2.2 聚類收斂速度的比較

針對Iris，Diabetes，Wine和Data數(shù)據(jù)集對算法的聚類收斂速度進行了實驗研究.在對這些數(shù)據(jù)集聚類時，Cmax分別初始化為18，13，18和18，ε＝0.001，η0＝4.圖1至圖4分別給出了SCAPC和M-SCAPC算法關于聚類收斂速度的實驗結(jié)果.由圖1可知，SCAPC算法經(jīng)過24次迭代才使目標函數(shù)值穩(wěn)定下來，而MSCAPC算法僅用17次迭代就穩(wěn)定下來，且對于M-SCAPC算法，在第7次迭代時獲得了正確簇數(shù)，而SCAPC算法在第8次得到正確的簇數(shù).同樣，由圖2至圖4的實驗結(jié)果可以獲得同樣的結(jié)論.這就表明，MSCAPC算法的收斂速度要優(yōu)于SCAPC算法.

2.3 點對約束與聚類性能的關系

由目標函數(shù)JM－SCAPC及算法可知，當給定樣本點的標簽信息和實際劃分出來的類屬信息不一致時，則目標函數(shù)中的懲罰項會變大，此時懲罰項會不斷的被調(diào)整，從而在迭代過程中一些錯誤的樣本點會被分到正確的類之中.為了驗證這個結(jié)論，對給定的4個數(shù)據(jù)集，實驗研究了點對約束數(shù)目和聚類結(jié)果的關系.針對Iris， Diabetes，Wine和Data數(shù)據(jù)集，實驗中η0分別被置為4，5，5.5和6，Cmax＝18，ε＝0.001，實驗結(jié)果如圖5所示.

圖1 SCAPC算法和M-SCAPC算法在Iris數(shù)據(jù)集上的聚類收斂速度Fig.1 Comparison with convergence speed between SCAPC and M-SCAPC on the Iris data set

圖2 SCAPC算法和M-SCAPC算法在Diabetes數(shù)據(jù)集上的聚類收斂速度Fig.2 Comparison with convergence speed betweenSCAPC and M-SCAPC on the Diabetes data set

圖3 SCAPC算法和M-SCAPC算法在Wine數(shù)據(jù)集上的聚類收斂速度Fig.3 Comparison with convergence speed between SCAPC and M-SCAPC on the Wine dataset

圖4 SCAPC算法和M-SCAPC算法在Data數(shù)據(jù)集上的聚類收斂速度Fig.4 Comparison with convergence speed between SCAPC and M-SCAPC on the Data dataset

圖5 不同數(shù)目的點對約束下的聚類正確率Fig.5 Clustering accuracy with different number of constraints

由圖5可以看到，隨著點對約束（must-link和cannot-link）數(shù)量的增加，M-SCAPC算法的正確率逐漸增高，這表明了約束懲罰項對目標函數(shù)有顯著的調(diào)整作用.當點對約束數(shù)目較少時，聚類結(jié)果的正確率相對較低；當點對約束數(shù)量增加時，聚類結(jié)果的正確率有顯著的提升；當點對約束數(shù)量達到一定值時，聚類結(jié)果逐漸穩(wěn)定，此時，點對約束的數(shù)目對聚類結(jié)果的影響較小.

2.4 不同算法的聚類正確率比較

為了進一步驗證M-SCAPC算法的有效性，選取FCM，AFCC和SCAPC算法進行了實驗比較.實驗中選取10個點對約束，表2給出了不同算法的實驗結(jié)果.可以看出改進的M-SCAPC算法在Iris，Diabetes，Wine和Data數(shù)據(jù)集上明顯提高了聚類結(jié)果的正確率，尤其是對于一些高維數(shù)據(jù)集如Diabetes和Wine獲得了較好的聚類結(jié)果.

表2 不同算法的聚類結(jié)果Tab.2 Clustering results using different algorithms

3 結(jié)論

本文通過應用馬氏度量且修改半監(jiān)督模糊聚類算法的目標函數(shù)，得到一個改進的半監(jiān)督模糊聚類算法M-SCAPC，并且針對不同的數(shù)據(jù)集Iris、Diabetes、Wine和Data進行了實驗研究.實驗結(jié)果表明改進的算法M-SCAPC顯著地提高了聚類結(jié)果的正確率和收斂速度.另外，與聚類算法FCM，AFCC和SCAPC進行了實驗比較，表明了M-SCAPC算法的有效性.

［1］ XIANG Shiming，NIE Feiping，ZHANG Changshui.Learning a Mahalanobis distance metric for data clustering a classification［J］.Pattern Recognition，2008，41（12）：3600-3612.

［2］ BAR-HILLEL A，HERTZ T，SHENTAL N，et al.Learning a Mahalanobis metric from equivalence constraints［J］.Journal of Machine Learning Research，2005，6：937 -965.

［3］ YIN Xuesong，SHU Ting，QI Huang.Semi-supervised fuzzy clustering with metric learning and entropy regularization［J］.Knowledge-Based Systems，2012，35：304-311.

［4］ YEUNG D Y，CHANG H.Extending the relevant component analysis algorithm for metric learning using both positive and negative equivalence constraints［J］.Pattern Recognition，2006，39（5）：1007-1010.

［5］ FRIGUI H，KRISHNAPURAM R.Clustering by competitive agglomeration［J］.Pattern Recognition，1997，30（7）：1109-1119.

［6］ GRIRA N，CRUCIANU M，BOUJEMAA N.Semi-supervised fuzzy clustering with pairwise constrained competitive agglomeration［Z］.IEEE International Conference on Fuzzy Systems，Reno，Nevada，USA，2005.

［7］ GRIRA N，CRUCIANU M，BOUJEMAA N.Active semi-supervised fuzzy clustering［J］.Pattern Recognition，2008，41（5）：1834 -1844.

［8］ GAO Cuifang，WU Xiaojun.A new semi-supervised clustering algorithm with pairwise constraints by competitive agglomeration［J］.Applied Soft Computing，2011，11（8）：5281-5291.

（責任編輯：孟素蘭）

A semi-supervised fuzzy clustering algorithm based on pairwise constraints and Mahalanobis distance

LI Kai，WANG Liang，ZHOU Yufei
（College of Mathematics and Computer Science，Hebei University，Baoding 071002，China）

The semi-supervised fuzzy clustering based on pair-wise constraints which introduces Mahalanobis distance into SCAPC（Semi-supervised fuzzy Clustering Algorithm with Pairwise Constraints）algorithm is mainly studied.And a new semi-supervised fuzzy clustering objective function is obtained.By solving the optimization problem，a semi-supervised fuzzy clustering algorithm M-SCAPC（Modified SCAPC）based on pairwise constraints and Mahalanobis distance is proposed.And some experimental researches are conducted for M-SCAPC algorithm using the selected standard data set and the artificial data set.Besides，clustering performance on M-SCAPC algorithm are compared with that of FCM（Fuzzy C-Means），AFCC（Active Fuzzy Constrained Clustering）and SCAPC algorithms.From the results，M-SCAPC is effective in the convergence speed and the accuracy.

semi-supervised clustering；pairwise constraints；metric learning；mahalanobis distance

半監(jiān)督聚類是半監(jiān)督學習的一個重要研究方向，它將監(jiān)督聚類和無監(jiān)督聚類的優(yōu)勢結(jié)合起來，利用少量具有監(jiān)督信息的樣本和大量無標簽樣本進行聚類.一般來說，監(jiān)督信息主要有2種形式：一種是偶對約束，例如must-link和cannot-link；另一種是直接給出樣本點的分類標記信息.目前，針對這2種監(jiān)督信息，研究人員提出了許多不同的半監(jiān)督聚類算法，這些方法大體可以歸結(jié)為2種類型：1）將監(jiān)督信息引入到現(xiàn)有的聚類算法中，以此獲得半監(jiān)督聚類算法；2）利用監(jiān)督信息對度量進行學習［13］.例如，Bar-Hillel等［2］利用mustlink約束通過學習馬氏度量提出了一種非迭代方法RCA（relevant component analysis），之后，Yeung等［4］針對RCA方法進行了擴展研究，在該方法中同時考慮了must-link約束和cannot-link約束.對于大多數(shù)聚類算法，不論是無監(jiān)督聚類和半監(jiān)督聚類，在聚類時通常都需要事先指定要聚類的簇數(shù)，然而在實際問題中，這個值是很難被確定的.關于這個問題，F(xiàn)rigui等［5］提出了CA（competitive agglomeration）算法，主要通過競爭方法自動計算合適的聚類數(shù)目，遺憾的是該算法的聚類效果較差.為了提高聚類的性能，Grira等［67］將半監(jiān)督聚類方法與CA算法進行有效的結(jié)合，提出了AFCC（active fuzzy constrained clustering）算法.鑒于AFCC算法中的偶對約束懲罰項和CA算法的目標函數(shù)在數(shù)量級上不一致，在聚類過程中可能引起樣本點的隸屬度調(diào)整過度問題.在2011年，Gao等［8］進一步改進了AFCC算法的目標函數(shù)，并在此基礎上提出了SCAPC（semi-supervised fuzzy clustering algorithm with pairwise constraints）算法.可以看到，不論AFCC算法還是SCAPC算法，在優(yōu)化問題中的目標函數(shù)都是基于歐氏距離，而歐氏距離僅對球形數(shù)據(jù)有比較好的聚類效果，對于那些非球形或者橢圓形的樣本點數(shù)據(jù)，使用這些算法并不能得到較好的聚類結(jié)果.針對這種情況，本文將馬氏距離引入到算法SCAPC的目標函數(shù)中，提出了一種基于馬氏距離的半監(jiān)督模糊聚類算法M-SCAPC（Modified SCAPC）.

TP391

A

1000-1565（2014）05-0535-06

10.3969／j.issn.1000 -1565.2014.05.016

2014-01 -09

國家自然科學基金資助項目（61375075）；河北省自然科學基金資助項目（F2012201014）

李凱（1963-），男，河北滿城人，河北大學教授，博士，主要從事機器學習、數(shù)據(jù)挖掘等方向研究.E-mail：likai＠hbu.edu.cn