基于主動學(xué)習(xí)先驗的半監(jiān)督K-means聚類算法

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

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

0 引言

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

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

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

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

1 本文算法IASSCF_PCK-means

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

1.1 構(gòu)建初始先驗節(jié)點集合

從數(shù)據(jù)集中選擇若干代表性較高的點，查詢這些點之間的約束關(guān)系(must-link或cannot-link)，構(gòu)建初始先驗節(jié)點集合。

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

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

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

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

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

(1)

其中

(2)

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

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

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

(3)

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

(4)

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

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

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

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

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

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

1)

t=0，l=1

2)

計算截斷距離dc；

3)

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

4)

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

5)

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

6)

N1={reprePoint[1]}

7)

forj=2 tok

8)

for 每個Ni∈N

9)

t++;

10)

查詢reprePoints[j]與所有xi∈Ni的約束關(guān)系。如果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 基于重要性多節(jié)點的主動選擇策略

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

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

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

(5)

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

(6)

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

*p(x∈Ni)

(7)

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

(8)

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

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

輸入 數(shù)據(jù)集D，當(dāng)前聚類指派結(jié)果π，鄰域集合N={N1,N2,…,Nl};

輸出 選定的樣本集合X。

1)

根據(jù)當(dāng)前聚類指派結(jié)果訓(xùn)練隨機森林，并求得樣本間相似度矩陣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中從數(shù)據(jù)集D中隨機選取一個樣本點作為先驗節(jié)點，加入到鄰域集合中，然后開始迭代。每次迭代以鄰域集合作為先驗信息進行一次半監(jiān)督聚類，并根據(jù)當(dāng)前聚類結(jié)果主動選擇一個最有價值的點，查詢該點與鄰域集合中各個鄰域中樣本點的關(guān)系，將該點加入到先驗節(jié)點集合，指導(dǎo)下一次半監(jiān)督聚類，直到查詢次數(shù)達到給定查詢次數(shù)。

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

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

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

輸出 聚類結(jié)果π。

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的約束關(guān)系

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

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

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

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

表1 實驗用數(shù)據(jù)集信息

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

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

圖1(c)與圖1(d)分別為三種算法在Seeds數(shù)據(jù)集和Ecoli數(shù)據(jù)集上的結(jié)果。圖中明顯可以看出基于迭代框架的兩個算法IASSCF_old和IASSCF_PCK-means的NMI值高于PCK-means算法，且?guī)в谐跏枷闰灩?jié)點集合的算法IASSCF_PCK-means相比IASSCF_old算法更穩(wěn)定，NMI值更高。

圖1 在不同數(shù)據(jù)集上給定不同查詢次數(shù)的NMI值

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

3 結(jié)語

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

圖2 在不同數(shù)據(jù)集上給定不同查詢次數(shù)的運行時間