基于主動學習先驗的半監督K-means聚類算法

柴變芳，呂 峰，李文斌，王 垚

(河北地質大學 信息工程學院，石家莊 050031)(*通信作者電子郵箱25304189@qq.com)

0 引言

當前信息社會產生大量數據，聚類技術可以幫助人們快速發現這些數據的類別，進而引用于決策, 有些時候可以很容易標記少量先驗信息，提高聚類算法的性能。先驗信息主要有兩類：第一類是標記的樣本類別；第二類是標記的成對約束集合，一對樣本屬于一類則為must-link，否則為cannot-link。標記樣本相當于已知數據的特征和類數，但有些時候很難獲得數據的類數，因此，基于兩個樣本是否屬于一類的先驗信息往往更易于獲得。例如對微博用戶的聚類，可通過一些用戶發表信息及交互記錄判斷他們是否屬于一類，甚至數據分析師可標定某些用戶的類別。半監督聚類技術可將這些先驗信息與聚類目標結合，更有效地指導數據的聚類。研究表明，高質量的先驗信息不僅可以指導未標注樣本進行正確聚類，提高聚類結果的準確性還可以加快聚類的收斂速度[1-4], 因此，設計主動半監督聚類算法是一個值得研究的關鍵問題。

研究者提出了一些半監督聚類算法，基于先驗信息的類別及使用方式分為3類[5]：1)基于距離的半監督聚類算法，這類算法利用成對約束來學習距離度量從而改變樣本間的距離，便于聚類。2)基于約束的半監督聚類[6-8], 這類算法使用must-link和cannot-link成對約束關系指導聚類過程。Basu等[6]在K-means算法的基礎上引入了must-link和cannot-link成對約束集合作為先驗信息，提出了半監督聚類算法PCK-means(Pairwise ConstrainedK-means),提高了K-means聚類算法的性能。3)基于約束與距離的半監督聚類算法, 這類算法實際上是對上述兩種算法的總結。Basu等[9]提出了一個基于隱馬爾可夫隨機場(Hidden Markov Random Field, HMRF)的半監督聚類的概率模型，該模型概括了先前將約束與歐氏距離相結合的方法，并在此基礎上提出了一種分區半監督聚類算法，最后通過實驗驗證了算法的性能。

半監督聚類效果經常受隨機選擇得到的先驗信息的影響，為得到更好的聚類效果，主動半監督聚類將主動學習與半監督聚類相結合，通過一定的選擇策略主動選擇未標注數據進行標注。Basu等[6]在PCK-means算法的工作基礎上，采用最遠距離優先策略，通過Explore和Consolidate兩個階段主動選擇樣本點，在給定的查詢次數內構建并擴充成對約束集合，提出了主動半監督聚類算法APCK-means(Active Pairwise ConstrainedK-means)，進一步提高了算法的準確性，但是該算法對于離群點和噪聲點過于敏感。Xiong等[10]提出了一種基于迭代的主動半監督聚類框架(Iteration-based Active Semi-Supervised Clustering Framework, IASSCF), 該框架初始隨機選擇一個節點，然后迭代進行聚類。在每次迭代過程中首先運行半監督聚類，然后根據當前聚類結果主動選擇一個最具價值信息的樣本點擴充到先驗信息集合。選擇的樣本點不確定性高，且確定該未標注樣本點與已標注樣本的約束關系所需的查詢次數盡可能少。IASSCF框架可基于約束先驗實現半監督聚類，并且能主動選擇信息量大的樣本去標注，聚類準確性高；但是其隨機選擇的初始先驗信息較少，導致迭代初期聚類效果不佳，進而影響后續聚類結果，此外，每次迭代只選擇信息量最大的一個點標記，導致運行速度慢、性能提升較慢。

針對此問題，本文設計一種基于主動學習先驗的半監督K-means聚類算法——IASSCF_PCK-means，該算法基于主動選取聚類初始中心的思想[11]，選取部分代表性較高的樣本點，查詢其之間的成對約束關系，構建初始先驗節點集合，將構建好的初始先驗節點集合作為IASSCF框架的初始先驗信息，用以解決在迭代初期先驗信息過少導致最終聚類結果效果不佳的問題；同時，將原IASSCF框架中每次迭代過程僅選擇一個最具有價值信息的樣本點改進為基于當前聚類結果為每一簇選擇一個最具價值信息的樣本，減少迭代次數，加快算法運行速度，提高算法性能。最后在UCI數據集[12]上驗證IASSCF_PCK-means算法的有效性。

1 本文算法IASSCF_PCK-means

帶有初始先驗節點集合的迭代式主動半監督聚類包括構建初始先驗節點集合和基于重要性多節點的主動半監督聚類兩部分。首先構建包含多個樣本點的初始先驗節點集合作為先驗信息；然后指導迭代式聚類過程，并且在迭代過程中通過主動選擇策略選擇多個價值信息較大的無標記樣本加入到先驗信息集合，指導后續聚類。

1.1 構建初始先驗節點集合

從數據集中選擇若干代表性較高的點，查詢這些點之間的約束關系(must-link或cannot-link)，構建初始先驗節點集合。

定義1 若兩個樣本點滿足must-link約束關系，則這兩個樣本必須被指派到同一簇中；若這兩個樣本滿足cannot-link約束關系，則這兩個樣本點必須被指派到不同的簇中。

代表性較高的點需同時滿足以下兩個特點：

1)本身的密度大且其周圍樣本點的密度均不超過它；

2)與其他密度更大的樣本點的距離較遠。

樣本點密度的計算公式如下：

(1)

其中

(2)

參數dc>0為截斷距離，通過計算數據集D中不同樣本兩兩之間距離并按升序排序，然后由用戶設定一個百分比參數，dc為該排列的參數百分比上的數。后文實驗中設定的百分比參數為2%。

由以上可知，樣本xi的密度ρi表示數據集D中除xi外的其他樣本點與xi的距離小于dc的樣本個數。

如果xi不是樣本集D中密度最大的樣本點，則xi與其他密度高于自身的樣本點之間的距離δi的計算公式為：

(3)

如果xi是樣本集D中密度最大的樣本點，則:

(4)

至此，可求得數據集D中每個樣本點的ρ和δ值，將D中的樣本點按照ρ·δ的值從大到小排序，則排序越靠前越具有代表性。查詢前幾個樣本的約束關系，構建初始先驗節點集合N={N1,N2,…,Nl}，其中l≤k,k為聚類的簇個數。構建初始先驗節點集合的算法在算法1中給出，初始先驗節點集合中的樣本點滿足如下關系：

1) 若xi與xj均屬于Np，則xi與xj有must-link約束關系。

2) 若xi屬于Np，xj屬于Nq，且p≠q, 則xi與xj滿足cannot-link約束關系。

算法1 initNeighborhoods(D,k,T,C)。

輸入 數據集D，指定選擇代表性高的樣本點個數k，給定查詢次數T，約束集合C=?;

輸出 鄰域集合N，剩余查詢次數Tleft,約束集C。

1)

t=0，l=1

2)

計算截斷距離dc；

3)

計算D中所有樣本點的ρ值；

4)

計算D中所有樣本點的δ值；

5)

將所有樣本點的ρ值與δ值對應相乘，并按照從大到小的順序排序，并取排序后的前k個樣本，得到reprePoints[1..k];

6)

N1={reprePoint[1]}

7)

forj=2 tok

8)

for 每個Ni∈N

9)

t++;

10)

查詢reprePoints[j]與所有xi∈Ni的約束關系。如果reprePoints[j]與xi滿足must-link約束，則Ni=Ni∪{reprePoints[j]}并更新約束集合C,否則，break；

11)

end for

12)

如果reprePoints[j]與N中所有樣本點均不滿足must-link約束，則l++；Nl= {reprePoints[j]}; N=N∪Nl

13) end for

14)

Return N;Tleft=T-t;C

1.2 基于重要性多節點的主動選擇策略

IASSCF中每次迭代都進行一次半監督聚類，并且依據當前聚類結果主動選擇一個最有價值的樣本點，查詢其與已標注樣本點的信息，將其加入到先驗信息集合, 該方法可以高效地擴充先驗信息集合，但是每次迭代僅選擇一個樣本點，導致迭代次數過多，算法運行過慢。基于其不確定性度量方法，改進主動選擇策略：在每次迭代過程中針對每一簇選擇一個價值信息率最大的樣本點擴充到先驗信息集合。主動選擇樣本點的方法基于以下假設：對不確定性越大的樣本進行標注帶給聚類結果的收益很顯著，相反，對于所屬簇較為明晰的樣本進行標注所帶來的收益微乎其微；同時，對于不確定性越大的樣本，對其進行標注所消耗的查詢次數花銷越大, 因此，要在不確定性和花銷之間權衡，即在給定的查詢次數內盡可能多地選擇不確定性大的樣本擴充到先驗節點集合，提高聚類性能。

主動選擇策略中選取最有價值的樣本點基于以下兩個指標：不確定性和查詢開銷的期望。這兩個指標均是在執行完一次聚類后，在其聚類結果的基礎上計算。π表示當前數據集的聚類結果，π(xi)表示樣本xi當前被指派的簇標記。

1)不確定性度量通過以下幾個步驟完成: 首先，使用留出法將帶有類標記的數據集劃分成訓練集和測試集，使用訓練集訓練出帶有50棵決策樹的隨機森林; 將數據集D中所有樣本兩兩一組使用隨機森林進行分類，統計隨機森林中將該對樣本劃分為一類的決策樹個數，統計出的決策樹個數除以隨機森林包含的決策樹總個數即為該對樣本的相似性; 計算完成后，得到樣本間相似度矩陣M，其中M為m×m維的矩陣，m為數據集D中的樣本個數，M(i,j)表示樣本xi和樣本xj的相似度； 然后，在樣本間相似度矩陣M的基礎上通過計算樣本x和Ni中所有樣本相似度的平均值作為x和Ni的相似度，歸一化求得樣本x屬于Ni的概率值p(x∈Ni)，計算公式如下：

(5)

其中：|Ni|表示鄰域Ni中樣本的個數，l表示鄰域集合N的元素個數。最后，計算樣本x屬于各個鄰域概率的熵值作為其不確定性度量指標，H(N|x)的計算公式如下：

(6)

2)查詢開銷的期望是基于式(5)的計算結果。通過式(5)已求得樣本x屬于鄰域集合N中各個鄰域的概率, 由于給定查詢次數有限，因此應力求消耗更少的查詢次數來確定x與各個鄰域的關系。通過式(5)的計算結果的值按照降序將各個鄰域重新編號，即排序后滿足p(x∈N1)≥p(x∈N2)≥…≥p(x∈Nl)。q(x)表示確定x與鄰域的所屬關系所用到的查詢次數，則p(q(x)=i)=p(x∈Ni)。查詢次數q(x)的期望值可表示為：

*p(x∈Ni)

(7)

將不確定性越大的樣本擴充到先驗節點集合，對算法結果帶來的收益越大，但是對不確定性大的樣本進行標注往往開銷很大，因此，應綜合考慮不確定性與查詢開銷，即不確定性盡可能大的同時查詢開銷盡可能少，可通過式(8)得到基于當前指派結果π的每個簇中性價比最高的樣本點。

(8)

其中u表示不在鄰域集合中的其他樣本集合。主動選擇策略在算法2中給出。

算法2 MostInformative(D,π,N)。

輸入 數據集D，當前聚類指派結果π，鄰域集合N={N1,N2,…,Nl};

輸出 選定的樣本集合X。

1)

根據當前聚類指派結果訓練隨機森林，并求得樣本間相似度矩陣M

2)

for 每個x∈D，且x?N

3)

fori=1 tol

4)

通過式(5)計算p(x∈Ni)

5)

end for

6)

通過式(6)計算H(N|x)

7)

通過式(7)計算E[q(x)]

8)

end for

9)

通過式(8)計算X

10)

ReturnX

1.3 算法描述

IASSCF中從數據集D中隨機選取一個樣本點作為先驗節點，加入到鄰域集合中，然后開始迭代。每次迭代以鄰域集合作為先驗信息進行一次半監督聚類，并根據當前聚類結果主動選擇一個最有價值的點，查詢該點與鄰域集合中各個鄰域中樣本點的關系，將該點加入到先驗節點集合，指導下一次半監督聚類，直到查詢次數達到給定查詢次數。

IASSCF的初始先驗節點集合中的樣本為隨機選擇。在迭代次數較少時由于先驗信息過少可能導致聚類準確率不高。IASSCF通過主動選擇策略選擇的樣本很大程度上依賴于上一次的聚類結果，因此，迭代初期聚類效果不好會直接導致最終的聚類結果不佳，且在IASSCF框架中每次迭代只選取一個最有價值的點擴充到先驗信息集合中，在給定查詢次數的前提下，存在先驗節點集合擴充過慢、迭代次數過多、算法運行時間過長等問題。鑒于此，使用Rodriguez等[11]提出的選擇代表性較高樣本的方法構建初始先驗節點集合，作為IASSCF框架的初始先驗節點集合, 并將IASSCF框架中每次迭代只選擇一個樣本的主動選擇策略改進為每次迭代基于當前指派結果為每一簇選擇一個信息價值最大的樣本。在以上改進的基礎上，本文提出了IASSCF_PCK-means算法。IASSCF_PCK-means的算法流程在算法3中給出。

算法3 IASSCF_PCK-means(D,k,T,C)。

輸入 數據集D，聚類個數k，給定查詢次數T，成對約束集合C=?；

輸出 聚類結果π。

1)

[N,Tleft,C] = initNeighborhoods(D,k,T,C)

2)

repeat

3)

π= PCK-means(D,k,C)

4)

X= MostInformative(D,π,N)

5)

for 每一個x*∈X

6) 按p(x*∈Ni)從大到小將N中的鄰域重新排序

7)

fori=1 tol

8) 查詢x*和所有xj∈Ni的約束關系

9)

Tleft--；

10)

如果x*和xj滿足must-link約束，則Ni=Ni∪{x*}并更新約束集合C,否則，break；

11)

end for

12)

若x*與N中所有樣本點均無must-link約束，則l++;Nl={x*};N=N∪Nl;

13)

end for

14)

untilTleft≤0

15)

Returnπ

算法3中，在步驟1)構建初始先驗節點集合N。從步驟2)開始進行迭代，在迭代過程中，步驟3)以成對約束集合C為先驗信息，通過PCK-means算法得到聚類結果π。步驟4)通過成對約束集合C和當前聚類結果選擇出最有價值信息的點集合X。對于每個x*∈X，在步驟6)將鄰域集合N重新排序。步驟7)～12)查詢x*與鄰域集合N中各個鄰域中樣本點的約束關系，并將x*加入到鄰域集合N中，同時更新成對約束集合C。步驟13)表示達到迭代停止條件即達到最大可查詢次數時算法結束。迭代停止后輸出最后一次聚類結果即為最終聚類結果。

2 實驗與結果分析

以標準互信息(Normalized Mutual Information, NMI)[13]作為評價指標，對比PCK-means算法、結合PCK-means算法和IASSCF框架的主動半監督聚類算法(下文用IASSCF_old表示)以及IASSCF_PCK-means算法的NMI值，測試迭代框架對聚類結果性能的提升以及改進IASSCF框架后的主動半監督K-means算法的性能; 同時，對比兩種主動半監督算法的運行時間，測試改進IASSCF框架后的IASSCF_PCK-means算法的效率。

實驗中，使用了4組UCI數據集：Iris、Wine、Seeds和Ecoli, 每種數據集的信息如表1所示。針對每個數據集分別給定50、100、150、200、250個可查詢次數，NMI值與運行時間均為程序運行10次的平均結果，具有一定的代表性。

表1 實驗用數據集信息

圖1(a)為三種算法在Iris數據集上的測試結果。橫向上，隨著給定約束對個數的增加，三種算法得出的聚類結果的NMI值均有不同程度的提升。PCK-means算法NMI值提升較為緩慢，但總體呈上升趨勢；IASSCF_PCK-means算法的NMI值提升最為明顯，在給定200個約束對時，NMI值已經達到1；IASSCF_old算法在給定200個約束對時NMI值達到峰值，當給定250個約束對時的NMI值不僅沒有提升，反而與給100個約束對時的NMI值基本持平，這是因為IASSCF_old算法的初始先驗節點為隨機選擇，在迭代初期的聚類效果不理想，影響了后續迭代，從而導致最終聚類結果的NMI值較低。縱向上，兩種基于迭代框架的IASSCF_old算法和IASSCF_PCK-means算法在給定相等的約束對的個數時，NMI值明顯高于PCK-means算法，體現出迭代框架的優越性。

圖1(b)為三種算法在Wine數據集上的測試結果。同樣，可以很明顯看出兩種基于迭代框架算法在給定相同約束對下聚類結果的NMI值要明顯高于PCK-means算法。IASSCF_PCK-means算法隨著約束對個數的增加，NMI值一直處于上升趨勢；IASSCF_old算法在給定約束對大于等于150個時，NMI值基本持平，在程序運行的10次中有少數幾次的聚類結果效果不好導致NMI的平均值較低；與IASSCF_old算法相比，帶有初始先驗節點集合的IASSCF_PCK-means算法的穩定性更好，NMI值更高。

圖1(c)與圖1(d)分別為三種算法在Seeds數據集和Ecoli數據集上的結果。圖中明顯可以看出基于迭代框架的兩個算法IASSCF_old和IASSCF_PCK-means的NMI值高于PCK-means算法，且帶有初始先驗節點集合的算法IASSCF_PCK-means相比IASSCF_old算法更穩定，NMI值更高。

圖1 在不同數據集上給定不同查詢次數的NMI值

圖2為IASSCF_old算法和IASSCF_PCK-means算法在不同數據集上的運行時間對比。IASSCF框架在迭代過程中不斷擴充先驗節點集合，對數據集進行重新聚類，并且每次選擇最具價值信息的樣本時都需要訓練隨機森林、計算樣本間的相似度矩陣等大量的計算過程； IASSCF_old算法每次迭代主動選擇一個最具價值信息的樣本擴充到先驗節點集合； 而IASSCF_PCK-means算法在每次迭代主動選擇每一簇中最具價值信息的樣本將其擴充到先驗節點集合。在給定查詢次數的前提下，IASSCF_PCK-means算法擴充先驗節點集合的速度更快，迭代次數更少，也能夠大幅提高算法的效率。從圖2的統計圖可以看出IASSCF_PCK-means的運行時間約為IASSCF_old的1/k，其中k為聚類個數。

3 結語

基于迭代框架的IASSCF_old算法和IASSCF_PCK-means算法在迭代過程中可以根據上次聚類結果主動選擇節點擴充到先驗節點集合，并根據先驗信息不斷調整聚類，在算法性能上要優于PCK-means算法; 并且加入了初始先驗節點集合的IASSCF_PCK-means算法在穩定性和NMI值上要更優于IASSCF_old算法，同時，由于在每次迭代中選擇多個信息價值較高的樣本點，所以在算法效率上，IASSCF_PCK-means算法要比IASSCF_old算法更高。但是，由于IASSCF框架需要大量的計算過程，相較于普通聚類算法執行效率仍然偏低。針對以上問題，下一步工作將圍繞以下兩方面進行：1)將IASSCF_PCK-means算法遷移到Spark平臺，如訓練隨機森林的過程即可以將訓練每一棵決策樹放到Spark集群的不同節點上，通過并行計算提高算法執行效率；2)將框架中的半監督聚類算法PCK-means替換為其他軟化分聚類方法，通過軟化分得到樣本屬于各個簇的概率，并計算熵值來作為其不確定性度量指標，省去訓練隨機森林的過程，提高算法效率。

圖2 在不同數據集上給定不同查詢次數的運行時間