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

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

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

0 引言

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

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

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

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

1 本文算法IASSCF_PCK-means

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

1.1 構(gòu)建初始先驗(yàn)節(jié)點(diǎn)集合

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

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

代表性較高的點(diǎn)需同時(shí)滿足以下兩個(gè)特點(diǎn)：

1)本身的密度大且其周圍樣本點(diǎn)的密度均不超過(guò)它；

2)與其他密度更大的樣本點(diǎn)的距離較遠(yuǎn)。

樣本點(diǎn)密度的計(jì)算公式如下：

(1)

其中

(2)

參數(shù)dc>0為截?cái)嗑嚯x，通過(guò)計(jì)算數(shù)據(jù)集D中不同樣本兩兩之間距離并按升序排序，然后由用戶設(shè)定一個(gè)百分比參數(shù)，dc為該排列的參數(shù)百分比上的數(shù)。后文實(shí)驗(yàn)中設(shè)定的百分比參數(shù)為2%。

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

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

(3)

如果xi是樣本集D中密度最大的樣本點(diǎn)，則:

(4)

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

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

1)

t=0，l=1

2)

計(jì)算截?cái)嗑嚯xdc；

3)

計(jì)算D中所有樣本點(diǎn)的ρ值；

4)

計(jì)算D中所有樣本點(diǎn)的δ值；

5)

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

6)

N1={reprePoint[1]}

7)

forj=2 tok

8)

for 每個(gè)Ni∈N

9)

t++;

10)

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

11)

end for

12)

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

13) end for

14)

Return N;Tleft=T-t;C

1.2 基于重要性多節(jié)點(diǎn)的主動(dòng)選擇策略

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

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

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

(5)

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

(6)

2)查詢開(kāi)銷的期望是基于式(5)的計(jì)算結(jié)果。通過(guò)式(5)已求得樣本x屬于鄰域集合N中各個(gè)鄰域的概率, 由于給定查詢次數(shù)有限，因此應(yīng)力求消耗更少的查詢次數(shù)來(lái)確定x與各個(gè)鄰域的關(guān)系。通過(guò)式(5)的計(jì)算結(jié)果的值按照降序?qū)⒏鱾€(gè)鄰域重新編號(hào)，即排序后滿足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)

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

(8)

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

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

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

輸出 選定的樣本集合X。

1)

根據(jù)當(dāng)前聚類指派結(jié)果訓(xùn)練隨機(jī)森林，并求得樣本間相似度矩陣M

2)

for 每個(gè)x∈D，且x?N

3)

fori=1 tol

4)

通過(guò)式(5)計(jì)算p(x∈Ni)

5)

end for

6)

通過(guò)式(6)計(jì)算H(N|x)

7)

通過(guò)式(7)計(jì)算E[q(x)]

8)

end for

9)

通過(guò)式(8)計(jì)算X

10)

ReturnX

1.3 算法描述

IASSCF中從數(shù)據(jù)集D中隨機(jī)選取一個(gè)樣本點(diǎn)作為先驗(yàn)節(jié)點(diǎn)，加入到鄰域集合中，然后開(kāi)始迭代。每次迭代以鄰域集合作為先驗(yàn)信息進(jìn)行一次半監(jiān)督聚類，并根據(jù)當(dāng)前聚類結(jié)果主動(dòng)選擇一個(gè)最有價(jià)值的點(diǎn)，查詢?cè)擖c(diǎn)與鄰域集合中各個(gè)鄰域中樣本點(diǎn)的關(guān)系，將該點(diǎn)加入到先驗(yàn)節(jié)點(diǎn)集合，指導(dǎo)下一次半監(jiān)督聚類，直到查詢次數(shù)達(dá)到給定查詢次數(shù)。

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

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

輸入 數(shù)據(jù)集D，聚類個(gè)數(shù)k，給定查詢次數(shù)T，成對(duì)約束集合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 每一個(gè)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中所有樣本點(diǎn)均無(wú)must-link約束，則l++;Nl={x*};N=N∪Nl;

13)

end for

14)

untilTleft≤0

15)

Returnπ

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

2 實(shí)驗(yàn)與結(jié)果分析

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

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

表1 實(shí)驗(yàn)用數(shù)據(jù)集信息

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

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

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

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

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

3 結(jié)語(yǔ)

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

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