劉學(xué)文，王繼奎，楊正國，易紀海，李 冰，聶飛平

1.蘭州財經(jīng)大學(xué) 信息工程學(xué)院，蘭州 730020

2.西北工業(yè)大學(xué) 計算機學(xué)院，光學(xué)影像分析與學(xué)習(xí)中心，西安 710072

傳統(tǒng)有監(jiān)督分類利用有標簽的數(shù)據(jù)訓(xùn)練分類器，但是有標簽樣本的獲取通常困難、昂貴或耗時。為了克服有監(jiān)督分類的缺點，建立更具泛化能力和高性能的分類器[1]，研究者提出了半監(jiān)督分類。半監(jiān)督分類屬于半監(jiān)督學(xué)習(xí)（semi-supervised learning，SSL）[2]的范疇，半監(jiān)督學(xué)習(xí)利用大量無標簽數(shù)據(jù)和少量有標簽數(shù)據(jù)，旨在解決人工成本高昂和分類準確性等問題。從20世紀末到21世紀初，半監(jiān)督學(xué)習(xí)領(lǐng)域陸續(xù)出現(xiàn)了許多方法，例如自訓(xùn)練（self-training）[3-8]、直推學(xué)習(xí)（transductive learning）[9-10]、生成式模型（generative model）、協(xié)同訓(xùn)練（co-training）[11-13]等。

Self-Training算法基于自身迭代學(xué)習(xí)，不斷地將高置信度樣本及其預(yù)測標簽加入訓(xùn)練集，如果樣本被誤分類而加進了訓(xùn)練集，此錯誤將會在迭代過程中不斷加深，因此Self-Training算法的效果很大程度上取決于高置信度樣本的識別準確度。文獻[14]提出SETRED算法，通過在相關(guān)鄰近圖（RNG）上統(tǒng)計樣本點割邊權(quán)重（cut edge weight），利用CEW[15]方法選擇高置信度點，其分類性能好，但是該算法構(gòu)造RNG的復(fù)雜度較高。半監(jiān)督分類需要滿足一些基本假設(shè)，常用的基本假設(shè)有平滑假設(shè)（smoothness assumption）、聚類假設(shè)（cluster assumption）和流形假設(shè)（manifold assumption）[16]。文獻[4，17]基于聚類假設(shè)利用FCM算法的類別隸屬度閾值篩選高置信度樣本點，但是當樣本類別數(shù)較多時閾值的設(shè)定較為困難。當前已有研究者將流形學(xué)習(xí)與半監(jiān)督學(xué)習(xí)結(jié)合起來，通常這類半監(jiān)督方法不僅復(fù)雜且參數(shù)調(diào)節(jié)較為繁瑣[18]，對噪聲較為敏感。聚類假設(shè)主要考慮數(shù)據(jù)的整體特性，而流形假設(shè)主要考慮數(shù)據(jù)的局部特性。為兼顧整體與局部特性。文獻[19]提出STDP算法，利用密度峰值[20]潛在的空間結(jié)構(gòu)，先將有標簽樣本的前驅(qū)作為高置信度點，再將有標簽樣本的后繼作為高置信度點。文獻[5]通過設(shè)定局部密度閾值，依次將有標簽樣本中的核心點、邊界點作為高置信度點添加進訓(xùn)練集。上述兩個方法的迭代速度非常快，但是沒有數(shù)據(jù)編輯步驟以去除誤分的高置信度樣本。文獻[21]在文獻[19]的基礎(chǔ)上結(jié)合CEW方法提出STDPCEW算法，利用數(shù)據(jù)編輯技術(shù)對選取的高置信度樣本進一步優(yōu)化，但是STDPCEW和SETRED均需要構(gòu)造RNG，造成算法的整體復(fù)雜度高，難以適用于大規(guī)模數(shù)據(jù)集。

在密度峰值聚類思想的啟發(fā)下，提出了一種近親結(jié)點圖編輯的Self-Training算法（self-training algorithm with editing direct relative node graph-DRNG）。DRNG算法主要工作如下：

（1）利用密度峰值定義樣本間的原型關(guān)系，并構(gòu)造出近親結(jié)點圖這一新型數(shù)據(jù)結(jié)構(gòu)。

（2）采用假設(shè)檢驗的方式識別近親結(jié)點圖中的高置信度樣本。綜合考慮密度與距離兩個方面定義了近親結(jié)點之間割邊的非對稱權(quán)重，減小了高密度樣本點被誤分類的概率。

（3）采用最近鄰（nearest neighbor，NN）分類器作為基分類器，提出了近親結(jié)點圖編輯的Self-Training算法（DRNG），在8個基準數(shù)據(jù)集上進行實驗，實驗結(jié)果驗證了DRNG算法的有效性。

1 相關(guān)工作

1.1 符號

將文中出現(xiàn)的部分符號及其說明列在表1中。

表1 符號及其說明Table 1 Notations and illustrations

1.2 DPC

密度峰值聚類[20]（DPC）是2014年由Rodriguez等人在Science期刊上提出的一種聚類算法，Rodriguez等人給出了兩種計算局部密度的方式，分別為截斷核（cutoff kernel，見公式（1））和高斯核（Gaussian kernel，見公式（2）），樣本xi的局部密度定義為：

樣本xi的峰值定義為：

DPC的機制在于選擇具有較大局部密度和峰值的樣本點作為潛在的類簇中心，在選取類簇中心之后，將剩余非中心點遞歸分配給距離其最近且密度大于它的樣本點完成類簇劃分。

圖1所示為3類別Iris數(shù)據(jù)集的二維投影和對應(yīng)的密度峰值分布決策圖。圖1中子圖（a）和（b）中數(shù)字表示樣本點密度與峰值之積即γ=ρ×δ的大小順序，圖中標記了前5個樣本點。點1的密度和峰值最大被選為類簇1的中心，點2的密度雖然接近于點3～5，但是其峰值明顯大于后者，其被選為類簇2的中心，同理點3被選為類簇3的中心。

DPC的特性在于無需先驗知識選取類簇中心，利用峰值所隱含的層級關(guān)系，低密度點會跟隨高密度點，類簇劃分只需一步，速度極快。通過密度和峰值的層級關(guān)系將空間內(nèi)的樣本點聯(lián)系在一起，不受類簇的形狀約束，能夠在任意形狀分布上進行聚類。因為異常點數(shù)據(jù)的局部密度較小，對類簇中心選取影響較小，難以影響類簇劃分，所以DPC對異常點也不敏感。

圖1 Iris樣本分布和密度峰值分布決策圖Fig.1 Samples distribution of Iris and density peak distribution with decision diagram

DPC也存在一些不可忽視的問題。密度和峰值的計算復(fù)雜度為O(n2)，計算復(fù)雜度高。密度和峰值依賴于距離計算，在高維數(shù)據(jù)上這種相似性度量方式將失效，使得DPC難以發(fā)現(xiàn)數(shù)據(jù)真實結(jié)構(gòu)。截斷距離的取值沒有考慮到樣本局部特性，對于密度不平衡的樣本表現(xiàn)欠佳。近年來，有關(guān)DPC的研究熱度不減，不少研究者對DPC的缺陷進行了改進，例如文獻[22-23]分別從相似性度量和聚類簇中心選擇方面對DPC進行了優(yōu)化。

1.3 Self-Training相關(guān)算法

Self-Training是一種開放性的包裹算法，是非常靈活的學(xué)習(xí)框架，可以嵌入不同的基分類器，也可以采用不同的高置信度樣本選取方案，能適應(yīng)內(nèi)容多樣的半監(jiān)督學(xué)習(xí)任務(wù)。Self-Training的半監(jiān)督分類性能取決于高置信度樣本的選取質(zhì)量和基分類器的性能。Self-Training算法的復(fù)雜度主要由基分類器的訓(xùn)練和預(yù)測以及高置信度樣本的選取這幾個過程所決定。

Self-Training不同于生成模型需要估計參數(shù)，當有標簽樣本稀缺時會得到錯誤的模型；也不同于協(xié)同訓(xùn)練一樣基于特定的、實際情況下不容易滿足的假設(shè)條件。接下來介紹4個相關(guān)的Self-Training算法。

1.3.1 SETRED

SETRED[14]首先從L中訓(xùn)練分類器H，再從U中抽取部分樣本U′，根據(jù)最近鄰規(guī)則（NN Rule），從U′中選取由H標記后的置信度較高的樣本S′，將L?S′作為潛在訓(xùn)練集并構(gòu)造相關(guān)鄰近圖（RNG）。RNG內(nèi)擁有不同樣本標記的兩個頂點所構(gòu)成的邊為割邊（cut edge），RNG內(nèi)與樣本點xi有邊相連的所有樣本點的集合Ni為其近鄰集。若某一樣本點與其近鄰之間存在大量的割邊，則將其視為存疑樣本點。

SETRED利用CEW[15]方法識別S′內(nèi)可能誤標記的樣本，在去除誤標記的樣本后，將更高置信度的樣本S″加入到訓(xùn)練集中。SETRED有效提升了半監(jiān)督分類性能，但其構(gòu)造RNG的過程耗時較長，在規(guī)模較大的數(shù)據(jù)集中受限。

1.3.2 STSFCM

STSFCM[17]通過在Self-Training過程中集成聚類方法，通過聚類發(fā)現(xiàn)無標簽樣本中的潛在空間結(jié)構(gòu)，訓(xùn)練更優(yōu)的分類器。

STSFCM將SSFCM[24-25]和SVM組合，在每次迭代過程中先由SSFCM計算無標簽樣本點xj∈U的隸屬模糊系數(shù)bij,i∈[1,c],c為樣本類簇數(shù)量，ε1為置信度閾值，從中選取b≥ε1的樣本點構(gòu)成無標簽樣本集U′；然后在L上由SVM訓(xùn)練分類器H，由H輸出樣本點xk∈U′的隸屬度fik,ε2為置信度閾值，從U′中取f≥ε2的樣本點構(gòu)成高置信度樣本集合S′。若S′=?則在下一迭代過程中減小ε1的值。

1.3.3 STDP

STDP[19]將DPC[20]算法集成到Self-Training過程中，利用DPC發(fā)現(xiàn)樣本空間潛在的類簇結(jié)構(gòu)，改善分類器性能。STDP首先在L上訓(xùn)練分類器H，選取L內(nèi)樣本點的無標簽前驅(qū)樣本構(gòu)成集合U′，U′?U，由H賦予其標簽構(gòu)成高置信度樣本集S′，更新L←L+S′，U←U-S′，重新訓(xùn)練H；然后再選取L內(nèi)所有樣本點的無標簽后繼構(gòu)成集合U″，U″?U，由H賦予其標簽構(gòu)成高置信度樣本集S″，更新L←L+S″，U←U-S″。

STDP迭代速度非?？欤玈TDP未進行數(shù)據(jù)編輯去除S′和S″內(nèi)的誤分類點，其性能還有提升空間。

1.3.4 STDPCEW

STDPCEW[21]融合了SETRED[14]與STDP[19]算法。依次選取L內(nèi)所有樣本點的無標簽前驅(qū)和后繼樣本作為高置信度樣本S′，在L?S′上構(gòu)造RNG，再利用CEW[15]方法識別并去除S′內(nèi)誤標記點，更新訓(xùn)練集并返回重新訓(xùn)練后的分類器。STDPCEW相比SETRED定義了不同的割邊權(quán)重，其新定義如下：

其中，d(xi,j,xi)表示樣本點xi與在RNG上的第j個近鄰的距離，D(xi,j,xi)表示樣本點xi與在RNG上的第j個近鄰的歸一化距離。

STDPCEW相比STDP新增了數(shù)據(jù)編輯步驟，但其構(gòu)造RNG的過程卻使其復(fù)雜度提升到O(n3)。STDPCEW犧牲計算時間換取了分類性能的提升。

2 近親結(jié)點圖編輯的Self-Training算法

為降低Self-Training算法迭代過程中的高置信度樣本被誤分類的風(fēng)險，提升半監(jiān)督分類性能，本文提出近親結(jié)點圖編輯的Self-Training（DRNG）算法。

DRNG利用DPC[20]獲取樣本集X內(nèi)空間結(jié)構(gòu)潛在的原型關(guān)系。

定義1樣本xi的原型Pi為：

其中，dij=‖xi-xj‖2,ρi和δi分別表示樣本xi的局部密度和峰值。

從定義1可以看出，原型關(guān)系是非對稱的偏序關(guān)系，是一種特殊的帶有方向的近鄰關(guān)系。由DPC的機制和特性可知，峰值融合了距離和密度信息，隱含了低密度點跟隨高密度點的指示關(guān)系，DRNG將這種關(guān)系抽象的表示為原型關(guān)系。

2.1 構(gòu)造原型樹

DRNG利用原型關(guān)系構(gòu)造原型樹，先由公式和計算各樣本點的局部密度ρ和峰值δ，再構(gòu)造出原型樹，步驟如下：

（1）確定根結(jié)點：局部密度最大的樣本點作為根結(jié)點，即根結(jié)點xr須滿足?j,ρr≥ρj。

（2）確定父結(jié)點：結(jié)點xi的原型Pi為其父結(jié)點，即xi的父結(jié)點滿足xj=Pi。

圖2所示為由包含3個類別的高斯分布數(shù)據(jù)所構(gòu)造的原型樹，其中星形、矩形和圓表示不同類別樣本點，為便于展示只選取了處于中心位置的一些結(jié)點。

圖2 原型樹部分結(jié)點Fig.2 Part of prototype tree node

如圖2所示，數(shù)字表示局部密度的大小順序，1表示該樣本點的局部密度最大。箭頭所指向為某一樣本點的原型，如樣本10的原型為9。按照密度由大到小的順序遍歷樣本，確定根結(jié)點和其余樣本的父結(jié)點，構(gòu)造出原型樹。實線箭頭指向相同類別的原型，虛線箭頭指向不同類別的原型。為了利用樣本間的原型關(guān)系來選取高置信度樣本點，定義近親結(jié)點集和近親結(jié)點圖。

定義2樣本xi的近親結(jié)點集Fi為：

由定義2可知，樣本xi的近親結(jié)點集由樣本xi在原型樹上的父親、兄弟和兒子結(jié)點構(gòu)成。近親結(jié)點集Fi中的元素稱為樣本xi的近親。

如圖2所示，樣本點3的近親集合Fi={x2,x4,x5,x6,x16},其中樣本點2是樣本點3的父結(jié)點，樣本點4、5、6是樣本點3的子結(jié)點，而樣本點16為樣本點3的兄弟結(jié)點。。

定義3樣本xi的近親結(jié)點圖Di為：

其中，Vi表示Di的頂點集，Ei表示Di的有向邊集。

由圖2原型樹構(gòu)造圖3樣本點3的近親結(jié)點圖D3。如圖3所示，D3中頂點2、4、5、6和16與頂點3存在有向邊連接，頂點3的出度為5，且E3={x3,x2,x3,x4,x3,x5,x3,x6,x3,x16}。

圖3的子圖（a）是包含樣本點3與近親之間的近親圖，子圖（b）是僅包含有割邊的近親圖。DRNGE利用近親結(jié)點圖來確定高置信度樣本，將識別出的高置信度樣本和其預(yù)測標簽添加到訓(xùn)練集。

圖3 樣本點3的近親結(jié)點圖和割邊Fig.3 Direct relative node graph of sample point 3

2.2 近親結(jié)點圖編輯

與CEW[15]方法一樣，DRNG中一條連接具有不同標簽的兩個頂點的邊為割邊（cut edge），若某個點與大量割邊相聯(lián)系，顯然它的周圍存在大量不同類別的樣本，其被誤分類的概率較大，因此可以對樣本點的割邊權(quán)重進行統(tǒng)計以識別高置信度樣本。DRNG通過統(tǒng)計近親結(jié)點圖中的割邊權(quán)重來識別高置信度樣本。

定義4樣本xi與近親xj之間的割邊權(quán)重qij為：

顯然割邊權(quán)重是非對稱的，即通常情況下qij≠qji，樣本的密度越大，其割邊權(quán)重也越大。

定義5樣本xi的割邊權(quán)重和Ji為：

如果樣本xi和xj屬于同一類別，則Iij=0；否則，Iij=1。DRNG與CEW[15]方法類似，也利用假設(shè)檢驗的方式識別高置信度樣本。

定義6零假設(shè)H0：樣本標記過程互相獨立且服從同一概率分布，為有標簽樣本中第k類樣本集，πk為初始有標簽樣本L內(nèi)的第k類樣本的先驗概率，c為類簇個數(shù)。

假設(shè)Ji近似服從正態(tài)分布，由公式可以計算其在H0下的均值和方差：

其中，πki為樣本xi屬于類別k的先驗概率。

顯然高置信度樣本會有更小比例的不同標簽的近親結(jié)點。因此為更高效地識別高置信度的樣本，采用假設(shè)檢驗的方式，設(shè)定一個顯著性水平θ，凡是落入左拒絕域內(nèi)的樣本將作為高置信度樣本加入到訓(xùn)練集中，而落入左拒絕域右側(cè)的樣本將被丟棄。

在圖2原型樹中，虛線連接不同類別的點，如點8為類2內(nèi)的點，點35為類3內(nèi)的點，這兩個點構(gòu)成的邊即為割邊。通常情況下，Self-Training迭代過程中密度越大的樣本誤分后對分類性能的影響越大。從圖2可以看出，點8的密度顯然大于點35，而點8距離點1和點2非常近，一旦點8被誤分類，很可能將錯誤蔓延至點1、2、7、16和38，從而導(dǎo)致誤分類風(fēng)險增大。

近親結(jié)點圖具有以下三點特性：

（1）存在邊連接的兩個近親結(jié)點是原型樹上的“近鄰”，可能相距較遠而非一般距離空間上的近鄰，比如圖2中點5和點9，這兩個點都位于不同的局部密度中心區(qū)域。

（2）利用原型樹結(jié)構(gòu)中低密度跟隨高密度點這樣一種特性，即使是在非球形分布數(shù)據(jù)上，所獲取的高置信度樣本質(zhì)量仍然比較高。

（3）近親結(jié)點圖中各結(jié)點構(gòu)成的邊為有向邊，兩個結(jié)點之間的邊權(quán)重是非對稱的，密度越大權(quán)重越大。非對稱權(quán)重增大了密度大的樣本點的割邊權(quán)重和，使其落在左拒絕域內(nèi)的概率降低，從而減小大密度點誤分導(dǎo)致跟隨的小密度近親點也被誤分的風(fēng)險。

DRNG與類似Self-Training算法都存在誤分的可能性。STSFCM[17]通過隸屬度閾值過濾掉置信度低的點，但可能由于FCM對于非球形數(shù)據(jù)的聚類效果不理想、初始點選取不當?shù)仍?，?dǎo)致有標簽樣本鄰近的無標簽樣本被誤分；SETRED[14]、STDPCEW[21]和DRNG都采用了CEW方法，當數(shù)據(jù)較少且數(shù)據(jù)分布不太符合假設(shè)的正態(tài)分布時，假設(shè)檢驗的效果可能不理想；STDP[19]、STDPCEW和DRNG都利用了密度峰值發(fā)現(xiàn)潛在空間結(jié)構(gòu)，當數(shù)據(jù)密度不平衡、高維數(shù)據(jù)距離失效或者截斷距離dc設(shè)置不合適時，發(fā)現(xiàn)的空間結(jié)構(gòu)可能與實際結(jié)構(gòu)偏差過大，導(dǎo)致誤分錯誤風(fēng)險累積、高置信度樣本質(zhì)量降低。

2.3 DRNG算法

DRNG算法利用假設(shè)檢驗識別出近親結(jié)點圖中的高置信度樣本，并將高置信度樣本及其預(yù)測標簽添加至訓(xùn)練集，迭代訓(xùn)練分類器。DRNG算法步驟在算法1中列出。

算法1DRNG算法

輸入：有標簽樣本L，無標簽樣本U，已有標簽YL，截斷距離比例閾值α，顯著性水平θ

輸出：分類器H

參數(shù)：左拒絕域閾值τ

1.根據(jù)公式（2）和（3）計算局部密度ρi和峰值δi

2.根據(jù)定義（1）計算樣本的原型Pi并構(gòu)造原型樹T

4.在有標簽樣本集L和YL上訓(xùn)練分類器H

6.在原型樹T中搜索L中樣本的無標簽近親結(jié)點集L′，利用分類器H賦予L′中樣本標簽

7.利用T，在L?L′中構(gòu)造近親結(jié)點圖，計算割邊權(quán)重qij和隨機變量Iij

9.根據(jù)公式和計算E(Ji|H0)和D(Ji|H0)，得到Ji的分布，計算左拒絕域閾值τ

10.若Ji的值落在左拒絕域閾值τ右側(cè)，則將xi從高置信度樣本中移除，L″=L′-xi

11.L←L?L″，重新訓(xùn)練分類器H

12.END WHILE

13.輸出分類器H

令n表示輸入樣本集的規(guī)模。DRNG算法計算ρ的時間復(fù)雜度為O(n2)，計算δ和P的時間復(fù)雜度為O(n2)，構(gòu)造原型樹T的時間復(fù)雜度為O(n2)，構(gòu)造近親結(jié)點圖的時間復(fù)雜度為O(n2)，計算J的時間復(fù)雜度為O(n2)，所以DRNG算法的整體時間復(fù)雜度為O(n2)。相似算法SETRED[14]算法耗時主要在于構(gòu)造RNG，整體時間復(fù)雜度為O(n3)。STSFCM[17]算法耗時主要在于訓(xùn)練SVM，其總體時間復(fù)雜度為O(n3)。STDP[19]算法主要耗時在于計算ρ和δ，其整體時間復(fù)雜度為O(n2)。所以，DRNG與SETRED、STSFCM相比時間復(fù)雜度要小得多，而與STDP相差非常小。

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

3.1 實驗設(shè)置

實驗環(huán)境為Intel?CoreTMi5-8265U CPU@1.8 GHz、16 GB RAM、Win10 64位操作系統(tǒng)、MATALAB R2019a。實驗所使用的PCA算法和NN算法均來自于MATALAB R2019a官方工具箱。

為對DRNG算法的有效性進行驗證，選取了Banknote、German、Heart、Segment、COIL20、MSRA25、ORL和Palm這8個基準數(shù)據(jù)集進行實驗，其中Banknote、German、Heart和Segment這4個數(shù)據(jù)集的維度較低，而COIL20、MSRA25、ORL、Palm這4個圖像數(shù)據(jù)集維度較高。

在選取的8個數(shù)據(jù)集中，涵蓋了樣本量較大的數(shù)據(jù)集和樣本量較小的數(shù)據(jù)集，涵蓋了維度很高的圖像數(shù)據(jù)和維度較低的非圖像數(shù)據(jù)集，不同數(shù)據(jù)集的類別個數(shù)差異也很大，能夠驗證DRNG的有效性。表2對8個數(shù)據(jù)集詳細信息進行了描述。

表2 數(shù)據(jù)集信息Table 2 Information of datasets

圖4展示了2個圖像數(shù)據(jù)集的部分數(shù)據(jù)。每個數(shù)據(jù)集各選取2個類別中的10個樣本展示，每行為同一個類別。圖像數(shù)據(jù)維度較高不便于進行分類實驗，所以統(tǒng)一用PCA把圖像數(shù)據(jù)降到10維，再進行實驗。

對比算法選取近年來相關(guān)的Self-Training算法SETRED[14]、STSFCM[17]、STDP[19]和STDPCEW[21]，以上算法均根據(jù)原文實現(xiàn)。各對比算法的參數(shù)設(shè)置在表3中列出。

如表3所示，SETRED[14]和STDP[19]只有1個參數(shù)，STSFCM[17]、STDPCEW[21]和DRNG有兩個參數(shù)。

圖4 COIL20、MSRA25和ORL代表樣本Fig.4 Representative sample of COIL20，MSRA25 and ORL

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

3.2 實驗結(jié)果分析

對選取的4個算法SETRED[14]、STSFCM[17]、STDPCEW[21]、STDP[19]和DRNG進行對比，5個算法各運行10次。分別在表2中的8個基準數(shù)據(jù)集上進行實驗。

由于COIL20、MSRA25、ORL、Palm這四個圖像數(shù)據(jù)維度較大，已先用PCA將其降到10維，再進行各算法對比實驗。

初始有標簽樣本比例為10%，即訓(xùn)練數(shù)據(jù)集中包含10%的有標簽樣本和90%的無標簽樣本。性能評價指標選取準確率（Accuracy）和F分數(shù)（Fscore-Macro），計算10次運行結(jié)果的準確率和F分數(shù)的平均值（mean）和標準差（std）。實驗結(jié)果如表4、表5所示，每個數(shù)據(jù)集上的算法性能最大值已加粗顯示。

表4的實驗結(jié)果表明，在所選取的Banknote、German和Heart數(shù)據(jù)集上，DRNG的準確率（Accuracy）和F分數(shù)（Fscore）值要高于SETRED、STSFCM，STDP和STDPCEW這4個算法，與排名第2的算法性能相比，DRNG的準確率（Accuracy）分別高出0.06、0.66和0.72個百分點，而STDPCEW僅在Banknote數(shù)據(jù)集上優(yōu)于STDP，在German和Heart數(shù)據(jù)集明顯弱于STDP，可能是因為上述兩個數(shù)據(jù)集上的特征取值范圍差異較大，最大近鄰歸一化距離權(quán)重不太適用于這種情況。在Segment數(shù)據(jù)集上DRNG的準確率分別稍低于SETRED和STDP算法0.45和0.11個百分點，但要高于STSFCM和STDPCEW。

表4 各算法在Banknote、German、Heart和Segment上的性能（mean±std）Table 4 Performance of each algorithm on Banknote，German，Heart and Segment（mean±std）%

表5 各算法在COIL20、MSRA25、ORL和Palm上的性能（mean±std）Table 5 Performance of each algorithm on COIL20，MSRA25，ORL and Palm（mean±std） %

表5的實驗結(jié)果表明，在COIL20和MSRA25這兩個數(shù)據(jù)集上，DRNG的Accuracy和Fscore值要高于SETRED、STSFCM、STDP和STDPCEW這4個算法，與第2名相比，Accuracy分別高了2.03和0.83個百分點。而在這兩個數(shù)據(jù)集上，STSFCM的性能要明顯低于SETRED、STDP和STDPCEW。在ORL和Palm這兩個數(shù)據(jù)集上，DRNG的Accuracy和Fscore值高于SETRED、STDP和STDPCEW，而SETRED要略微低于STDP。從表5可以看出，STSFCM算法在不同數(shù)據(jù)集上的性能差異很大，在ORL和Palm數(shù)據(jù)集上性能較好，而在COIL20和MSRA25數(shù)據(jù)集上則明顯低于對比算法。在類別分布都較為平衡的情況下，Accuracy和Fscore的值趨向于一致。

對8個基準實驗數(shù)據(jù)集上的實驗結(jié)果綜合分析可得：

（1）DRNG算法在Banknote、German、Heart、COIL20和MSRA25數(shù)據(jù)集上性能優(yōu)于對比的SETRED、STSFCM、STDP和STDPCEW算法，在ORL和Palm數(shù)據(jù)集上性能低于STSFCM算法，在Segment數(shù)據(jù)集上各對比算法性能接近。

（2）DRNG算法采用原型樹構(gòu)建近親圖，所選擇的高置信度樣本點質(zhì)量較高，所以，DRNG在Banknote、German、Heart、COIL20、MSRA25、ORL和Palm數(shù)據(jù)集上優(yōu)于同樣采用NN算法作為基分類器的SETRED、STDP和STDPCEW。

（3）DRNG算法采用NN算法作為基分類器，對類簇數(shù)比較小的數(shù)據(jù)集效果更好，而SVM算法對類簇數(shù)比較大的數(shù)據(jù)集性能更好。ORL數(shù)據(jù)集有40個類簇，Palm數(shù)據(jù)集有100個類簇，在這兩個數(shù)據(jù)集上，采用NN算法作為基分類器的方法性能均低于采用SVM算法作為基分類器的STSFCM算法。實驗結(jié)果與理論分析一致。

綜上所述，DRNG算法利用非對稱割邊權(quán)重進行高置信度樣本識別，能夠更好地識別出高置信度樣本，從而降低了自訓(xùn)練迭代過程中的誤分類風(fēng)險，提升了半監(jiān)督分類性能。

3.3 運行時間分析

為對比5個算法的運行耗時，各算法以10%的初始有標簽樣本比例運行10次，計算出平均耗時，表6為各算法的運行時間。

表6 算法運行時間比較Table 6 Algorithm running time comparison s

從表6中的數(shù)據(jù)可以看出，總體上，STDPCEW的耗時接近SETRED，因為復(fù)雜度都為O(n3)，DRNG的耗時接近STDP，因為復(fù)雜度都為O(n2)。SETRED在小數(shù)據(jù)集Banknote、German、Heart和Segment上耗時最長，而在另外四個圖像數(shù)據(jù)COIL20、MSRA25、ORL和Palm上耗時少于STSFCM。STSFCM在較大圖像數(shù)據(jù)集COIL20、MSRA25、ORL和Palm上耗時最長，而在較小數(shù)據(jù)集Banknote、German、Heart和Segment上耗時僅高于STDP，STDP在所有數(shù)據(jù)集上耗時最少，DRNG耗時僅次于STDP。

3.4 參數(shù)研究

DRNG算法涉及超參數(shù)截斷距離比例α和顯著性水平θ。圖5為準確率（Accuracy）和F分數(shù)（Fscore）隨α值變化的情況。圖6為準確率（Accuracy）和F分數(shù)（Fscore）隨α值變化的情況。

（1）α值對分類準確度的影響

α在[0.5,5]區(qū)間內(nèi)取值，步長為0.5。α對應(yīng)截斷距離,d為距離集合。dc的取值影響高置信度樣本選取，過大會導(dǎo)致類簇難以劃分，使近親結(jié)點圖割邊數(shù)量增加，過小導(dǎo)致局部中心點數(shù)量過多，近親結(jié)點過少。

圖5 α值對準確率和F分數(shù)的影響Fig.5 Effect of parameterαto Accuracy and Fscore

圖6 θ值對準確率和F分數(shù)的影響Fig.6 Effect of parameterθto accuracy and Fscore

如圖5所示，在Segment、ORL和Palm數(shù)據(jù)集上α值取0.5時分別獲得了最大的分類準確率95.06%、86.35%和91.43%，而在German和Heart數(shù)據(jù)集上α值取1時分別獲得最大的分類準確率63.77%和56.92%，在Banknote、COIL20和MSRA25數(shù)據(jù)集上，準確率為96.7%～97.2%。小數(shù)據(jù)集如German、Heart和ORL對dc的取值較為敏感，而大數(shù)據(jù)集如Banknote和MSRA25等對dc的取值不太敏感。根據(jù)實驗經(jīng)驗，α的建議取值范圍為[0.5,2]。

（2）θ值對分類準確度的影響

θ表示顯著性水平，θ在[0.05,0.5]區(qū)間內(nèi)取值，步長為0.05。θ的取值過小會使落在拒絕域內(nèi)的樣本點過少，每次迭代過程中獲取的高置信度樣本過少，會丟失一些重要的結(jié)構(gòu)信息。θ的取值過大會使拒絕域范圍擴大，會使高置信度樣本的質(zhì)量降低、誤分類點增加，從而降低分類性能。

由圖6可以看出，在Segment和Palm上，θ值取0.05時分別獲得了最大的分類準確率95.06%和91.43%，在ORL數(shù)據(jù)集上θ值取0.2時準確率為86.35%。而Banknote、German、Heart、COIL20和MSRA25數(shù)據(jù)集對θ的取值不敏感，這是因為原型樹內(nèi)近親結(jié)點已經(jīng)具有較高的置信度，含有非常少的割邊，利用融合密度信息的非對稱割邊權(quán)重檢驗后，即使拒絕域發(fā)生變化，Ji幾乎都落在拒絕域內(nèi)。根據(jù)實驗經(jīng)驗，θ的建議取值范圍為[0.05,0.2]。

4 結(jié)束語

本文提出一種近親結(jié)點圖編輯的Self-Training算法，通過密度峰值定義原型關(guān)系，并構(gòu)造近親結(jié)點圖。在基分類器預(yù)測的有標簽樣本的近親結(jié)點集內(nèi)，定義非對稱割邊權(quán)重，并利用假設(shè)檢驗的方式來識別出高置信度樣本，降低了高密度樣本在Self-Training迭代學(xué)習(xí)過程中的誤分類風(fēng)險。在8個基準數(shù)據(jù)集上和相關(guān)的Self-Training算法進行對比實驗，結(jié)果表明DRNG算法的分類性能整體上優(yōu)于SETRED、STSFCM、STDP和STDPCEW。但該算法仍存在可以繼續(xù)改善的地方，比如峰值和距離計算的方法，尤其是面臨高維數(shù)據(jù)因采樣過于稀疏而導(dǎo)致距離計算失效的問題，這將是下一步工作的重點。