Spark環(huán)境下基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法

丁家滿，王思晨，賈連印，游進(jìn)國，姜 瑛

(昆明理工大學(xué) 信息工程與自動化學(xué)院， 昆明 650500)

1 引 言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)正以前所未有的速度在不斷地增長和積累.數(shù)據(jù)在各個領(lǐng)域的應(yīng)用價值比以往任何時候都重要.如何高效、準(zhǔn)確地從數(shù)據(jù)信息中挖掘有價值的信息引起了學(xué)者們的廣泛關(guān)注.然而現(xiàn)有的這些數(shù)據(jù)具有多樣性和復(fù)雜性以及數(shù)據(jù)分布嚴(yán)重不平衡等特點, 經(jīng)常會遇到許多大規(guī)模的多類別不平衡數(shù)據(jù)分類問題，如文本分類[1]、疾病診斷[2]以及圖像分類[3]等.然而傳統(tǒng)分類算法在處理不平衡數(shù)據(jù)時少數(shù)類樣本分類準(zhǔn)確率過低從而導(dǎo)致分類器的整體性能下降[4].因此選擇合適的技術(shù)提高少數(shù)類樣本的占比，提高對少數(shù)類的分類準(zhǔn)確率以及分類器的整體性能顯得尤為重要.目前有諸如改變數(shù)據(jù)的分布和改進(jìn)已有分類算法等方式試圖從不同的角度解決上述問題，也取得了較好的成效[ 5-7].其中改變數(shù)據(jù)的分布來達(dá)到數(shù)據(jù)平衡最常見的策略有隨機(jī)過采樣(over-sampling)、隨機(jī)欠采樣(under-sampling).隨機(jī)過采樣是對少數(shù)類的樣本進(jìn)行復(fù)制使數(shù)據(jù)集的樣本數(shù)達(dá)到平衡，隨機(jī)欠采樣則以一定的策略選取多數(shù)類樣本中的一個子集達(dá)到同樣的目的. 李克文等人[8]提出基于RSBoost算法的不平衡數(shù)據(jù)分類方法，該方法采用 SMOTE 算法對少數(shù)類進(jìn)行過采樣處理，然后對整個數(shù)據(jù)集進(jìn)行隨機(jī)欠采樣處理來改善整個數(shù)據(jù)集的不平衡性，提高少數(shù)類的分類準(zhǔn)確性. 李雄飛等人[9]提出一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法 PCBoost，該算法用數(shù)據(jù)合成方法添加合成的少數(shù)類樣本，平衡訓(xùn)練樣本.雖然以上方式能夠在特定環(huán)境下一定程度的解決數(shù)據(jù)不平衡問題，但是為了達(dá)到數(shù)據(jù)平衡按比例機(jī)械地抽樣將破壞原始數(shù)據(jù)的分布特點、而對多數(shù)類樣本進(jìn)行簡單抽樣則可能移除潛在有用的分類信息，這將導(dǎo) 致分類效率低、分類精度低等問題.另外，隨著數(shù)據(jù)規(guī)模增大、加之算法為不平衡數(shù)據(jù)的預(yù)處理帶來運算代價，不平衡數(shù)據(jù)分類效率成為了瓶頸問題.

云平臺和并行化技術(shù)的出現(xiàn)為我們提供了解決分類效率問題的環(huán)境，并取得了有效的成果[10-15].其中Wang Z等人[13]針對不平衡數(shù)據(jù)提出一種基于MapReduce框架的分布式加權(quán)極限學(xué)習(xí)機(jī)，實驗結(jié)果表明該方法具有較好的可擴(kuò)展性以及較高處理不平衡大數(shù)據(jù)的效率.然而MapReduce計算框架不適合迭代算法，它計算的得到的中間結(jié)果寫入到磁盤，使用時再從磁盤加載讀取，其網(wǎng)絡(luò)和I/O開銷代價高.Apache Spark[注]http://spark.apache.org是一個基于內(nèi)存的快速處理大數(shù)據(jù)框架，解決了機(jī)器學(xué)習(xí)算法的迭代計算和交互式數(shù)據(jù)挖掘等問題. 王雯等人[14]提出一種在Spark平臺上的基于關(guān)聯(lián)規(guī)則挖掘的短文本特征擴(kuò)展及分類方法，其實驗結(jié)果顯示相較于傳統(tǒng)分類方法平均得到15%的效率提升. Chen J等人[15]提出了Spark平臺大數(shù)據(jù)的并行隨機(jī)森林算法，大量實驗結(jié)果表明了其在分類精度和效率的優(yōu)勢.在Spark平臺下這些分類方法在效率方面獲得較好的成效.因此，如何最大限度地利用Spark框架的計算優(yōu)勢來解決不平衡數(shù)據(jù)分類效率問題顯得尤為重要.

針對上述問題，本文提出了一種在Spark環(huán)境下基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法.該方法首先提出基于綜合權(quán)重的采樣方法得到平衡訓(xùn)練數(shù)據(jù)集，其次為了提高分類精度，優(yōu)化并改進(jìn)了隨機(jī)森林算法；最后，在Spark環(huán)境下進(jìn)行算法實現(xiàn)及實驗驗證.

2 隨機(jī)森林的優(yōu)化

隨機(jī)森林[16](Random Forest，RF)是一種集成分類器，它基于隨機(jī)化的思想構(gòu)建了一群相互獨立且互不相同的決策樹.它通過自助法(bootstrap)重采樣技術(shù)，首先從原始訓(xùn)練樣本集 中有放回地重復(fù)隨機(jī)抽取 個新的自助樣本集，并由此構(gòu)建 棵分類樹(通常采用決策樹)，每次未被抽到的樣本組成了 個袋外數(shù)據(jù)；然后將生成的多棵分類樹組成隨機(jī)森林；最后用隨機(jī)森林分類器對新的數(shù)據(jù)進(jìn)行判別與分類，分類結(jié)果按各分類器的投票結(jié)果而定.在訓(xùn)練的時候，每一棵樹的輸入樣本都不是全部的樣本，這既保證了訓(xùn)練的子本分類器之間差異性又不容易出現(xiàn)過擬合現(xiàn)象.但是隨機(jī)森林算法也存在著不足，例如訓(xùn)練數(shù)據(jù)的嚴(yán)重不平衡以及通過隨機(jī)的方式進(jìn)行選擇特征引起的分類效果不佳，所以本文主要從兩個方面對隨機(jī)森林算法進(jìn)行改進(jìn).一方面提出基于綜合權(quán)重的數(shù)據(jù)平衡方法使樣本達(dá)到平衡；另外一方面是從特征選擇上，改變傳統(tǒng)的隨機(jī)選擇的方式.

2.1 基于綜合權(quán)重的數(shù)據(jù)平衡方法

為了達(dá)到數(shù)據(jù)平衡并保留原始數(shù)據(jù)的分布特點，以及挖掘多數(shù)類樣本中更具有價值的數(shù)據(jù)，本文提出基于綜合權(quán)重的數(shù)據(jù)平衡方法.首先按照少數(shù)類樣本的數(shù)量和多數(shù)類樣本中每個類別樣本數(shù)量占多數(shù)類樣本數(shù)量的比重來計算綜合權(quán)重，并依據(jù)綜合權(quán)重從多數(shù)類樣本中抽取每一類別的樣本數(shù)量，再將少數(shù)類樣本與抽取的樣本組合，使少數(shù)類樣本在訓(xùn)練樣本中所占比例升高.采樣次數(shù)與少數(shù)類樣本和多數(shù)類樣本相關(guān).最后將獲得的經(jīng)處理后的訓(xùn)練樣本子集作為隨機(jī)森林的輸入樣本數(shù)據(jù).其中相關(guān)定義如下：

定義1.將具有M個特征的N個樣本組成的樣本集合表示X={a1,a2,…,aN}，樣本的類別集合表示Y={y1,y2,…,yN}，則訓(xùn)練樣本用矩陣Z表示如下：

(1)

其中ai={xi1,xi2,…,xij,…,xiM}表示樣本ai的M個特征值，其中xij表示樣本ai的第j個特征值.

定義3.設(shè)多數(shù)類類別分布T1，T2,…,Tr,每個類別包含樣本數(shù)量為{Count(T1),Count(T2),…,Count(Tr)}，則T1,T2,…,Tr的抽樣權(quán)重為：

(2)

樣本數(shù)量越小，則抽樣權(quán)重越大.記少數(shù)類樣本數(shù)目為p，則從多數(shù)類類別Ti中采樣的樣本綜合權(quán)重：

(3)

2.2 特征選擇

傳統(tǒng)的特征子集通過隨機(jī)的方式進(jìn)行選擇，所以在面對噪聲特征和冗余特征的數(shù)據(jù)集，分類的準(zhǔn)確性會受到影響，錯誤率也會提高.這些噪聲特征和冗余特征對于分類的準(zhǔn)確性沒有貢獻(xiàn)，特征的重要性很低.因此本文在謝娟英等人[17]研究的基礎(chǔ)上提出基于相關(guān)性的特征選擇方法進(jìn)行特征選擇，刪除噪聲特征和冗余特征.特征選擇從空集開始，依次選擇類別間區(qū)分能力強的特征，選擇最優(yōu)的u個特征，且需要滿足u

定義4.設(shè)訓(xùn)練樣本集規(guī)模為N，類別數(shù)為l，即{(ak,yk)|yk∈{1,2,…,l},k=1,2,…,N}.其中第j類的樣本數(shù)為nj，則特征i的類別間區(qū)分度Fi的計算公式如下：

(4)

3 方法在Spark上實現(xiàn)

3.1 內(nèi)存分布式計算框架--Spark

Spark是UC Berkeley AMP Lab 開源的類Hadoop通用的并行計算框架，它基于Hadoop MapReduce算法實現(xiàn)分布式計算，其中間輸出和結(jié)果不同于Hadoop保存在HDFS中，而是直接保存在內(nèi)存中.Spark提出了彈性分布式數(shù)據(jù)集RDD(Resilient Distributed Dataset)的概念，RDD是分布在集群中的只讀對象集合，在集群中的多個節(jié)點上進(jìn)行分區(qū)，它支持用戶在執(zhí)行計算時選擇緩存數(shù)據(jù)集在內(nèi)存中，便于下次計算時重用數(shù)據(jù)集，提供了更快速的數(shù)據(jù)訪問，減少了不必要的磁盤重復(fù)讀寫操作.它不僅支持基于數(shù)據(jù)集的應(yīng)用，還具有容錯、局部計算調(diào)度和可擴(kuò)展等特性.因此Spark能更好地適用于機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等領(lǐng)域.

3.2 方法描述

為了挖掘大規(guī)模不平衡數(shù)據(jù)集中有價值信息、降低數(shù)據(jù)通信I/O的開銷提高分類效率，本文提出了Spark環(huán)境下基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法.本文方法包括基于綜合權(quán)重采樣的訓(xùn)練數(shù)獲取和子分類器學(xué)習(xí)以及并行化實現(xiàn)，主要包括3個階段：

1) 將原始數(shù)據(jù)集轉(zhuǎn)換為Spark能處理的數(shù)據(jù)RDD形式，并轉(zhuǎn)換成少數(shù)類RDDmin和多數(shù)類RRDmaj兩種形式；

2) 設(shè)計綜合權(quán)重采樣方法以獲得平衡規(guī)模的訓(xùn)練集；

3) 采用改進(jìn)的隨機(jī)森林算法訓(xùn)練子分類器，并在Spark環(huán)境下實現(xiàn)，最后通過加權(quán)投票的方式獲得測試數(shù)據(jù)的最終分類結(jié)果.

圖1 第一階段RDDs的譜系圖Fig.1 Hierarchical graph of RDDs in phase 1

第1階段.將數(shù)據(jù)集轉(zhuǎn)換為Spark能處理的RDD格式，RDDs之間的轉(zhuǎn)換如圖1所示.首先使用sparkContext.textFile函數(shù)從HDFS分布式件系統(tǒng)中讀取訓(xùn)練集數(shù)據(jù)并將其轉(zhuǎn)換為RDD的形式，用map()函數(shù)將每一條數(shù)據(jù)記錄映射成(key,value)這樣的元組形式.其中的key為樣本類別，value值則是樣本一條記錄.通過調(diào)用collect()函數(shù)計算每類的樣本量并調(diào)用sortBy()函數(shù)使得按照升序排序，最后獲得RDDmin和RDDmaj,將用于下一階段的采樣階段.其算法過程如算法1所示.

算法1.RDDmin和RDDmaj生成算法

Input:D,raw data

Output:RDDmin,RDDmaj

1.for each sample x inD

2.instance←x.map(class,x)

3.totalInstance←instance.combineByKey().map(num+1).collect()

4.sortInstance←totalInstance.sortBy(num,false)

5.RDDmin←sortInstance(0)

6.RDDmaj←sortInstance(1)

第2階段. 基于綜合權(quán)重進(jìn)行采樣.為了達(dá)到數(shù)據(jù)平衡并保留原始數(shù)據(jù)的分布特點以及挖掘多數(shù)類樣本中更具有價值的數(shù)據(jù),本文提出基于綜合權(quán)重的采樣方法獲得平衡規(guī)模的訓(xùn)練集.算法具體過程如算法2所示.

算法2.基于綜合權(quán)重的采樣方法

Input:RDDmin,RDDmaj,C,numbers of classes

Output:RDDi,a balanced train set

1.C1,C2,…,Cn←n classes

2.sum←numbers ofRDDmajsample

3.p←numbers ofRDDminsample

4.M←numbers of train subsets

5.for each classCi

6. if key==Cithen

7.num++

8.Ration(Ci),Weight(Ci)←according the definitions calculate it

9.RDDi←select samples intoRDDi

10.RDDj←RDDi∪RDDmin(i∈[1,M])

第3階段.訓(xùn)練分類器并加權(quán)投票決策.本文采用改進(jìn)的隨機(jī)森林訓(xùn)練分類器.運用前兩個階段處理過的訓(xùn)練集與特征子集進(jìn)行訓(xùn)練各個子分類器，并獲得分類模型.傳統(tǒng)的隨機(jī)森林算法采用簡單投票原則，對每個決策樹賦予相同的權(quán)重，忽略了強分類器與弱分類器的差異，影響了隨機(jī)森林分類器的整體分類性能，本文采用加權(quán)投票法進(jìn)行選擇最終的類別的結(jié)果.利用在未被抽樣的數(shù)據(jù)作為袋外(OOB)數(shù)據(jù)，計算各個決策樹分類器對其的分類準(zhǔn)確率，并將其作為對應(yīng)決策樹的投票權(quán)重.

4 實驗結(jié)果與分析

實驗環(huán)境基于Spark集群，包括1個master，7個slave節(jié)點，所有節(jié)點的配置如下：操作系統(tǒng)為Centos 7,CPU為Intel Core i7-6700 cpu @2.60Ghz 2.59Ghz,8GB內(nèi)存,使用Scala 2.10.4開發(fā)，集群環(huán)境建立在Hadoop2.6.0之上的Spark1.6.0.

4.1 實驗數(shù)據(jù)和對比算法

為評價本文方法對不平衡數(shù)據(jù)集分類問題的有效性，本文選擇6個少數(shù)類和多數(shù)類樣本比例不平衡的數(shù)據(jù)集進(jìn)行實驗，數(shù)據(jù)集來源于 UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫的數(shù)據(jù)集，見表1，其中UCI數(shù)據(jù)集樣本數(shù)用#Ex表示，#F代表特征數(shù)，#C代表數(shù)據(jù)集類別數(shù)，#R代表少數(shù)類樣本占數(shù)據(jù)集的比重.為了驗證本文算法在spark平臺上的有效性，采用KDD Cup 99數(shù)據(jù)集[19]，其整個訓(xùn)練數(shù)據(jù)有500000條記錄，以及URL Reputation數(shù)據(jù)集，其訓(xùn)練數(shù)據(jù)有2396130條記錄，數(shù)據(jù)容量2.05GB.為了評估本文算法的性能，實驗部分選擇了決策樹C4.5算法以及隨機(jī)森林RF算法進(jìn)行對比，對比算法都在Spark平臺下的運行，以保證實驗運行環(huán)境的一致性.本文訓(xùn)練的基分類器采用C4.5算法迭代20次；其中對照算法C4.5決策樹算法以及隨機(jī)森林RF算法直接對不平衡數(shù)據(jù)集進(jìn)行分類，實驗中選擇的特征數(shù)一致以及隨機(jī)森林算法訓(xùn)練每棵決策樹時使用C4.5算法.

表1 UCI數(shù)據(jù)集信息說明Table 1 Summary description of the used datasets

表2 混淆矩陣Table 2 Confusion matrix for a two-class problem

4.2 評估指標(biāo)

本文采用查全率、查準(zhǔn)率和 F-measure 作為評價分類器性能的指標(biāo).這3個指標(biāo)在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中應(yīng)用廣泛.傳統(tǒng)的二分類評價指標(biāo)基于混淆矩陣，其中在不平衡數(shù)據(jù)集中正類和負(fù)類分別代表少數(shù)類和多數(shù)類.TP和TN分別表示正確分類的正類和負(fù)類樣本的個數(shù)；FP表示為誤分為正類的樣本個數(shù)；FN表示為誤分為負(fù)類的樣本個數(shù)，見表2.

評價指標(biāo)計算公式如下：

4.3 實驗結(jié)果分析

實驗1. 數(shù)據(jù)處理前后少數(shù)類樣本占比.

在不平衡數(shù)據(jù)集中，多數(shù)類樣本個數(shù)遠(yuǎn)遠(yuǎn)多于少數(shù)類，傳統(tǒng)分類算法往往會傾向于多數(shù)類，如即使把所有樣本分為多數(shù)類，依然會獲得很高的分類精度，但是卻不能識別少數(shù)類.因此在處理不平衡數(shù)據(jù)時，提高少數(shù)類樣本在訓(xùn)練樣本中所占比重能夠有效的提高少數(shù)類樣本的分類性能.圖2表明經(jīng)過基于綜合權(quán)重的數(shù)據(jù)平衡對不平衡數(shù)據(jù)經(jīng)處理后，每個數(shù)據(jù)集訓(xùn)練樣本中少數(shù)類樣本的比例明顯提高了.

實驗2.不同分類算法準(zhǔn)確率的比較.

在分類過程中分別設(shè)計采用C4.5算法、隨機(jī)森林算法以及本文方法3組實驗，每一組實驗針對上述的數(shù)據(jù)集分別測試.實驗結(jié)果如圖3-圖5所示.根據(jù)圖3和圖4可以看出，C4.5算法在Segment、Vehicle數(shù)據(jù)集上的查準(zhǔn)率偏低，而RF算法在Segment、Sick數(shù)據(jù)集上有較高的查全率和查準(zhǔn)率.同 RF和C4.5算法相比較，本文算法分別在Balance-scale、Satimage以及Yeast數(shù)據(jù)集上的查準(zhǔn)率具有顯著的優(yōu)勢.在這6個數(shù)據(jù)集上本文算法顯著優(yōu)于C4.5算法，在Segment 、Sick數(shù)據(jù)集上與RF算法水平相當(dāng).圖5是幾種不同的方法在不平衡數(shù)據(jù)分類性能的評估指標(biāo)F-measure的比較.只有當(dāng)查全率和查準(zhǔn)率都較大時，F(xiàn)-measure才會相應(yīng)地較大.因此F-measure可以合理地評價分類器對于少數(shù)類的分類性能.本文提出采用基于綜合權(quán)重采樣和集成學(xué)習(xí)相結(jié)合的方法來處理不平衡數(shù)據(jù)的分類問題，相比其他兩種方法，分類性能得到大幅度提升,在數(shù)據(jù)集Balance-scale、Satimage以及Yeast上，本文算法在準(zhǔn)確率指標(biāo)上比其他兩種算法提高了10%以上.

實驗3.決策樹數(shù)量對分類準(zhǔn)確率的影響.

為驗證決策樹數(shù)量對分類準(zhǔn)確率的影響，測試設(shè)置不同的決策樹棵數(shù){5,10,15,20,25,30}，通過實驗統(tǒng)計表明決策樹的棵數(shù)對分類準(zhǔn)確率的提高發(fā)揮中重要的作用.當(dāng)決策樹的數(shù)目等于5時，Random Forest算法的平均分類準(zhǔn)確率沒有本文算法CWID的高.隨著決策樹的數(shù)量的增加，這些算法的平均分類準(zhǔn)確率提升幅度相對下降，這意味著決策樹數(shù)量達(dá)到最佳.CWID算法在決策樹的數(shù)目等于20的時候，平均分類準(zhǔn)確率達(dá)到頂峰.CWID的分類準(zhǔn)確率高于另外兩種算法，并具有優(yōu)越性和顯著的優(yōu)勢.

實驗4.CWID在不同數(shù)據(jù)集上的執(zhí)行效率.

為驗證本文提出的在Spark環(huán)境下基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法的效率，將本文提出的算法與傳統(tǒng)單機(jī)上分類算法進(jìn)行對比，并測試在KDD Cup 1999實驗數(shù)據(jù)集以及UCI數(shù)據(jù)集上的URL Reputation數(shù)據(jù)集,本文算法加速比隨集群節(jié)點數(shù)量的變化情況，節(jié)點數(shù)量取{1,2,3,4,5,6,7}.通過對比試驗，分析本文提出的分類方法的分類效率.算法加速比，是算法在單機(jī)環(huán)境下和分布式環(huán)境下運行消耗時間的比率值，用來評價程序并行化后的效果.圖6是CWID算法的加速比實驗結(jié)果.

由上述實驗結(jié)果可知，隨著spark集群計算節(jié)點的增加而逐漸上升，并在數(shù)據(jù)集上加速比的變化從線性增長到平穩(wěn)，在數(shù)據(jù)集kddnormal_VS_U2R和kddnormal_VS_R2L上較為明顯.這個主要是由于數(shù)據(jù)集容量太小，以及算法的分布式處理能力沒有得到充分的利用；與此同時，在相同節(jié)點的情況下，數(shù)據(jù)集規(guī)模較大時，曲線增長更為明顯，且算法的速度性能較好.因此，在Spark環(huán)境下訓(xùn)練的分類器具有較好的并行化性能.所以在訓(xùn)練海量數(shù)據(jù)時，完全可以通過增加spark集群中計算節(jié)點的數(shù)量，來大大減少訓(xùn)練模型所需要的時間.

5 總 結(jié)

為了保持原始數(shù)據(jù)的分布特點、更好的利用潛在有用的分類信息，以及保證集成學(xué)習(xí)中的各分類器之間的差異性，本文采用在Spark環(huán)境下基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法處理不平衡數(shù)據(jù)分類問題.通過UCI數(shù)據(jù)集實驗，與C4.5算法、RF算法進(jìn)行比較，并將查全率、查準(zhǔn)率、F-measure 以及算法加速比作為度量對算法進(jìn)行評價，實驗結(jié)果表明本文算法提高了整體分類精度，并較好地利用了Spark分布式平臺高效的計算能力,提高整體分類效率.由于數(shù)據(jù)集本身的多樣性和復(fù)雜性，噪聲樣本和冗余樣本等均會影響不平衡數(shù)據(jù)分類性能，如果進(jìn)行有針對性的數(shù)據(jù)預(yù)處理工作，將會使得基于綜合權(quán)重采樣的樣本更具有分類價值，后期針對該問題，進(jìn)一步提高該方法的泛化性能.