劉瑩瑩，王士同

1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122

2.江南大學(xué) 江蘇省媒體設(shè)計與軟件技術(shù)重點實驗室，江蘇 無錫 214122

1 引言

許多實際的工作中，例如對象識別、多媒體檢索和文本分類等任務(wù)，標(biāo)記的示例通常是少量的且需要花費昂貴的代價才能獲取，但大量的未標(biāo)記的示例又是可以利用的。雖然這些大量的未標(biāo)記示例沒有標(biāo)簽，但它們可能提供了數(shù)據(jù)分布的先驗信息，使其在標(biāo)記示例很少的情況下能夠進(jìn)行準(zhǔn)確的分類。半監(jiān)督學(xué)習(xí)（semi-supervised learning，SSL）[1-4]就是這樣的一種學(xué)習(xí)策略，目的是利用這些大量的未標(biāo)記示例來提高學(xué)習(xí)性能。SSL 已經(jīng)被許多研究者從不同的角度進(jìn)行了深入的研究。眾所周知，SSL 算法應(yīng)該在正確的假設(shè)下進(jìn)行，否則未標(biāo)記的示例可能會顯著影響其性能。通常情況基于圖形的SSL 算法使用的兩個基本假設(shè)是聚類假設(shè)和流形假設(shè)[5]，大多數(shù)流行的SSL 算法也都是基于這兩個假設(shè)之一進(jìn)行的研究[6-7]。

本文目標(biāo)是基于流形假設(shè)的前提下設(shè)計一種新的基于圖形的SSL 算法。與現(xiàn)有的基于圖形的直接從統(tǒng)計學(xué)中推導(dǎo)出來的線性近鄰傳遞（linear neighborhood propagation，LNP）[8]算法不同，本文結(jié)合物理學(xué)中彈性力理論提出了一種新的SSL 標(biāo)簽傳播方案——基于彈力理論傳播的半監(jiān)督學(xué)習(xí)新方法（novel semi-supervised learning method by elastic-force theory based propagation，EFTP）。EFTP 算法一方面模擬了節(jié)點之間的作用力，使得標(biāo)記節(jié)點的標(biāo)簽在傳播中擴散。把標(biāo)記節(jié)點可以看作是標(biāo)簽信息高度集中的擴散源，表現(xiàn)在彈力理論中就是標(biāo)記節(jié)點對未標(biāo)記節(jié)點的彈力很大，而對于未標(biāo)記節(jié)點來說它對于其他節(jié)點的彈力幾乎為0。當(dāng)擴散過程開始時，標(biāo)簽信息將從標(biāo)記節(jié)點轉(zhuǎn)移到剩余的未標(biāo)記節(jié)點。當(dāng)傳播過程完成后，圖中所有的節(jié)點都會得到一定量的標(biāo)簽信息，為最終的分類提供基礎(chǔ)。另一方面考慮到不同節(jié)點被其他節(jié)點同化和同化其他節(jié)點的能力是不同的，使得EFTP 算法比菲克定律協(xié)助傳播（Fick's law assisted propagation，F(xiàn)LAP）[9]算法更加逼真。在EFTP 算法中，一個示例接收或者傳輸標(biāo)簽信息的時間和數(shù)量和應(yīng)該將這些標(biāo)簽傳播到哪里，都直接受彈力理論的約束。

本文主要專注于設(shè)計彈力理論傳播的半監(jiān)督學(xué)習(xí)新算法。在人造數(shù)據(jù)集、圖像以及真實數(shù)據(jù)集上進(jìn)行實驗，EFTP 方法都獲得了比LNP、FLAP 更好的效果。

2 理論基礎(chǔ)

2.1 相關(guān)介紹

半監(jiān)督學(xué)習(xí)算法的目標(biāo)是將標(biāo)記節(jié)點的信息傳到未標(biāo)記節(jié)點中去，在本文中用如下符號表示：一組標(biāo)記節(jié)點記作，一組未標(biāo)記的節(jié)點記作，xi∈Rm,1 ≤i≤n(n=p+w)且都是從未知的邊際分布中取樣，1 ≤i≤p，yi從{-1,1}中取值，目的是將標(biāo)簽信息從P傳播到W。文獻(xiàn)[10]中開發(fā)了局部學(xué)習(xí)穩(wěn)定器來預(yù)測每個樣本標(biāo)簽來自其鄰居的標(biāo)簽。文獻(xiàn)[8]中提出了線性鄰域傳播（LNP），即假設(shè)圖上的每一個例子都可以由其鄰域進(jìn)行最優(yōu)重構(gòu)。這些算法通常假設(shè)鄰居對于測試示例的標(biāo)簽是確定的。文獻(xiàn)[9]中提出了菲克定律協(xié)助傳播（FLAP），模擬流體的擴散進(jìn)行標(biāo)簽傳播，設(shè)定流體分子的同化與被同化能力是相等的。然而，這些算法中假設(shè)并不總是適用于各種數(shù)據(jù)分布，因此上述方法有時可能會得到不滿意的結(jié)果。

本文對SSL 方法進(jìn)行探索，從一個新的角度研究傳播的過程。傳播是社會生活中一種很常見的現(xiàn)象，舉個很常見的例子：在人口遷移中，起初每個人都居住在自己的領(lǐng)域，但是在個人因素和社會因素共同作用下，人們會選擇遷徙。這個過程中，人口遷移可以看成是由一系列的“力”引起的。這就是社會學(xué)中的著名的人口遷移推拉力模型（參見文獻(xiàn)[11-12]）。當(dāng)然，由于個體的差異性，一個區(qū)域?qū)€體的排斥力和吸引力參數(shù)都是不同的。這就可以類比成在實際工作中每個節(jié)點它的同化與被同化的系數(shù)是不一樣的。可以把此現(xiàn)象看成人口的流動傳播。除此之外，很多社會學(xué)家還為推拉理論引入很多量化模型。例如文獻(xiàn)[13]把物理學(xué)中的重力模型以及統(tǒng)計學(xué)中馬爾科夫鏈模型引入遷移理論。目的就是為了使人口遷移的定量分析成為可能。受這種想法的啟發(fā)，利用彈力模型，使得本文的傳播算法更具有兼容性，讓本文的標(biāo)簽傳播在處理多種數(shù)據(jù)分布的數(shù)據(jù)集時更具有魯棒性。下面將介紹本文所提出的SSL模型——彈力模型。

2.2 彈力模型

自然界中每個物體在外力作用下都會發(fā)生形變。如果撤回這些外力，物體就會恢復(fù)原來狀態(tài)，把這些外力稱作“彈力”。在彈性限度內(nèi)，彈簧發(fā)生彈性形變時，彈力的大小跟彈簧形變量成正比。具體表達(dá)式如下：

其中，Δx表示彈簧的形變量，k稱為彈簧的倔強系數(shù)（也稱作勁度系數(shù)或彈性系數(shù)），大小與其自身的性質(zhì)有關(guān)。如彈力理論所描述的形式一樣，現(xiàn)在把彈簧形變量Δx類比成標(biāo)簽信息量在節(jié)點之間的擴散距離d。倔強系數(shù)k大小在本文中除了與節(jié)點之間傳播時單個節(jié)點的輸入系數(shù)λ1和輸出系數(shù)γ1有關(guān)之外，還與當(dāng)前時刻互相傳播的兩個節(jié)點標(biāo)簽數(shù)值有一定關(guān)系。后期會對這兩個參數(shù)進(jìn)行適當(dāng)調(diào)整來實現(xiàn)滿意的分類結(jié)果。因此，在標(biāo)簽傳播和力學(xué)中彈力理論之間畫一個平行關(guān)系是很自然的。接下來詳細(xì)解說節(jié)點之間的傳播。類比圖如圖1 所示。

從圖1 可以看出標(biāo)簽信息在節(jié)點之間的傳播過程和結(jié)果。顏色偏重的圓類比于較多標(biāo)簽信息的示例。同理具有較少標(biāo)簽信息的示例，則用顏色偏淡的圓來類比。以xw節(jié)點為例來分析傳播過程。圖1中藍(lán)色箭頭和綠色箭頭分別代表其他節(jié)點中的標(biāo)簽信息流向節(jié)點xw的過程和節(jié)點xw傳播自己的標(biāo)簽信息的過程。顏色較重的圖形傳播的標(biāo)簽信息較多，用重色箭頭表示；顏色較淺的圖形傳播的標(biāo)簽信息較少，用淡色箭頭表示。在綜合輸入輸出圖之后，畫出了最后標(biāo)簽信息的流向用紅色箭頭表示。紅色箭頭顯示的是xw與外界所有節(jié)點標(biāo)簽交流之后的合力方向，也就是標(biāo)簽傳播總方向。自然的，設(shè)?v∈{1,2,…,n}，可以用如下彈力模型公式解釋標(biāo)簽傳播過程：

Fig.1 Elastic force mode圖1 彈力模型

這里設(shè)置λ1是xw被其他節(jié)點傳播的系數(shù)，形象地說是輸入系數(shù)。γ1是xw節(jié)點對其他節(jié)點的同化能力系數(shù)，也是其輸出系數(shù)。除此之外，定義節(jié)點xw在t時刻的軟標(biāo)簽為。這里軟標(biāo)簽意味著l從一個實際范圍[-1,1]中取一個值，借助式（1）、式（2）可以變成如下表達(dá)式：

式（3）意味著xw在擴散距離dvw=exp(-‖xv-xw‖2/(2σ2))上將其標(biāo)簽信息傳播到其他節(jié)點和接收其他節(jié)點的標(biāo)簽信息。根據(jù)牛頓第二定律，粒子運動的加速度等于作用力與粒子質(zhì)量的比值：

在時間Δt內(nèi)標(biāo)簽信息的傳播距離S有如下表達(dá)式：

因此過Δt時間后，結(jié)合式（4）、式（5），xw節(jié)點在Δt時間段內(nèi)將標(biāo)簽信息在擴散的過程中散布了一個路徑的總信息量。可以得到如下表達(dá)式：

式（4）、式（5）中的Δt、m可以簡單地設(shè)為1，同時令2-1λ1=λ,2-1γ1=γ，為了后續(xù)證明，這里令λ1=γ1μ。結(jié)合式（3）、式（4）、式（5）、式（6），整個數(shù)據(jù)集的傳播過程用如下式子表達(dá)：

考慮到xw的初始狀態(tài)，式（7）可以變換為：

如果xw分別是一個正的、負(fù)的或未標(biāo)記的例子，那么分別取1，-1 或0。α∈(0,1)是xw從外界接收到的信息以及輸出去的標(biāo)簽信息和xw的初始狀態(tài)之間的平衡系數(shù)。式（8）模擬了節(jié)點之間的標(biāo)簽傳播過程。與最初的彈力定律稍有不同，在實際任務(wù)中，如圖1 所示xw除了接收其他節(jié)點的傳播信息之外，同時它也在向其他節(jié)點傳輸標(biāo)簽信息。換句話說，一個節(jié)點從數(shù)據(jù)集中的所有其他節(jié)點接收標(biāo)簽信息能力系數(shù)和其輸出系數(shù)是不同的。

式（8）說明數(shù)據(jù)集中一個節(jié)點與另一個節(jié)點之間的傳播過程，表示未標(biāo)記節(jié)點的接收標(biāo)簽信息可以理解為其他節(jié)點發(fā)出的信息的集成。

根據(jù)前面的介紹，在半監(jiān)督學(xué)習(xí)中，將彈力模型應(yīng)用于無標(biāo)記和有標(biāo)記的節(jié)點。EFTP 算法允許任意兩個節(jié)點之間的標(biāo)簽信息交換，而不考慮它們當(dāng)前的標(biāo)簽值。因此，在傳播過程中可以更改節(jié)點的標(biāo)簽。幸運的是，文獻(xiàn)[9]中定理1 表明被標(biāo)記的示例的標(biāo)簽在迭代過程之后不會改變，也就意味著被標(biāo)記示例的原始標(biāo)簽，即1 或-1，不會從1 轉(zhuǎn)成-1。

定理1 被標(biāo)記節(jié)點的標(biāo)簽在迭代過程之后不會改變。

3 彈性理論傳播算法

3.1 算法傳播進(jìn)程介紹

彈力理論傳播的半監(jiān)督學(xué)習(xí)新方法需要對樣本中的每個節(jié)點進(jìn)行傳播，隨著時間的推移，越來越多的節(jié)點加入傳播行列，進(jìn)行反復(fù)迭代計算，直至收斂。在傳播過程中同時更新所有示例的標(biāo)簽，用標(biāo)簽向量來表示，初始狀態(tài)用向量y=(y1y2…yn)T來表示。各個示例的標(biāo)簽值用如下公式表示：

把迭代矩陣D定義為：

由式（9）可知，一個示例的標(biāo)簽是其初始狀態(tài)與包括其自身在內(nèi)的所有示例標(biāo)簽的線性組合。迭代計算式（9）直到其收斂，收斂判定由如下公式表示：

式中，δ是預(yù)定義的一個極小的正數(shù)。通過迭代過程可得到收斂向量L*。給定一個硬閾值0，若則確定xw為正（是L*向量中的第w個元素），否則為負(fù)數(shù)。

雖然式（9）是為二元分類推導(dǎo)出來的，但是可以通過將標(biāo)簽向量L和初始狀態(tài)向量y替換為標(biāo)簽向量矩陣L和初始狀態(tài)矩陣Y，式（9）可以直接擴展到多類分類。具體表達(dá)式如下：

式（12）中矩陣L和Y的規(guī)格是n×m，m表示類別的總數(shù)。若xw被標(biāo)記，則yw=m1那么。反之如果xw沒有標(biāo)記，那么=0 (1 ≤m1≤m)，最后xw屬于種類。

由文獻(xiàn)[14-15]中定理2 可知式（12）以線性速率收斂。定理2 的內(nèi)容直接適用于式（9）。

定理2 由式（12）生成的序列{L(t)},t=1,2,…最終收斂到如下式子：

此時也對標(biāo)簽傳播的停止準(zhǔn)則進(jìn)行了相應(yīng)的修改：

這里‖· ‖L表示范數(shù)。因為式（12）是一個根據(jù)示例之間的相似性傳遞標(biāo)簽信息的傳播算法，所以它可以處理任何類型的數(shù)據(jù)分布。此外，EFTP 是一種基于圖形的算法，可以有效地利用隱藏在數(shù)據(jù)集中的流形結(jié)構(gòu)[16-17]，因此它總能得到滿意的分類結(jié)果。

3.2 算法收斂性證明

為了直觀地比較EFTP、FLAP、LNP，并顯示其優(yōu)越性，在經(jīng)典正則化理論背景下重新構(gòu)造了EFTP 算法，具體表達(dá)式如下：

式中，Dkj是矩陣D中的第(k,j)個元素。式（15）右側(cè)的第一項形成了特定的先驗知識，使示例標(biāo)簽在L中平穩(wěn)變化。這表明類似示例的軟標(biāo)簽之間不應(yīng)該有太大的差別。第二個擬合項表示所確定的標(biāo)簽應(yīng)與示例原始標(biāo)簽狀態(tài)保持一致。而正則化參數(shù)φ＞0控制平滑項和擬合項之間的權(quán)衡。

定理3 正則式(15)是一個凸優(yōu)化問題。

證明Q(L)對L進(jìn)行求導(dǎo)的過程步驟如下：

在式（17）中Q(L)對L求導(dǎo)后變成如下形式：

將式（17）右邊設(shè)為0，因此式（18）可以被重新表述如下：

變形得到與式（13）相同的閉合式，表達(dá)式如下：

因此式（15）是式（9）的迭代結(jié)果，在式（15）中迭代矩陣D可變換成如下形式：

為了保證D是非負(fù)隨機矩陣以及D1每行和為1，設(shè)置。

從文獻(xiàn)[14]中的Gerschgorin 圓定理得到D1所有特征值都在范圍內(nèi)，這表明D1是正定矩陣。

而對于對角矩陣D2其特征值就是對角線，為使得其為正定矩陣設(shè)置u＞1。

根據(jù)正定矩陣的性質(zhì)可知正定矩陣的和仍是正定矩陣。由此可以證明本文的迭代矩陣D也是正定矩陣。因此，式（15）是凸優(yōu)化問題，收斂結(jié)果也是全局的最優(yōu)的。 □

定理3 表明，EFTP 算法式（15）的收斂點對應(yīng)全局最優(yōu)解。這些處理方式差異使得EFTP的收斂精度更高。至此以上內(nèi)容即為本文所提算法的主要內(nèi)容。

4 實驗分析

本章采用不同形狀的人造數(shù)據(jù)、圖像數(shù)據(jù)以及真實數(shù)據(jù)分別對EFTP、LNP、FLAP 算法進(jìn)行評估。重點討論這三個算法中的兩個問題：（1）對每個數(shù)據(jù)集只給出很少的標(biāo)記示例的情況下，算法對未標(biāo)記示例的分類精度；（2）算法的穩(wěn)定性。實驗軟硬件環(huán)境為Intel Corei3-2130 3.4 GHz CPU，4.0 GB RAM，Windows 7，Matlab R2016b。

4.1 參數(shù)設(shè)置和評價標(biāo)準(zhǔn)

本節(jié)將說明實驗中的參數(shù)設(shè)置情況和使用的評價標(biāo)準(zhǔn)。

兩個參數(shù)k、u是EFTP 算法獲得令人滿意結(jié)果的關(guān)鍵。k控制一個既定的稀疏圖，u在平衡算法準(zhǔn)確性和穩(wěn)定性中起著重要的作用。

u選擇：u對EFTP 算法性能的影響是雙重的。直觀上，從式（3）觀察到u代表從xv同化xw的效果，xv同化xw的概率越大，u的值就越大，xw的標(biāo)簽就越容易受到xv的影響。并且在第3 章中證明此算法的收斂性是在u>1 的情況下。但是u的取值并不是無限大，因為在一個數(shù)據(jù)集之中不同類的數(shù)據(jù)可能會相似，所以u的取值要在一定的范圍內(nèi)。同時為了此算法可以適用于大樣本高維的數(shù)據(jù)集，對數(shù)據(jù)集選取一定的代表點以此來反映數(shù)據(jù)集的整體情況。在這種情況下用文獻(xiàn)[18]中的參數(shù)尋優(yōu)方法找到合適的u。利用最優(yōu)的u帶入到原數(shù)據(jù)集中得到最高的分類精度。

簡而言之，u>1 會收斂，在保證收斂的情況下，趨于無限大時或者取值太小都會降低算法穩(wěn)定性和精度。因此，u的選擇應(yīng)該在保證其準(zhǔn)確性和穩(wěn)定性前提下作一個適中的權(quán)衡。下面的參數(shù)敏感性實驗信息圖將闡述這一點。在Wine 數(shù)據(jù)集中通過固定L=18，EFTP 的精度和穩(wěn)定性的變化如圖2（a）和圖2（b）。顯然在Wine 數(shù)據(jù)集里，設(shè)置u=1.4 精度相對較高，該設(shè)置下的穩(wěn)定性也是可以接受的。

Fig.2 Sensitivity test analysis diagram of parameter u圖2 參數(shù)u 的敏感性實驗分析圖

k選擇：一個合適的圖形對提高算法性能非常重要，k是決定已建立圖的鄰域數(shù)目和稀疏性的一個關(guān)鍵參數(shù)。在DS1、DS2、DS3、DS4 數(shù)據(jù)集上讓k從小到大取值。一般情況下，如果圖太稀疏（例如k=2），EFTP 達(dá)不到令人滿意的性能。然而，當(dāng)k在某值（k=6）左右取值時，EFTP 分類性能就是正常的，效果令人滿意。綜合實驗表明k的選擇對穩(wěn)定性和精度影響不大，很容易調(diào)優(yōu)。具體參數(shù)敏感性實驗分析如圖3 所示。

Fig.3 Sensitivity test analysis diagram of parameter k圖3 參數(shù)k 的敏感性實驗分析圖

為了公平比較，下列所有實驗中EFTP 參數(shù)設(shè)置為a=0.99,，η設(shè)置在[0,1]內(nèi)。在FLAP 中a也設(shè)置為0.99。為所有算法構(gòu)造了相同的K近鄰（K-NN）圖。σ、u在不同數(shù)據(jù)集中會進(jìn)行相應(yīng)調(diào)整，以達(dá)到最佳性能。

采 用NMI（normal mutual information）、RI（rand index）[19]指標(biāo)對算法進(jìn)行評估。NMI 與RI 的定義如下：

首先給出包含n個對象的數(shù)據(jù)集，X定義了已知標(biāo)簽的原始數(shù)據(jù)，Y定義了對已知標(biāo)簽原始數(shù)據(jù)的聚類效果，a定義了X、Y任意兩個具有相同類標(biāo)簽并且屬于同一個樣本的個數(shù)，b定義了X、Y中任意兩個具有不同標(biāo)簽并且屬于不同類樣本的個數(shù)。兩種指標(biāo)對算法進(jìn)行評估，指標(biāo)越高，說明聚類效果越好。

4.2 人造數(shù)據(jù)集實驗

本節(jié)使用人造平面數(shù)據(jù)集DS1、DS2、DS3、DS4將EFTP、FLAP 以及LNP 三種算法的傳播過程可視化，以此來進(jìn)行三種算法的驗證和比較。由于LNP與FLAP 算法的分類效果相近，限于篇幅，LNP 的分類效果可視圖不再給出。算法中所用到的四個數(shù)據(jù)集為了在精度和穩(wěn)定性上形成對比，都采用了較多數(shù)據(jù)點。除此之外，為了證明EFTP 算法的魯棒性，本節(jié)的數(shù)據(jù)集的選取也具有不同的類別形式，數(shù)據(jù)量由簡單到復(fù)雜，覆蓋面較為廣泛，具體信息如表1所示。

Table 1 Synthetic datasets表1 人造數(shù)據(jù)集

DS1、DS2 數(shù)據(jù)集與使用雙月數(shù)據(jù)集進(jìn)行實驗的文獻(xiàn)[7]和文獻(xiàn)[20]相比，減少了類間距離。分別讓兩個類盡可能地鑲嵌與靠近，使月、正方、圓形態(tài)不規(guī)則增加分類難度。DS3、DS4 數(shù)據(jù)樣本量大于10 000的數(shù)據(jù)集也分別進(jìn)行EFTP、FLAP、LNP 算法實驗。本節(jié)依次在圖4、圖5、圖6、圖7 中給出了其原圖、代表點圖以及運行FLAP 及EFTP 算法后的圖解。

Fig.4 Original graph and experimental graph of DS1圖4 DS1 原圖及實驗圖

Fig.5 Original graph and experimental graph of DS2圖5 DS2 原圖及實驗圖

Fig.6 Original graph and experimental graph of DS3圖6 DS3 原圖及實驗圖

Fig.7 Original graph and experimental graph of DS4圖7 DS4 原圖及實驗圖

從圖4～圖7 中可以看出，相對于FLAP 算法，EFTP 算法對于各種形狀數(shù)據(jù)集傳播分類的效果都非常好。為了在DS1、DS2、DS3、DS4 數(shù)據(jù)集上更好地實現(xiàn)分類效果，為EFTP 算法構(gòu)建了5-NN、6-NN、8-NN 和10-NN 圖。

在運行EFTP 算法時，各數(shù)據(jù)集的代表點數(shù)為525、750、812 和1 250，其傳播分類結(jié)果與直接使用FLAP、LNP 算法精確度都有顯著提升。為了進(jìn)行定量比較，本文通過更多實驗對比三種算法分類精度，具體情況如表2 所示。

在實驗中，由于選標(biāo)記示例點時存在隨機的情況，則會造成每次實驗結(jié)果出現(xiàn)小范圍內(nèi)波動。為此，實驗數(shù)據(jù)則選取均值作為數(shù)據(jù)結(jié)果。以上每組實驗所記錄數(shù)據(jù)都是在運行數(shù)十次之后計算均值得到。從實驗數(shù)據(jù)可以明顯看出，同預(yù)想一樣，本文提出的EFTP 算法同F(xiàn)LAP、LNP 算法相比較，在標(biāo)記示例很少的情況下都能取得較高的精度。當(dāng)然，隨著標(biāo)記示例l逐漸增大，算法的分類精度也會相應(yīng)提高。從以上實驗結(jié)果來看，本文算法在精度、穩(wěn)定性方面都有了很大的提升，完全達(dá)到預(yù)期目標(biāo)。

4.3 圖像分割實驗

本文選取4 幅圖像（http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench）用于圖像分割實驗中，名稱分別是Horse、Elephant、Sky、Grassland，每幅圖的分辨率均為320×320 像素。限于版面，本文的示意圖都進(jìn)行了一定比例的縮放，如圖8 所示。

本節(jié)為了說明EFTP 的有效性，與FLAP、LNP 算法分類結(jié)果進(jìn)行對比。4 幅圖的類別數(shù)分別為2、2、3、3，圖9、圖10 分別為本文算法和FLAP 算法的圖像分割效果，LNP 與FLAP 的分類效果相似，不再給出。本實驗采用NMI、RI[19]指標(biāo)進(jìn)行評估，目的是為了可以定量地分析圖像分割的效果。該指標(biāo)進(jìn)行評估之前首先要對像素點劃分類標(biāo)，方法見文獻(xiàn)[19]。EFTP 算法分別在4 幅圖片上運行10 次，求得平均NMI、RI指標(biāo)記錄在表3、表4 中。

從實驗結(jié)果中可以看出：在Horse、Elephant 中，兩種算法的指標(biāo)相近，都能有效地分割出目標(biāo)物體。但是在Sky、Grassland 圖片中，EFTP 明顯優(yōu)于FLAP、LNP 算法，因此EFTP 更具有實用性。

Table 2 Experimental results on synthetic datasets表2 人造數(shù)據(jù)集的實驗結(jié)果

Fig.8 Images used in segmentation圖8 分割實驗的圖像

4.4 真實數(shù)據(jù)集

采用4 個UCI（http://archive.ics.uci.edu/ml/datasets.html）數(shù)據(jù)集Iris、Wine、BreastCancer 以及National Clas-sification of Economic Activities-9 (CNAE-9)來比較EFTP 與FLAP、LNP 算法的分類精度。數(shù)據(jù)集具體信息如表5 所示。

Table 3 NMI of 3 algorithms on 4 images表3 3 類算法在4 幅圖片上的NMI

Table 4 RI of 3 algorithms on 4 images表4 3 類算法在4 幅圖片上的RI

Fig.9 Segmentation results of EFTP on each image圖9 EFTP 算法在圖像上的分割效果

Table 5 Real datasets表5 真實數(shù)據(jù)集

本節(jié)中對標(biāo)記集L在不同大小下的分類精度進(jìn)行了實驗。算法在每個L下獨立實現(xiàn)10次，隨機選取標(biāo)記示例，表6 列出了10 次運行輸出的精度平均值以及方差。請注意，在生成標(biāo)記集時，每個類中至少保證有一個標(biāo)記示例。分別為Iris、Wine、Breast Cancer和CNAE-9 構(gòu)建了10-NN、6-NN、7-NN 和10-NN 圖。

從表6 可以看出，當(dāng)L由小變大時，EFTP 一般可以達(dá)到比較算法中最高的精度?？梢钥闯?，在大多數(shù)情況下，EFTP 算法的效果優(yōu)于FLAP 和LNP 算法。因此本文提出的算法EFTP的結(jié)果是滿足期望的。

Fig.10 Segmentation results of FLAP on each image圖10 FLAP 算法在圖像上的分割效果

5 結(jié)束語

采用物理力學(xué)中彈力基本理論，本文提出了用于SSL 標(biāo)簽傳播的EFTP 算法。EFTP 也可以在傳統(tǒng)正則化理論的背景下推導(dǎo)出來，將EFTP 算法與已有的算法相聯(lián)系，意味著EFTP 的收斂點是全局最優(yōu)的。同時也證明了參數(shù)u在決定分類性能和穩(wěn)定性方面扮演了重要的角色。綜合實驗結(jié)果表明，與FLAP、LNP 算法相比，EFTP 具有很大優(yōu)勢。

與大多數(shù)標(biāo)簽傳播算法相似，直接將EFTP 應(yīng)用于大數(shù)據(jù)問題在計算上并不容易，這是因為圖結(jié)構(gòu)的復(fù)雜度是O(n3)。然而，超圖技術(shù)的最新發(fā)展，如文獻(xiàn)[21]和文獻(xiàn)[22]，可以解決這個問題。并且EFTP 算法所提出的模型在u＞1 情況下進(jìn)行，u＜1 是否依舊收斂找到優(yōu)解是今后擬探討的課題。

Table 6 Experimental results on real datasets表6 真實數(shù)據(jù)集的實驗結(jié)果