基于高密度近鄰和確定性標(biāo)記樣本選擇的標(biāo)簽傳播算法

摘" 要：半監(jiān)督學(xué)習(xí)由于能夠充分利用未標(biāo)記數(shù)據(jù)而廣受關(guān)注，其中圖半監(jiān)督學(xué)習(xí)方法具有表示直觀和概念清晰的優(yōu)點(diǎn)。然而，基于圖的半監(jiān)督學(xué)習(xí)方法大多需要迭代優(yōu)化，且由于初始標(biāo)記點(diǎn)的選取變化，會(huì)導(dǎo)致預(yù)測準(zhǔn)確性不穩(wěn)定。為了解決這一問題，提出了一種基于高密度近鄰和確定性標(biāo)記（high density nearest neighbors and determinate labeling， HDN-DL）的半監(jiān)督分類方法，利用數(shù)據(jù)中的潛在結(jié)構(gòu)和信息，選擇影響力較高的節(jié)點(diǎn)作為標(biāo)簽傳播的起點(diǎn)，通過密度峰值聚類算法（density peak clustering， DPC）得到初始的無監(jiān)督聚類圖結(jié)構(gòu)后，將該圖斷開得到引領(lǐng)森林，再根據(jù)每個(gè)樣本點(diǎn)的所在層次計(jì)算其高密度近鄰及其相對(duì)距離，以此來綜合考慮多個(gè)屬性以判定當(dāng)前樣本的標(biāo)簽，避免級(jí)聯(lián)誤分。標(biāo)簽傳播的過程無需迭代，復(fù)雜度為O（n）。在多個(gè)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)驗(yàn)證了該方法的有效性和穩(wěn)定性。

關(guān)鍵詞：圖半監(jiān)督學(xué)習(xí);密度峰值聚類;引領(lǐng)森林;高密度近鄰;確定性標(biāo)記

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)" 1000-5269（2025）01-0060-09

DOI：10.15958/j.cnki.gdxbzrb.2025.01.09

收稿日期：2024-04-19

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61966005，62366008）

作者簡介：任" 剛（1996—），男，在讀碩士，研究方向：機(jī)器學(xué)習(xí)，E-mail：rengang_33@163.com.

*通訊作者：徐" 計(jì)，E-mail：jixu@gzu.edu.cn.

在當(dāng)今信息時(shí)代，數(shù)據(jù)的快速增長和獲取已經(jīng)成為一種常態(tài)，隨之而來的是對(duì)這些海量數(shù)據(jù)的高效處理和分析的需求。機(jī)器學(xué)習(xí)作為一種強(qiáng)大的工具，為應(yīng)對(duì)這一挑戰(zhàn)提供了有效的解決方案。在機(jī)器學(xué)習(xí)領(lǐng)域，監(jiān)督學(xué)習(xí)在標(biāo)注數(shù)據(jù)上表現(xiàn)出色。然而，相比于未標(biāo)注數(shù)據(jù)，獲取標(biāo)注數(shù)據(jù)通常是耗時(shí)并且昂貴的。因此，半監(jiān)督學(xué)習(xí)［1-3］逐漸成為解決實(shí)際問題中標(biāo)記數(shù)據(jù)相對(duì)較少且標(biāo)注困難的有效手段。半監(jiān)督學(xué)習(xí)有許多類別，包括混合模型［4］、協(xié)同訓(xùn)練［5］、半監(jiān)督支持向量機(jī)［6］和基于圖的半監(jiān)督學(xué)習(xí)［7］等，本文重點(diǎn)研究基于圖的半監(jiān)督學(xué)習(xí)。

圖半監(jiān)督學(xué)習(xí)的主要優(yōu)點(diǎn)是能夠充分利用標(biāo)注數(shù)據(jù)和未標(biāo)注數(shù)據(jù)之間的圖結(jié)構(gòu)關(guān)系，為模型提供更多的學(xué)習(xí)信號(hào)，以提高模型性能［8］。通常，圖模型將每個(gè)樣本視為頂點(diǎn)，標(biāo)簽傳播算法將已標(biāo)記節(jié)點(diǎn)作為起點(diǎn)，通過節(jié)點(diǎn)之間的連接迭代地傳播標(biāo)簽。在每次迭代中，節(jié)點(diǎn)會(huì)考慮其鄰居節(jié)點(diǎn)的標(biāo)簽，然后更新自己的標(biāo)簽，直到標(biāo)簽在整個(gè)圖中趨于穩(wěn)定。如今，一些經(jīng)典的基于圖的半監(jiān)督學(xué)習(xí)模型：高斯場調(diào)和函數(shù)（GFHF）［9］、局部和全局一致性（LGC）［10］、線性投影（LDA）［11］、鄰域成分分析（NCA）［12］，因隨機(jī)初始化而難有穩(wěn)定的表現(xiàn)，因此引入了DPC算法［13］，實(shí)現(xiàn)尋找更優(yōu)初始化節(jié)點(diǎn)的目的。

DPC算法在2014年提出，時(shí)至今日，人們對(duì)其研究的熱度只增不減。DPC聚類算法無需預(yù)先設(shè)定簇?cái)?shù)量。通過計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度和相對(duì)距離，該算法能夠自動(dòng)識(shí)別潛在簇中心，即密度峰值點(diǎn)。這些峰值點(diǎn)對(duì)應(yīng)于數(shù)據(jù)集中的高密度區(qū)域，反映出簇的核心，并通過相對(duì)距離判定數(shù)據(jù)點(diǎn)的簇分配實(shí)現(xiàn)聚類過程。密度峰值聚類算法具有不同于傳統(tǒng)算法的先驗(yàn)假設(shè)，以及對(duì)不規(guī)則簇結(jié)構(gòu)的適應(yīng)性，因此在處理真實(shí)世界的復(fù)雜數(shù)據(jù)時(shí)表現(xiàn)出色，同時(shí)，其獨(dú)特的性質(zhì)使其在各領(lǐng)域的模式識(shí)別和數(shù)據(jù)挖掘任務(wù)中備受關(guān)注。SHU等［14］結(jié)合密度峰值聚類方法提出了一種新的半監(jiān)督三維形狀分割方法，其能在簡化標(biāo)簽傳播過程的同時(shí)確保標(biāo)簽的高質(zhì)量。TAO等［15］提出了基于密度峰值聚類的半監(jiān)督費(fèi)歇爾判別法：采用DPC生成標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)的偽聚類標(biāo)簽，對(duì)生成的偽標(biāo)簽進(jìn)行探索，構(gòu)建了2種正則化策略，并對(duì)局部費(fèi)歇爾判別分析的類內(nèi)和類間散射矩陣進(jìn)行正則化，最終通過求解局部費(fèi)歇爾判別的目標(biāo)函數(shù)得到最優(yōu)投影向量。TU等［16］提出了一種基于空間密度峰值聚類的方法來檢測訓(xùn)練集中的錯(cuò)誤標(biāo)記樣本。MA等［17］提出了一種基于空間向量搜索的密度峰值聚類（VS-DPC）算法：在n維正交坐標(biāo)系中將數(shù)據(jù)點(diǎn)映射為以原點(diǎn)為起點(diǎn)的空間向量，計(jì)算向量的模和統(tǒng)一坐標(biāo)軸正方向間的夾角；利用截?cái)嗑嚯x和截?cái)嘤成浣谴_定相似范圍搜索相似向量；利用相似向量確定有效密度點(diǎn)從而構(gòu)建稀疏相似度矩陣，降低時(shí)間復(fù)雜度。XU等［18］提出的LaPOLeaF算法同樣基于DPC算法，它將DPC的初始聚類結(jié)果轉(zhuǎn)化為樹結(jié)構(gòu)，然后進(jìn)行3個(gè)階段的標(biāo)簽傳播：先將標(biāo)簽從子節(jié)點(diǎn)傳播到父節(jié)點(diǎn)，接著從一棵子樹的根節(jié)點(diǎn)傳播到另一棵子樹的根節(jié)點(diǎn)，最后從父節(jié)點(diǎn)傳播到孩子節(jié)點(diǎn)。然而，這些方法通常都存在2個(gè)問題：一是忽略了高密度節(jié)點(diǎn)引領(lǐng)低密度節(jié)點(diǎn)這一核心思想，如LaPOLeaF算法中存在用低密度節(jié)點(diǎn)指導(dǎo)高密度節(jié)點(diǎn)的情況；二是難以處理由于某些節(jié)點(diǎn)的標(biāo)簽傳播錯(cuò)誤導(dǎo)致一連串標(biāo)簽錯(cuò)誤。因此，本文提出了高密度近鄰的概念，在遵守高密度指向的思想下，努力解決部分標(biāo)簽錯(cuò)誤帶來的連鎖反應(yīng)。

在DPC算法的基礎(chǔ)上，將DPC的聚類結(jié)果看作“引領(lǐng)樹”的思想［19］，并綜合考慮高密度近鄰節(jié)點(diǎn)對(duì)低密度節(jié)點(diǎn)標(biāo)簽指導(dǎo)的算法，本文提出基于高密度近鄰和確定性標(biāo)記（high density nearest neighbors and determinate labeling， HDN-DL）的半監(jiān)督分類方法。在實(shí)驗(yàn)部分，將本文方法與現(xiàn)有的基于圖的半監(jiān)督學(xué)習(xí)方法進(jìn)行比較，驗(yàn)證了HDN-DL方法的有效性。此外，還在水質(zhì)數(shù)據(jù)集上進(jìn)行了回歸預(yù)測任務(wù)，取得了良好的效果。最后，對(duì)影響算法模型的幾個(gè)主要參數(shù)進(jìn)行了參數(shù)敏感性測試，并分析了它們對(duì)模型性能的影響的方式及程度。

1" 相關(guān)工作

1.1" 密度峰值聚類算法

DPC算法主要基于2個(gè)假設(shè)：一是類簇中心周圍會(huì)有更多的點(diǎn)，導(dǎo)致其密度比周圍的點(diǎn)大；二是類簇中心到比它密度更大的點(diǎn)的距離相對(duì)其他點(diǎn)會(huì)更遠(yuǎn)。DPC算法的主要流程如下：

1）給定數(shù)據(jù)集X={x1，x2，…，xn}，計(jì)算樣本間距離矩陣：

D={di，j1≤i≤n，1≤j≤n}（1）

式中：di，j為樣本xi與樣本xj之間的距離，可以使用任意距離度量計(jì)算，在HDN-DL算法中使用歐式距離作為度量。

2）計(jì)算每個(gè)樣本的局部密度。xi，xj∈X，xi的局部密度計(jì)算如下：

ρi=∑j∈I＼{i}χ（di，j－dc），χ（x）=1，xlt;00，x≥0 （2）

ρi=∑j∈I＼{i}e－（di，jdc）2（3）

式中：I為數(shù)據(jù)的下標(biāo)集；dc為截?cái)嗑嚯x。其中，式（2）為截?cái)嗪说木植棵芏榷x方式，式（3）為高斯核的局部密度定義方式。本文采用高斯核的局部密度定義方式計(jì)算樣本局部密度。

3）得到每個(gè)樣本的局部密度ρi后，將向量ρ=（ρ1，ρ2，…，ρn）按降序排列，得到新的下標(biāo)向量Q=（q1，q2，…，qn），使得ρq1≥ρq2≥…≥ρqn。為每個(gè)樣本（密度最大的樣本除外）計(jì)算其通往密度更高的數(shù)據(jù)點(diǎn)的最近距離δ=（δ1，δ2，…，δn），公式如下：

δqi=mini≥j {dqi，qj}，i≥2

maxj≥2{dqi，qj}，i=1（4）

式中：q1為對(duì)應(yīng)局部密度最大的數(shù)據(jù)點(diǎn)；δq1為與該點(diǎn)相距最遠(yuǎn)的點(diǎn)所對(duì)應(yīng)的距離。

4） 節(jié)點(diǎn)xi的父節(jié)點(diǎn)用Pi表示，則Pi為密度比節(jié)點(diǎn)xi更高且距其最近的點(diǎn)。形式化描述公式如下：

Pi=0，" if" i=q1

j，" if" i≠q1" and" δi=di，j （5）

5） 計(jì)算每個(gè)節(jié)點(diǎn)的決策值γ，xi∈X，xi的決策

γi=ρiδi（6）

選取γ值較大的節(jié)點(diǎn)作為初始聚類中心，根據(jù)密度的指向分配樣本點(diǎn)的類簇。

1.2" 引領(lǐng)森林

引領(lǐng)森林是對(duì)DPC算法得到的聚類結(jié)果的一種新穎理解。DPC算法是構(gòu)造圖的過程，它為每個(gè)節(jié)點(diǎn)（密度最大的節(jié)點(diǎn)除外）尋找其最近的一個(gè)高密度父節(jié)點(diǎn)。因此，每一個(gè)節(jié)點(diǎn)都可以看作是被其他更高密度的節(jié)點(diǎn)引領(lǐng)到圖中。決策值γ較大的節(jié)點(diǎn)，所對(duì)應(yīng)的δ值通常也較大，它是被距離相對(duì)較遠(yuǎn)的點(diǎn)引領(lǐng)到圖中，因此這2個(gè)點(diǎn)的相關(guān)性其實(shí)較小。在DPC算法中選擇γ較大的點(diǎn)作為初始聚類中心也能說明這一點(diǎn)。

將決策值較大的點(diǎn)與其父節(jié)點(diǎn)的連接斷開，就得到引領(lǐng)森林，其中每一棵樹，稱之為引領(lǐng)樹。

2" HDN-DL算法

HDN-DL算法在引領(lǐng)森林的基礎(chǔ)上引入了高密度鄰域和節(jié)點(diǎn)層次的概念，以實(shí)現(xiàn)DPC算法中利用高密度節(jié)點(diǎn)指導(dǎo)低密度節(jié)點(diǎn)的核心思想。此外，通過選擇決策值高的標(biāo)簽傳播起始節(jié)點(diǎn)，確保了聚類的準(zhǔn)確性和魯棒性，提高了算法的性能。

算法在DPC算法的基礎(chǔ)上得到初始圖后，通過決策值γ將其斷開，得到引領(lǐng)森林。接著選取影響力最強(qiáng)的標(biāo)簽傳播起始節(jié)點(diǎn)，綜合考慮節(jié)點(diǎn)所在層次以及其高密度近鄰的標(biāo)簽，為無標(biāo)記節(jié)點(diǎn)賦予置信度最高的標(biāo)簽。整個(gè)過程從上至下，逐層推進(jìn)。

由于高密度鄰域及節(jié)點(diǎn)層次的引入，該算法具備在一定程度上避免級(jí)聯(lián)誤分的能力，有效解決傳統(tǒng)算法中一個(gè)節(jié)點(diǎn)錯(cuò)誤分類導(dǎo)致連鎖錯(cuò)誤的問題。標(biāo)簽傳播的過程如圖1所示。圖1中：（a）為MNIST數(shù)據(jù)集中的一個(gè)子集，每個(gè)圖片的下方是其對(duì)應(yīng)的編號(hào)。（b）是MNIST樣本子集經(jīng)過LLE［20］ 降維后在二維空間中的分布。 （c）為將其構(gòu)造為引領(lǐng)樹結(jié)構(gòu)的示意圖，其中節(jié)點(diǎn)2、節(jié)點(diǎn)9和節(jié)點(diǎn)10為標(biāo)簽傳播的初始節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)用黑色帶箭頭的實(shí)線指向其父節(jié)點(diǎn)。在本次標(biāo)簽傳播的過程中，幾乎所有節(jié)點(diǎn)的標(biāo)簽都與其父節(jié)點(diǎn)的相同，但節(jié)點(diǎn)5除外。（d）展示HDN-DL算法的標(biāo)簽傳播。在傳統(tǒng)的DPC算法和LaPOLeaf算法中，節(jié)點(diǎn)5是節(jié)點(diǎn)1的孩子節(jié)點(diǎn)，節(jié)點(diǎn)5的預(yù)測標(biāo)簽將與節(jié)點(diǎn)1的相同，導(dǎo)致節(jié)點(diǎn)的錯(cuò)誤劃分。與之不同的是，HDN-DL算法能夠根據(jù)節(jié)點(diǎn)的高密度近鄰及其相對(duì)距離進(jìn)行綜合考慮，再預(yù)測其標(biāo)簽。用紅色實(shí)線和紅色虛線表示該節(jié)點(diǎn)的高密度鄰域。其中，紅色實(shí)線指向該節(jié)點(diǎn)的父節(jié)點(diǎn)（父節(jié)點(diǎn)必定屬于該節(jié)點(diǎn)的高密度近鄰），紅色虛線指向其他的高密度近鄰節(jié)點(diǎn)。在本例中，節(jié)點(diǎn)5的高密度近鄰有節(jié)點(diǎn)1、8、7，節(jié)點(diǎn)8和節(jié)點(diǎn)7對(duì)于該節(jié)點(diǎn)標(biāo)簽決策的貢獻(xiàn)之和大于單獨(dú)的節(jié)點(diǎn)1，至此，該方法為節(jié)點(diǎn)8傳播了正確的標(biāo)簽。并且，若節(jié)點(diǎn)5擁有孩子節(jié)點(diǎn)，DPC算法和LaPOLeaf算法會(huì)出現(xiàn)級(jí)聯(lián)誤分的情況，而HDN-DL算法能進(jìn)行正確的傳播。

2.1" 節(jié)點(diǎn)層次

在得到DPC的初始聚類結(jié)果后，根據(jù)決策值γ將其斷開，得到引領(lǐng)森林。至此，除了每棵樹的根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)。節(jié)點(diǎn)xi的層次用layeri表示，根節(jié)點(diǎn)的所在層次為1，它的孩子節(jié)點(diǎn)層次為2，以此類推，能夠得到所有節(jié)點(diǎn)的所在層次。通過研究發(fā)現(xiàn)，越接近根的節(jié)點(diǎn)通常越穩(wěn)定，即根節(jié)點(diǎn)的周圍節(jié)點(diǎn)通常都與它屬于同一類別。

2.2" 高密度近域

在機(jī)器學(xué)習(xí)領(lǐng)域中，有許多關(guān)于近鄰的研究，如最近鄰［21］、共享近鄰［22］、自然鄰居［23］等。不同于這些思想，考慮到在引領(lǐng)森林中，樹的構(gòu)成是基于密度指向的，本文提出了高密度近鄰這一概念：節(jié)點(diǎn)xi的高密度鄰域?yàn)槊芏却笥谒墓?jié)點(diǎn)集合，其中k個(gè)最近的節(jié)點(diǎn)，即為節(jié)點(diǎn)xi的高密度近鄰，k取決于節(jié)點(diǎn)所在層次。節(jié)點(diǎn)xi的高密度近鄰集合Ω（xi）計(jì)算式如下：

Ω（xi）=Topk（Sort（xj∈Xρjgt;ρi，di，j））（7）

k=layeri－1，" if" layeri≤44，" if" layerigt;4" （8）

對(duì)于根節(jié)點(diǎn)，由于其擁有較高的穩(wěn)定性，用于指導(dǎo)低密度點(diǎn)的標(biāo)簽決策；對(duì)于非根節(jié)點(diǎn)，根據(jù)當(dāng)前節(jié)點(diǎn)所在層次，找到相應(yīng)數(shù)量的高密度近鄰節(jié)點(diǎn)。節(jié)點(diǎn)所在層次越接近根節(jié)點(diǎn)，它所需要的指導(dǎo)越少，相反，當(dāng)其所在層次較深時(shí)，需要更多的高密度近鄰來幫助其進(jìn)行標(biāo)簽決策；但由于深層節(jié)點(diǎn)的高密度近鄰所在層次通常也較大，穩(wěn)定性較差，因此不宜選擇太多。此外，根據(jù)偏序關(guān)系，不同的近鄰對(duì)其標(biāo)簽決策的貢獻(xiàn)是不同的。

2.3" 確定性標(biāo)記樣本選擇與標(biāo)簽傳播

研究表明，隨機(jī)選擇初始訓(xùn)練樣本會(huì)導(dǎo)致標(biāo)簽傳播算法性能的不穩(wěn)定。受密度峰值聚類算法的啟發(fā)，提出了選擇決策值高的節(jié)點(diǎn)作為標(biāo)簽傳播的初始節(jié)點(diǎn)的方法。經(jīng)驗(yàn)證，該方法能有效地提高算法的性能與穩(wěn)定性。此外，在DPC及其衍生算法中，由于非中心節(jié)點(diǎn)的簇分配只取決于它的父節(jié)點(diǎn)，會(huì)導(dǎo)致級(jí)聯(lián)誤分［24］。因此，綜合考慮了多個(gè)高密度近鄰并根據(jù)距離定義權(quán)重，為節(jié)點(diǎn)賦予標(biāo)簽。

給定數(shù)據(jù)集X={x1，x2，…，xn}，以及對(duì)應(yīng)的標(biāo)簽集合y={y1，y2，…，yc}，xi屬于每類標(biāo)簽的權(quán)重的計(jì)算方法如下：

y（xi）=argmaxm∑y（xj）=ymxj∈Ω（xi）idi，j（9）

i=∑xj∈Ω（xi）di，jΩ（xi）（10）

式中：xj為節(jié)點(diǎn)xi的高密度近鄰中標(biāo)簽為ym的節(jié)點(diǎn)集合；i為節(jié)點(diǎn)xi到其高密度近鄰集合的平均距離；·為基數(shù)運(yùn)算符，計(jì)算集合中元素的數(shù)量。

2.4" 算法描述

基于高密度近鄰集合確定性標(biāo)記的標(biāo)簽傳播方法，從引領(lǐng)樹的根節(jié)點(diǎn)開始，逐層地進(jìn)行標(biāo)簽傳播。具體算法步驟如下：

輸入：數(shù)據(jù)集X，樣本類別C，截?cái)嗑嚯xdc，引領(lǐng)樹數(shù)量lt_num，標(biāo)簽傳播初始節(jié)點(diǎn)數(shù)量l；

輸出：無標(biāo)簽節(jié)點(diǎn)的預(yù)測標(biāo)簽y。

Step 1" 由式（1）～（6）構(gòu)造初始的圖結(jié)構(gòu)；

Step 2" 選擇γ值較大的lt_num個(gè)節(jié)點(diǎn)作為引領(lǐng)樹的根節(jié)點(diǎn)，斷開根節(jié)點(diǎn)與其父節(jié)點(diǎn)的連接，得到引領(lǐng)森林及節(jié)點(diǎn)層次；

Step 3" 根據(jù)節(jié)點(diǎn)所在層次，由式（7）和式（8）計(jì)算節(jié)點(diǎn)的高密度近鄰；

Step 4" 為每個(gè)類別選擇一個(gè)或多個(gè)γ值較大的節(jié)點(diǎn)作為標(biāo)簽傳播的起始節(jié)點(diǎn)，共選擇l個(gè)，根據(jù)式（9）和式（10）逐層進(jìn)行標(biāo)簽傳播；

Step 5" 返回預(yù)測標(biāo)簽y。

2.5" 算法時(shí)間復(fù)雜度

HDN-DL算法主要由兩部分組成，一是引領(lǐng)森林的構(gòu)造，二是標(biāo)簽傳播。其中最耗時(shí)的是第一步中計(jì)算樣本間距離矩陣D，復(fù)雜度為O（n2）。在HDN-DL算法中，將其轉(zhuǎn)化為矩陣計(jì)算而非成對(duì)地計(jì)算每兩個(gè)樣本的距離，降低了數(shù)據(jù)維度對(duì)計(jì)算時(shí)間的影響，有效地減少了該部分的計(jì)算耗時(shí)。標(biāo)簽傳播的過程，在每棵引領(lǐng)樹上逐層推進(jìn)，復(fù)雜度為O（n） 。因此，該算法的時(shí)間復(fù)雜度為O（n2）。

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

3.1" 實(shí)驗(yàn)環(huán)境

所有實(shí)驗(yàn)都在64位的Windows 10操作系統(tǒng)下進(jìn)行，處理器為I7-11800H，內(nèi)存為64 GiB，顯卡為RTX3060移動(dòng)版。編程語言為Python3.7。

開源地址：https：//github.com/Virouse/HDN-DL。

3.2" 對(duì)比算法與數(shù)據(jù)集

為了驗(yàn)證HDN-DL算法的有效性，實(shí)驗(yàn)中除了選取LDA［11］、NCA［12］、SDA［25］、LGC［10］等經(jīng)典模型，還選取了FLP［26］、EAGR［27］、LaPOLeaF［18］、AWSSL［28］、OBGSSL［29］等類似的或較新的方法進(jìn)行比較。將數(shù)據(jù)集分為3組，其中：Iris、Wine、Yeast為第1組，Iris、Wine是只有3個(gè)類別的小型數(shù)據(jù)集，而Yeast有10個(gè)類別；第2組Crx、German、Heart、Ionosphere、Votes、Pima和Monkl都來自公開的UCI數(shù)據(jù)集，類別數(shù)都是2；Letter和MNIST分別是手寫英文字母和手寫數(shù)字的圖像數(shù)據(jù)集，為第3組。表1展示了實(shí)驗(yàn)選取的數(shù)據(jù)集。

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

為了驗(yàn)證HDN-DL算法的有效性，分別在第1組、第2組、第3組數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。表2是第1組數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。

LaPOLeaF算法雖然與HDN-DL算法最為類似，但是它存在一些不足：一是LaPOLeaF隨機(jī)地為每個(gè)類別選擇初始訓(xùn)練樣本，導(dǎo)致其預(yù)測性能在某些數(shù)據(jù)集上不穩(wěn)定；二是LaPOLeaF的標(biāo)簽傳播方法存在子節(jié)點(diǎn)指導(dǎo)父節(jié)點(diǎn)標(biāo)簽的情況，這不符合密度指向的思想。

Iris數(shù)據(jù)集選擇了6個(gè)樣本進(jìn)行訓(xùn)練，除了LaPOLeaF算法在最優(yōu)情況下的準(zhǔn)確率優(yōu)于HDN-DL算法，HDN-DL算法都取得了更好的效果。對(duì)于Wine數(shù)據(jù)集，HDN-DL算法的分類準(zhǔn)確率優(yōu)于其他算法。Yeast數(shù)據(jù)集選擇了111個(gè)樣本進(jìn)行訓(xùn)練，HDN-DL算法的分類準(zhǔn)確率有著明顯的優(yōu)勢，超越第二名7個(gè)百分點(diǎn)。總體而言，HDN-DL算法通過決策值選擇標(biāo)記樣本，非隨機(jī)選擇，其準(zhǔn)確率不存在波動(dòng)；而其他算法由于選擇訓(xùn)練樣本的隨機(jī)性，其準(zhǔn)確率會(huì)出現(xiàn)較大的起伏，因此凸顯了HDN-DL算法的穩(wěn)定性。

在第2組7個(gè)數(shù)據(jù)集上，對(duì)8種不同的算法進(jìn)行10次實(shí)驗(yàn)，并取最高值進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表3所示。從表3可以看出，HDN-DL算法的分類性能依然是最優(yōu)的。

Letter和MNIST數(shù)據(jù)集數(shù)據(jù)量大、類別多，因此采用了多層次的標(biāo)簽傳播方法，即先將樣本構(gòu)造為多棵引領(lǐng)樹，再將每棵引領(lǐng)樹看作一個(gè)子集，根據(jù)其數(shù)量及類別選擇再次劃分或者直接進(jìn)行標(biāo)簽傳播。實(shí)驗(yàn)結(jié)果如表4所示。HDN-DL算法在Letter數(shù)據(jù)集上的表現(xiàn)良好，準(zhǔn)確率高出了第二名近7個(gè)百分點(diǎn)。在MNIST數(shù)據(jù)集上，HDN-DL算法的分類性能接近OBGSSL算法。

3.4" 參數(shù)敏感性分析

HDN-DL算法主要有3個(gè)參數(shù)：截?cái)嗑嚯xdc、引領(lǐng)樹數(shù)量lt_num、標(biāo)簽傳播初始節(jié)點(diǎn)數(shù)量l。對(duì)于不同的數(shù)據(jù)集，它們的影響也各不相同。

截?cái)嗑嚯x決定了高斯核的寬度，從而影響數(shù)據(jù)點(diǎn)之間的距離權(quán)重。調(diào)整高斯核的截?cái)嗑嚯x會(huì)影響數(shù)據(jù)點(diǎn)的密度排序。具體來說，當(dāng)dc較小時(shí)，高斯核的曲線相對(duì)較窄，只有距離較近的數(shù)據(jù)點(diǎn)才會(huì)對(duì)局部密度產(chǎn)生顯著的貢獻(xiàn)。這可能導(dǎo)致在密度較高的區(qū)域內(nèi)形成比較尖銳的峰值，使得在這些區(qū)域的數(shù)據(jù)點(diǎn)密度更為明顯。反之，當(dāng)dc較大時(shí)，高斯核的曲線較寬，遠(yuǎn)離的數(shù)據(jù)點(diǎn)也會(huì)對(duì)局部密度產(chǎn)生影響，可能導(dǎo)致平滑的密度分布。合適的截?cái)嗑嚯x的選擇通常需要根據(jù)具體問題和數(shù)據(jù)集的特性來進(jìn)行調(diào)整，以確保算法能夠?qū)γ芏冉Y(jié)構(gòu)有良好的感知。圖2展示了超參數(shù)dc的變化對(duì)算法分類準(zhǔn)確率的影響。

圖3展示了參數(shù)lt_num的變化對(duì)算法分類準(zhǔn)確率的影響。調(diào)整引領(lǐng)樹的數(shù)量會(huì)影響節(jié)點(diǎn)所在的層次。節(jié)點(diǎn)所在的層次決定了節(jié)點(diǎn)高密度近鄰的數(shù)量，從而影響標(biāo)簽傳播時(shí)的決策。具體來說，當(dāng)lt_num較小時(shí)，平均節(jié)點(diǎn)所在層次較大，高密度近鄰數(shù)量更多，近鄰距離當(dāng)前節(jié)點(diǎn)的平均距離也越大，而過多的高密度近鄰反而可能導(dǎo)致決策的錯(cuò)誤。當(dāng)lt_num較大時(shí)，由于高密度近鄰數(shù)量較少，節(jié)點(diǎn)標(biāo)簽會(huì)更傾向于其父節(jié)點(diǎn)標(biāo)簽，容易產(chǎn)生級(jí)聯(lián)誤分。

圖4展示了參數(shù)l的變化對(duì)算法分類準(zhǔn)確率的影響。與絕大多數(shù)半監(jiān)督學(xué)習(xí)算法類似，一味地增加訓(xùn)練樣本并不總是會(huì)提升分類的準(zhǔn)確性，有時(shí)甚至?xí)?dǎo)致準(zhǔn)確率降低。

3.5" 水質(zhì)預(yù)測實(shí)驗(yàn)

水質(zhì)數(shù)據(jù)集由中國重慶開縣水質(zhì)監(jiān)測站提供，包含2014年3月3日至2014年11月21日的樣本。采集間隔為15 min，觀測次數(shù)為28 605次。選擇PH指數(shù)和溶解氧（dissolved oxygen， DO）指數(shù)進(jìn)行預(yù)測實(shí)驗(yàn)，將HDN-DL的預(yù)測結(jié)果與LSSVR［30］進(jìn)行比較，后者是一種已廣泛應(yīng)用于生態(tài)環(huán)境監(jiān)測的經(jīng)典模型［31］。

水質(zhì)數(shù)據(jù)是時(shí)間序列數(shù)據(jù)。首先將PH和DO數(shù)據(jù)分別折疊成維度為6和13的向量，接著將前5個(gè)和12個(gè)元素分別視為觀測屬性x，將最后一個(gè)元素視為響應(yīng)變量y。至此，將PH數(shù)據(jù)集轉(zhuǎn)換為PH-5和PH-12。類似地，DO數(shù)據(jù)集被轉(zhuǎn)換為DO-5和DO-12。實(shí)驗(yàn)選擇了10 000個(gè)樣本作為訓(xùn)練集，1 000個(gè)樣本作為測試集，并采用殘差平方和評(píng)估性能。預(yù)測結(jié)果如表5所示。

真實(shí)值和預(yù)測值之間的差異如圖5所示。由圖5可以看出：HDN-DL能夠較為準(zhǔn)確地近似PH和DO數(shù)據(jù)集的真實(shí)值。在PH數(shù)據(jù)集上，HDN-DL的預(yù)測精度略低于 LSSVR，但具有可比性；在DO數(shù)據(jù)集上，HDN-DL的預(yù)測性能顯著優(yōu)于LSSVR。這些性能差異歸因于兩種方法的核心概念不同。LSSVR試圖將核化樣本擬合到超平面上，而HDN-DL則基于相似性查詢。如果樣本不能在超平面上表示，那么LSSVR生成的回歸結(jié)果可能較差。對(duì)于HDN-DL，其訓(xùn)練過程為構(gòu)造引領(lǐng)樹，是不帶標(biāo)簽的訓(xùn)練方式，只有在測試時(shí)才會(huì)使用到訓(xùn)練樣本的標(biāo)簽。

4" 結(jié)論

本文結(jié)合密度峰值聚類算法提出了一種選取決策值較高的點(diǎn)的初始化方法HDN-DL，解決傳統(tǒng)基于圖的半監(jiān)督學(xué)習(xí)方法中隨機(jī)初始化有標(biāo)簽樣本導(dǎo)致性能不穩(wěn)定的問題，再通過引入高密度近鄰和節(jié)點(diǎn)層次，在一定程度上解決了DPC及其衍生算法中級(jí)聯(lián)誤分的問題，在與經(jīng)典算法、主流算法及較新算法的比較中，證明了HDN-DL算法的有效性和穩(wěn)定性。

本文的主要貢獻(xiàn)包括4個(gè)方面：

1）結(jié)合DPC算法提出了高密度近鄰標(biāo)簽傳播算法，能夠在一定程度上解決級(jí)聯(lián)誤分的問題。

2）提出了一種選擇標(biāo)簽傳播起始點(diǎn)的方法，能夠有效地提升標(biāo)簽傳播方法的準(zhǔn)確性和穩(wěn)定性。

3）HDN-DL算法在7個(gè)公開的UCI數(shù)據(jù)集及2個(gè)圖像數(shù)據(jù)集上完成分類任務(wù)，證明了該方法在真實(shí)數(shù)據(jù)集上的有效性。

4）在水質(zhì)數(shù)據(jù)集上進(jìn)行了回歸預(yù)測實(shí)驗(yàn)，證明了該方法能夠應(yīng)用于時(shí)間序列數(shù)據(jù)的預(yù)測。

在未來的工作中，將進(jìn)一步改善模型，深入研究模型參數(shù)的選擇。在保證甚至提升性能的前提下，做到減少參數(shù)，自動(dòng)選擇參數(shù)等。

參考文獻(xiàn)：

KINGMA D P， MOHAMED S， REZENDE D J， et al. Semi-supervised learning with deep generative models［J］. Advances in Neural Information Processing Systems， 2014， 27： 3581-3589.

［2］ BERTHELOT D， CARLINI N， GOODFELLOW I， et al. Mixmatch： a holistic approach to semi-supervised learning［J］. Advances in Neural Information Processing Systems， 2019， 32： 5050-5060.

［3］ VAN ENGELEN J E， HOOS H H. A survey on semi-supervised learning［J］. Machine Learning， 2020， 109（2）： 373-440.

［4］ LI J N， SOCHER R， HOI S C H. DivideMix： Learning with noisy labels as semi-supervised learning［C］//International Conference on Learning Representations. Addis Ababa： ICLR， 2020： 1-14.

［5］ ZHANG Y H， WEN J H， WANG X B， et al. Semi-supervised learning combining co-training with active learning［J］. Expert Systems with Applications， 2014， 41（5）： 2372-2378.

［6］ DING S F， ZHU Z B， ZHANG X K. An overview on semi-supervised support vector machine［J］. Neural Computing and Applications， 2017， 28： 969-978.

［7］ SONG Z X， YANG X L， XU Z L， et al. Graph-based semi-supervised learning： a comprehensive review［J］. IEEE Transactions on Neural Networks and Learning Systems， 2022， 34（11）： 8174-8194.

［8］ YANG Z L， COHEN W， SALAKHUDINOV R. Revisiting semi-supervised learning with graph embeddings［C］//International Conference on Machine Learning. New York： PMLR， 2016： 40-48.

［9］ ZHU X J， GHAHRAMANI Z， LAFFERTY J D. Semi-supervised learning using gaussian fields and harmonic functions［C］//Proceedings of the 20th International conference on Machine learning （ICML-03）. Washington， DC： AAAI Press， 2003： 912-919.

［10］ZHOU D Y， BOUSQUET O， LAL T， et al. Learning with local and global consistency［J］. Advances in Neural Information Processing Systems， 2004， 16： 321-328.

［11］BELHUMEUR P N， HESPANHA J P， KRIEGMAN D J. Eigenfaces vs. fisherfaces： recognition using class specific linear projection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1997， 19（7）： 711-720.

［12］GOLDBERGER J， HINTON G E， ROWEIS S， et al. Neighbourhood components analysis［J］. Advances in Neural Information Processing Systems， 2005， 17： 513-520.

［13］RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks［J］. Science， 2014， 344： 1492-1496.

［14］SHU Z Y， YANG S P， WU H Y， et al. 3D shape segmentation using soft density peak clustering and semi-supervised learning［J］. Computer-Aided Design， 2022， 145： 103181.1-103181.12.

［15］TAO X M， BAO Y X， ZHANG X H， et al. Regularized semi-supervised KLFDA algorithm based on density peak clustering［J］. Neural Computing and Applications， 2022， 34（22）： 19791-19817.

［16］TU B， ZHANG X F， KANG X D， et al. Spatial density peak clustering for hyperspectral image classification with noisy labels［J］. IEEE Transactions on Geoscience and Remote Sensing， 2019， 57（7）： 5085-5097.

［17］馬振明， 安俊秀. 基于空間向量搜索的密度峰值聚類算法［J］. 計(jì)算機(jī)工程與應(yīng)用， 2023， 59（15）： 123-131.

［18］XU J， LI T， WU Y M， et al. Lapoleaf： label propagation in an optimal leading forest［J］. Information Sciences， 2021， 575： 133-154.

［19］XU J， WANG G Y， LI T R， et al. Local-density-based optimal granulation and manifold information granule description［J］. IEEE Transactions on Cybernetics， 2018， 48（10）： 2795-2808.

［20］ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding［J］. Science， 2000， 290： 2323-2326.

［21］ALTMAN N S. An introduction to kernel and nearest-neighbor nonparametric regression［J］. American Statistician， 1992： 175-185.

［22］ERTOZ L， STEINBACH M， KUMAR V. A new shared nearest neighbor clustering algorithm and its applications［C］//Workshop on Clustering High Dimensional Data and Its Applications at 2nd SIAM International Conference on Data Mining. 2002， 8： 105-115.

［23］ZHU Q S， FENG J， HUANG J L. Natural neighbor： a self-adaptive neighborhood method without parameter K［J］. Pattern Recognition Letters， 2016， 80： 30-36.

［24］JIANG J H， CHEN Y J， MENG X Q， et al. A novel density peaks clustering algorithm based on k nearest neighbors for improving assignment process［J］. Physica A： Statistical Mechanics and Its Applications， 2019， 523： 702-713.

［25］CAI D， HE X F， HAN J W. Semi-supervised discriminant analysis［C］//Proceedings of the 11th International Conference on Computer Vision. Chicago： IEEE Press， 2007： 1-7.

［26］NI B B， YAN S C， KASSIM A. Learning a propagable graph for semisupervised learning： classification and regression［J］. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（1）： 114-126.

［27］WANG M， FU W J， HAO S J， et al. Scalable semi-supervised learning by efficient anchor graph regularization［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（7）： 1864-1877.

［28］NIE F P， SHI S J， LI X L. Semi-supervised learning with auto-weighting feature and adaptive graph［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 32（6）： 1167-1178.

［29］HE F， NIE F P， WANG R， et al. Fast semi-supervised learning with optimal bipartite graph［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 33（9）： 3245-3257.

［30］SUYKENS J A K， VAN GESTEL T， DE BRABANTER J， et al. Least Squares Support Vector Machines［M］. Cambridge： World Scientific Publishing， 2002.

［31］ADNAN R M， YUAN X H， KISI O， et al. Improving accuracy of river flow forecasting using LSSVR with gravitational search algorithm［J］. Advances in Meteorology， 2017， 2017： 2391621.1-2391621.23.

（責(zé)任編輯：周曉南）

Label Propagation Algorithm Based on High-Density Nearest

Neighbors and Determinate Labeling

REN Gang， XU Ji*

（State key Laboratory of Public Big Data， Guizhou University， Guiyang 550025， China）

Abstract：

Semi-supervised learning has garnered widespread attention due to its ability to effectively utilize unlabeled data， especially graph-based semi-supervised learning methods that have the advantages of intuitive representation and clear conceptualization. However， most graph-based semi-supervised learning methods require iterative optimization， and its unstable prediction accuracy due to the variations in selecting initial labeled points. To address this issue， a graph-based semi-supervised learning method is proposed， which is based on high-density neighbors and deterministic labeled sample selection. By leveraging the latent structure and information in the data and selecting highly influential nodes as the starting points for label propagation. This method ensures more ideal stability. After getting the initial unsupervised clustering graph structure by density peak clustering algorithm（DPC）， then the structure is fragmented so as to obtain the leading forest. In addition， the high-density neighbors and their relative distances are calculated according to the layer of each sample point. In this way， multiple attributes are considered to determine the label of the current sample in order to avoid cascading misclassification. The complexity of label propagation is O（n） without iteration in this proposed method. Experiments on several data sets verify the effectiveness.

Key words：

graph-based semi-supervised learning; density peak clustering; leading forest; high-density nearest neighbor; determinate labeling