基于證據(jù)理論融合兩級分類規(guī)則的不平衡數(shù)據(jù)分類方法

李莎莎

（安徽廣播電視大學，安徽 合肥 230039）

1 引 言

現(xiàn)實世界中不平衡數(shù)據(jù)分布廣泛[1]，在醫(yī)療診斷、入侵檢測以及文本分類等領域中多有涉及[2]，正確識別少數(shù)類樣本具有極其重要的現(xiàn)實意義。不平衡數(shù)據(jù)中類的分布是不平衡的，只通過一組具有較好分類性能的分類規(guī)則很難取得較高的分類準確率[3]。若對訓練集提取兩組分類規(guī)則，簡單投票又可能因產(chǎn)生過多規(guī)則沖突導致分類準確率下降。證據(jù)理論方法[4]可將每組分類規(guī)則作為一組證據(jù)，通過將多組分類規(guī)則集成，建立基于多證據(jù)組決策模型，能夠有效地融合多分類器中的分類信息，從而提高分類準確率。

文中提出的基于證據(jù)理論的不平衡數(shù)據(jù)分類方法CET（Classification based on evidential theory）是通過對原始不平衡數(shù)據(jù)集學習兩次生成兩組分類規(guī)則，利用證據(jù)理論融合兩組分類規(guī)則。一次學習假定數(shù)據(jù)類分布均衡，通過決策樹[5]分類器提取規(guī)則。二次學習用于提取更多少數(shù)類信息。首先，利用信息增益度量少數(shù)類樣本與多數(shù)類樣本距離，按距離將多數(shù)類樣本進行排序；依次從多數(shù)類中提取與少數(shù)類樣本等量的數(shù)據(jù)并與之結合，生成多個平衡小訓練集；在每個小訓練集上以決策樹作為基分類器提取二級規(guī)則。采用證據(jù)理論方法，根據(jù)兩級分類規(guī)則的分類結果計算基本概率，使用Dempster合成規(guī)則計算具有最大可信度的類別作為兩組分類規(guī)則的集成分類結果。實驗證明該方法在不平衡數(shù)據(jù)學習時，少數(shù)類樣本以及整體數(shù)據(jù)集的分類準確率都能得到有效提升。

2 相關研究成果

2.1 不平衡數(shù)據(jù)分類方法

本文考慮兩類別不平衡數(shù)據(jù)學習問題，當存在多類別數(shù)據(jù)的不平衡情形，將少數(shù)類類別通稱為正類，多數(shù)類類別通稱為負類。目前，不平衡數(shù)據(jù)學習方法常見策略有代價敏感學習[6]、數(shù)據(jù)采樣[7]、boosting技術等。Boosting技術通過組合多個分類器迭代創(chuàng)建集成模型，避免分類器過擬合，如RUS-Boost[8]和 DataBoost-IM[9]等。RUSBoost 應 用 隨 機 欠采樣從多數(shù)類隨機移除樣例，克服欠采樣引起信息丟失問題，但沒有最大限度的挖掘少數(shù)類與多數(shù)類邊界信息。

2.2 基于證據(jù)理論分類

Huawei Guo 等人在2005 年提出了基于證據(jù)理論的決策樹算法[10]，使用新的證據(jù)理論合成規(guī)則。2009年Yang Yi等人提出了基于證據(jù)理論的多分類器集成方法[11]。但這些分類方法未充分考慮不平衡數(shù)據(jù)分類特點。

3 基于證據(jù)理論融合兩級分類規(guī)則的不平衡數(shù)據(jù)分類

3.1 兩級規(guī)則生成方法

元組T={t1,t2,…，tn}中，每個元組t有m個屬性{A1,A2,…，Am}，C為類標 {C1,C2,…，Ck}。每個樣本v代表一個屬性值，規(guī)則r包含多個樣本v和一個類標c,形式為v1∧v2∧ … ∧vl→c。分類規(guī)則由分類器中提取，如果一個元組t滿足r中v1∧v2∧…∧vl的形式，r預測t屬于類別c。

CET 選取值覆蓋決策樹作為基分類器：根據(jù)信息增益度量，選取能覆蓋元組T的一組最優(yōu)屬性值v1,v2,…vi，在每個屬性值vk各自條件庫中遞歸選取最優(yōu)屬性值與vk連接生成pattern。當每個patternX在Ti上的信息增益等于0，X可預類別C，X→C屬于一級規(guī)則。

任意兩個樣本X與Y相同屬性值為v1,v2,…vn，X與Y的距離定義如下[12]：

由定義2知，兩條樣本距離越近，代表兩條樣本間相似程度較高。

CET 建立二級規(guī)則，首先度量每條多數(shù)類樣例與少數(shù)類樣例的距離，按距離將多數(shù)類樣例由近至遠進行排序。排序后從多數(shù)類樣本中按距離選擇與少數(shù)類樣例相同數(shù)目的樣例，與少數(shù)類樣例進行混合，將原始訓練集劃分為多個平衡類別的小訓練集。在這些平衡小訓練集中，有些訓練集是少數(shù)類與距離最近的多數(shù)類樣本組合而成，這些小訓練集組合少數(shù)類以及少數(shù)類邊界樣本，對預測類別有著更重要的決定作用，稱為重要小訓練集。因此在預測未知實例的類別時，應給與更高的權重。在每個小訓練集上做值覆蓋決策樹算法，得到多組分類規(guī)則。在測試時，每組規(guī)則都可以為未知樣例預測類別。

3.2 證據(jù)理論合成規(guī)則

CET使用證據(jù)理論將提取的規(guī)則作為兩組證據(jù)構建識別框架，在測試未知實例時，將兩組規(guī)則作為兩個mass函數(shù)進行規(guī)則合成。

第二組規(guī)則提取通過構建多個平衡小訓練集，每個平衡訓練集中提取的分類規(guī)則都能對未知實例進行類別預測。將規(guī)則按照置信度conf（X）和支持度sup（X）排序[13]，匹配未知實例在整體訓練集上的最高conf（X）和sup（X）的規(guī)則，對未知實例進行類別預測。在得到多個預測結果之后，需根據(jù)小訓練集的重要程度對預測結果進行權值的分配，重要訓練集的預測結果具有更高的權值。選擇半數(shù)訓練集作為重要訓練集，其結果預測比重增倍。所得結果歸一化處理，作為第二組mass函數(shù)m2（）。例如有4個平衡小訓練集，選2個為重要訓練集，每個訓練集的預測結果比重分配如表1所示。

表1 平衡訓練集預測未知實例比重分配

將表1 中比重分配所示，預測結果為正類和負類的概率歸一化處理后分別是：

二級規(guī)則預測結果概率作為第二組mass 函數(shù)m2（）。由這兩個mass函數(shù)m1m2構成識別框架，根據(jù)Dempster合成規(guī)則將結果進行合成。

根據(jù)所求各類別的mass組合函數(shù)，可以計算預測各類別概率，確定最大概率類別為最終預測結果。

4 實驗評價度量與結果分析

為驗證CET算法有效性，在11個UCI不平衡數(shù)據(jù)集上進行10-折交叉測驗，數(shù)據(jù)特點如表2所示。數(shù)據(jù)集Auto、Car和Lymph合并2個最少數(shù)目類別作為少數(shù)類樣本，余下類作為多數(shù)類；數(shù)據(jù)集Glass 和Zoo合并3個最少數(shù)目類別作為少數(shù)類，余下類作為多數(shù)類。類別合并后各數(shù)據(jù)集類分布比例由表2所示。為綜合評價不平衡數(shù)據(jù)分類器性能，本文將選用F-measure[14]度量少數(shù)類分類，選取G-mean[15]來衡量分類器對整體數(shù)據(jù)集的分類。

表2 UCI數(shù)據(jù)集特點

表3 列出了在11 個數(shù)據(jù)集上決策樹方法、隨機-CET 和 CET 方法的F-measure和G-mean值，最后一行列出每種方法在所有數(shù)據(jù)集上的平均結果。圖1給出了3種方法的F-measure值的比較，圖2 給出了3 種方法的G-mean值的比較。由表3 可知，利用證據(jù)理論集成兩組規(guī)則，其中一種規(guī)則假定類分布均衡，而第二組規(guī)則采用隨機欠采樣方式生成多個類平衡小訓練集，其F-measure和G-mean值高于單覆蓋決策樹。CET在二級規(guī)則度量多數(shù)類與少數(shù)類相近距離的邊界樣例，改善證據(jù)合成規(guī)則時mass 函數(shù)，分類不平衡數(shù)據(jù)的F-measure和G-mean值最高。

表3 3種方法的F-measure和值G-mean對比

圖1 3種方法F-measure值的比較

圖2 3種方法G-mean值的比較

5 總 結

不平衡數(shù)據(jù)的分類一直是分類領域中的一項難題，怎樣在保證不平衡數(shù)據(jù)整體分類準確率的情況下又能正確分類少數(shù)類樣例，是提高不平衡數(shù)據(jù)集分類準確率的關鍵。文中提出一種基于證據(jù)理論融合兩級分類規(guī)則的不平衡數(shù)據(jù)分類方法，提取兩級分類規(guī)則增加規(guī)則數(shù)量，且第二級分類規(guī)則根據(jù)少數(shù)類與多數(shù)類樣本距離生成了多個平衡小訓練集，充分考慮了不平衡數(shù)據(jù)集特點。運用證據(jù)理論將兩級規(guī)則集成，解決了對少數(shù)類識別率較低的問題。實驗結果表明，該算法不僅提高了不平衡數(shù)據(jù)中少數(shù)類實例的分類準確率，而且提高了數(shù)據(jù)集整體的準確率。