基于動態選擇技術的食品安全謠言不平衡數據集分類方法

何思宇 汪顥懿 左 敏 張青川

(北京工商大學農產品質量安全追溯技術及應用國家工程實驗室 北京 100048)

0 引 言

不平衡數據集(Imbalanced Datasets)的特征是一個類的樣本數量明顯高于另一個類。這類數據在現實生活中非常常見，例如，在食品檢疫中不合格品數量通常遠小于合格品數量；在垃圾郵件過濾中垃圾郵件的數量往往小于一般郵件的數量[1]；在欺詐交易識別中絕大部分交易是正常的，只有極少部分的交易屬于欺詐交易等，諸如此類。

有關食品領域的食品安全謠言識別也是典型的不平衡數據集分類問題。有關食品的謠言，在因互聯網普及而信息傳播極快的今天，傳播速度與范圍也變得越加快而廣。并且由于食品領域關系國計民生，為解決困擾食品領域的謠言識別問題，針對不平衡數據集開發健壯的機器學習過程十分重要。

通常，機器學習算法對數據集的每個樣本都給予同等的重視，這使得它們在實驗中偏向于大多數類[2]。這就產生了一個問題，因為從商業角度來看，在現實生活中少數類重要性往往要高于多數類。針對不平衡數據集開發的這些機器學習過程要考慮到數據分布的不平衡特性，并相應地進行處理。

動態選擇(Dynamic Selection，DS)是一種技術，它生成一個分類器池，并根據在測試樣本局部區域的預測能力，為每個測試樣本選擇一個基分類器或一組基分類器。動態選擇是近年來一個活躍的研究領域，有研究稱它優于一些更標準的分類器組合方法，如Boosting[3]。

近年來，已有一些學者對解決不平衡學習問題的不同方法進行了比較：He等[4]提供了可能是最廣泛的關于不平衡學習方法的調查。Branco等[5]的工作建立在He等[4]開發的工作之上，并針對不平衡數據集而提出了一種新的分類方法。Krawczyk[6]描述了該領域的開放性研究問題，并指出了未來的研究方向。他們提出的一個建議是探索不同分類器的局部能力，并為每個分類器創建相應區域。這拓展了將動態選擇方法應用于不平衡學習的思路。

本文打算探討動態選擇方法如何有助于解決不平衡學習問題，并提出一種新的動態分類器選擇(Dynamic Classifier Selection,DCS)算法，稱為多分類不平衡數據集動態分類器選擇法(DCS-MI)，專門針對多類不平衡數據集的情況，并將其最終運用到食品安全謠言識別中。

1 動態選擇

1.1 動態選擇簡介

如前所述，動態選擇(DS)技術首先生成一個分類器池，對于每個測試樣本，根據它們在測試樣本的局部區域內的預測能力，選擇一個基分類器或一個分類器集合。該局部區域通常被稱為勝任域，通常由k-NN算法確定。用于選擇勝任域的數據集可以是訓練數據集，也可以是驗證數據集，稱為動態選擇數據集(dynamic selection dataset,DSEL)[7]。

總體而言，在動態選擇中，一個新的查詢樣本的分類通常包括三個步驟:

1) 勝任域的界定，也就是說，如何定義查詢樣本xj周圍的局部區域，在該區域中估計基本分類器的能力級別。

2) 確定用于估計基本分類器的能力水平的選擇標準，如準確性、概率性和排名。

3) 根據估計的能力水平確定選擇單個分類器(DCS)或分類器集合(DES)的選擇機制。

1.2 動態選擇算法分類

一般來說，動態選擇算法可分為動態分類器選擇(DCS)與動態集成選擇(Dynamic Ensemble Selection,DES)兩種類型。

圖1反映了動態分類器選擇和動態集成選擇的過程。

(a) Dynamic Classifier Selection(DCS)

(b) Dynamic Ensemble Selection(DES)圖1 動態選擇算法示意圖

動態分類器選擇技術是為每一個測試樣本選擇最優單個基分類器的技術，其中典型的算法有：

算法1局部分類器精度[7](Local Classifier Accuracy,LCA)技術，針對每個測試樣本x，在勝任域內選擇精度最高的基分類器。

算法2改進的分類器排名[7](Modified Classifier Ranking,RANK)技術，它選擇的基分類器能夠正確地預測連續最近鄰的最大數量。

而動態集成選擇技術則是選擇合適的集成基分類器組合的技術[8]，其中典型的算法有：

算法3KNORAU[9](Knora-Union)技術，它選擇能夠正確預測勝任域內單個樣本的所有基本分類器集合。

算法4META-DES[7](Meta Dynamic Classifier Selection)技術，它將基本分類器的選擇視為一個元學習問題。為了達到這個效果，它定義了一組元特征fi，與衡量基分類器ci預測樣本xi能力的標準相對應。這些元分類器編碼到一個向量vi,j，元分類器λ是訓練有素的預測如果ci為xj做出正確的預測。

最近有研究稱，與標準的集成機器學習技術相比，META-DES表現出了更好的性能。

算法5DES-MI[10](Dynamic Ensemble Selection for multiclass imbalanced datasets )技術：該算法利用隨機平衡方法生成平衡的訓練數據集。通過在驗證數據集中運用k-NN算法選擇勝任域Ω。然后，在Ω中的每個樣本s，將num設為在Ω中同為類s的樣本數量，以下是權重的分配計算公式:

式中：α是一個常數。考慮在勝任域內最準確的分類器的百分比，并對每個樣本的準確性進行加權，然后作為一個整體進行選擇。

2 不平衡學習

2.1 不平衡數據集

不平衡數據集是指在數據集中各類別樣本數量分布比例不均衡，即某些類別的數量遠大于或遠小于其他類別。在出現此類數據失衡嚴重的情況時，使用傳統標準機器學習算法處理不平衡數據集，會導致算法性能較差[11]。有研究表明，傳統分類器在數據不均衡比例超過4 ∶1時就會偏向于大的類別[12]。

2.2 不平衡數據集處理

根據Galar等[13]的研究成果，不平衡學習方法可以分為三類：

1) 算法級方法嘗試調整標準的機器學習算法，這樣算法就不會偏向多數類而忽略少數類。

2) 代價敏感的方法可以通過在少數類的樣本中引入更高的權重來調整數據，或者通過讓分類器接受代價來調整算法，例如在分類器的損失函數中進行調整。

3) 數據級方法尋求通過對少數類進行過采樣或對多數類進行欠采樣來重新采樣數據集。

但在實際應用中，算法級方法需要根據不同數據集進行調整，代價敏感學習代價也往往需要人為設定，沒有普遍適用性。因此本文嘗試從數據級方法出發，對數據進行處理，改變數據結構，以針對不平衡數據集提高分類器性能。

過采樣(over-sampling)和欠采樣(under-sampling)是兩類數據處理方法。過采樣方法即是對少數類的數據樣本進行隨機采樣來增加少數類的數據樣本個數；欠采樣即是對大類的數據樣本進行隨機采樣來減少大類的數據樣本個數。

本文采用過采樣技術中最具代表性的技術之一，合成少數類過采樣(Synthetic Minority Oversampling Technique，SMOTE)[14]來進行數據處理。它克服了過采樣的一些缺點，而且加強了原始數據，并已經被證明在很多領域解決不平衡學習問題都比較有效。

3 DCS-MI算法

3.1 Bagging集成算法

算法6Bagging[15]算法是集成學習中兩大類算法中的一個代表算法，其學習器之間不存在依賴關系并且可以并行生成學習器。 Bagging 方法具有可以減小過擬合的優點，所以其通常被使用在強分類器和復雜模型上，并且往往能夠取得良好的表現。

Bagging算法可以解決回歸問題和分類問題。它從原始數據中隨機抽取n個樣本，抽取過程重復s次，產生s個訓練集。在每個訓練集上進行訓練并得到一個弱分類器，最終會訓練出s個弱分類器。預測結果將由這些分類器投票決定：

過程：

1： fort=1,2,…,Tdo

3： end for

輸出：

3.2 SMOTE技術

算法7SMOTE[16]主要是基于數據集中現存的少數類樣本，計算樣本特征空間之間的相似度，以創建人工合成樣本。其步驟如下：

1) 對于少數類Smin∈S中的樣本，即xi∈Smin，計算它的k個近鄰。

2) 通過計算n維空間的歐氏距離，得到距離xi最近的k個Smin中的樣本數據。

3) 然后從k個近鄰中，隨機選擇一個樣本，產生人工合成的數據：

(a)

(b)圖2 SMOTE采樣具體過程

圖2展示了SMOTE的具體過程。其中：(a)展示了一個典型的不平衡的數據，SMOTE中的k取值為6。(b)展示了一個隨機產生的合成樣本，這個樣本是沿著和的直線產生的。這個隨機點將被添加到數據集，然后重復此過程，直到達到所需的樣本數量為止。

3.3 k-NN算法

算法8k-NN[17](k-Nearest Neighbor)算法是機器學習算法中最基礎、最簡單的算法之一。它既能用于分類，也能用于回歸。

k-NN分類是通過測量不同樣本之間的距離來實現。一般來說，在實踐過程中，k-NN中的k值采用交叉驗證的方式選取，而距離一般使用歐氏距離或曼哈頓距離：

歐氏距離公式為：

曼哈頓距離公式為：

k-NN算法可描述為：

1) 根據給定的距離量度方法在訓練集T={(x1,y1),(x2,y2),…，(xn,yn)}中，找出與初始樣本點x最近的k個樣本點，并將這k個樣本點所表示的集合記為Nk(x)，其中：x為預測樣本；xi∈X∈Rn為n維的樣本特征向量；yi∈Y={c1,c2,…,ck}為樣本的類別，i=1,2,…,N。

2) 根據多數投票的原則確定樣本x所屬類別y：

i=1,2,…,N，j=1,2,…,K

式中：I為指示函數。I計算如下：

3.4 DCS-MI算法提出

算法9將訓練數據集進行適當的劃分，這些訓練集將用于訓練基本分類器，驗證數據集即本文的DSEL。在訓練基分類器時，先在適當的訓練集上使用Bagging算法，然后使用SMOTE技術來進行數據處理，這樣在最后的數據集中，每個基分類器訓練的每個類的頻率是相同的。算法結構如圖3所示。

圖3 DCS-MI概述

通過對DSEL應用k-NN算法來確定勝任域。勝任域內的每個樣本都根據整個DSEL中同類樣本的數量進行加權。假設cl(x)是樣本x的類，num(c)是DSEL中c類樣本的數量，則勝任域內每個樣本x的權值為：

考慮其中一個分類器Ci，設Ci,c(x)是分類器Ci預測樣本x屬于c類的概率。于是，Ci在勝任域Ω中的損失如下:

最終，選擇損失值最小的分類器來預測測試樣本的分類。

3.5 DCS-MI算法時間復雜度

令tr為合適的訓練數據集的大小，b為基分類器的數量，m為每個樣本的特征數量?？紤]到Bagging子過程的時間復雜度為O(tr)，而SMOTE子過程的時間復雜度為O(m×tr2)，最壞情況下生成基本分類器的時間復雜度為O(b×m×tr2)。

設v為驗證數據集的大小，te為測試樣本的數量，k為k-NN算法中使用的近鄰的數量。應用k-NN算法的復雜度為O(v×m+v×k)。為每個類尋找權重的時間復雜度是O(v)。值得注意的一點是，只需要在開始時為類找到權重，而不是每次預測一個測試樣本的類時。因此，在勝任域內尋找樣本權值的時間復雜度為O(k)，明顯低于運行k-NN算法的時間復雜度。因此，預測測試樣本類的時間由應用k-NN所需的時間決定。因此，為te測試樣本選擇基本分類器的時間復雜度為O(te×v×m+te×v×k)。

最后，不考慮基分類器的訓練時間和預測時間，最壞情況下DCS-MI的時間復雜度為O(b×m×tr2+te×v×m+te×v×k)。

4 DCS-MI算法的實現與分析

本文通過實驗比較了DCS-MI算法與一些最新的動態選擇算法在4個公共數據集中的表現。在本文的實驗中，合適的訓練數據集、驗證數據集和測試數據集的樣本劃分比例為60%、20%、20%。DCS-MI算法和用作對比的最新算法都使用了10個基本分類器，對于其中每種算法，包括DCS-MI算法，基分類器都是一個最大深度為10的決策樹。

4.1 實驗數據

本文使用了從Keel獲取的4個公共多分類不平衡數據集。

1) 天平平衡數據集(B.S.)：這個數據集是用來模擬心理實驗結果的，樣本內容包含天平的一端向右。一端向左或保持平衡。屬性包括左權值、左距離、右權值和右距離。

2) 汽車評價數據集(C.E.)：該數據集來自于一個簡單的層次決策模型。該模型根據6個輸入屬性來評估汽車：購買、維護、門、人員、引導和安全；4個輸出類別：不可接受、可接受、非常好和良好。

3) 心臟病數據集(H.D.)：該數據集來自位于美國俄亥俄州克利夫蘭的事務診所的退伍軍人，每個樣本代表一個病人，數據集中包含14個屬性。分類任務是預測病人是否患有心臟病。分類類別用0、1、2、3、4表示，其中：0表示沒有心臟病；4表示患有心臟病的風險最高。

4) 頁面塊數據集(P.B.)：這個數據集包含文檔頁面布局的塊，它是由分割過程檢測到的。分類任務是確定塊的類型:文本(1)，水平線(2)，圖形(3)，垂直線(4)或圖像(5)。

數據集信息見表1。

4.2 實驗評價指標

在分類方法有效性評價中，準確率是經常被使用的評價指標。然而在不平衡數據分類中，準確率不再適合用來評價分類性能的好壞。例如，在二分類情況下，若是訓練集的不均衡比例超過4 ∶1，即超過80%的樣本是屬于同一個類的，而訓練過程中分類器將所有的訓練樣本都分類為數量占比大的類別，可以看出，盡管該分類器的分類準確率超過80%，實際上我們仍然認為該分類器是無效的。

類似的常用評價指標還有精度和召回率。同樣假設在二分類情況下，分類器若將不平衡數據集中的所有樣本都預測為少數類，其分類的召回率將達到100% ，但同時其精度將會很差；相反，若正確分類出很少的少數類，且又識別出所有多數類，則將達到很高分類的精度，卻得到很低的召回率。

因此本文選用了3個分類績效指標來對算法進行衡量：每個類平均的F1值，每個類平均的AUC值和Cohen’s Kappa值。

1) F1值。F1值是模型精確率和召回率的一種加權平均，它的取值范圍是[0,1]。F1值能夠對精度和召回率進行平衡，當F1值較高時，精度和召回率都能保證在較高的水平。

2) AUC值。AUC (Area Under Curve) 是一個數值，其定義為ROC曲線下的面積值。由數學推導可知，ROC曲線下的面積數值不大于1。又由于一般情況下ROC曲線在y=x直線的上方，因此可知AUC的取值范圍一般為[0.5,1.0]。舍棄ROC曲線而采用AUC值作為評價標準，是因為AUC值相較于ROC曲線傳達的信息，能夠更清晰明了地進行解讀，即對應AUC值更大的分類器效果更好。

3) Cohen’s Kappa值。Kappa值是1960年由Cohen等提出的，作為評價判斷模型一致性程度的指標。Kappa值的取值范圍為[0,1]，Kappa值越大，代表一致性越強或分類精度越高。實踐證明，Kappa值是一個描述數據結果一致性較為理想的指標，同時也可用于衡量模型分類精度，因此其在實驗中得到了廣泛應用。

4.3 實驗結果

與本文提出的DCS-MI算法進行對比實驗的為1.2節中介紹的LCA、RANK、KNORAU、METADES和DES-MI技術。表2、表3和表4給出了實驗得到的結果，粗體展示的表示性能最好的技術。

表3 平均AUC值

表4 Cohen’s Kappa值

4.4 結果分析

由實驗結果可以看出，DCS-MI算法獲得了12個數據集/度量對中9個的最佳結果。因此，與其他的動態選擇技術相比，DCS-MI在處理多類不平衡數據集時具有較好的性能。

需要進一步注意的是，與DES-MI相比，DCS-MI算法在12對數據中有11對得到了相對更好的結果，而DES-MI是一種針對多類不平衡數據集的動態選擇技術。對比結果如圖4所示。

圖4 平均F1值:DCS-MI和DES-MI

圖5 平均AUC值:DCS-MI和DES-MI

圖6 平均Cohen’s Kappa值:DCS-MI和DES-MI

可以看出，DCS-MI算法即使是與專門針對多分類數據集而設計的算法相比，也表現出了更優越的算法性能。

5 DCS-MI算法實現食品謠言文本的識別分類

經實驗驗證了DCS-MI算法在公共不平衡數據集上取得了良好的性能表現。為進一步驗證其在食品安全謠言文本分類方面的分類效果，本文通過網絡爬蟲獲取食品安全新聞文本數據集，并進行實驗。與此同時，為對比驗證DCS-MI算法性能較傳統機器學習算法性能在處理不平衡數據時的優越性，選取傳統機器學習算法貝葉斯(Bayes)和隨機森林(Radom Forest)作為對比實驗。數據集結構如表5所示。

表5 食品安全新聞數據集分布

5.1 實驗數據處理

獲取文本數據后，首先進行分詞處理。本文采用jieba分詞工具對文本數據去停用詞并進行分詞。使用jieba將文本分割為字詞后，再使用Word2vec進行詞向量計算，得到每條新聞文本數據的向量表示。數據處理過程如圖7所示。

圖7 食品安全新聞數據處理

5.2 實驗結果及分析

將處理后的食品安全謠言數據分別作為DCS-MI模型、貝葉斯模型及隨機森林模型的輸入，實驗評價指標采用平均F1值和AUC值。圖8展示了實驗結果。

圖8 三種算法對食品安全謠言數據分類結果

可以看出，DCS-MI算法對于食品安全謠言數據的分類也取得了0.918 F1值和0.916 AUC值的良好效果。

與貝葉斯模型與隨機森林模型對比來看，DCS-MI依然在三個模型中取得了最佳實驗結果，隨機森林的結果表現最差，即使與表現不錯的貝葉斯相比，DCS-MI的AUC值提升了0.056，F1值也有0.123的明顯提升，這說明了針對不平衡數據集優化后的DCS-MI算法與傳統機器學習算法相比，能夠在不平衡數據問題上取得更好的分類表現。

6 結 語

本文提出一種新的動態選擇技術DCS-MI，專門用于處理不平衡數據集。DCS-MI使用SMOTE方法對不平衡的訓練數據集進行重新采樣，并引入了一個新的損失函數來為每個測試實例選擇最好的分類器。然后，在4個不同的公共數據集上進行了DCS-MI算法與其他5種算法的對比實驗，驗證了DCS-MI的優越性能。而后在爬蟲獲取的食品安全謠言不平衡數據集上使用DCS-MI算法進行實驗，并同時使用貝葉斯與隨機森林算法進行對比實驗，進一步驗證了DCS-MI在食品安全謠言識別分類方面應用的有效性及針對不平衡數據集優化的有效性。

未來的研究方向包括:研究不同的重采樣方法對DCS-MI的影響，分析基分類器數量對DCS-MI與其他動態選擇技術性能差異的影響，使用不同的損失函數選擇最佳基分類器。