趙建華，劉 寧

1(商洛學院 數(shù)學與計算機應(yīng)用學院，商洛 726000)

2(商洛學院 經(jīng)濟管理學院，商洛 726000)

1 引言

隨著數(shù)據(jù)采集技術(shù)和存儲技術(shù)的發(fā)展，獲取大量無標記樣本已經(jīng)比較容易，而由于需要耗費一定的人力和物力，獲取大量有標記樣本則比較困難[1].如果只使用少量有標記樣本，采用有監(jiān)督學習方法進行分類，那么有監(jiān)督學習訓練得到的學習模型不具有很好的泛化能力，同時造成大量無標記樣本的浪費；如果只使用大量無標記樣本，采用無監(jiān)督學習方法進行分類，那么無監(jiān)督學習將會忽略有標記樣本的價值.因此，研究如何綜合利用包含少量有標記樣本和大量無標記樣本來提高學習性能的半監(jiān)督學習(Semi-supervised Learning)成為當前機器學習非常重要的研究領(lǐng)域之一[1-3].

半監(jiān)督學習[4，5]是一種介于傳統(tǒng)有監(jiān)督學習和無監(jiān)督學習之間的新的機器學習方法，其目的就是充分利用大量的無標記樣本來彌補有標記樣本的不足.半監(jiān)督分類主要研究從有監(jiān)督學習的角度出發(fā)，當有標記訓練樣本不足時，如何利用大量無標記樣本信息輔助分類器的訓練.目前的半監(jiān)督學習方法大致有四種主流范型[6]，即基于生成式模型的方法、半監(jiān)督SVM 方法、基于圖的方法和基于協(xié)同訓練的方法.半監(jiān)督學習是當前的一個研究熱點，廣泛應(yīng)用到各種實際應(yīng)用中，且取得了較好的成果[1，4，5].

雖然半監(jiān)督學習方法被成功應(yīng)用于處理不同類型的數(shù)據(jù)集，但是半監(jiān)督學習過程中無標記樣本的選擇會增加算法的隨機性，同時傳統(tǒng)的半監(jiān)督學習對不同的參數(shù)值敏感，會導致不穩(wěn)定的結(jié)果，這些都會影響半監(jiān)督學習的魯棒性[7-9].

集成學習可以減少由于無標記樣本的隨機選擇導致分類器性能的下降.與單一的半監(jiān)督學習方法相比，半監(jiān)督集成學習方法能夠?qū)牟煌瑪?shù)據(jù)集中生成的多個學習模型產(chǎn)生的結(jié)果進行集成，得到的結(jié)果更準確、更穩(wěn)定，魯棒性更強[7，8].已有不少學者從事半監(jiān)督集成學習方面的研究，且取得了較好的研究成果.Zhou 和Li[10]對標準的協(xié)同訓練算法Co-training 進行改進，提出了一種既不要求充分冗余視圖、也不要求使用不同類型半監(jiān)督分類器的tri-training 算法.Mallapragada 等人[11]將Boosting 技術(shù)推廣到半監(jiān)督學習中，提出了Boosting的半監(jiān)督版本SemiBoost.Yaslan 和Cataltepe[12]利用隨機子空間技術(shù)研究自學習半監(jiān)督學習.Yan 等人[13]提出了一種有效的魯棒半監(jiān)督集成學習方法處理帶有噪聲標簽的大規(guī)模數(shù)據(jù)集.Stanescu 和Caragea[14]將半監(jiān)督集成學習方法應(yīng)用到不平衡數(shù)據(jù)集的分類領(lǐng)域.Yu 等人[15，16]提出了一種漸進子空間集成學習方法.Ding 等人[16]提出一種高效的半監(jiān)督聚類集成算法.Liu 等人[17]提出了一種基于稀疏特征空間表示的半監(jiān)督多源自適應(yīng)學習框架.Yu 等人[18]提出一種增量式半監(jiān)督聚類集成方法和一種基于選擇約束投影的半監(jiān)督集成聚類.

但是，傳統(tǒng)的半監(jiān)督集成學習方法仍然存在下面幾個局限性:

(1)很少考慮如何處理高維且具有極少量有標記樣本的數(shù)據(jù)集[7，18].

(2)大多數(shù)集成方法在處理一些高維數(shù)據(jù)時，只考慮樣本空間中數(shù)據(jù)的分布，或者特征空間中屬性的分布.沒有將這兩種分布綜合起來進行處理，以獲得更好的結(jié)果[15].

將樣本空間中數(shù)據(jù)的分布和特征空間中屬性的分布兩者綜合起來，實現(xiàn)高維數(shù)據(jù)的分類，能有效改善分類性能.一方面能有效的縮減問題的規(guī)模，縮短分類時間，另一方面能有效選取對分類貢獻大的屬性和樣本參與分類，提高分類效率，改善分類性能[15].

本文從探索數(shù)據(jù)樣本空間和特征空間兩個角度出發(fā)，提出一種結(jié)合隨機子空間技術(shù)和集成技術(shù)的安全半監(jiān)督學習算法(A safe semi-supervised learning algorithm combining stochastic subspace technology and ensemble Technology，S3LSE)，處理僅包含極少量有標記樣本的高維數(shù)據(jù)分類問題.首先，S3LSE 采用隨機子空間技術(shù)將高維數(shù)據(jù)集分解為B個特征子集，并根據(jù)樣本間的隱含信息對每個特征子集優(yōu)化，形成B個最優(yōu)特征子集；接著，將每個最優(yōu)特征子集抽樣形成G個樣本子集，在每個樣本子集中使用安全的數(shù)據(jù)樣本標記方法擴充有標記樣本，生成G個分類器，并對G個分類器進行集成；然后，對B個最優(yōu)特征子集生成的B個集成分類器再次進行集成組合，實現(xiàn)高維數(shù)據(jù)的分類.最后，使用高維數(shù)據(jù)集模擬半監(jiān)督學習進行實驗，驗證算法的有效性.

2 提出的算法

算法S3LSE 充分利用高維數(shù)據(jù)特征之間的關(guān)系，挖掘高維數(shù)據(jù)之間的隱含信息，擴充有標記高維數(shù)據(jù)的數(shù)目.主要通過將高維數(shù)據(jù)的分類問題轉(zhuǎn)化為低維數(shù)據(jù)的分類問題.通過對新增標記進行可靠性驗證的方法，保證新增標記樣本的增加后，分類器的性能不會惡化，分類器向著誤差減小的方向進行演化.同時，通過多分類器集成的方法，提高分類器的魯棒性.

算法S3LSE的輸入是訓練集Tr，包括無標記數(shù)據(jù)集Tu和有標記數(shù)據(jù)集Tl，其定義如下:

算法S3LSE 流程如圖1所示，首先，采用隨機子空間技術(shù)將高維數(shù)據(jù)集Tr分解為B個特征子集，并挖掘樣本間的隱含信息，對每個特征子集進行特征優(yōu)化，形成最優(yōu)特征子集；接著，對每個最優(yōu)特征子集進行抽樣生成G個樣本子集，在每個樣本子集中使用安全的半監(jiān)督學習算法生成G個分類器，并對G個分類器進行集成；最后，對B個最優(yōu)特征子集中的形成的B個集成分類器再次進行集成，挖掘高維數(shù)據(jù)的隱含信息，實現(xiàn)高維數(shù)據(jù)的分類.具體步驟如下:

圖1 算法流程圖

(1)使用隨機子空間技術(shù)進行特征子集劃分

假設(shè)每個樣本的特征數(shù)目為m，特征選取率為τ，隨機子空間的特征數(shù)目為τ*m.被選中的特征的序號為:

式中，j表示被選中的特征的序號，?為0 到1 之間的隨機變量，m為特征的數(shù)目.

在隨機選擇過程中，每個被選中的序號對應(yīng)的特征將會被記錄，避免重復(fù)采樣，同時被重復(fù)選中的特征直接被忽略.上述操作反復(fù)進行，直到τ*m個特征全部被選中.選中的τ*m個特征對應(yīng)的樣本組成一個隨機子空間集(特征子集).完成一個特征子集的選擇后，其它B-1個特征子集依次進行.在整個特征選擇過程中，記錄每個特征子集所選中的特征序號.

(2)特征子集優(yōu)化(Feature optimization，F(xiàn)L)

隨機子空間技術(shù)選取的特征具有隨機性，不能很好的反映出特征之間的相關(guān)性等信息.因此，在這里，我們進行特征優(yōu)化操作.建立一個包括特征和標簽之間的相關(guān)性(即特征的相關(guān)性)、特征之間的冗余度等信息的目標函數(shù)，通過計算對應(yīng)于每個特征子集的目標函數(shù)的值，得出每個特征子集的對應(yīng)的最優(yōu)特征值，形成最優(yōu)特征子集.特征的相關(guān)性函數(shù)如式(5)所示，特征之間的冗余度計算如式(6)所示，構(gòu)造的最優(yōu)化函數(shù)如式(9)所示.

式中，(xi,xj)∈ΩML表示樣本i和j屬于同一類別，(xi,xj)∈ΩCL表示樣本i和j屬于不同類別，r表示特征集R的第r個特征，fri表示第i個樣本的第r個特征，frj表示第j個樣本的第r個特征.

式中，ρ(fr,fc)表示皮爾遜相關(guān)系數(shù)，和分別表示平均值.

通過對式(9)進行優(yōu)化，在每個隨機子空間集中產(chǎn)生最優(yōu)的特征子集.

(3)在最優(yōu)特征子集內(nèi)，使用抽樣技術(shù)進行樣本子集劃分

在最優(yōu)特征子集中，有標記樣本的數(shù)目很少.那么，在進行隨機抽樣過程中，有可能造成某個樣本子集中沒有抽取到有標記樣本，影響后面的半監(jiān)督學習.所以，在每個最優(yōu)特征子集的抽樣過程中，我們首先僅僅對無標記樣本集TU進行不放回抽樣，形成G個無標記子集；然后，將有標記集Tl和G個無標記子集分別進行合并，形成G個樣本子集；最后，其它B-1個最優(yōu)特征子集中，依次類推.考慮到算法的時間效果，在多個最優(yōu)特征子集中可以并發(fā)運行.

(4)使用安全的樣本標記方法在樣本子集內(nèi)進行樣本標記

每個最優(yōu)特征子集對應(yīng)的G個樣本子集中，分別使用安全的數(shù)據(jù)樣本標記算法對無標記樣本進行標記，挖掘無標記樣本的隱含信息，擴充有標記樣本的數(shù)目.

算法的主要思想是使用多個偽標記對無標記樣本進行標記，將具有偽標記的樣本加入到有標記樣本集中，參與訓練和測試，將使分類器誤差較小的偽標記作為無標記樣本的最終標記[19].

算法的主要過程如下:①選取一個無標記樣本集U，按照不同的分類類別對U中的無標記樣本分別進行偽標記；②將標記后的候選樣本放入有標記樣本集中，將有標記集進行分組，各組依次作為訓練集和測試集進行組合，使用訓練集訓練分類器，在測試集上進行測試，記錄每次組合對應(yīng)的誤差，將平均值作為每種偽標記對應(yīng)的誤差值；③選取誤差值最小的偽標記作為樣本的預(yù)測標記值.算法的描述如算法1所示.

算法1.安全樣本標記方法(Safe Labeling method，SL)輸入:有標記樣本集L；無標記樣本x；有監(jiān)督分類器輸出:無標記樣本x 對應(yīng)的標記過程:For i=1 to m/* m 表示數(shù)據(jù)的分類類別數(shù)*/使用偽標記Mi 去標注無標記樣本x，記做yi；將yi 添加到訓練集L中；將L 分為k 組，記做L(1)，L(2)，…，L(k)；For j=1 to k讓L(j)作為測試集，其它k-1個組中的有標記樣本作為訓練集；使用訓練集訓練分類器Cij；用Cij 去測試測試集；記錄此時的是正確分類率為acci (j)；EndFor計算第i個偽標記對應(yīng)的誤差:ei=1-(acci(1)+acci(2)+…+acci(k))/k；EndFor獲取e1，e2，…，em的最小值，記為emin；emin 對應(yīng)的標記t 作為樣本x的預(yù)測標記.

該算法保證分類器朝著誤差降低的方向進行演化，能很好的提高標記的正確率，較好的保證分類器的安全性.考慮到算法的時間效果，在G個樣本子集中程序并發(fā)運行.最終，在每個最優(yōu)特征子集中，形成G個分類器.

(5)在最優(yōu)特征子集內(nèi)進行分類器集成

在最優(yōu)特征子集內(nèi)實現(xiàn)G個分類器的集成，采用最大投票法進行集成，即將相同標記數(shù)目最多的分類器對應(yīng)的標記作為集成分類器的標記.集成方法如下:

式中，f(t，b)表示測試樣本xt在第b個最優(yōu)特征子集中的預(yù)測標記；yib表示在第b個最優(yōu)特征子集中，第i個分類器的預(yù)測標記；k表示分類的類別.

(6)在最優(yōu)特征子集間進行分類器集成

在B個最優(yōu)特征子集之間也采用最大投票法進行集成，將集成結(jié)果作為輸入高維數(shù)據(jù)的最終分類結(jié)果，擴充高維數(shù)據(jù)有標記樣本的數(shù)目.集成方法如下所示:

式中，f(t)表示測試樣本xt的最終標記值，yi表示測試樣本xt在第i個最優(yōu)特征子集中的預(yù)測標記，k表示分類的類別.

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

3.1 實驗平臺及數(shù)據(jù)集

在UCI中的高維數(shù)據(jù)集上進行實驗，實驗數(shù)據(jù)集如表1所示.實驗?zāi)M半監(jiān)督學習過程，將樣本集分為有標記樣本和無標記樣本，其中有標記樣本所占的比例很小.實驗中，與經(jīng)典半監(jiān)督集成算法(Co-Forest[9]，Tri-training[10]，PSEMISEL[15])進行比較，對提出S3LSE的有效性和魯棒性進行評估.

3.2 實驗評價指標

分類問題中，通常采用下面四個度量來評估結(jié)果.

?True Positive (TP):分類正確，把原本屬于正類的樣本分成正類.

?True Negative (TN):分類正確，把原本屬于負類的樣本分成負類.

?False Negative (FN):分類錯誤，把原本屬于正類的錯分成了負類.

?False Positive (FP):分類錯誤，把原本屬于負類的錯分成了正類.

表1 實驗數(shù)據(jù)集

由于本實驗中選取數(shù)據(jù)集是平衡的，主要將accuracy等參數(shù)作為算法的性能評價指標，進行30 次實驗求平均值，評價本文提出的算法與傳統(tǒng)的經(jīng)典算法之間的差別性，驗證所提出算法的有效性.基于上述四個度量，使用式(12)定義Accuracy:

實驗主要分為以下三大類進行操作:

實驗一:驗證提出的半監(jiān)督算法處理高維數(shù)據(jù)的有效性.模擬半監(jiān)督實驗過程，使用經(jīng)典半監(jiān)督集成算法(Co-Forest，Tri-training，PSEMISEL)和本文提出的半監(jiān)督學習算法S3LSE 分別處理高維數(shù)據(jù)，對比幾種算法的實驗結(jié)果.

實驗二:驗證隨機子空間集中特征優(yōu)化的有效性.實驗分兩種進行，第一種實驗不使用特征優(yōu)化算法，直接對隨機子空間集產(chǎn)生的樣本集進行半監(jiān)督學習，計算對應(yīng)高維數(shù)據(jù)的分類正確率；第二種實驗使用特征優(yōu)化算法對隨機子空間集產(chǎn)生的數(shù)據(jù)進行優(yōu)化，形成最優(yōu)特征子集，在最優(yōu)特征子集中進行半監(jiān)督學習，計算對應(yīng)高維數(shù)據(jù)的分類正確率.最后，對比兩種實驗的結(jié)果.

實驗三:驗證本文提出的安全的數(shù)據(jù)樣本標記方法的有效性.模擬半監(jiān)督實驗，與其它算法進行比較.

3.3 實驗結(jié)果及分析

3.3.1 實驗一的結(jié)果及分析

本實驗中模擬半監(jiān)督實驗過程，使用經(jīng)典半監(jiān)督集成算法(Co-Forest，Tri-training，PSEMISEL)和本文提出的S3LSE 分別處理高維數(shù)據(jù)，實驗結(jié)果如表2所示.

表2 準確率(Accuracy)對比表

從表2 可以看出，本文提出的算法S3LSE 相對傳統(tǒng)的經(jīng)典半監(jiān)督集成算法具有較好的分類性能.這是因為:(1)算法S3LSE 充分利用高維數(shù)據(jù)特征之間的關(guān)系，挖掘高維數(shù)據(jù)之間的隱含信息，擴充有標記高維數(shù)據(jù)的數(shù)目，提高了高維半監(jiān)督學習的性能.(2)算法S3LSE 對新增標記進行可靠性驗證的方法，保證新增標記樣本的增加后，分類器的性能不會惡化，保證分類器向著誤差減小的方向進行演化.(3)算法S3LSE 通過多分類器之間的多次集成，提高分類器的魯棒性.

3.3.2 實驗二的結(jié)果及分析

第一種實驗不使用特征優(yōu)化算法，直接對隨機子空間集產(chǎn)生的樣本集進行半監(jiān)督學習(算法記作S3LSE - FL)，計算對應(yīng)高維數(shù)據(jù)的分類準確率和分類時間；第二種實驗使用特征優(yōu)化算法對隨機子空間集產(chǎn)生的數(shù)據(jù)進行優(yōu)化，形成最優(yōu)特征子集，在最優(yōu)特征子集中進行半監(jiān)督學習(即S3LSE)，計算對應(yīng)高維數(shù)據(jù)的分類準確率和分類時間.

實驗結(jié)果如表3所示，從表中可以看出本文提出的算法S3LSE 通過對特征集進行優(yōu)化，減少了特征的數(shù)目，縮短了分類時間.和沒有使用特征優(yōu)化的算法S3LSE - FL 相比，S3LSE 分類準確率并沒有因為特征的減少而降低.同時，在有些數(shù)據(jù)集中，S3LSE的分類準確率不但沒有降低反而得到了提高，這是因為特征優(yōu)化算法選取了最優(yōu)的特征組合，刪除了一些與分類無關(guān)或者作用不大的特征，新的特征集更有助于分類，分類性能更好.

3.3.3 實驗三的結(jié)果及分析

實驗中模擬半監(jiān)督學習，一種方法使用本文提出安全的數(shù)據(jù)樣本標記方法實現(xiàn)對未標記樣本進行標記(記做S3LSE，一種方法使用S3VM[20]實現(xiàn)對未標記樣本進行標記(記做S3VM)，對比兩種方法的實驗性能.

表3 準確率和分類時間對比表:準確率(%)/分類時間(s)

實驗結(jié)果如表4所示，通過實驗結(jié)果可以看出，采用本文提出安全的數(shù)據(jù)樣本標記方法能保證新增加樣本標記的可靠性，分類準確率得到了有效提高.這是因為本文提出安全的數(shù)據(jù)樣本標記方法保證新樣本添加到有標記樣本集后，分類器向著誤差降低的方向進行演化.

表4 準確率對比表

通過以上實驗結(jié)果可以看出，算法S3LSE 是一個性能較好的分類算法.其從探索數(shù)據(jù)樣本空間和特征空間兩個角度出發(fā)，結(jié)合隨機子空間技術(shù)和多分類器集成技術(shù)，處理僅包含極少量有標記樣本的高維數(shù)據(jù)分類問題.它通過對特征子集進行優(yōu)化，選取能有效反映特征的相關(guān)性、特征之間的冗余度等信息的特征進行半監(jiān)督學習，使用安全的數(shù)據(jù)樣本標記算法提高算法安全性，并使用集成技術(shù)提高算法的魯棒性.

4 結(jié)束語

本文從探索數(shù)據(jù)樣本空間和特征空間兩個角度出發(fā)，提出一種結(jié)合隨機子空間技術(shù)和集成技術(shù)的安全半監(jiān)督學習算法，處理僅包含極少量有標記樣本的高維數(shù)據(jù)分類問題.實驗結(jié)果表明本文的提出的算法能有效發(fā)揮集成學習和半監(jiān)督學習的優(yōu)勢，同時為處理高維數(shù)據(jù)開創(chuàng)了一種新途徑.下一步的研究內(nèi)容是將該算法應(yīng)用到大規(guī)模高維數(shù)據(jù)分類領(lǐng)域.