基于采樣技術的主動不平衡學習算法研究

李青雯 ，孫 丹 ，于化龍 ，2

（1.江蘇科技大學計算機科學與工程學院，江蘇鎮江212003；2.東南大學自動化學院，江蘇南京210095）

近年來，隨著數據獲取與數據存儲技術的高速發展，各行各業均積累了海量的數據，如何對這海量數據進行分析成為了困擾機器學習與數據挖掘領域研究者的核心問題。如對這海量數據的類別進行標注，進而建立分類模型，無疑會大幅增加人力、物力與時間成本的開銷，而主動學習則是可有效解決上述問題的利器。眾所周知，主動學習通過迭代的方式來選取當前信息含量最大的樣本，進而不斷提升分類模型的質量，故其可在不明顯損失分類性能的情況下，有效地降低訓練樣本的復雜性。

經過多年研究，研究人員已提出了多種有效的主動學習算法，但其幾乎均忽略了一個重要問題，即在樣本不平衡分布場景下，這些算法是否會仍舊有效。對于主動學習與類別不平衡學習的結合方式，目前一共有兩種，其一是利用主動學習來解決類別不平衡分類問題，Ertekin等人[1-2]發現主動學習可有效緩解類別不平衡分布對分類器的負面影響；其二則是在類別不平衡場景下，如何保證主動學習的效率，Zhu及Hovy[3]對該問題進行了初步的研究，并提議：對于分布不均衡的數據，應在主動學習過程中引入平衡控制策略，從而保證在迭代過程中每一輪所生成的分類面都是公平公正的。本文主要關注上述的第二種結合方式，即如何在類別不平衡數據中保持主動學習的效率與性能。

文中考慮采用類別不平衡學習領域中最為簡單與常用的樣本采樣技術來作為主動學習過程的平衡控制策略。并通過分析現有采樣算法的不足之處，提出了一種適用于此類場景的邊界過采樣算法。特別地，為了加速主動學習的進程，我們采用極限學習機（Extreme Learning Machine，ELM）作為主動學習的基分類器，因其同時兼具泛化能力強與訓練速度快兩大優點，具體采用文獻[4]中的“查詢樣本”選擇策略。通過12個基準數據集對添加了“平衡控制”策略的主動學習算法與傳統主動學習算法進行了比較，得出前者可大幅提升主動學習性能的結論。

1 基于池的主動學習模式概述

主動學習，即通過主動獲取樣本的方式來進行學習。其目的是通過標注盡可能少的樣例來使分類性能最大化[5]。根據應用場景的不同，主動學習大致可以分為以下兩類：基于流的主動學習模式和基于池的主動學習模式。本文側重于基于池的主動學習模式，而圖1則描述了在這一模式下的主動學習過程。

圖1 基于池的主動學習模式過程示意圖

從圖1中，不難看出，在此類模式下，主動學習由以下5個基本構件組成：1）一個已標記樣例集L；2）一個未標記樣例集U；3）一個分類模型S；4）一個查詢算法q及5）一個人工標注者T。最初，人工標注者T僅隨機地標注少量的未標注樣本，并將其置于已標記樣例集L中，并訓練一個初始的分類模型S。接下來，進入循環迭代過程：利用分類模型S評價未標記樣例池U中的每一個樣例，并利用查詢算法q提取各樣例的信息量，進而根據信息量大小對其進行排序，選取一個或一批信息量最大的樣例提交給人工標注者T進行標注，最后再將標注的樣例添加到已標記樣例集L中，對分類模型S進行更新。上述過程循環往復，直至達到某個預設的停止條件為止。

然而，若已標注與未標記樣例集均是類別分布不均衡的，則會對上述主動學習流程產生較大負面影響。若學習過程中每一輪所建立的分類模型都是偏倚的，那么必然會導致“查詢樣本”選擇得不準確，進而影響到下一輪所更新模型的質量。此時，應引入平衡控制策略，文中考慮采用樣本采樣技術作為平衡控制策略。

2 方法

2.1 樣本采樣技術

樣本采樣技術是用于解決類別不平衡問題的基本技術之一。所謂樣本采樣，即是通過增加少數類樣本或減少多數類樣本的方式來獲得相對平衡的訓練集，以修正分類面偏倚的問題。其中，增加少數類樣本的方法被稱為過采樣（Oversampling），而減少多數類樣本的方法則被稱為降采樣（Undersampling）。隨機過采樣（ROS，Random Over-Sampling）與隨機降采樣（RUS，Random Under-Sampling）是最簡單、也是最為常用的樣本采樣技術。但上述二者均有其各自的缺點，其中，前者會增加分類器建模的時空開銷，并易于產生過適應的現象，而后者則會造成分類信息嚴重缺失，從而導致分類性能顯著下降。為克服隨機采樣的缺點，Chawla等人[6]于2002年提出了一種新的過采樣方法：SMOTE（Synthetic Minority Oversampling TEchnique）。不同于隨機過采樣方法，SMOTE通過在兩個鄰近的少數類樣本間插入虛擬樣本，有效解決了ROS方法易于陷入過適應的問題。

可以說，樣本采樣技術的最大優點在于其過程與分類器訓練的過程是相互獨立的，故若采用此項技術作為主動學習的平衡控制策略，可能更具實用性與便捷性。

2.2 邊界過采樣算法

考慮到在主動學習每一輪迭代時，所選取的“查詢樣本”往往都位于當前分類面，即分類邊界附近，故若對少數類樣本進行過采樣，顯然更應該集中在邊界域。基于上述思想，對傳統的SMOTE算法進行了改進，提出了一種邊界過采樣（BOS，Boundary Over-sampling）算法，使其僅能對邊界少數類樣本進行過采樣，該算法的流程描述如下：

算法1：BOS算法

輸 入 ：訓 練 集S={（xi，yi），i=1，2，…，N，yi∈{+，-}}；多數類樣本數N-，少數類樣本數N+，其中，N-+N+=N；不平衡比率IR=N-/N+；近鄰數K，邊界樣本比例λ

輸出：過采樣后的訓練集S’={（xi，yi），i=1，2，…，N，i=1，2，…，2×N-，yi∈{+，-}}

算法步驟：

1）從訓練集S中取出全部多數類與少數類樣本，組成多數類樣本集S-及少數樣本集S+；保留全部的多數類訓練樣本，選取最靠近分類面的λ*N+個少數類樣本，并置于一個獨立的集合S+Neighbor；

2）置新生成樣本集SNew為空；

3）Fori=1:|N--N+|

①在S+Neighbor中隨機選取一個少數類樣本x，作為主樣本；

②在S中找到主樣本x的K近鄰樣本，并將其置于近鄰樣本集SNer中；

③在SNer中隨機指定一個主近鄰樣本x’；

④通過下式計算得到新的虛擬的邊界少數類樣本xnew:xnew=x+rand×（x’-x），其中，rand∈[0，1]；

⑤ 添加xnew至SNew，即SNew=SNew∪xnew；

⑥置近鄰樣本集SNer為空；

End

4）得到過采樣后的訓練集S’=S∪SNew。

從上述算法流程不難看出：BOS算法是對SMOTE算法的一種改進，即僅在靠近邊界區域的部分樣本上執行SMOTE算法過程。當然，這個“部分”的范疇是由參數λ所指定的，可以說，該參數設置的好壞與否將直接影響到最終的采樣效果。

2.3 極限學習機與主動極限學習機

極限學習機（ELM，Extreme Learning Machine）是由南洋理工大學Huang等人[7]于2006年所正式提出的一種單隱層前饋神經網絡訓練算法。ELM通過隨機指定隱層參數，并利用最小二乘法求解輸出層權重的方式來訓練網絡，故其具有泛化能力強、訓練速度快等優點[8-9]。

設訓練集包括N個訓練樣本，可將其表示為(xi,ti)∈Rn×Rm，其中，xi表示n×1維的輸入向量，ti表示第i個訓練樣本的期望輸出向量，n即代表訓練樣本的屬性數，m則代表樣本的類別數。若一個具有L個隱層節點的SLFN能以零誤差擬合上述N個訓練樣本，則意味著存在βi，ai及bi，使得：

其中，ai和bi分別表示第i個隱層節點的權重與偏置，βi表示第i個隱層節點到各輸出節點的連接權重，則式（1）可進一步簡化為下式：

其中

其中，G(ai,bi,xj)表示第j個訓練樣本在第i個隱層節點上的激活函數值，T為所有訓練樣本對應的期望輸出矩陣，H被稱為隱層輸出矩陣，其第i列為第i個隱層節點在所有訓練樣本上的輸出向量，第j行為第j個訓練樣本在整個隱藏層中對應的輸出向量。

在ELM中，由于所有ai和bi均是在[-1，1]區間內隨機所生成的，故輸入樣本、隱層權重與偏置、期望輸出（類別標記）均已知，則輸出權重矩陣β的近似解?即可由下式直接計算得到的：

其中，H?為隱層輸出矩陣的Moore-Penrose廣義逆。根據其定義，可推知為該網絡的最小范數最小二乘解。由于在求解過程中，約束了輸出權重矩陣β的l2范數，使其最小化，故可保證網絡具有較強的泛化性能。鑒于ELM的優點，其也在諸多應用領域得到了應用，如行為識別[10]、遙感圖像分類[11]、電價預測[12]、風能生成預測[13]及生物信息學[14]等。

主動極限學習機，即AL-ELM算法，是Yu等人[4]所提出的一種以ELM作為基分類器，且以樣本在ELM中的輸出值作為不確定性度量準則，進而選取“查詢樣本”的主動學習算法。受篇幅所限，在此不再贅述，有關該算法的具體細節，可參見文獻[4]。

2.4 結合采樣技術的主動不平衡極限學習機算法

結合AL-ELM算法與樣本采樣技術，可知主動不平衡極限學習機算法的具體流程如下：

算法2：主動不平衡極限學習機算法

輸入：初始已標注樣本集L，未標注樣本集U；樣本采樣算法P

輸出：最終的極限學習機分類器M

算法步驟：

1）利用初始已標注樣本集L訓練一個初始的極限學習機分類器M；

2）采用M，并利用AL-ELM算法中的“查詢樣本”選擇策略，選取并標注查詢樣本，進而將其置入集合Sselect中；

3）while（未達到學習停止條件）

①L=L+Sselect；

②U=U-Sselect；

③ 置Sselect為空；

④調用樣本采樣算法P對樣本集L進行采樣處理；

⑤利用已標注樣本集樣本集L對分類器M進行更新；

⑥采用M，并利用AL-ELM算法中的“查詢樣本”選擇策略，在U中選取并標注查詢樣本，進而將其置入集合Sselect中；

⑦若達到學習停止條件，則退出，否則轉步驟①；

End

4）輸出最終訓練的極限學習機分類器M。

從上述算法流程中，可以看出：其與傳統的主動學習算法僅有一點不同，即該算法在提取并標注“查詢樣本”后，多出了一個平衡控制過程，而這一過程采用了樣本采樣的策略，采樣算法既可以選擇RUS、ROS、SMOTE，也可以選擇本文所提出的BOS算法。

3 實驗結果與分析

3.1 數據集描述

文中實驗共采用了12個采集自Keel數據庫[15]的基準數據集，用以比較傳統的主動學習算法和采用了樣本采樣技術作為平衡控制策略的主動學習算法之間的性能。特別需要說明的是，實驗所選取的數據集均為二類數據集，有關這些數據集的具體信息如表1所示。

表1 實驗所用數據集

3.2 實驗設置

為證明樣本的不平衡分布確實會對主動學習產生影響，同時也為了展示加入了平衡控制策略的算法的優越性，確定了如下5種比較算法：

1）AL-ELM：即基準的主動極限學習機算法[4]；

2）AL-ELM-RUS：即以RUS算法作為平衡控制策略的主動極限學習機算法；

3）AL-ELM-ROS：即以ROS算法作為平衡控制策略的主動極限學習機算法；

4）AL-ELM-SMOTE：即以 SMOTE 算法作為平衡控制策略的主動極限學習機算法；

5）AL-ELM-BOS：即以BOS算法作為平衡控制策略的主動極限學習機算法；

在實驗中，預設各數據集初始已標注樣本比例為15%，未標記樣本比例為55%，剩余的30%作為測試樣本。主動學習考慮基于池的場景，以批處理方式進行，每輪標注初始未標注樣本集規模的5%。為了窺探主動學習過程的全貌，故未預設學習停止條件，即意味著學習過程將隨著未標注樣本池中的樣本耗盡位置。

此外，考慮到對于不平衡分類問題而言，整體分類精度不再是一種有效的性能測度，故采用G-mean測度及ALC測度[4]來反應各算法的性能。

最后，對于ELM分類器，其參數在各類算法上均保持統一設置，即激活函數選用Sigmoid，隱層節點數為100，懲罰因子則設為10000。

圖2 五種學習算法在12個數據集上的學習曲線

3.3 結果與討論

圖2給出了5種主動學習算法在12個數據集上的學習曲線，而表2則給出了它們對應的ALC測度值和學習過程中能達到的MAX G-mean測度值，其中，用粗體標識每個數據集上最優的結果，粗斜體則標識第二好結果。

基于上述圖表中的結果，可得出如下結論：

1）在絕大多數數據集上，采用樣本采樣技術做平衡控制策略的主動學習算法均要優于原始的主動學習算法。實際上，這一現象是易于解釋的，這主要是因為前者采用了平衡控制策略，故在學習過程中的每一輪所訓練的分類面位置均是相對公正的，故可保證所選取的“查詢樣本”的公正性，而后者則無法保證這一點。另從ALC和Max G-mean測度值中可以看出，原始的主動學習算法幾乎總是處于較低水平。所以可以得出主動學習算法的性能確實會受到樣本不平衡分布負面影響的結論。

2）AL-ELM-RUS算法在超過半數數據集上均獲得了優于其它算法性能的結果。這種現象不僅體現在那些不平衡比率較低的數據集上，在某些極度不平衡數據集上，如abalone19數據集，也是如此。因此，我們相信這不僅與數據集的不平衡比率有關，可能還關聯著諸多的因素，如樣本的類重疊面積大小、訓練樣本的絕對數量、噪聲樣本的比率等[16]。此外，RUS算法也有著過采樣算法所無法比擬的一個優勢，那就是時間復雜度低。故在實際應用中，AL-ELM-RUS算法將是一個較好的備選方案。

3）相比于AL-ELM-ROS與AL-ELM-SMOTE算法，AL-ELM-BOS算法顯然已在更多數據集上獲得了較優的性能。這一現象也不難理解：首先，ROS算法易于導致分類模型陷入過適應；其次，SMOTE算法在生成虛擬少數類樣本時，采取的是均勻采樣，而主動學習所標注的多數類樣本則普遍存在于分類邊界附近，這就導致了在邊界區域的樣本分布不均衡；最后，BOS算法雖然繼承自SMOTE算法，但其生成的少數類樣本均分布于分類邊界附近，這便可保證下一輪所生成分類面位置的合理性。

4）當然，也有一些特殊的情況存在，如在led7digit_0_2_4_5_6_7_8_9_vs_1和vowel0這兩個數據集上，原始的AL-ELM算法的分類性能始終處于一個較高的水平，甚至要好于那些添加了平衡控制策略的主動學習算法。我們認為上述現象的出現仍與樣本分布的特點相關，這兩個數據集上不同類樣本的分布顯然具有更強的可分性。

基于上述分析，可凝練得出如下兩點結論：1）在大多數情況下，樣本的類別不平衡分布會對傳統的主動學習算法產生負面影響；2）在主動學習的每一輪迭代過程中引入樣本采樣技術，確實可明顯提升其性能，且采取隨機降采樣法或本文所提出的邊界過采樣法有望獲得更好的性能。

表2 5種學習算法在12個數據集上的ALC測度值和MAX G-mean值

4 結束語

針對在樣本類別分布不均衡時，傳統的主動學習算法可能失效這一問題展開了調查與研究。提出在主動學習過程中，引入樣本采樣技術作為平衡控制策略，并在分析其過程的基礎上，對SMOTE算法進行了改進，進而提出了一種邊界過采樣算法，即BOS算法。考慮到極限學習機所具有的諸多優點，采用其作為主動學習的基分類器。通過12個基準二類不平衡數據集對上述算法思想進行了驗證，表明了其有效性與可行性。在未來工作中，希望能將本文工作擴展應用于多類不平衡數據上，同時也希望能借鑒類別不平衡學習領域的最新成果，以提出更為有效與高效的平衡控制算法。

[1]Ertekin S，Huang J，Giles C L.Active learning for class imbalance problem[C]//Proceedings of the 30th annual international ACM SIGIR conference on research and developmentin information retrieval，ACM Press，2007:823-824.

[2]Ertekin S，Huang J，Bottou J，et al.Learning on the border:active learning in imbalanced data classification[C]//Proceedings of the sixteenth ACM conference on information and knowledge management，ACM Press，2007:127-136.

[3]Zhu J，Hovy E.Active Learning for Word Sense Disambiguation with Methods for Addressing the Class Imbalance Problem[C]//Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning，Prague，2007：783-790.

[4]Yu H，Sun C，Yang W.AL-ELM:One uncertaintybased active learning algorithm using extreme learning machine[J].Neurocomputing，2015（166）:140-150.

[5]Wang M，Hua X S.Active learning in multimedia annotation and retrieval:a survey[J].ACM Transactions on Intelligent System and Technology，2011，2（2）:210-231.

[6]Chawla N，Bowyer K W，Hall L O.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research，2002，16（1）:321-357.

[7]Huang G B，Zhu Q Y，Siew C K.Extreme learning machine:theory and applications[J].Neurocomputing，2006（70）:489-501.

[8]Huang G B，Zhou H，Ding X，et al.Extreme learning machine for regression and multiclass classification[J].IEEE Transactions on Systems，Man and Cybernetics，Part B:Cybernetics，2012，42（2）:513-529.

[9]Huang G，Huang G B，Song S，et al.Trends in Extreme Learning Machine:A Review[J].Neural Networks，2015，61:32-48.

[10]Minhas R，Baradarani A，Seifzadeh S，et al.Human action recognition using extreme learning machine based on visual vocabularies[J].Neurocomputing，2010，73（10-12）:1906-1917.

[11]Samat A，Du P，Liu S，et al.ELMs:Ensemble ExtremeLearningMachinesforHyperspectral Image Classification[J].IEEE Journal of Selected Topics in Applied Earth Observations And Remote Sensing，2014，7（4）:1060-1069.

[12]Chen X，Dong Z Y，Meng K，et al.Electricity Price Forecasting With Extreme Learning Machine and Bootstrapping[J].IEEE Transactionson Power Systems，2012，27（4）:2055-2062.

[13]WanC，XuZ，PinsonP，etal.ProbabilisticForecasting of Wind Power Generation Using Extreme Learning Machine[J].IEEE Transactions on Power Systems，2014，29（29）:1033-1044.

[14]Li L N，Ouyang J H，Chen H L，et al.A Computer Aided Diagnosis System for Thyroid Disease Using Extreme Learning Machine[J].Journal of Medical Systems，2012，36（5）:3327-3337.

[15]Alcalá-Fdez，Fernandez A，Luengo J，et al.KEEL Data-Mining Software Tool:Data Set Repository，Integration of Algorithms and Experimental Analysis Framework[J].Journal of Multiple-Valued Logic and Soft Computing，2011（17）:255-287.

[16]Lopez V，Fernandez A，Garcia S，et al.，An insight into classification with imbalanced data:Empirical results and current trends on using data intrinsic characteristics[J].Information Science，2013，250（11）:113-141.