結合弱監督信息的凸聚類研究

權禎臻 陳松燦

(南京航空航天大學計算機科學與技術學院 南京 211106) (zz.quan@nuaa.edu.cn)

結合弱監督信息的凸聚類研究

權禎臻 陳松燦

(南京航空航天大學計算機科學與技術學院 南京 211106) (zz.quan@nuaa.edu.cn)

基于目標函數的聚類是一類重要的聚類分析技術，其中幾乎所有算法均是經非凸目標的優化建立，因而難以保證全局最優并對初始值敏感.近年提出的凸聚類通過優化凸目標函數克服了上述不足，同時獲得了相對更穩定的解.當現實中存在輔助信息(典型的如必連和或不連約束)可資利用時，通過將其結合到相應目標所得優化模型已證明能有效提高聚類性能，然而，現有通過在目標函數中添加約束懲罰項的常用結合方式往往會破壞其原有凸目標的凸性.鑒于此，提出了一種新的結合此類弱監督輔助信息的凸聚類算法.其實現關鍵是代替在目標函數中添加約束，而是通過對目標函數中距離度量的改造以保持凸性，由此既保持了原凸聚類的優勢同時有效提高了聚類性能.

基于目標函數的聚類；凸聚類；弱監督信息；約束；距離度量；半監督聚類

聚類算法是多元數據分析的重要工具，是知識發現和數據挖掘的關鍵技術，已廣泛用于生物信息學[1]、圖像處理[2]、信息檢索[3]等領域.聚類是依據給定的相似性度量，將數據集樣本劃分成若干個通常不相交的子集或簇，使得簇內相似度和簇間相異度最大[4].目前已有眾多聚類算法被提出[5]，其中，基于目標函數的聚類是一類重要的聚類方法，其通過最小化或最大化一個全局目標函數實現對無標記數據的最優劃分[6]，常見此類算法有k均值算法、模糊k均值算法、最大期望聚類算法等.然而，幾乎所有基于目標函數的聚類算法都難以保證解及性能的穩定性，歸咎于通過非凸目標的優化建立，易陷入局部最優解且對初始值敏感.為克服上述不足，2011年，Lindsten等人[7]和Hocking等人[8]分別將k均值算法和層次聚類凸松弛化，通過促使簇中心的融合獲取全局最優解.鑒于凸聚類具有可求取全局最優解、對數據擾動相對不敏感及自動獲取簇數的優勢，近年已備受關注，相關研究集中在優化方面(如文獻[9])和數據結構信息的結合方面(如文獻[10-13]).

聚類本身是一種典型的無監督學習任務，然而當有一些額外的監督信息可資利用時，利用這些監督信息能獲得更優的聚類效果[14].常用的監督信息大致有2種：1)個體的樣本標記或類別；2)樣本必連(must-link)和不連(cannot-link)約束，前者是指2個樣本必須屬于同一簇，后者則指2個樣本必不屬于同一簇.由于這種成對約束給出的先驗信息弱于數據標記給出的先驗信息[15]，故又被稱為弱監督信息或輔助信息.本文主要關注第2種輔助型監督信息.將輔助信息結合到聚類目標所得優化模型已被證明能夠有效提高聚類性能，如文獻[15-20].現有的此類半監督聚類算法都基于非凸目標建模和優化，故按上述方式添加約束后目標函數的性質未改變，遺傳了非凸優化對初始值敏感、難以保證全局最優的缺點.

依據上述在基于非凸目標函數的聚類中添加輔助信息可提高性能的經驗，我們猜測凸聚類結合此類信息也可提高其性能.然而此方面研究尚未出現，故本文嘗試彌補這一缺漏.在凸聚類中添加約束看似容易，然而研究中發現將必連約束作為懲罰項添加到目標函數中仍能保持其凸性，但將不連約束作為懲罰項添加到目標函數則會破壞其凸性，從而失去凸聚類的優勢并退化為一個基于非凸目標函數的聚類任務.因此本文嘗試通過對凸聚類目標函數中距離度量的改造以保持凸性.對于容易處理的必連約束，借鑒Klein等人[15]的方法改造距離矩陣，再恢復樣本空間；對于較難處理的不連約束，受到Asafi等人[19]工作的啟發，將不連約束轉化為特征空間的增廣.由此處理輔助信息后，對改變了距離度量的數據集進行凸聚類.最后，在模擬數據集和UCI數據集上的實驗結果顯示本文所提模型能夠有效提高凸聚類的性能.

1 相關工作

首先回顧凸聚類及相關工作.Lindsten等人[7]和Hocking等人[8]將聚類任務改造為一個凸優化問題，對于由n個無標記樣本構成的數據集X={x1,x2,…,xn}(xi∈M)，優化嚴格凸的目標函數：

(1)

其中，第1項是損失函數，第2項是正則化項且一般取1,2范數，取1范數時式(1)與fused拉索[21]具有相似性.權重wij非負且wij=wji，ui是樣本xi的簇中心.對于任意參數γ，式(1)存在唯一的最小值，參數γ控制簇數：若γ=0，則ui=xi時式(1)取最小值，每個簇僅有一個樣本；隨著γ的增大，簇中心逐漸融合，ui=uj時將xi與xj歸為同一簇；若γ過大，則將所有樣本聚為一個簇.

對凸聚類的研究主要在2方面展開.1)優化方面.鑒于交替迭代乘子方法(alternating direction method of multipliers, ADMM)適用于解決統計學、機器學習等領域的分布式的凸優化問題[22]，Chi等人[9]提出用ADMM方法[22]加速式(1)的求解過程，并提出了運行效率更高的交替最小化方法(alternating minimization algorithm, AMA)[23]，這2種方法現已成為凸聚類相關算法的常用優化方法.2)數據結構信息的結合方面.其包括2個子方向：①改造凸聚類使其適用于特定情形：Hallac等人[10]提出了具有較強擴展性的network拉索，其是group拉索的泛化形式，適用于大規模圖網絡的聚類和優化；Wang等人[11]提出了適用于高維數據的稀疏凸聚類，該算法能夠在凸聚類的同時進行特征選擇，不僅提高凸聚類的性能而且極大地降低了算法時間復雜度；②將已有聚類算法凸松弛化：Lu等人[12]將譜聚類改造為凸稀疏譜聚類，并將該算法拓展為成對的稀疏譜聚類以利用數據的多視圖信息提高聚類性能；Chi等人[13]將凸聚類拓展到凸雙聚類，其目標函數的正則化項由行、列簇中心的fused拉索懲罰項共同構成，通過迭代地對行、列進行凸聚類實現算法.

將輔助信息與非凸目標結合的聚類算法，大致有3種:

1) 貪婪迭代搜索方法[1]，如Wagstaff等人[16-17]提出的COP-COBWEB算法和約束k均值(COP-Kmeans)算法，前者基于Fisher等人[24]提出的COBWEB算法，后者基于傳統的k-means算法.每次都會檢查數據分配是否符合約束條件，若整個聚類過程都不違反約束，則得到的簇符合要求.其主要缺點是不能將成對約束給出的信息擴散到整個樣本空間，即不能充分利用約束以反映樣本空間的分布[15]，導致聚類結果失真.

2) 將約束作為懲罰項[18]添加到相應目標函數中，而后優化出模型.這是一種較為常用的半監督聚類方法，如文獻[18]，但此方法可能改變原目標函數的性質.

3) 改造距離度量，此方法可彌補前2種方法的不足.必連關系具有傳遞性且具有明顯的幾何特征，容易處理，然而，尋找滿足不連約束的距離度量是一個NP完全的問題[15]，故改造距離度量的難點在于不連約束的處理.Klein等人[15]提出了基于層次聚類的CCL(constrained complete-link)算法，其處理不連關系的巧妙之處在于代替直接恢復樣本空間的距離度量，而是在每次合并簇時獲取一個新的距離度量，間接地將不連約束提供的信息擴散到樣本空間.Asafi等人[19]提出了一種有趣的方法處理不連約束：若向特征空間為M維的數據集添加N個不連約束，則每個不連約束對應一個新的特征維度，利用擴散映射(diffusion map)[25]將特征空間增廣到M+N維，具體參考3.2節.鑒于相對約束衡量了3個樣本之間的相似關系，能夠較好地反映樣本分布的局部區域信息從而指導聚類，Lesek等人[20]在文獻[19]的基礎上將相對約束轉化為特征空間的增廣.

2 模型建立

結合弱監督信息的凸聚類算法具體分為2個階段：1)通過距離度量的改造添加約束；2)對改造距離度量后的數據集進行凸聚類.本節將分別對其詳細地介紹.

2.1添加約束

(2)

φ(xi,xj)=|Ψt(xi)-Ψt(xj)|，

(3)

(4)

(5)

(6)

2.2凸聚類

2.2.1 權重

(7)

2.2.2 正則化項參數的選擇

Lange等人[29]提出用聚類穩定性理論評價模型的有效性：從同一數據源抽取若干組樣本進行聚類時，結果應具有可重現性、對于抽取的樣本不敏感.Wang等人[30]用此理論選擇簇數：每次將包含n個樣本的數據集劃分成2組訓練集和1組驗證集，用驗證集衡量訓練得到的2個模型的穩定性.這種方法的缺點是訓練樣本數量縮減為n3，所得模型不可靠.為提高訓練模型的可靠性，Fang和Wang等人[31]對上述方法做出改進：每次用Bootstrap方法抽取2組各包含n個樣本的訓練集，得到2個訓練模型并計算其聚類距離，如式(8).推廣上述理論：一個好的正則化參數也應對于微小的數據擾動不敏感，故將Bootstrap方法用于式中正則化參數的選取，具體如算法1所示：

算法1. 選取正則化參數γ.

輸出：最優正則化參數γ.

/*第1階段：抽樣*/

① forb=1,2,…,Bdo

② forj=1,2 do

④ end for

⑤ end for

/*第2階段：計算各正則化參數對應的聚類不穩定性*/

⑥ forg=1,2,…,Gdo

⑦ forb=1,2,…,Bdo

(8)

⑨ end for

⑩ end for

(9)

/*第3階段：獲取最優正則化參數*/

2.2.3 AMA算法

本文涉及的凸聚類均用AMA算法優化.首先，給出式(1)的增廣拉格朗日形式：

(10)

再用對偶上升方法迭代地更新各變量，第m次迭代過程如下：

(11)

AMA算法的具體推導過程可參考文獻[9].由于其實際迭代過程中只需更新U,Λ，且更新Λ的復雜度取決于權重集合W的稀疏性，故相比式(11)極大地減少了算法運行時間.具體如算法2所示：

算法2. AMA.

輸入：數據集X、權重集合W、正則化參數γ；

輸出：變量V.

① 初始化Λ0;

② repeat

③ fori=1,2,…,n

(12)

⑤ end for

(13)

⑧ end for

⑨ until滿足收斂條件.

(14)

優化結束后進行簇的分配.首先，由X構造包含n個頂點的圖，并將滿足v=0的第對樣本用一條邊連接；再對該圖進行廣度優先搜索，得到若干連通分量，每個聯通分量對應一個簇.

3 實驗與結果

3.1實驗設置

(15)

為方便敘述，將必連約束記為ML，不連約束記為CL.弱監督信息可通過2種方法獲取:1)隨機獲取.從同一/不同類中隨機抽取的2個樣本構成一個ML/CL.2)由樣本真實分布獲取.用L(xi)表示xi的真實類號，設定k1，k2且k1>k2.對于每個樣本xi，若k1NN(xi)中滿足L(xi)=L(xj)(xj∈k1NN(xi))的樣本數目小于k2，則選取距xi較近且滿足L(xi)≠L(xj)的樣本xj構成CL，記為(xi,xj).若(xi,xj)、(xi,xt)都是與xi相關的CL，且Di,j

對X′進行3種實驗：僅添加ML、僅添加CL、同時添加2種約束(ML與CL各 占12).逐漸增加約束數目，并針對每個約束數目隨機選取4～5組不同的約束進行實驗.每次實驗等同于將X′按照第2節進行建模與優化，其凸聚類階段的相關設置具體如下：正則化項取2范數；結合高斯核(用局部尺度化方法改造)與k近鄰計算權重集合W，且k=

實驗均在配置為英特爾i5-3470 CPU，16 GB內存的計算機上執行，由R語言實現，且用R的多線程實現正則化參數選擇模塊的加速.

3.2實驗結果

本文在模擬數據集和真實數據集上實驗：模擬生成的2個圓圈數據集和2個半月數據集，如圖1所示，4個真實數據集取自UCI[36](Iris選取了難分的2類數據)，具體如表1所示：

Table 1 Data Sets表1 數據集

Fig. 1 Simulated data sets圖1 模擬數據集

Fig. 2 Evaluation on clustering performance圖2 聚類性能評價結果

聚類性能的比較結果如圖2所示，橫坐標為約束數目，縱坐標為聚類性能評價結果，由圖和實驗數據可獲得5種信息：

1) 結合弱監督信息的凸聚類性能優于無約束的凸聚類.隨著約束的增多，聚類效果更優，這與直覺吻合.部分數據集在添加少量約束時就已獲得較高性能，反映了約束的稀疏性.

2) 具體比較3種實驗的性能.僅添加ML時，性能的提高幅度較明顯并趨于最優；僅添加CL時，性能相對穩定；同時添加ML和CL時，性能的提高幅度也較明顯，有時優于僅添加ML或CL時的情形.整體而言，性能在約束較少時波動較大，隨約束的增多趨于穩定，ARI的波動比RI大.

3) 比較聚類所得簇數與真實類數.表2為部分數據集在不同約束下的平均簇數，可見：僅添加ML的實驗在約束較少時簇數偏多，約束增多時簇數趨于真實類數；只添加CL時簇數相對穩定，約束過多時簇數相對較多；同時添加ML和CL時簇數穩定，約束較多時更逼近真實類數.

4) 比較聚類結果的約束符合率，即符合約束條件的樣本對的數目與所添約束總數的比值.表3為Banknote在3種實驗中的平均約束符合率，可見：僅添加ML的實驗在約束較少時符合率較低，另外2種實驗的約束符合率一直保持較高水平；在約束較少時，同時添加ML和CL使得ML的約束符合率也很高，故聯合使用CL可提高約束符合率.

Table 2 Average Number of Clusters表2 平均簇數

Table 3 Average Coincidence of Constraints in Banknote表3 Banknote的平均約束符合率

5) 比較約束的重要性對聚類性能的影響.表4為將Iris數據集依照樣本分布獲取的約束按重要性降序排序后，相同約束數目下前3組實驗的RI值.可見：約束數目相同時，聚類性能與約束的重要性呈正相關關系，約束數目增多時性能趨于穩定，故弱監督信息的質量對聚類結果有重要影響.

Table 4 RI of Iris with Constraints Sorted表4 Iris的芮氏指標(約束依重要性排序)

4 總結與展望

本文鑒于凸聚類的優勢及基于非凸目標函數的半監督聚類算法可獲取更優聚類效果的經驗，提出了一種結合必連與不連輔助信息的凸聚類算法，通過對凸聚類目標函數中距離度量的改造保持了其凸性，并通過實驗證明了此算法能夠有效提高聚類性能.此算法存在2個缺點：1)不連約束過多時算法運行時間較長，影響算法效率；2)遺傳了凸聚類不允許聚簇重疊的缺點.針對缺點1，可考慮2個層面：1)實驗結果反映了約束的稀疏性，即添加相對少的約束就可獲得較高的聚類性能，故實際應用中毋須添加過多約束以避免冗余；2)結合聚類集成[37]方法，將約束集合劃分為若干允許重疊的子集，并行地運行凸聚類再集成聚類結果.針對缺點2，可將模糊C均值算法與凸聚類結合，進行建模與優化.故下一步工作是聚類集成以及模糊C均值算法與凸聚類的結合.

[1] Madeira S C, Oliveira A L. Biclustering algorithms for biological data analysis: A survey[J]. IEEE/ACM Trans on Computational Biology and Bioinformatics, 2004, 1(1): 24-45

[2] Oliveira D, Valente J, Pedrycz W, et al. Advances in fuzzy clustering and its applications[M]. New York: John Wiley & Sons, 2007: 285-311

[3] Liu Ming, Liu Bingquan, Liu Yuanchao. A fast clustering algorithm for information retrieval[J]. Journal of Computer Research and Development, 2013, 50(7): 1452-1463 (in Chinese)(劉銘, 劉秉權, 劉遠超. 面向信息檢索的快速聚類算法[J]. 計算機研究與發展, 2013, 50(7): 1452-1463)

[4] Wong K C. A short survey on data clustering algorithms[C] //Proc of the 2nd Int Conf on Soft Computing and Machine Intelligence (ISCMI). Piscataway, NJ: IEEE, 2015: 64-68

[5] Xu Rui, Wunsch D. Survey of clustering algorithms[J]. IEEE Trans on Neural Networks, 2005, 16(3): 645-678

[6] Hall L O. Objective function-based clustering[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012, 2(4): 326-339

[7] Lindsten F, Ohlsson H, Ljung L. Just Relax and Come Clustering!: A Convexification ofk-means Clustering[M]. Link?ping: Link?ping University Electronic Press, 2011

[8] Hocking T D, Joulin A, Bach F, et al. Clusterpath an algorithm for clustering using convex fusion penalties[C] //Proc of the 28th Int Conf on Machine Learning. New York: ACM, 2011: 1

[9] Chi E C, Lange K. Splitting methods for convex clustering[J]. Journal of Computational and Graphical Statistics, 2015, 24(4): 994-1013

[10] Hallac D, Leskovec J, Boyd S. Network lasso: Clustering and optimization in large graphs[C] //Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 387-396

[11] Wang Binhuan, Zhang Yilong, Sun Wei, et al. Sparse Convex Clustering[OL]. arXiv preprint arXiv: 1601.04586, 2016 [2016-05-01]. http: / /arxiv.org /abs /1601.04586

[12] Lu Canyi, Yan Shuicheng, Lin Zhouchen. Convex sparse spectral clustering: Single-view to multi-view[J]. IEEE Trans on Image Processing, 2016, 25(6): 2833-2843

[13] Chi E C, Allen G I, Baraniuk R G. Convex biclustering[J]. Biometrics, 2016, 73(1): 10-19

[14] Zhou Zhihua. Machine Learning[M]. Beijing: Tsing University Press, 2016: 293-312 (in Chinese)(周志華. 機器學習[M]. 北京: 清華大學出版社, 2016: 293-312 )

[15] Klein D, Kamvar S D, Manning C D. From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering [R]. Stanford, CA: Stanford University InfoLab, 2002

[16] Wagstaff K, Cardie C, Rogers S, et al. Constrainedk-means clustering with background knowledge[C] //Proc of the 18th Int Conf on Machine Learning. New York: ACM, 2001: 577-584

[17] Wagstaff K, Cardie C. Clustering with instance-level constraints[C] //Proc of the 17th Int Conf on Machine Learning, New York: ACM, 2000: 1103-1110

[18] Fang Ling, Chen Songcan. Semi-supervised clustering learning combined with feature preferences[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(1): 105-111 (in Chinese)(方玲, 陳松燦. 結合特征偏好的半監督聚類學習[J]. 計算機科學與探索, 2015, 9(1): 105-111)

[19] Asafi S, Cohen-Or D. Constraints as features[C] //Proc of the 31st IEEE Conf on Computer Vision and Pattern Recognition (CVPR). Piscataway, NJ: IEEE, 2013: 1634-1641

[20] Lasek P, Lasek K. Relative constraints as features[C] //Proc of the 23rd Int Workshop on Concurrency, Specification and Programming. Berlin: Humboldt University, 2014: 121-125

[21] Tibshirani R, Saunders M, Rosset S, et al. Sparsity and smoothness via the fused lasso[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2005, 67(1): 91-108

[22] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends?in Machine Learning, 2011, 3(1): 1-122

[23] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[J]. SIAM Journal on Control and Optimization, 1991, 29(1): 119-138

[24] Fisher D H. Knowledge acquisition via incremental conceptual clustering[J]. Machine Learning, 1987, 2(2): 139-172

[25] Lafon S, Lee A B. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(9): 1393-1403

[26] Wickelmaier F. An introduction to MDS[M]. Denmark: Aalborg University, 2003

[27] Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416

[28] Zelnik-Manor L, Perona P. Self-tuning spectral clustering[C] //Advances in Neural Information Processing System. Berlin: Springer, 2005: 1601-1608

[29] Lange T, Roth V, Braun M L, et al. Stability-based validation of clustering solutions[J]. Neural Computation, 2004, 16(6): 1299-1323

[30] Wang Junhui. Consistent selection of the number of clusters via crossvalidation[J]. Biometrika, 2010, 97(4): 893-904

[31] Fang Yixin, Wang Junhui. Selection of the number of clusters via the bootstrap method[J]. Computational Statistics and Data Analysis, 2012, 56(3): 468-477

[32] Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends?in Optimization, 2014, 1(3): 127-239

[33] Donoho D L. De-noising by soft-thresholding[J]. IEEE Trans on Information Theory, 1995, 41(3): 613-627

[34] Al Shalabi L, Shaaban Z, Kasasbeh B. Data mining: A preprocessing engine[J]. Journal of Computer Science, 2006, 2(9): 735-739

[35] Hubert L, Arabie P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218

[36] Asuncion A, Newman D. UCI machine learning repository[DB].

[37] Strehl A, Ghosh J. Cluster ensembles-a knowledge reuse framework for combining partitionings[C] //Proc of the 18th National Conf on Artificial Intelligence. New York: ACM, 2002: 93-99

ConvexClusteringCombinedwithWeakly-SupervisedInformation

Quan Zhenzhen and Chen Songcan

(CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106)

Objective function-based clustering is a class of important clustering analysis techniques, of which almost all the algorithms are built by optimization of non-convex objective. Thus, these algorithms can hardly get global optimal solution and are sensitive to the provided initialization. Recently, convex clustering has been proposed by optimizing a convex objective function, not only does it overcome the insufficiency illustrated above, but it also obtains a relatively stable solution. It has been proven that clustering performance can be improved effectively by combining useful auxiliary information (typically must-links andor cannot-links) obtained from reality with the corresponding objective. To the best of our knowledge, all such semi-supervised objective function-based clustering algorithms are based on non-convex objective, semi-supervised convex clustering has not been proposed yet. Thus, we attempt to combine pairwise constraints with convex clustering. However, the existing methods usually make the original convex objectives lose their convexity, which add constraint penalty terms to the objective function. In order to deal with such problem, we introduce a novel semi-supervised convex clustering model by using the weakly-supervised information. In particular, the key idea is to change distance metric instead of adding constraint penalty terms to the objective function. As a result, the proposed method not only maintains the advantages of convex clustering, but also improves the performance of convex clustering.

objective function-based clustering; convex clustering; weakly-supervised information; constraints; distance metric; semi-supervised clustering

Quan Zhenzhen, born in 1991. Master candidate. Student member of CCF. Her main research interests include machine learning and pattern recognition.

Chen Songcan, born in 1962. Professor and PhD supervisor of pattern recognition and artificial intelligence. Senior member of CCF. His main research interests include pattern recognition, machine learning and neural computing.

2017-05-23；

：2017-06-19

國家自然科學基金項目(61672281) This work was supported by the National Natural Science Foundation of China (61672281).

陳松燦(s.chen@nuaa.edu.cn)

TP391.4