薛子晗，潘 迪，何 麗

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

0 概述

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

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

以上基于圖的改進(jìn)方法雖然能在一定程度上降低算法的時(shí)間復(fù)雜度，但標(biāo)注正確率較低。為保證算法在標(biāo)注正確率上的優(yōu)勢，降低圖的規(guī)模，文獻(xiàn)［14］提出了密度峰值聚類（Density Peaks Clustering，DPC）算法，隨后研究人員在DPC算法的基礎(chǔ)上進(jìn)行優(yōu)化與應(yīng)用，取得了較好的效果［15-17］。但是這些方法都不適用于局部聚類。為使局部聚類方法能夠在不同聚集形態(tài)的數(shù)據(jù)集上都能表現(xiàn)出較好的魯棒性，本文基于DPC算法設(shè)計(jì)一種迭代選擇中心點(diǎn)的密度峰值聚類（Iteration Density Peaks Clustering，IDPC）算法。利用該算法進(jìn)行局部聚類，并運(yùn)用每個(gè)簇的聚類中心為頂點(diǎn)構(gòu)造圖，通過迭代篩選出的聚類中心點(diǎn)表征原始數(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ā)個(gè)已標(biāo)記樣本的標(biāo)簽集合，LGC的學(xué)習(xí)目標(biāo)是利用D與Yl來計(jì)算Du中樣本的標(biāo)簽集合Yu。用表示D中樣本的初始化標(biāo)簽矩陣，其中，c為D中樣本的不同標(biāo)簽數(shù)。將定義為D中樣本對各個(gè)類的概率矩陣，F(xiàn)ij表示xi屬于第j個(gè)類的概率。

W為G中各個(gè)頂點(diǎn)之間的相似度矩陣，wij的計(jì)算方法如式（1）所示：

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

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

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

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

1.2 密度峰值聚類算法

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

其中，dij為樣本xi和xj之間的特征距離，dc是截?cái)嗑嚯x，χ(·)為計(jì)數(shù)函數(shù)，定義如式（5）所示：

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

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

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

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

2 IDPC-LGC方法

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

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

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

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

3）以C中的每個(gè)中心點(diǎn)為聚類中心進(jìn)行局部聚類，得到D上的簇集合CLS=｛CL1，CL2，…，CLP｝。

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

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

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

2.1 基于迭代的中心點(diǎn)選取方法

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

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

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

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

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

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

算法1基于迭代的中心點(diǎn)選取算法

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

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

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

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

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

2.2 基于中心點(diǎn)的局部聚類方法

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

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

算法2基于中心點(diǎn)的局部聚類算法

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

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

為分析數(shù)據(jù)集規(guī)模對算法性能的影響，首先使用代碼生成的雙月數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，噪聲率noise=0.16，標(biāo)記樣本數(shù)固定為16。不同數(shù)據(jù)規(guī)模下各個(gè)算法的標(biāo)注正確率和運(yùn)行時(shí)間對比如圖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算法；在運(yùn)行時(shí)間上，隨著數(shù)據(jù)量的增大，LGC算法的運(yùn)行時(shí)間增幅較快，而本文算法的增幅較小，且遠(yuǎn)低于LGC算法；相對于本文算法，BB-LGC與improved-LGC算法的時(shí)間效率優(yōu)化并不明顯；隨著數(shù)據(jù)量的增大，本文算法在運(yùn)行時(shí)間上的優(yōu)勢越來越明顯，這主要是因?yàn)樵谕惶卣鞣植枷?，?shù)據(jù)規(guī)模越大，數(shù)據(jù)的密集程度就會越高，冗余性變強(qiáng)，這時(shí)利用中心點(diǎn)進(jìn)行聚類可以獲得更好的樣本縮減比，能更有效地降低算法依賴的圖的規(guī)模；LGC-（l0，K）算法的準(zhǔn)確率最低，是因?yàn)樵撍惴ㄊ褂胟-means算法對原始數(shù)據(jù)集進(jìn)行粗分類，但是k-means算法以計(jì)算各個(gè)點(diǎn)到聚類中心的距離為核心，在近似球狀分布的數(shù)據(jù)集上有較好的表現(xiàn)，在雙月數(shù)據(jù)集上表現(xiàn)不佳，因此，LGC-（l0，K）算法的性能受數(shù)據(jù)集中樣本聚集形態(tài)的影響；KNN算法與EEKNN算法的運(yùn)行時(shí)間較短，但在標(biāo)注正確率上表現(xiàn)較差。當(dāng)數(shù)據(jù)集的規(guī)模為n時(shí)，LGC算法的時(shí)間復(fù)雜度為O（n3），而本文算法的時(shí)間復(fù)雜度為O（（n/t）3）+O（n2），t為局部聚類中各個(gè)簇的平均樣本數(shù)，也即在局部聚類時(shí)構(gòu)建圖可以縮減的倍數(shù)。當(dāng)n很大時(shí)，因?yàn)椋╪/t）3＜＜n3，所以本文方法在運(yùn)行時(shí)間上的優(yōu)勢明顯。

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

為進(jìn)一步說明標(biāo)記樣本數(shù)對算法性能的影響，本文使用代碼生成的雙月數(shù)據(jù)集，并選擇噪聲率noise=0.16，樣本規(guī)模n=3 000和多個(gè)不同的標(biāo)記樣本數(shù)進(jìn)行實(shí)驗(yàn)，結(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)記正確率，這是因?yàn)楸疚氖褂玫牡芏确逯稻植烤垲愃惴軌蚝芎玫亟鉀Q類的邊界重疊問題。從圖3（b）可以看出，已標(biāo)記樣本數(shù)的變化對算法的運(yùn)行時(shí)間影響很小，EEKNN與KNN算法雖然在運(yùn)行時(shí)間上優(yōu)于本文算法，但標(biāo)注正確率較低?？傮w上，本文算法在不同已標(biāo)記樣本數(shù)的情況下，在標(biāo)注正確率和運(yùn)行時(shí)間兩個(gè)指標(biāo)上優(yōu)勢明顯。

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

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

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

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

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

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

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

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

從表3和表4可以看出，在4個(gè)數(shù)據(jù)集上本文算法在標(biāo)注正確率上均優(yōu)于LGC、BB-LGC與improved-LGC算法，且LGC算法在數(shù)據(jù)集Flame上的標(biāo)注正確率較低。LGC-（l0，K）雖然在S2與D31兩個(gè)數(shù)據(jù)集上具有最高的標(biāo)注準(zhǔn)確率，但在Flame上表現(xiàn)較差，因?yàn)樵撍惴ㄊ褂胟-means進(jìn)行粗分類，聚類結(jié)果與數(shù)據(jù)集中樣本的聚集形態(tài)有關(guān)。表3的結(jié)果說明，本文算法對不同聚集形態(tài)和規(guī)模的數(shù)據(jù)集都具有較好的適應(yīng)性，魯棒性較好。在運(yùn)行時(shí)間上，本文算法在規(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ùn)行時(shí)間上的優(yōu)勢明顯，并且數(shù)據(jù)集的規(guī)模越大，這種優(yōu)勢將更加明顯，這主要是因?yàn)楸疚氖褂没诘拿芏确逯稻植烤垲惙椒軌蛴行Ы档蚅GC算法依賴的圖的規(guī)模。

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

3.5 參數(shù)討論

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

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

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

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

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

4 結(jié)束語

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