結(jié)合改進密度峰值聚類的LGC半監(jiān)督學(xué)習(xí)方法優(yōu)化

薛子晗，潘 迪，何 麗

（天津財經(jīng)大學(xué)理工學(xué)院，天津 300222）

0 概述

強監(jiān)督的機器學(xué)習(xí)方法需要大量有標(biāo)簽數(shù)據(jù)的支持，但隨著大數(shù)據(jù)時代應(yīng)用領(lǐng)域數(shù)據(jù)量的日益膨脹，通常獲得的是大量的無標(biāo)簽數(shù)據(jù)。因此，半監(jiān)督學(xué)習(xí)成為模式識別和機器學(xué)習(xí)領(lǐng)域的一個新的研究熱點。半監(jiān)督學(xué)習(xí)介于監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)之間，是通過少量標(biāo)記樣本對大量未標(biāo)記樣本進行標(biāo)注的一種學(xué)習(xí)方法［1］?；趫D的半監(jiān)督學(xué)習(xí)是該研究領(lǐng)域極具代表性的一種方法，在樣本標(biāo)注正確率上具有明顯優(yōu)勢。

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

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

1 相關(guān)理論

1.1 局部與全局一致性算法

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

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

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

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

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

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

1.2 密度峰值聚類算法

傳統(tǒng)DPC算法假設(shè)聚類中心比其臨近點的局部密度更高，且與其他聚類中心的距離較遠(yuǎn)。在這種假設(shè)下，若要選取聚類中心，首先需要計算數(shù)據(jù)集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的樣本個數(shù)。xi的局部密度ρi的計算方法如式（4）所示：

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

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

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

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

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

2 IDPC-LGC方法

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

IDPC-LGC算法實現(xiàn)的主要步驟如下：

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

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

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

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

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

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

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

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

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

1）屬于不同類的中心點之間的距離應(yīng)盡可能遠(yuǎn)，使篩選出來的中心點盡量遠(yuǎn)離類邊界。

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

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

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

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

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

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

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

圖1 原始數(shù)據(jù)與中心點的比較結(jié)果Fig.1 Comparison result of raw data and central points

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

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

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

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

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

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

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

3.1 實驗設(shè)計

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

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

3.2 數(shù)據(jù)集規(guī)模對算法性能的影響

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

圖2 數(shù)據(jù)集規(guī)模對算法性能的影響Fig.2 Effect of dataset size on algorithm performance

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

3.3 標(biāo)記樣本數(shù)對算法性能的影響

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

圖3 標(biāo)記樣本數(shù)對算法性能的影響Fig.3 Effect of labeled sample number on algorithm performance

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

3.4 數(shù)據(jù)集樣本的聚集形態(tài)對算法性能的影響

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

表1 數(shù)據(jù)集屬性Table 1 Dataset attribute

IDPC-LGC算法在各個數(shù)據(jù)集上使用的參數(shù)設(shè)置和產(chǎn)生的中心點數(shù)如表2所示。

表2 參數(shù)設(shè)置Table 2 Parameter settings

表3和表4比較了各算法在4個數(shù)據(jù)集上的標(biāo)注正確率和運行時間。

表3 標(biāo)注正確率結(jié)果比較Table 3 Comparison of labeling accuracy results %

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

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

實驗結(jié)果顯示，本文提出的IDPC-LGC算法在不同規(guī)模、不同標(biāo)記樣本數(shù)和不同聚集形態(tài)的數(shù)據(jù)集上，都能在標(biāo)注正確率和運行時間兩個評價指標(biāo)上保持較好的優(yōu)勢。

3.5 參數(shù)討論

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

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

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

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

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

4 結(jié)束語

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