基于粒度和信息熵的并行支持向量機算法

毛伊敏， 張劉鑫， 盧欣榮

(1.江西理工大學信息工程學院， 贛州 341000； 2.江西理工大學應用科學學院， 贛州 341000)

支持向量機(support vector machine, SVM)算法是數據挖掘和機器學習的常用方法之一，其以結構風險最小化為準則設計學習模型，具有較好的魯棒性；利用核函數將樣本數據映射到高維特征空間，避免了“維度災難”；將原問題轉化為凸二次規劃問題，求解目標函數可以獲得全局最優解[1]。因此，支持向量機算法被廣泛應用于圖像分析[2]、目標檢測[3]、生物醫學[4]等各種領域。

隨著信息技術的快速發展以及大數據時代的來臨，大數據相較于傳統數據具有了Volume(數量大)、Veracity(準確性)、Variety(種類多)、Velocity(速度快)、Value(價值密度低)的“5V”特性[5]。但是傳統的支持向量機所需的時間復雜度較高，只適用于較小規模的數據集，而在處理大數據時，無疑會產生巨額的計算復雜度[6]。所以，如何降低支SVM算法的計算復雜度并提高其執行效率、使其能夠處理大數據是個關鍵性的難題。

隨著Google開發的MapReduce架構的廣泛應用，以Hadoop、Spark為代表的分布式計算架構受到了越來越多的關注[7-9]。為了能進一步降低SVM算法的計算復雜度，通過改進傳統的支持向量機算法，并與分布式的計算架構結合成為當前支持向量機算法的研究熱點。Alham等[10]提出了基于MapReduce和Bagging的并行集成支持向量機算法(MapReduce-based distributed SVM ensembles algorithm，MRESVM)，該算法利用MapReduce計算模型在Hadoop平臺上并行訓練SVM，在保證分類精度的同時有效地提高了算法的執行效率，但是，隨著訓練樣本的增大，算法的運行時間會迅速增長。在此基礎上，Kun等[11]提出了并行組合支持向量機算法(parallel sequential minimal optimization,PSMO)，為解決支持向量機處理大規模數據時執行效率低的問題，該算法將原始數據集劃分成規模較小的子數據集，在每個子數據集上訓練SVM模型，合并所有局部支持向量并單獨訓練支持向量機得到最終分類模型，實驗結果分類準確度不高。為了進一步提高算法的性能，丁萱萱等[12]提出了基于MapReduce和Bagging的并行組合支持向量機算法(parallel recombined SVM ensembles algorithm,PRESVM)，該算法首先采用分組訓練的方式刪除大部分的非支持向量，縮小訓練集的規模，然后利用隨機梯度下降算法加快SVM的訓練過程，實驗表明該算法的執行效率得到了提高。然而，這些算法都未有效識別和刪除噪聲數據，導致大數據環境下算法的分類準確度較低。

如何解決并行支持向量機算法的噪聲數據較敏感問題，并提高大數據環境下算法的分類準確度，一直是并行SVM算法的重要研究內容。為了解決這個問題，Fan等[13]提出了基于概率推理的分布式支持向量機算法(distributed SVM algorithm based on probabilistic inference,PIDSVM)，該算法利用概率推理方法找出隱藏在訓練集中的噪聲特征，并將其考慮到建模中。同時，Sarumathiy等[14]提出了基于特征提取和互信息的并行支持向量機算法(parallel SVM algorithm based on feature select and mutual information,FMPSVM)，該算法有效地識別數據集中相關度較低的特征，降低了噪聲數據的影響。雖然以上算法可以有效地識別和刪除大數據環境下的噪聲數據，避免了噪聲數據成為支持向量，影響分類決策平面的構建，但是這些算法都忽略了訓練樣本數據冗余問題對模型訓練的影響，導致算法的時間復雜度較高。針對這個問題，王瑞等[15]提出了基于K-means的分布式SVM優化算法，該算法通過聚簇的方式劃分數據集，快速刪除訓練樣本中的冗余數據，有效地加快了算法的執行效率。除此之外，Hu等[16]提出了一種基于MapReduce的并行迭代SVM算法(parallel iterative SVM algorithm based on cuckoo search,PISVM-CS)，該算法利用布谷鳥算法優化SVM的參數，以并行迭代的方式篩選類邊界樣本，從而得到較好的分類模型。雖然目前基于MapReduce的并行支持向量機算法的研究已經取得了一些成果，但如何有效地識別并刪除大數據環境下的噪聲數據，從而提高算法的分類精度，如何迅速刪除冗余的訓練樣本集，降低算法的時間復雜度，仍是當前亟需解決的問題。

針對以上問題，提出基于粒度和信息熵的(the SVM algorithm by using granularity and information entropy based on MapReduce,GIESVM-MR)算法。主要工作為：①提出噪聲清除策略(noise cleaning, NC)對每個特征屬性的重要程度進行評價，獲得樣本與類別之間的相關度，以達到識別和刪除噪聲數據的目的；②提出基于粒度的數據壓縮策略(data compression based on granulation, GDC)，通過篩選信息粒的方式來保留類邊界樣本刪除非支持向量，獲得規模較小的數據集，從而解決了大數據環境下訓練樣本數據冗余問題；③結合Bagging的思想和MapReduce計算模型并行化訓練SVM，生成最終的分類模型。實驗表明，GIESVM-MR算法的分類效果更佳，且在大規模的數據集下算法的執行效率更高。

1 相關概念介紹

1.1 信息熵

對于一個離散型的變量X，其信息熵[17]為

(1)

式(1)中：p(x)為離散變量X在系統事件中出現的概率。

1.2 粒度支持向量機

粒度支持向量機是由Tang等[18]最先提出來的，給定一個數據集D={x1,x2,…,xn}，可以以某種方式構建粒度空間，信息粒可以表示為

G={g1,g2,…,gm}

(2)

式(2)中：m為信息粒的個數。

2 GIESVM-MR算法

GIESVM-MR算法主要包括3個階段：噪聲過濾、數據壓縮和并行SVM模型構建。

(1)在噪聲過濾階段：提出了噪聲清除策略NC對每個特征屬性的重要程度進行評價，獲得樣本與類別之間的相關度，有效地識別和刪除大數據環境下的噪聲數據。

(2)在數據壓縮階段：提出基于粒度的數據壓縮策略GDC, 通過篩選信息粒的方式保留類邊界樣本刪除非支持向量，獲得規模較小的數據集，從而解決了大數據環境下訓練樣本數據冗余問題。

(3)在并行SVM模型構建階段：結合Bagging的思想和MapReduce計算框架并行訓練SVM模型，組合所有基學習器得到最終分類模型。

2.1 噪聲過濾

由于大數據環境下并行SVM算法對噪聲數據較敏感，當噪聲數據成為支持向量，會嚴重影響SVM分類決策平面的構建，從而導致算法的分類準確度降低。為了解決大數據環境下并行支持向量機的噪聲敏感問題，提出NC策略來識別和刪除噪聲數據，首先判斷每個特征屬性的重要程度，并以信息熵加權的方式獲得屬性的權值；然后結合屬性權值和歐式距離公式設計信息熵加權距離公式IEWED，計算樣本間的相似度；最后對樣本與類別之間的相關度進行度量，識別并刪除大數據環境下的噪聲數據。具體步驟如下：

2.1.1 獲得每個特征屬性的權值

(3)

(4)

式中：t表示在類別判斷中某一個特征屬性的重要程度；m表示特征屬性的數目；P(t)表示正類樣本中屬性t出現的概率；count(t)表示正類樣本中屬性t出現的次數，count(n)表示正類樣本的數目。

證明：

(1)單調性。對于?t1,t2且t1-t2>0，P(t1)-P(t2)>0，則H′[P(t1)]-H′[P(t2)]<0。

(3)累加性。對于?t1,t2∈X，H′(X)=H′[P(t1,t2)]=H′[P(t1)·P(t2)]=H′[P(t1)]+H′[P(t2)]。

因此式(3)滿足信息熵定義的基本條件，是算法穩定的度量公式。

由于每個屬性的重要程度不一樣，在類別判定中起的作用不同，可以利用信息熵的比值來顯性地表示某個屬性在類別劃分中所占的權值，則基于信息熵的加權系數ωi可以表示為

(5)

2.1.2 計算樣本間的相似度

傳統的歐式距離只能計算兩個樣本之間的線性距離，是建立在所有特征屬性都同等重要的條件下[19]。然而，樣本的屬性不一定和類別相關聯，如果樣本的屬性與類別相關聯，其相關聯程度也不一定相同，僅僅使用歐氏距離來衡量兩個樣本間的關聯程度，沒有考慮樣本內不同屬性與類別的相關度，加強相關聯比較大的屬性和減弱相關聯比較小的屬性能夠更加準確地計算樣本間相似度。因此，結合特征屬性權值和歐式距離公式設計的信息熵加權的距離(IEWED)公式可以表示為

d(x,y)=

(6)

式(6)中：q為樣本的特征數；x、y為數據集S={x1,x2,…,xn}中的兩個樣本；xq、yq分別為樣本x、y第q個屬性的數值。

證明：

(1)對于?x,y∈S且x≠y，存在d(x,y)>0，非負性滿足。

(2)對于?x,y∈S，d(x,y)=d(y,x)，對稱性滿足。

(3)對于?x,y,z∈S，d(x,y)+d(y,z)>d(x,z)，三角不等式滿足。

因此式(6)滿足相似性度量的以上3個特性，是相似性度量公式。

2.1.3 獲取樣本與類別之間的相關度

對于數據集S={x1,x2,…,xn}，其中正類樣例集P中樣本的個數為nS+,負類樣例集N中樣本的個數為nS-，且nS++nS-=nS。根據中心點計算公式[20]，可以設置正類樣例的類中心c+和負類樣例的類中心c-為

(7)

(8)

式中：q表示樣本的特征數。可以根據信息熵加權的距離公式(IEWED)分別計算每個樣本到正類中心和負類中心的距離d(xi,c+)和d(xi,c-)，d(xi,c+)和d(xi,c-)的計算公式如下：

d(xi,c+)=

(9)

d(xi,c-)=

(10)

利用d(xi,c+)和d(xi,c-)表示樣本與類別之間的相關聯程度，對于?xi∈P,如果d(xi,c-)

NC策略的偽代碼如下。

算法1 NC策略

輸入：訓練集S={x1,x2,…,xn}

輸出：噪聲過濾后的數據集set(S′)

(1) Foriinndo{

(2) Calculated(xi,c+) by Eq.(9)

(3) Calculated(xi,c-) by Eq.(10)

(4) Ifxi∈P&&d(xi,c-)

(5) Regardxias noise

(6) }

(7) Else if{

(8)set(S′)←xi

(9) }end if

(10) Ifxi∈N&&d(xi,c+)

(11) Regardxias noise

(12) }

(13) Else if{

(14)set(S′)←xi

(15) }end if

(16)}end for

(17)Returnset(S′)

2.2 數據壓縮

2.2.1 獲取全局支持向量

在利用NC策略識別和刪除大數據環境下的噪聲數據后，為了進一步降低并行SVM算法處理大規模數據的時間復雜度，需要刪除訓練樣本中的冗余數據。對此，提出了GDC策略來刪除大數據環境下的訓練樣本冗余數據，首先對樣本特征空間進行等分，并獲得劃分后的信息粒；然后篩選并保留邊界樣本對應的信息粒，即支持向量，以此解決了訓練樣本數據冗余問題。具體步驟如下。

1)信息粒的劃分

(11)

對于信息粒gi，用Pi表示該信息粒中正例所占的比例，Ni表示該信息粒中負例所占的比例，則信息粒gi的純度Purityi可以表示為

Purityi=1-min(Pi,Ni)

(12)

性質1對于?gi∈G={g1,g2,…,gm}，m為信息粒的個數，若Purityi=1，則表示該信息粒為純粒，信息粒中僅有正例或負例；若Purityi∈[1/2,1)，則表示該信息粒為混合粒，信息粒中同時含有正例和負例，且Purityi值越小，該信息粒混合度越高，Purityi值越大，該信息粒混合度越低。

證明：

因為Purity=1-min(Pi,Ni)

所以 當Purityi=1時，1-min(Pi,Ni)=1

則存在Pi=1,Ni=0或Pi=0,Ni=1

因此信息粒gi僅有正例或負例，即為純粒。

所以當Purityi∈[1/2,1)時，1-min(Pi,Ni)∈[1/2,1)，則min(Pi,Ni)∈(0,1/2]，存在Pi≠0且Ni≠0,當且僅當Pi=Ni=1/2時Purityi=1/2，此時信息粒gi中正例和負例的數目相等，信息粒的混合度最高。因此信息粒gi中同時含有正例和負例，即為混合粒。

由性質1可知，如果某信息粒為純粒，則該信息粒中僅有正例或負例；如果信息粒為混合粒，則該信息粒中同時含有正例和負例。由于SVM的決策平面與支持向量相關，而支持向量多為類邊界樣本[21]。因此可以保留混合粒中的樣本，即支持向量，刪除純粒中的樣本，即非支持向量。從而達到保證SVM模型分類準確度的同時迅速縮減訓練集的目的，進而提高算法的執行效率。

2)信息粒的篩選

對于任一混合粒，如果信息粒中樣本數目大于給定閾值ε，則對該信息粒對應特征空間的每個特征值域進行二等分。直到所有信息粒為混合粒的同時滿足以上條件，則停止信息粒的劃分。此時得到的信息粒都是混合粒即類邊界樣本，合并所有混合粒得到與原始問題近似的全局支持向量。(取ε=4)。

GDC策略的偽代碼如下。

算法2GDC策略

輸入：訓練集D={x1,x2,…,xn}，樣本的特征空間維度d，停止劃分閾值ε

輸出：數據壓縮后的數據集set(D′)

(1) DivideDinto 2dgi

(2) Foriin 2ddo{

(3) Calculate Purityiby Eq.(12)

(4) If Purityi=1 {

(5) Regardgias pure grain

(6) }

(7) Else if {

(8) Regardgias mixture grain

(9) }end if

(10) While(Ngi>ε) {

(12) }

(14) }end for

(15) Returnset(D′)

2.2.2 并行獲取全局支持向量

在提出了GDC策略后，為了能更快地刪除訓練樣本中的冗余數據，進一步加快算法的執行效率，結合MapReduce計算模型，提出并行獲取全局支持向量的方法。在Split階段，將給定的數據集劃分成同等規模并存儲在每個mapper節點上；在Map階段，對每個數據塊內的數據使用GDC策略篩選支持向量，刪除冗余的訓練數據，獲得局部支持向量；在Reduce階段，合并所有Mapper節點上得到的支持向量得到全局支持向量。并行獲取全局支持向量的偽代碼如下。

算法3并行獲取全局支持向量

輸入：數據集D={x1,x2,…,xn},節點個數T

輸出：數據壓縮后的數據集set(D′)

(1) Split(DatasetD)

(2) Divide datasetDinto same size block by Hadoop file block strategy

(3) Create(MR-job)

(4) Map：

(5) For each mappers do

(6) Obtain local SVs result by calling GDC strategy

(7) Reduce：

(8)set(D′)←SVs

(9) Returnset(D′)

2.3 并行SVM模型構建

在經過數據壓縮獲得較小規模的數據集后，需要訓練SVM模型。由于單個支持向量機模型容易產生誤分類的問題，導致算法的分類準確度不高。基于Bagging的集成學習方法可以有效地克服這個問題，通過訓練多個基學習器共同做決策，有效地避免了單一分類器模型出現的誤差問題，加強了算法整體的穩定性[22]。為了提高算法的分類準確度，基于Bagging的思想訓練多個基分類器，采用投票法獲得類別劃分的結果。為了進一步加快SVM模型的訓練過程，提高算法的總體并行化效率，利用MapReduce計算模型并行訓練支持向量機模型。在數據劃分階段，根據bootstrap自助抽樣的方法獲得m個與初始樣本集同等規模的數據集，并分發給每個Mapper節點；在Map階段，利用每個子數據集單獨訓練一個支持向量機模型，將訓練得到的基學習器組合起來得到一個強的分類模型。并行SVM模型構建的偽代碼如下。

算法4 并行SVM模型構建

輸入：數據集D′={x1,x2,…,xn}，節點個數T

輸出：預測模型

(1) Split(DatasetD′)

(2) Replicate datasetS′based on bootstrap and getmtraining datasets

(3) Map：

(4) For each Block do

(5) Train SVM onmtraining datasets

(6) Obtainfi(x)

(7) Save the SVM model in each node of Hadoop

(8) Emit PredictionModel()

2.4 GIESVM-MR算法步驟

GIESVM-MR算法的具體實現步驟如下。

步驟1 根據輸入的原始數據集，通過調用算法1的NC策略識別并刪除噪聲數據，得到噪聲清除后的訓練集；

步驟2 在數據壓縮階段，通過調用算法3并行執行GDC策略，快速獲得數據壓縮后的全局支持向量SVs；

步驟3 獲取數據壓縮后的數據集，啟動MapReduce任務，調用算法4并行訓練SVM模型，從而獲得最終的分類模型。

2.5 GIESVM-MR算法的時間復雜度分析

GIESVM-MR算法的時間復雜度主要由噪聲過濾、數據壓縮、并行SVM模型構建這幾個步驟構成。這些步驟的時間復雜度分別為：

(1)噪聲過濾階段，設原數據集的大小為M，使用“NC”策略對數據集進行噪聲樣本的識別和刪除，其中需要計算每個樣本到正類中心和負類中心的距離，則進行噪聲過濾的時間復雜度為O(M)。

(2)數據壓縮階段，設經過噪聲過濾得到的樣本集大小為N，樣本的維度為d，則使用GDC策略進行粒度化并劃分，需要對2d個信息粒進行判斷，則進行數據壓縮獲得SVs的時間復雜度為O(2d)。

(3)并行SVM模型構建階段，假設數據壓縮后的樣本集中樣本數目為M′,則訓練支持向量機模型的時間復雜度為O(M′3)。因此GIESVM-MR算法時間復雜度為數據壓縮、噪聲過濾和并行SVM模型構建的時間復雜度之和O(2d+M+M′3)。

3 實驗結果及分析

3.1 實驗環境

為驗證GIESVM-MR算法的性能展開了相關實驗。實驗的硬件設備為Master主機1臺和Slaver機3臺，共4個節點，每一臺硬件設備的處理器均為Intel(R)Core(TM)i5-9400H CPU @ 2.9 GHz，內存16G。實驗的軟件編程環境均為python3.5.2；操作系統均為Ubuntu 16.04；MapReduce架構均為Apache Hadoop3.2版本。

3.2 實驗數據

GIESVM-MR算法采用的實驗數據是來自標準UCI數據庫的真實數據集，分別是NDC數據集[23]、Skin-Segmentain數據集[24]和Cover type數據集[25]。其中，NDC數據集是由正態分布集群數據發生器隨機生成的數據，該數據集樣本數量為100 000，維度為32，具有數據量小、噪聲數據多的特點；Skin-Segmentain數據集是隨機采集的人臉圖像，包含不同種族、不同年齡、不同性別的數據，該數據集樣本數量為245 057，維度為3，具有維度小的特點； Cover type數據集是美國地質調查局和USF記錄某森林覆蓋率的數據，其中包含多種植被的數據，將其劃分為兩類：A類植被和非A類植被，該數據集樣本數目為581 012，維度為10，具有數據量大，支持向量少的特點。數據集的具體信息如表1所示。

表1 實驗數據

3.3 評價指標

使用F-Measure作為指標來評價算法的分類準確度，F-Measure綜合考慮了分類結果的正確率(precision)和召回率(recall)的情況，能夠較為準確地評價分類算法的結果，其計算公式為

通常情況下，參數λ設置為1，當F-Measure的值較高時，表示分類結果更為準確合理。

3.4 參數選取

GIESVM-MR算法使用GDC策略根據特征屬性將原始數據劃分為信息粒，通過保留類邊界樣本對應的混合粒，刪除對SVM模型構建沒有作用的純粒，即非支持向量，以達到刪除訓練樣本中的冗余數據的目的，進而降低支持向量機的訓練時間。但對于信息粒再劃分的閾值ε來說，需要指定具體的數值，閾值ε過小，原始訓練集將壓縮為空集，所以閾值ε的值至少大于1，同時，如果閾值ε設置過大，不僅不能有效地識別訓練集中的支持向量，而且通過GDC策略得到的訓練集規模較大，導致GIESVM-MR算法的整體執行時間增加。為了加快GIESVM-MR算法執行效率的同時能獲得更加準確的分類結果，需要對閾值ε的取值進行合理的設置，在基于NDC數據集下，保證其他參數不變，將閾值ε的取值設置為[2，10]，重復運行10次，取10次的F-Measure平均值進行分析。從圖1中可以看出，閾值ε給定的太小會影響分類結果的準確度。實驗結果表明，在ε的值取4的時候，能得到準確的分類結果，并且此時利用GDC策略得到的訓練集規模較小。

圖1 閾值ε的選取

3.5 算法性能比較分析

3.5.1 算法的時間復雜度分析

將GIESVM-MR算法分別與PIDSVM[13]、FMPSVM[14]和PISVM-CS[16]算法在NDC、Skin-Segmentain和Cover type數據集下進行對比實驗，在實驗中分別比較了不同數據規模下GIESVM-MR算法與PISVMAM算法和PIDSVM算法的執行時間，實驗結果如圖2所示。

圖2 不同算法在3個數據集上的執行時間

從圖2中可以明顯看出，隨著數據規模的增大，GIESVM-MR算法的執行時間呈線性小幅度的增長，而PIDSVM、FMPSVM和PISVM-CS算法的執行時間呈幾何倍數增長。在規模較小的NDC數據集上，GIESVM-MR算法的執行時間相較于PIDSVM、FMPSVM和PISVM-CS算法分別降低了76.2%、43.7%和60.5%；隨著訓練數據規模的增大，在Skin-Segmentain數據集上，與PIDSVM、FMPSVM和PISVM-CS算法相比，該算法的執行時間分別降低了83%、71.2%和60%；在規模最大的Cover type數據集上，相較于PIDSVM、FMPSVM和PISVM-CS算法3種算法，GIESVM-MR算法的執行時間分別降低了82.4%、72.1%和68.4%。其主要原因是：GIESVM-MR算法使用GDC策略篩選支持向量，刪除大規模數據中的冗余數據即非支持向量，以更優的方式適應了大數據環境。其中，相較于PIDSVM算法雖然利用分布式的訓練方式處理大規模數據，但是每個支持向量機需要處理的數據規模還是相當龐大的，沒有利用一種有效的方法來篩選支持向量，縮小原始訓練集的規模，對于FMPSVM算法雖然利用特征選擇的方式減少了相關度較低的特征，降低了訓練樣本集的維度，但是支持向量機模型的訓練還是需要處理大規模的數據集，導致算法的執行時間較大。同時，PISVM-CS算法，利用遺傳算法尋找最優的參數，以迭代的方式尋找支持向量，模型的訓練過程中存在大量的迭代過程，多次執行MapReduce任務，增加了節點間的信息傳輸時間，隨著訓練數據集規模的增大算法的迭代尋優過程更加復雜，導致算法的訓練時間急劇增長。因此，GIESVM-MR算法能夠克服此類問題是因為首先將數據粒化，并根據特征空間劃分成不同的信息粒，篩選類邊界樣本所對應的混合粒，即支持向量，迅速減小了訓練集的規模，有效地提高了大數據環境下GIESVM-MR算法的執行效率。

3.5.2 算法的分類準確度分析

將GIESVM-MR算法分別與PIDSVM[13]、FMPSVM[14]和PISVM-CS[16]算法在NDC、Skin-Segmentain和Cover type數據集下進行對比實驗，在實驗中分別比較了GIESVM-MR算法與PISVMAM算法和PIDSVM算法的分類準確度F-Measure，實驗結果如圖3所示。

圖3 各種算法在3個數據集上的F-Measure

從圖3可以看出，GIESVM-MR算法在3個數據集上的分類準確度均較高。在噪聲數據較多的NDC數據集上，GIESVM-MR算法的分類準確度相較于PIDSVM、FMPSVM和PISVM-CS算法分別提高了3.2%、3.4%和27.4%，這是因為該算法使用NC策略有效的識別并刪除數據中的噪聲，獲得沒有噪聲的數據集，從而避免了噪聲數據成為支持向量影響分類決策平面的確立。PIDSVM算法利用概率推理方式識別隱藏在數據集中的噪聲數據，并將其考慮到模型的構建中，克服了噪聲數據的干擾。同時，FMPSVM算法結合特征選擇和互信息有效識別了數據集中相關度較低的特征，降低了噪聲數據的影響。然而，PISVM-CS算法沒有有效地識別數據集中的噪聲數據，多次迭代反而會積累誤差，導致分類準確度較差。在Skin-Segmentain數據集上，與PIDSVM、FMPSVM和PISVM-CS算法相比，GIESVM-MR算法的分類準確度分別提高了2.1%、4.3%和6.5%。而在數據規模最大的Cover type數據集上，GIESVM-MR算法的分類準確度比PIDSVM、FMPSVM和PISVM-CS 3種算法分別提高了5.5%、4.6%和10.4%。這是因為GIESVM-MR算法利用NC策略有效地識別和刪除了噪聲數據，進而提高了大數據環境下算法的分類準確度。

3.6 算法的可擴展性分析

為了驗證GIESVM-MR算法在不同節點數目下的分類準確度和訓練時間， 在NDC數據集上進行10次重復實驗，計算均值作為最終結果，實驗結果如圖4所示。

圖4 GIESVM-MR算法在不同節點數目上執行時間和F-Measure

從圖4(a)可以看出， GIESVM-MR算法的執行時間隨著節點數的增多而迅速減少。這是由于節點數的增多，有效地提高了算法的并行化程度，減少了每個節點上的任務量，同時降低了每個節點上的訓練時間，從而減小了算法整體的運行時間；但是節點數超過10以后，算法的執行時間保持在60 s左右，每個節點上的執行時間趨于平緩，節點間的信息傳輸時間會增加，所以算法的運行時間不會明顯減少。此外，由圖4(b)可知，算法的分類準確度會隨著節點數目的增加而逐漸減小，從2個節點增加到16個節點，算法的分類準確度從96.3%降低到90.2%。隨著數據的不斷劃分，數據的空間分布會發生改變，根據GDC策略得到的支持向量會發生變化，導致算法的分類準確度降低,因此在提高算法執行效率的同時應該考慮節點數目增加導致算法分類準確度降低的問題。綜合上述分析，GIESVM-MR算法處理大數據環境下的分類問題具有更強的適應性以及更好的分類準確度。

4 結論

為解決并行SVM算法在大數據背景下存在噪聲數據較敏感，訓練樣本數據冗余等問題，提出了基于粒度和信息熵的GIESVM-MR算法。首先，該算法對原始數據集提出了噪聲清除策略NC對每個特征屬性的重要程度進行評價，獲得樣本與類別之間的相關度，有效的識別和刪除大數據環境下的噪聲數據；其次提出基于粒度的數據壓縮策略GDC, 通過篩選信息粒的方式保留類邊界樣本刪除非支持向量，獲得規模較小的數據集，從而解決了大數據環境下訓練樣本數據冗余問題；最后結合Bagging的思想和MapReduce計算模型并行化訓練SVM，生成最終的分類模型。為了驗證GIESVM-MR算法的性能，在NDC、Skin-Segmentain和Cover type 3個數據集下與現有算法進行綜合性能對比分析。實驗結果表明GIESVM-MR算法的分類效果更佳，且在大規模的數據集下算法的執行效率更高。