面向高維數據的安全半監督分類算法①

趙建華，劉 寧

1(商洛學院 數學與計算機應用學院，商洛 726000)

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

1 引言

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

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

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

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

但是，傳統的半監督集成學習方法仍然存在下面幾個局限性:

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

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

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

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

2 提出的算法

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

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

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

圖1 算法流程圖

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

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

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

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

(2)特征子集優化(Feature optimization，FL)

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

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

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

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

(3)在最優特征子集內，使用抽樣技術進行樣本子集劃分

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

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

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

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

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

算法1.安全樣本標記方法(Safe Labeling method，SL)輸入:有標記樣本集L；無標記樣本x；有監督分類器輸出:無標記樣本x 對應的標記過程:For i=1 to m/* m 表示數據的分類類別數*/使用偽標記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個偽標記對應的誤差:ei=1-(acci(1)+acci(2)+…+acci(k))/k；EndFor獲取e1，e2，…，em的最小值，記為emin；emin 對應的標記t 作為樣本x的預測標記.

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

(5)在最優特征子集內進行分類器集成

在最優特征子集內實現G個分類器的集成，采用最大投票法進行集成，即將相同標記數目最多的分類器對應的標記作為集成分類器的標記.集成方法如下:

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

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

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

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

3 實驗及結果分析

3.1 實驗平臺及數據集

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

3.2 實驗評價指標

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

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

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

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

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

表1 實驗數據集

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

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

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

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

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

3.3 實驗結果及分析

3.3.1 實驗一的結果及分析

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

表2 準確率(Accuracy)對比表

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

3.3.2 實驗二的結果及分析

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

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

3.3.3 實驗三的結果及分析

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

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

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

表4 準確率對比表

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

4 結束語

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