近親結點圖編輯的Self-Training算法

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

1.蘭州財經大學 信息工程學院，蘭州 730020

2.西北工業大學 計算機學院，光學影像分析與學習中心，西安 710072

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

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

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

（1）利用密度峰值定義樣本間的原型關系，并構造出近親結點圖這一新型數據結構。

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

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

1 相關工作

1.1 符號

將文中出現的部分符號及其說明列在表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數據集的二維投影和對應的密度峰值分布決策圖。圖1中子圖（a）和（b）中數字表示樣本點密度與峰值之積即γ=ρ×δ的大小順序，圖中標記了前5個樣本點。點1的密度和峰值最大被選為類簇1的中心，點2的密度雖然接近于點3～5，但是其峰值明顯大于后者，其被選為類簇2的中心，同理點3被選為類簇3的中心。

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

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

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

1.3 Self-Training相關算法

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

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

1.3.1 SETRED

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

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

1.3.2 STSFCM

STSFCM[17]通過在Self-Training過程中集成聚類方法，通過聚類發現無標簽樣本中的潛在空間結構，訓練更優的分類器。

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

1.3.3 STDP

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

STDP迭代速度非?？?，但STDP未進行數據編輯去除S′和S″內的誤分類點，其性能還有提升空間。

1.3.4 STDPCEW

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

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

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

2 近親結點圖編輯的Self-Training算法

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

DRNG利用DPC[20]獲取樣本集X內空間結構潛在的原型關系。

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

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

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

2.1 構造原型樹

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

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

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

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

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

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

定義2樣本xi的近親結點集Fi為：

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

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

定義3樣本xi的近親結點圖Di為：

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

由圖2原型樹構造圖3樣本點3的近親結點圖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利用近親結點圖來確定高置信度樣本，將識別出的高置信度樣本和其預測標簽添加到訓練集。

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

2.2 近親結點圖編輯

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

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

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

定義5樣本xi的割邊權重和Ji為：

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

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

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

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

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

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

近親結點圖具有以下三點特性：

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

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

（3）近親結點圖中各結點構成的邊為有向邊，兩個結點之間的邊權重是非對稱的，密度越大權重越大。非對稱權重增大了密度大的樣本點的割邊權重和，使其落在左拒絕域內的概率降低，從而減小大密度點誤分導致跟隨的小密度近親點也被誤分的風險。

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

2.3 DRNG算法

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

算法1DRNG算法

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

輸出：分類器H

參數：左拒絕域閾值τ

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

2.根據定義（1）計算樣本的原型Pi并構造原型樹T

4.在有標簽樣本集L和YL上訓練分類器H

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

7.利用T，在L?L′中構造近親結點圖，計算割邊權重qij和隨機變量Iij

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

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

11.L←L?L″，重新訓練分類器H

12.END WHILE

13.輸出分類器H

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

3 實驗結果與分析

3.1 實驗設置

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

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

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

表2 數據集信息Table 2 Information of datasets

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

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

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

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

表3 參數設置Table 3 Parameter settings

3.2 實驗結果分析

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

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

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

表4的實驗結果表明，在所選取的Banknote、German和Heart數據集上，DRNG的準確率（Accuracy）和F分數（Fscore）值要高于SETRED、STSFCM，STDP和STDPCEW這4個算法，與排名第2的算法性能相比，DRNG的準確率（Accuracy）分別高出0.06、0.66和0.72個百分點，而STDPCEW僅在Banknote數據集上優于STDP，在German和Heart數據集明顯弱于STDP，可能是因為上述兩個數據集上的特征取值范圍差異較大，最大近鄰歸一化距離權重不太適用于這種情況。在Segment數據集上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的實驗結果表明，在COIL20和MSRA25這兩個數據集上，DRNG的Accuracy和Fscore值要高于SETRED、STSFCM、STDP和STDPCEW這4個算法，與第2名相比，Accuracy分別高了2.03和0.83個百分點。而在這兩個數據集上，STSFCM的性能要明顯低于SETRED、STDP和STDPCEW。在ORL和Palm這兩個數據集上，DRNG的Accuracy和Fscore值高于SETRED、STDP和STDPCEW，而SETRED要略微低于STDP。從表5可以看出，STSFCM算法在不同數據集上的性能差異很大，在ORL和Palm數據集上性能較好，而在COIL20和MSRA25數據集上則明顯低于對比算法。在類別分布都較為平衡的情況下，Accuracy和Fscore的值趨向于一致。

對8個基準實驗數據集上的實驗結果綜合分析可得：

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

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

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

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

3.3 運行時間分析

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

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

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

3.4 參數研究

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

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

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

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

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

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

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

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

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

4 結束語

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