基于稀疏鄰域的主動不平衡學習算法

古平，凌照

（重慶大學計算機學院，重慶 400044）

0 引言

不平衡學習是機器學習中一種重要的分類問題，其中包含樣本數目較多的為多數類，而樣本數較少的為少數類。在許多實際應用中都存在不平衡問題，例如網絡入侵檢測[1]、信用卡欺詐檢測和垃圾郵件檢測。自不平衡學習問題被提出以來，已有大量的學習方法被開發用于解決該問題，這些工作大多分為兩類：重采樣技術和代價敏感學習技術[2]。重采樣是一種重新平衡類分布的技術，它通過對少數類進行過采樣或對多數類進行欠采樣而實現。代價敏感方法則為每個類提供不同的錯誤分類代價，而且一般少數類的分類錯誤的代價較大。與現有的方法不同，Ertekin等人提出了基于主動學習[3]策略的不平衡學習算法[4]（AL-SVM）來處理虛擬樣本合成以及信息量的度量問題。最近，P Vateekul等人提出了一種基于G-means的主動學習模型來解決不平衡問題，并發現尤其適用于大規模數據集[5]。

直覺上主動學習在不平衡學習中的應用是從未標記的數據集中主動選擇可能的少數類樣本，然后標記并添加它們到初始訓練集中以產生平衡的數據集。不幸的是，該技術可能會在不平衡的設定下遭受標記成本較大的風險，也就是說，由于初始數據分布是傾斜的，所以未標記的多數類樣本將比少數類樣本更頻繁地被查詢和標記，最后導致主動學習在降低不平衡率的效果上將受到較大的限制。

經過對主動學習和半監督學習[6]的研究啟發，我們通過計算樣本的少數類置信度，提出了一種新的針對不平衡學習的主動學習算法：基于稀疏鄰域的主動不平衡學習算法（ASS-SN）。它有效地克服了虛擬樣本合成的局限性，并且具有針對少數類樣本有效查詢的優點。其基本思想是僅使用小規模的有標記數據和大量未標記數據計算出未標記樣本的少數類置信度，然后選擇置信度最高的未標記樣本作為迭代查詢的標準。其中我們利用半監督學習技術來確定每個未標記樣本的少數類置信度，受稀疏編碼的啟發，與其他基于圖結構的半監督方法不同，我們通過求解一個L1最優化問題來計算出圖結構的頂點與邊權重信息，從而不需要預先設定相關參數的大小。

1 算法過程及框架

1.1 相關概念以及動機

給定不平衡數據集X={x1,x2,…,xm+n},xi∈Rd,1≤i≤m+n，其中d為維數?？梢詫⒃摬黄胶鈹祿疿劃分為XL和XU，其中XL=(x1,y1)…(xm,ym)是有標記的數據集，而且每一個樣本包含有獨一無二的屬于（0,1）的樣本標簽，yi代表其類別標簽。XU=(xm+1,ym+1)…(xm+n,ym+n)代表未標記的數據集，其類別標簽未知。在有標記的數據集XL中，IR代表該數據集的不平衡比率。

我們所提出的問題是如何在以下情況使用未標記數據來提高監督學習算法的準確性：①只有少量有標記的樣本可用。②有大量未標記的數據。③在有標記的數據集中，少數類樣本數量遠遠少于多數類。經過AL-SVM算法的啟發，我們發現該方法存在一個主要的缺點：直接將SVM算法應用到不平衡的數據集會導致該超平面存在偏倚，并且偏向于多數類樣本，因此該算法并沒有考慮查詢有效性的問題，即希望不平衡學習算法能夠有效地查詢未標記的樣本盡可能為少數類樣本以達到均衡數據集的目的，從而降低人工標注成本。為此，我們采用了一種完全不同的主動采樣策略，其目標是盡可能多地標記少數類樣本，從而均衡初始的有標記數據集并提高分類性能。因此該策略包含本文的核心問題定義：少數類置信度。

定義1少數類置信度（MC）：對于任意未標記樣本xi∈XU，假設其屬于少數類或者多數類的概率為yui mi或yui ma，那么該樣本xi的少數類置信度（MC）可以通過以下公式計算：

Mci越大，表示該樣本屬于少數類的可能性就越高。如果我們根據少數類置信度相應地對未標記的樣本進行主動采樣，則更有可能正確地選擇并標記它們為少數類樣本。

1.2 半監督學習技術求解少數類置信度問題

根據定義1，我們的主動采樣策略是根據未標注樣本的少數類置信度選擇最可能的少數類樣本，也就是說，這個問題可以轉換為求解未標記樣本分別屬于多數類和少數類的概率。為了解決這個問題，在機器學習中我們知道半監督學習旨在對標記樣本和未標記樣本進行學習，尤其是基于圖的半監督學習方法。大多數現有的半監督學習方法是基于k最近鄰（knn）圖提出的，但k值在實際應用中難以預先確定，且尤其是在不平衡數據集中。受稀疏編碼的啟發，我們通過求解L1最優化問題來構建稀疏鄰域圖[7]，這避免了在不同場景中預先定義k值的難題。最后通過在樣本的稀疏鄰域中實現標簽傳播來測量未標記樣本的少數類置信度。

（1）構建稀疏鄰域圖

假設定義一個線性方程組：xi=Xiαi，其中xi是要表示的樣本，αi是重建系數的向量，Xi是除了xi的其他樣本，可以表示為：Xi=[x1…xi-1,xi+1…xm+n]。通過稀疏編碼的啟發，激勵我們通過解決以下最優化問題來尋求xi=Xiαi的最稀疏的解決方案：

通過求解結果我們發現在系數重建過程中某些距離表示樣本較遠的“壞的”樣本的重建系數一般較小而且會對標簽傳播起到負面作用。為了解決這個問題，我們定義了給定樣本xi的稀疏鄰域。

定義2稀疏鄰域（SN）：給定參數ε，樣本xi的稀疏鄰域定義為：如果重建過程中樣本xj，i≠j的重建系數αj滿足αj＞ε，則認為樣本在xj給定樣本xi的稀疏鄰域中，或者xj∈SN(xi)。

根據定義2，對于給定的樣本xi，我們刪除了那些所謂的“壞的”樣本，即這些樣本的重建系數很小。也就是說，我們強調那些在稀疏鄰域中的樣本的作用并且認為這些樣本與被表示的樣本“相似”。因此，構造的稀疏鄰域圖的目標函數由下式給出：

其中G表示稀疏鄰域圖，如果αij＜ε，則αij=0。這表明如果樣本xj不在樣本xi稀疏鄰域中，則重建系數將為0。

（2）基于稀疏鄰域的標簽傳播

假設對于樣本xi，xi的標簽可以由來自xi的稀疏鄰域的那些樣本標簽線性重建。并且我們假設標簽空間和樣本空間共享相同的局部線性重建權重，因此通過以下式子估計所有樣本的標簽：

基于基本的代數知識，可以很容易地推斷出：

I是一個單位矩陣，令W=(I-G)T(I-G)，我們可以得到結論：tr(YTWY)，tr(·)表示矩陣的跡。將Y進行劃分：Y=[YL；YU]，YU表示待求解的未標記樣本的標簽矩陣，YL表示有標記樣本的標簽矩陣。將矩陣W劃分為四個部分：

通過結論（5）：tr(YTWY)，我們求出關于Y的偏導數：

最后求解上式，獲得所有未標記樣本的標簽概率矩陣：

通過將上述推導過程應用于訓練數據集，每個未標記樣本將分別獲得屬于少數類和多數類的概率，該求解結果可以表示為因此跟據定義1，我們可以計算每個未標記樣本的少數類置信度，即

1.3 算法框架

基于稀疏鄰域的主動不平衡學習算法（ASS-SN）包括兩個關鍵步驟。首先我們通過求解L1最優化問題的方式構建稀疏鄰域圖，并在其基礎上進行標簽傳播，以計算每個未標記樣本的少數類置信度。其次，通過主動學習技術結合這種查詢策略進行迭代學習，并在每一次迭代中更新標簽傳播矩陣，直到數據集幾乎平衡。ASS-SN算法的框架如下：

輸入：XL：有標記的數據集

XU：大量的未標記數據集

輸出：XL：有標記數據集

（1）根據定義2以及公式（3）求解以下最優化問題，并構建稀疏鄰域圖G：

（2）while（IR＞1）：

①根據圖G，構建傳播矩陣W：W=(I-G)T(I-G),基于W進行標簽傳播，并計算出未標記樣本的標簽矩陣

②對每一個未標記樣本xi∈XU，根據定義1和標簽矩陣計算樣本xi的少數類置信度,Mci：

③根據Mci，選擇其中少數類置信度最大的ul個樣本交與專家標注，并將其中標注的少數類樣本添加到過渡集V中。最后讓XL=XL?{V},XU=XU{V}

④基于貝葉斯分類器重新訓練XL并跟新標簽傳播矩陣W

（3）end while

2 實驗結果與分析

實驗主要在來自UCI機器學習庫的數據集上進行，即Prima數據集。為了深度分析不平衡數據集對ASS-SN算法的影響，我們通過隨機刪除Prima數據集中樣本的標簽來獲得主動學習中所需的未標記樣本。表1顯示了在這種情況下選擇的數據集。為了評估不同算法在不平衡問題上的分類性能，我們采用了針對不平衡問題的經典評估方法，即F-measure[8]。在本文算法第1.2小節中，需要對是否處于稀疏鄰域中的樣本進行判定，我們根據經驗和稀疏表示的特征選擇ε的值，并且將稀疏鄰域ε的半徑固定在0.02。本文算法與兩種流行的主動學習算法進行比較，即AL-EN[3]和AL-SVM，其中AL-EN是一種基于信息熵測量的主動學習方法。

表1 實驗所采用的數據集

從圖1可以看出，對于每種主動學習技術，每次查詢的樣本中少數類樣本的數量都受到不平衡數據集的強烈影響。例如，如果查詢284個未標記的樣本，通過本文算法可以有效地標記181個少數類樣本，而在AL-EN和AL-SVM中則只能標記98和73個少數類樣本。從算法整體來分析可以看出由于本文算法有效地利用稀疏標簽傳播算法使得在主動學習采樣的過程中，少數類未標記樣本的采樣概率大幅度提升。因此在每一輪標注占比上，本文算法完全優于其他主動學習算法，并且會提前完成對大部分少數類樣本的標注。

從圖2中，可以看到在每次的迭代過程中，F1值隨著主動采樣過程而逐漸增加，但是可以觀察到，ASSSN的F1值優于AL-EN和AL-SVM。例如，AL-EN和AL-SVM的最佳 F1值分別為 0.6278和 0.5098，而ASS-SN算法可以達到0.7107?？傊?，這種性能提升是由于通過這種有傾向性的主動學習算法在少數類上具有強大的搜索能力，特別是當這些樣本遠離最初的少數類群體時；傳統的主動學習算法傾向于丟棄這些樣本，而本文的標簽傳播機制可以有效地找到它們。

圖1 少數類的標記效率

圖2 每次迭代采樣后的分類性能

3 結語

本文中我們提出了一種自適應的主動學習方法針對不平衡學習問題，本文算法的一個優點是利用稀疏鄰域的標簽傳播策略計算未標注樣本的少數類置信度，并專注于采樣其置信度較高的樣本，從而有效地解決不平衡問題并降低標記成本。其次通過引入主動學習技術的迭代過程，使得本文算法能夠有效地提高不平衡數據集的分類性能。雖然ASS-SN算法在大多數情況下都能獲得更好的性能，但仍有許多問題需要解決，例如我們所提出的算法比其他算法消耗更多的時間。