結合改進密度峰值聚類的LGC半監督學習方法優化

薛子晗，潘 迪，何 麗

（天津財經大學理工學院，天津 300222）

0 概述

強監督的機器學習方法需要大量有標簽數據的支持，但隨著大數據時代應用領域數據量的日益膨脹，通常獲得的是大量的無標簽數據。因此，半監督學習成為模式識別和機器學習領域的一個新的研究熱點。半監督學習介于監督學習與無監督學習之間，是通過少量標記樣本對大量未標記樣本進行標注的一種學習方法［1］。基于圖的半監督學習是該研究領域極具代表性的一種方法，在樣本標注正確率上具有明顯優勢。

自文獻［2］提出圖分割最小割算法以來，基于圖的半監督學習方法得到了廣泛應用。文獻［3］針對處于類邊界區域的標記樣本往往會降低標簽傳播有效性的問題，提出親和力標簽傳播算法。文獻［4］提出將標簽傳播和圖卷積網絡相結合的框架，擴展了建模能力，實現了標注效率的提升。文獻［5］在LGC的基礎上提出一種基于稀疏分解的l0構圖方法［6］，并將其結合到LGC算法中，提升了算法的分類精度和性能。文獻［7］為LGC提供了一種新的歸納過程，誘導局部與全局一致性，提升了LGC算法的正確率。文獻［8］在計算鄰接矩陣時利用K-近鄰圖代替完全連接圖，提升了時間效率，并在LGC開始迭代之前挑出噪聲點，提高了LGC算法的準確率。文獻［9］在計算鄰接矩陣時利用K-近鄰圖代替完全連接圖，在標簽傳遞過程中，僅將未標記樣本的標簽根據相似度傳遞給其近鄰，而將已標記樣本的標簽強制填回以確保標簽傳遞源頭的準確性。以上基于圖的半監督學習方法雖然獲得了較好的標注正確率，但是并沒有考慮大規模數據集對算法執行時間的影響，忽略了算法的時間效率。針對上述問題，文獻［10］提出了一個新的框架，將生成混合模型與基于圖的正則化相結合；文獻［11］使用頂點之間的線性組合關系來定義權重；文獻［12］用生成樹對圖進行近似，以最小化總體切割大小的方式來標記樹，并提出了一種新的方法，對生成樹通過最小化目標函數，來預測未標記樣本的標簽［13］。

以上基于圖的改進方法雖然能在一定程度上降低算法的時間復雜度，但標注正確率較低。為保證算法在標注正確率上的優勢，降低圖的規模，文獻［14］提出了密度峰值聚類（Density Peaks Clustering，DPC）算法，隨后研究人員在DPC算法的基礎上進行優化與應用，取得了較好的效果［15-17］。但是這些方法都不適用于局部聚類。為使局部聚類方法能夠在不同聚集形態的數據集上都能表現出較好的魯棒性，本文基于DPC算法設計一種迭代選擇中心點的密度峰值聚類（Iteration Density Peaks Clustering，IDPC）算法。利用該算法進行局部聚類，并運用每個簇的聚類中心為頂點構造圖，通過迭代篩選出的聚類中心點表征原始數據的特征分布，以降低圖的規模。

1 相關理論

1.1 局部與全局一致性算法

令數據集D=｛xi|xi∈?m，i=1，2，…，n｝，n為D中的樣本數。其中，Dl=｛（x1，y1），…，（xl，yl）｝為已標記樣本集合，l＜＜n，Du=｛xl+1，…，xn｝表示未標記樣本集合，Yl為前l個已標記樣本的標簽集合，LGC的學習目標是利用D與Yl來計算Du中樣本的標簽集合Yu。用表示D中樣本的初始化標簽矩陣，其中，c為D中樣本的不同標簽數。將定義為D中樣本對各個類的概率矩陣，Fij表示xi屬于第j個類的概率。

W為G中各個頂點之間的相似度矩陣，wij的計算方法如式（1）所示：

傳播矩陣S的計算方法如式（2）所示：

其中，D是對角矩陣，Dii為W第i行的和。

獲得傳播矩陣S后，迭代計算式（3）直到F收斂，可以得到收斂狀態下的最優F*。

文獻［5］在LGC算法中給出了LGC收斂性證明，并推導出F*是一個固定的值。因此，F*是LGC算法的唯一解而且與F的初始值無關。

1.2 密度峰值聚類算法

傳統DPC算法假設聚類中心比其臨近點的局部密度更高，且與其他聚類中心的距離較遠。在這種假設下，若要選取聚類中心，首先需要計算數據集D中每個樣本x（ixi∈D，1≤i≤n）的局部密度ρi和相對距離δi。用dij表示樣本xi和xj之間距離，且dij=dist(xi，xj)是這兩個樣本之間的歐式距離，依此建立距離矩陣DM，即DM=(dij)n×n。對于具有離散值的樣本，在DPC算法中，ρi的定義為與xi的距離小于dc的樣本個數。xi的局部密度ρi的計算方法如式（4）所示：

其中，dij為樣本xi和xj之間的特征距離，dc是截斷距離，χ(·)為計數函數，定義如式（5）所示：

對數據集D中的任一樣本xi計算其局部密度ρi后，若D中存在xj使ρj＞ρi，則可以使用式（6）計算其距離δi：

在式（6）中，若D中存在點xj使ρj＞ρi，則將δi定義為與離xi最近且局部密度更高的樣本之間的距離；否則，將δi定義為與xi相距最遠的樣本距xi之間的距離。

對D中的每個樣本x（i1≤i≤n），得到其局部密度ρi與距離值δi后，可使用式（7）來選擇聚類中心：

其中，γi值越大，表示xi為聚類中心的概率越大。對所有樣本計算γi后，選擇最大的若干個樣本作為聚類中心進行聚類。

2 IDPC-LGC方法

傳統的DPC方法只選擇ρ與δ突出的極少數點作為聚類中心，而本文使用局部聚類的中心點作為頂點構造圖，需要大量中心點來描述原始數據的特征分布。因此，本文設計了一種迭代選取中心點的方法，并提出一種改進的DPC聚類方法IDPC。該方法使用迭代的方式選取多個中心點，并以中心點為聚類中心進行局部聚類，最后運用聚類生成簇中的已標記樣本的標簽對該簇的中心點進行標注。

IDPC-LGC算法實現的主要步驟如下：

1）對數據集D中的所有樣本，計算任意兩個樣本之間的歐式距離，并建立距離矩陣DM。

2）使用迭代的方法選取中心點，得到D的中心點集合C。

3）以C中的每個中心點為聚類中心進行局部聚類，得到D上的簇集合CLS=｛CL1，CL2，…，CLP｝。

4）對CLS中的每一個簇CL（i1≤i≤P），使用CLi中已標記樣本的標簽對CLi的中心點進行標注，得到中心點集合C的標簽集合Yc。

5）以中心點集合C中的每個樣本為頂點構造圖G，并按照式（1）計算G中的任意兩個頂點之間的相似度，建立相似矩陣W，然后利用Yc完成基于LGC理論的樣本標注過程，得到中心點集合C的預測標簽集合Yp。

6）利用Yp中中心點的標簽對各中心點所在簇中的所有未標注樣本進行標注。

2.1 基于迭代的中心點選取方法

在IDPC-LGC算法中，中心點既是局部聚類的中心，也是基于LGC算法的樣本標注的基礎。為提升IDPC-LGC的標注準確率和算法執行的時間效率，選取的中心點應該能夠描述原始數據集的樣本分布形態，并使中心點的數量盡可能少。IDPC-LGC算法使用基于中心點的圖結構實現LGC的標簽傳播過程。根據LGC的標簽傳遞思想，建立圖結構后，樣本的標記信息不斷向圖中各個頂點的鄰近樣本傳播，直至全局收斂穩定。因此，若屬于不同類的中心點之間的距離太近，就可能導致本應屬于不同類的中心點在LGC階段被標注成相同的標簽，導致中心點標注錯誤。

為保證LGC階段中心點標注的準確率，本文在中心點選取時要求滿足以下兩個條件：

1）屬于不同類的中心點之間的距離應盡可能遠，使篩選出來的中心點盡量遠離類邊界。

2）應屬于同一個類的中心點需盡量分布均勻，保持連貫，避免出現明顯的間斷情況。

對數據集D中的每個樣本xi(1≤i≤n)，n為D中的樣本數。按照傳統DPC算法計算其局部密度ρi與距離值δi，并計算γi=ρi×δi。對D中所有樣本按γ值從大到小進行排序，將排序后的樣本編號順序加入到數組q中，即有

根據DPC聚類算法的思想，樣本的γ值越大，其成為簇中心的可能性越大，因此，該樣本成為中心點的概率也越大。所以，可以按數組q中各個樣本的出現順序進行中心點篩選。為使篩選出的中心點能夠遠離分類邊界，這里約定只有局部密度大于平均局部密度的樣本才能參與迭代。若用表示D上所有樣本的平均局部密度，對樣本當時，將樣本添加到迭代訓練數據集中的計算方法如式（8）所示：

算法1基于迭代的中心點選取算法

算法1中K值的大小對算法的執行時間和中心點的分布有直接影響。K值越大，篩選出的中心點會越少，可能會導致中心點在分布形態上的不連貫，并使得標注準確率下降，但算法的執行時間會減少；反之，算法的標注準確率會提升，但過多的中心點會導致消耗額外的算法執行時間。K值的選取與訓練數據集的規模、數據集中隱藏的類別數和數據集中樣本的聚集形態有關，本文將在實驗部分對K值的選取進行討論。

算法1中的步驟4進行了由大到小的排序，對隨機序列進行排序可以達到的最好時間復雜度為O（nlogan），步驟5～步驟12為K近鄰迭代過程，時間復雜度為O（Kn2），但在實際應用中，K值一般較小。因此，算法1的時間復雜度近似為O（n2）。

為進一步說明本文提出的基于迭代的中心點選取方法對原始數據集特征描述的有效性，在其生成的帶有噪聲的雙月數據集上進行了中心點選取實驗。實驗中數據集的樣本數為3 000，已標記樣本數為16，噪聲率設為0.16。數據集的原始圖像和中心點選取結果如圖1所示。其中，圖1（a）為生成的原始數據圖像，圖1（b）為產生的中心點結果。從圖1（a）可以看出，由于噪聲的存在，兩個雙月之間存在比較明顯的樣本重疊。

圖1 原始數據與中心點的比較結果Fig.1 Comparison result of raw data and central points

從圖1（a）和圖1（b）的對比可以看出，本文使用迭代選擇出的中心點能夠較好地描述原始數據集中兩個類的特征，而在規模上，中心點的數量要明顯少于原始數據集中的樣本數。并且篩選出的中心點在同一分類上連貫性很強，且基本能夠向類中心聚集。同時從圖1（b）可以看出，兩個類的中心點集群相距足夠遠，這為基于LGC的樣本標注提供了很好的基礎。

2.2 基于中心點的局部聚類方法

局部聚類的主要目的是利用同一聚類中的樣本應該擁有相同類標簽這一規則，來得到中心點集C的標簽集合Yc。這里的局部聚類是在已知中心點集合的情況下進行的，而且中心點理論上可以是每個聚類的中心或接近聚類中心的樣本。根據DPC聚類對聚類中心的假設，中心點在局部應該擁有最高的局部密度。因此，可將非中心點歸屬到與其最近且密度更高的樣本所在的簇，如此迭代，可以將數據集中的每個非中心點歸屬到其對應的中心點所在的簇。

為方便描述，本文引入聚類數組qc來記錄在數據集D中離當前樣本最近且局部密度更高的樣本的下標。對樣本xi，qc［i］表示D中離xi最近且局部密度更高的樣本的下標，若D中不存在比xi密度更高的樣本，則qc［i］中存儲xi的下標。

算法2基于中心點的局部聚類算法

在算法2中，步驟2對D中的每個樣本xi按ρi進行由大到小排序可以達到的最好時間復雜度為O（nlogan），對非中心點進行迭代聚類的最壞時間復雜度為O（（n-C）×maxρ），其中，C為中心點個數，maxρ為D中的各個樣本局部密度的最大值，maxρ遠小于n，所以，算法2的時間復雜度為O（nlogan）。

3 實驗與結果分析

3.1 實驗設計

為分析不同數據規模和已標記樣本比例下本文IDPC-LGC算法的有效性，首先在代碼生成的有噪聲的雙月數據集上進行實驗，以分析數據規模對標注正確率和運行時間的影響。同時，為驗證IDPC-LGC算法在不同聚集形態數據集上的性能，選擇4個擁有不同聚集形態和規模的公開數據集進行實驗。在實驗中，將本文算法與LGC、BB-LGC［9］、improved-LGC［8］、LGC（-l0，K）［6］、KNN（K=1）、EEKNN［18］算法進行了比較。實驗環境為Windows 7系統，8 GB內存，i5-4590處理器，實現語言為python，所有結果均為30次實驗的平均值。

實驗使用標注正確率和運行時間作為評價指標，標注正確率為標注正確樣本數與數據集中的未標記樣本總數的比值。

3.2 數據集規模對算法性能的影響

為分析數據集規模對算法性能的影響，首先使用代碼生成的雙月數據集進行實驗，噪聲率noise=0.16，標記樣本數固定為16。不同數據規模下各個算法的標注正確率和運行時間對比如圖2所示。

圖2 數據集規模對算法性能的影響Fig.2 Effect of dataset size on algorithm performance

從圖2可以看出：隨著數據量的增大，本文IDPC-LGC算法的標注正確率始終優于LGC算法與BB-LGC算法；在運行時間上，隨著數據量的增大，LGC算法的運行時間增幅較快，而本文算法的增幅較小，且遠低于LGC算法；相對于本文算法，BB-LGC與improved-LGC算法的時間效率優化并不明顯；隨著數據量的增大，本文算法在運行時間上的優勢越來越明顯，這主要是因為在同一特征分布下，數據規模越大，數據的密集程度就會越高，冗余性變強，這時利用中心點進行聚類可以獲得更好的樣本縮減比，能更有效地降低算法依賴的圖的規模；LGC-（l0，K）算法的準確率最低，是因為該算法使用k-means算法對原始數據集進行粗分類，但是k-means算法以計算各個點到聚類中心的距離為核心，在近似球狀分布的數據集上有較好的表現，在雙月數據集上表現不佳，因此，LGC-（l0，K）算法的性能受數據集中樣本聚集形態的影響；KNN算法與EEKNN算法的運行時間較短，但在標注正確率上表現較差。當數據集的規模為n時，LGC算法的時間復雜度為O（n3），而本文算法的時間復雜度為O（（n/t）3）+O（n2），t為局部聚類中各個簇的平均樣本數，也即在局部聚類時構建圖可以縮減的倍數。當n很大時，因為（n/t）3＜＜n3，所以本文方法在運行時間上的優勢明顯。

3.3 標記樣本數對算法性能的影響

為進一步說明標記樣本數對算法性能的影響，本文使用代碼生成的雙月數據集，并選擇噪聲率noise=0.16，樣本規模n=3 000和多個不同的標記樣本數進行實驗，結果如圖3所示。

圖3 標記樣本數對算法性能的影響Fig.3 Effect of labeled sample number on algorithm performance

從圖3（a）可以看出，所有比較算法的標注正確率都會不同程度地受到標記樣本數的影響，標記樣本增加，標注的正確率也隨之提升，而本文算法在較少標記樣本數的情況下也能夠獲得較高的標記正確率，這是因為本文使用的迭代密度峰值局部聚類算法能夠很好地解決類的邊界重疊問題。從圖3（b）可以看出，已標記樣本數的變化對算法的運行時間影響很小，EEKNN與KNN算法雖然在運行時間上優于本文算法，但標注正確率較低。總體上，本文算法在不同已標記樣本數的情況下，在標注正確率和運行時間兩個指標上優勢明顯。

3.4 數據集樣本的聚集形態對算法性能的影響

為說明本文提出的IDPC-LGC算法在不同聚集形態和不同類別分布情況下的魯棒性，在4個公開數據集上分別進行實驗，并對不同算法在各個數據上的標注正確率和運行時間進行了比較，如表1所示。IDPC-LGC算法適用于大規模的數據集，并且數據集中各個類的邊界越模糊，IDPC-LGC算法的優勢將會越明顯。為證明這一點，選擇兩個有邊界重疊的近似球型數據集D31［19］和S2［20］。同時，為證明本文方法在小數據集和其他形態數據集上的有效性，選擇了數據集Aggregation以及Flame。從表1可以看出，4個數據集的規模和類別數有較明顯的變化。

表1 數據集屬性Table 1 Dataset attribute

IDPC-LGC算法在各個數據集上使用的參數設置和產生的中心點數如表2所示。

表2 參數設置Table 2 Parameter settings

表3和表4比較了各算法在4個數據集上的標注正確率和運行時間。

表3 標注正確率結果比較Table 3 Comparison of labeling accuracy results %

表4 運行時間結果比較Table 4 Comparison of running time resultss

從表3和表4可以看出，在4個數據集上本文算法在標注正確率上均優于LGC、BB-LGC與improved-LGC算法，且LGC算法在數據集Flame上的標注正確率較低。LGC-（l0，K）雖然在S2與D31兩個數據集上具有最高的標注準確率，但在Flame上表現較差，因為該算法使用k-means進行粗分類，聚類結果與數據集中樣本的聚集形態有關。表3的結果說明，本文算法對不同聚集形態和規模的數據集都具有較好的適應性，魯棒性較好。在運行時間上，本文算法在規模較大的D31和S2數據集上明顯優于在標注正確率上表現較好且穩定的LGC、BBLGC與improved-LGC算法，雖然不及KNN和EEKNN算法，但是KNN和EEKNN的標注正確率相對較低，并且表現不穩定。與表現較好的LGC、BBLGC與improved-LGC算法相比，本文算法在運行時間上的優勢明顯，并且數據集的規模越大，這種優勢將更加明顯，這主要是因為本文使用基于迭代的密度峰值局部聚類方法能夠有效降低LGC算法依賴的圖的規模。

實驗結果顯示，本文提出的IDPC-LGC算法在不同規模、不同標記樣本數和不同聚集形態的數據集上，都能在標注正確率和運行時間兩個評價指標上保持較好的優勢。

3.5 參數討論

IDPC-LGC算法涉及的參數較多，其中影響最大的是DPC聚類算法中的截斷距離dc與迭代中K值的選取。因為dc值在各樣本間距離值排列在前1%位置時，能夠在各個數據集上獲得最佳的聚類效果，而算法對K值的選取比較敏感，所以本節主要分析K值變化對算法性能的影響。K值的選取方法如式（9）所示：

其中，c為樣本類別數，θ為調整系數，可以根據數據集中樣本分布的特征及數據規模的大小進行調整，本文默認為1。若圖像上各個聚類的形態類似球型，且數據量偏大，則表明可以用更少的中心點對原始數據的特征進行表征，這時θ值可以略大于1；若各個聚類的形態扁平或表現為各種不規則形狀，這時需要避免篩選出的中心點出現斷層或分布不均勻的情況，因此需要將θ設置為小于1的數；在數據量極小且分類邊界模糊的數據集上，如3.4節提到的Flame數據集，需要通過調整θ值使K值為1。

在數據集D31的實驗中，將θ值設為1時，使用式（9）得到K=10。本節將觀察K值變化對D31實驗結果的影響，如圖4所示。

圖4 K 值變化對IDPC-LGC性能的影響Fig.4 Effect of K value on IDPC-LGC performance

從圖4（b）可以看出，當K值過小時，IDPC-LGC的運行時間偏高，因為K值越小，使用迭代篩選出的中心點數就越多，運用中心點建立的圖的規模就越大，LGC運行所花費的時間也越多。同時，從圖4可以發現，隨著K值的增加，運行時間和中心點數下降較快，而標注正確率在一定范圍內能夠保持相對穩定。然而，當K值繼續增加到30時，算法的標注正確率大幅下降，這是因為K值過大會導致中心點數量偏少，使得同一類別的中心點集出現斷層或分布不均勻的情況，從而影響最終的標注正確率。

4 結束語

針對LGC半監督學習算法時間復雜度較高的問題，本文提出一種改進的半監督學習算法IDPC-LGC。通過迭代產生的少量中心點構建局部與全局一致性運行的圖結構，實現基于LGC的半監督學習。實驗結果表明，該算法能夠有效降低LGC算法運行圖的規模。同時，使用基于中心點的局部聚類方法能夠較好地表達原始數據集的特征分布，適應不同聚集形態數據集的特征分布，有效降低噪聲對標注準確率的影響，獲得更優的標注準確率和運行時間。下一步將研究迭代過程中K值的自適應選取以及IDPC-LGC算法在大規模數據場景中的具體應用。