并行PSO結(jié)合粗糙集的大數(shù)據(jù)屬性約簡算法

李 華，劉占偉，郭育艷

(1.河南工程學(xué)院 計算機(jī)學(xué)院，河南 鄭州 451191；2.河南工程學(xué)院 理學(xué)院，河南 鄭州 451191；3.河南財經(jīng)政法大學(xué) 科研處，河南 鄭州 450046)

0 引 言

從海量復(fù)雜事件中按照既定要求提取所需信息是實現(xiàn)大數(shù)據(jù)分析與模式識別的首要步驟。然而，這些復(fù)雜事件通常具有分布式、多源異構(gòu)以及冗余性較高等特征。因此，最大程度減少由于信息冗余或不相關(guān)數(shù)據(jù)引起的額外物理開銷或時間開銷是十分必要的。其關(guān)鍵技術(shù)稱為數(shù)據(jù)集屬性約簡[1]。

文獻(xiàn)[2]提出基于樸素貝葉斯數(shù)據(jù)過濾的屬性約簡算法，但該算法在數(shù)據(jù)屬性數(shù)量或?qū)傩蚤g關(guān)聯(lián)度過大時，約簡算法性能將呈現(xiàn)明顯下降趨勢。文獻(xiàn)[3,4]提出基于數(shù)據(jù)封裝和嵌入的屬性約簡算法，針對預(yù)先設(shè)定的歸納方法和區(qū)域，制定最佳的屬性子集，然而這樣的性能改進(jìn)會消耗大量的計算資源[5,6]。文獻(xiàn)[7]針對教育大數(shù)據(jù)高維度、不完備、增量型等現(xiàn)狀，基于粗糙集理論構(gòu)建了不完備決策表的差別信息增量更新算法，實現(xiàn)高維數(shù)據(jù)屬性的有效約簡。文獻(xiàn)[8]指出，求解屬性約簡問題屬于NP-hard問題，而傳統(tǒng)串行啟發(fā)式搜索方法存在求解耗時過長甚至無解的情形[9]。

因此，提出基于MapReduce(映射-歸約)框架的并行粒子群算法結(jié)合粗糙集理論的數(shù)據(jù)屬性約簡算法。主要創(chuàng)新點總結(jié)如下：

(1)對基于粗糙集理論的大數(shù)據(jù)屬性最小約簡問題進(jìn)行建模，通過定義數(shù)據(jù)集屬性的上、下逼近實現(xiàn)了對數(shù)據(jù)屬性不確定性的有效處理；

(2)提出了基于粗糙集大數(shù)據(jù)屬性約簡與并行粒子群算法相結(jié)合的完整算法設(shè)計步驟，相比傳統(tǒng)串行求解算法，提出的并行算法在同樣的迭代次數(shù)下，能夠有效提升數(shù)據(jù)屬性約簡運(yùn)行效率；

(3)基于MapReduce框架搭建了提出的并行求解算法的實驗平臺，分別給出了MapReduce框架中驅(qū)動程序、映射程序和匯總程序的算法步驟。

基于幾個公開數(shù)據(jù)集，通過實驗對提出的方法和其它現(xiàn)有方法進(jìn)行比較分析，驗證了提出方法的優(yōu)越性。

1 提出的數(shù)據(jù)屬性約簡方法

1.1 粗糙集理論

數(shù)據(jù)集中隱藏的信息可用四元組(U,A,V,f)表示，其中U={u1,u2,…,uN}為N個對象或?qū)嵗姆强沼邢藜?，稱為論域，A為具有(n+k)個屬性或特征的集合。V為屬性值集合，f為U×A→V的一個映射。此外，屬性集A滿足A=C∪D，其中C={a1,a1,…,an}是具有n維度的條件屬性集，D={d1,d2,…,dk}為具有k維度的決策屬性集。對于A中的每個元素a(即a∈A)，在屬性值集合V中均能找到對應(yīng)的值Va，從而屬性值集合V即為A的值域。四元組(U,A,V,f)又稱為決策表。

在對數(shù)據(jù)集進(jìn)行分類時，相差不大的個體被歸于同一類，而同一類中的數(shù)據(jù)間的關(guān)系稱為不可分辨等價關(guān)系(indiscernibility relation，IND)。用數(shù)學(xué)語言描述為，對于任意一個非空屬性集合P?C，不可分辨關(guān)系表述為

IND(P)={(u1,u2)∈U×U:?a∈P,
f(u1,a)=f(u2,a),a∈P}

(1)

其中，f(u,a)表示實例u對應(yīng)屬性a的取值。若(u1,u2)∈IND(P)，則u1的屬性無法與u2的屬性區(qū)分開。進(jìn)一步地，令[u]P表示P下的元素u(∈U)，從而集合U可約簡出存在不可分辨關(guān)系的集合，稱為基本等效類集合，記為U/P滿足

[u]P∈U/P

(2)

對于集合X?U，當(dāng)集合X能夠表示為基本等效類集合時，則稱其是可以精確定義的；反之，集合X僅能通過基本等效類集合以逼近的方式來刻畫。其中，集合X關(guān)于不可分辨關(guān)系P的下逼近定義為

P_(X)={u∈U:[u]P?X}

(3)

其實際意義為根據(jù)已有知識來判定肯定屬于集合X的對象所組成的最大集合，并將P_(X)稱為集合X的正區(qū)，而根據(jù)已有知識來判定肯定不屬于集合X的對象組成的集合則稱為集合X的負(fù)區(qū)。

集合X關(guān)于不可分辨關(guān)系P的上逼近定義為

P_(X)={u∈U:[u]P∩X≠?}

(4)

其實際意義為，P_(X)為所有與X相較非空的[u]P的并集，即那些可能屬于集合X的對象所組成的最小集合。從而集合X關(guān)于P的邊界區(qū)定義為

BN(X)=P_(X)-P_(X)

(5)

如果邊界區(qū)域是空集，則稱X為精確集合，反之則稱其為粗糙集合。為了衡量兩個不同屬性間的依賴程度，引入依賴度量函數(shù)，定義如下：

設(shè)P、Q為集合U的兩個不同屬性，則屬性Q對屬性P的依賴度函數(shù)γP(Q)定義為

(6)

式中：γP(Q)∈[0, 1]，∪表示并集操作，|·|表示集合的勢，用于度量集合規(guī)模的大小。若γP(Q)的取值更接近于1，表明Q更依賴于P。根據(jù)這一概念，若約簡集合R是條件屬性集合C的子集，則應(yīng)存在γR(D)=γC(D)。

1.2 基于粗糙集的大數(shù)據(jù)屬性約簡建模

若屬性a能夠從集合P中移除而不改變U相對于P的等效類劃分，則它在P中稱為是多余的屬性，反之則稱其為不可或缺的屬性。為此，定義條件屬性集合C的最小約簡集R*?C，刪去R*中任何屬性項，等價類集合P都將發(fā)生變化，即

[x](R*-{a})≠[x]C

(7)

集合R*同樣被稱為信息系統(tǒng)(U,A,V,f)的基本屬性。不妨令集合R1為與γC(D)具有相同依賴度的所有約簡集，則最小約簡集的定義為

R*∈{R∈R1:|R|≤|S|,?S∈R1

(8)

因此，可將最小約簡問題的求解形式描述為

(9)

2 基于MapReduce的并行粒子群求解算法設(shè)計

對于大數(shù)據(jù)分析或模式識別問題而言，數(shù)據(jù)集存在格式多樣、信息稀疏的特點，故暴力枚舉或串行求解算法的時間復(fù)雜度極高。為提升對目標(biāo)問題(9)的求解效率，從兩個層面提升數(shù)據(jù)集屬性約簡效率：①采用并行粒子群算法代替串行粒子群算法對最小約簡集進(jìn)行求解；②采用MapReduce并行計算框架對數(shù)據(jù)集進(jìn)行分解操作以降低問題求解規(guī)模。

2.1 MapReduc框架下總體求解方案

MapReduce作為谷歌公司開發(fā)的并行計算框架，如圖1所示。

圖1 MapReduce并行數(shù)據(jù)集屬性約簡框架

包含兩個關(guān)鍵的操作：①map(映射)操作，即分解計算任務(wù)；②reduce(匯總)操作，即將子任務(wù)計算結(jié)果匯總。其核心思想是利用數(shù)據(jù)的局部特性將數(shù)據(jù)分割為相互獨立的數(shù)據(jù)塊，由多個映射器進(jìn)行并行處理后，最終由reduce操作對映射器輸出結(jié)果進(jìn)行匯總。所提MapReduce框架的求解過程如圖1所示(假設(shè)有4個計算節(jié)點)。Map-Reduce上運(yùn)行數(shù)據(jù)集屬性約簡并行粒子群算法可分為3個主要部分：驅(qū)動程序、映射程序和匯總程序。

2.2 驅(qū)動程序

驅(qū)動程序的作用是在計算節(jié)點之間劃分計算任務(wù)量，從而使得各計算節(jié)點能夠根據(jù)劃分的數(shù)據(jù)塊計算生成前文所述的子信息系統(tǒng)。為保證每個計算節(jié)點的承擔(dān)的任務(wù)量均衡，即平衡計算負(fù)載以確保計算性能，提出如算法1所示的驅(qū)動程序，其核心思想是每次MapReduce迭代完成后，通過計算每個計算節(jié)點要處理的數(shù)據(jù)塊的起始索引和大小，實時調(diào)整下一次迭代時每個計算節(jié)點的任務(wù)量。其中m表示m次迭代結(jié)果，ST是m次和m-1次迭代結(jié)果的平均數(shù)，K表示計算節(jié)點數(shù)量。

算法1：驅(qū)動程序

(1)ST←m(m-1)/2；S← [ST/K]；

(2)is← 1;count← 1; %is為數(shù)據(jù)塊的起始索引，count為計數(shù)器

(3)whilecount≤Kdo%程序在計算節(jié)點數(shù)量內(nèi)運(yùn)行

(4)a1←m-is;

(5)b← -(1+2a1);

(7) compute a valid value forn;

(8) saveis, n;

(9)is←is+n;count←count+ 1;

(10)endwhile

2.3 映射程序

映射程序是為了計算提取子數(shù)據(jù)集的信息系統(tǒng)參數(shù)，即生成子數(shù)據(jù)集的決策表。其中前N行表示條件屬性，最后一行表示決策屬性，最終生成的決策表記為b，其中的元素構(gòu)造方法如下

(10)

(11)

算法2示出了計算節(jié)點生成子數(shù)據(jù)集決策表的流程，即首先從HDFS中讀取數(shù)據(jù)集，并使用驅(qū)動程序進(jìn)行數(shù)據(jù)集劃分，最終計算節(jié)點的計算結(jié)果輸出至匯總程序。

算法2： 映射程序

(1)r←is; %r為數(shù)據(jù)塊起始索引， 由算法1確定

(2)whiler

(3)i←r+1;

(4)whilei≤mdo% 以下程序執(zhí)行對數(shù)據(jù)集的劃分

(5)ifd(r)≠d(i) then

(6) DistinctTable[r] = Compare(Dataset[r], Dataset[i])

(7) emit(DistinctTable[r]);

(8)endif

(9)i←i+1;

(10)endwhile

(11)r←r+1;

(12)endwhile

2.4 匯總程序

計算節(jié)點的輸出結(jié)果可供所有的匯總節(jié)點使用，每個匯總節(jié)點負(fù)責(zé)收集各計算節(jié)點的決策表作為初始粒子群并執(zhí)行并行粒子群算法操作。粒子群算法的程序同樣由驅(qū)動程序執(zhí)行，包含粒子數(shù)量、適應(yīng)值計算、最優(yōu)個體極值、最優(yōu)全局極值[10]。

粒子群優(yōu)化(particle swarm optimization，PSO)算法的基本概念是，建立一個群體中每個個體都遵循的運(yùn)動模型，通過迭代獲取個體和群體的最優(yōu)解，也就是個體極值和全局(局部)極值。PSO算法的數(shù)學(xué)描述始于二維空間中，對個體運(yùn)動的圖形化表達(dá)，并由此延申到N維空間，構(gòu)成了PSO算法的完整數(shù)學(xué)表達(dá)：Xi=(x1,x2,…,xN)表示粒子i在N維空間內(nèi)的位置，Vi=(v1,v2,…,vN)表示粒子的飛行速度，對于第k次迭代，每個粒子的運(yùn)動可以表示為

(12)

(13)

式中：群體粒子總數(shù)為M，i=1, 2,…,M，表示第k次迭代粒子i速度矢量的第d維分量，表示第k次迭代粒子i位置矢量的第d維分量，pid表示粒子i個體發(fā)現(xiàn)最好位置的第d維分量，pgd表示群體發(fā)現(xiàn)最好位置的第d維分量，c1、c2表示權(quán)重因子，w表示慣性權(quán)重函數(shù)。算法流程如圖2所示。

圖2 粒子群優(yōu)化算法流程

并行PSO算法采用主從和多數(shù)據(jù)流結(jié)合的模式編程，完成初始化、任務(wù)分配、粒子選擇和粒子適應(yīng)性計算的過程。具體的迭代過程與式(12)和式(13)相同，即通過比較優(yōu)選整個種群的最優(yōu)值，更新每個粒子的速度及位置，最終找到滿足要求的最小適應(yīng)閾值。算法3示出了匯總操作階段的算法流程。

算法3： 匯總程序

(1)gen ← 0;

(2)MaxFitness ← -In finity;

(3)InitializeParticleSwarm (ParticleSwarm); %初始化粒子群算法

(4)while Fitness≤finialvalue do %當(dāng)適應(yīng)度數(shù)值<終止條件時執(zhí)行

(5)Evaluate (ParticleSwarm, DistinctTable);

(6)r← 1;

(7)whiler< NumParticleSwarm do

(8)UpdateSpeedPosition (ParticleSwarm, DistinctTable); %更新粒子速度與位置

(9)end while

(10) gen ← gen + 1;

(11)end while

(12)emit(MaxIndividual(ParticleSwarm))

3 實驗結(jié)果及討論

3.1 實驗設(shè)置和數(shù)據(jù)集

為驗證所提算法的優(yōu)異性和可行性，采用傳統(tǒng)串行PSO[11]、非MapReduce框架的并行粒子群算法[12]作為對比算法對同一數(shù)據(jù)集屬性進(jìn)行最小化約簡。設(shè)置4個數(shù)據(jù)集進(jìn)行實驗，見表1，包括實例數(shù)(#Inst)、屬性數(shù)(#Attr)、組合數(shù)(#Comb)和區(qū)分表中的行數(shù)(#DTRows)。并評估不同約簡算法的性能：Spam-base[13]、NSL-KDD[14]、Kyoto[15]和CDMC2012[16]。這些數(shù)據(jù)集被廣泛用作相關(guān)入侵軟件檢測、垃圾郵件過濾等算法的基準(zhǔn)算例，且不同的數(shù)據(jù)集具有不同的統(tǒng)計特征，擁有大量的個體實例與特定的屬性。實驗使用分布式Hadoop集群[17]進(jìn)行，軟件環(huán)境為Java 7.0、Ubuntu 14.0.4系統(tǒng)，硬件配置為16 GB RAM、4核Intel處理器。分布式粒子群算法的種群大小設(shè)置為100，迭代終止閾值設(shè)置為屬性約簡維度變化小于1。其中，約簡維度表示從原始高維數(shù)據(jù)映射到低維數(shù)據(jù)空間后所減少的維度數(shù)量。

表1 實驗數(shù)據(jù)集

3.2 算法運(yùn)行時長與數(shù)據(jù)屬性約簡性能對比

首先對比分析傳統(tǒng)順序粒子群算法和并行粒子群算法在同樣迭代次數(shù)下的算法運(yùn)行時長和屬性約簡性能。此外，本組實驗還討論了計算節(jié)點數(shù)量對運(yùn)行時長與約簡性能的影響。實驗結(jié)果如圖3所示。當(dāng)計算節(jié)點數(shù)量設(shè)置為4時，相同迭代次數(shù)下，對4個數(shù)據(jù)集屬性約簡采用本文提出的MapReduce-并行PSO的運(yùn)行時長比傳統(tǒng)串行PSO分別縮短了69%、70.7%、72.7%和72.4%，平均運(yùn)行時間降低了71.2%；而比非MapReduce-并行PSO[12]分別縮短了56.67%、57.89%、57.14%和60.81%，平均運(yùn)行時間縮短了58.13%；而計算節(jié)點數(shù)量設(shè)置為8時，相同迭代次數(shù)下，對4個數(shù)據(jù)集屬性約簡采用本文提出的MapReduce-并行PSO的運(yùn)行時長比傳統(tǒng)串行PSO分別縮短了57.1%、62.2%、63.6%和62.9%；而比非MapReduce-并行PSO分別縮短了40%、45.61%、42.86和47.30%。故可知本文提出的MapReduce-并行PSO能夠顯著提升算法執(zhí)行效率。此外，4個數(shù)據(jù)集下8計算節(jié)點的算法運(yùn)行時長比4計算節(jié)點的運(yùn)行時長上升了27.8%、22.6%、25%和25.6%。表明簡單地增加計算節(jié)點并不能始終帶來算法執(zhí)行效率的提升，這是由于計算節(jié)點的增加導(dǎo)致MapReduce需要更多地執(zhí)行數(shù)據(jù)遷移與存儲操作，從而導(dǎo)致額外的物理開銷與時間開銷。

圖3 3種算法對不同數(shù)據(jù)集的運(yùn)行時長

進(jìn)一步地，在相同迭代次數(shù)下，串行PSO與2個并行PSO對統(tǒng)一數(shù)據(jù)集的屬性約簡性能如圖4所示。此外，同樣討論了計算節(jié)點數(shù)量對屬性約簡性能的影響。可知，相同迭代次數(shù)下，當(dāng)計算節(jié)點為4時，本文提出的MapReduce-并行PSO對4個數(shù)據(jù)集的屬性約簡維度比串行PSO分別下降11.3%、16.7%、50%和46.7%；而比非MapReduce-并行PSO分別縮短了6%、9.09%、33.3%和20%；當(dāng)計算節(jié)點為8時，提出的并行粒子群算法對4個數(shù)據(jù)集的屬性約簡維度比串行PSO則分別下降28.3%、4.2%、40%和40%。表明所提算法在規(guī)定的迭代次數(shù)中具有更好的屬性約簡效果。此外，4個數(shù)據(jù)集下8計算節(jié)點的約簡維度比4計算節(jié)點的運(yùn)行時長分別下降19.1%、-15%、-20%和-12.5%，而比非MapReduce-并行PSO分別縮短了24%、-4.55%、21.43%和10%，這表明通過簡單地增加計算節(jié)點不能始終帶來約簡維度的下降。

圖4 3種算法對不同數(shù)據(jù)集的屬性約簡效果

為進(jìn)一步說明所提算法的優(yōu)異性，分析達(dá)到相同屬性約簡效果下的算法運(yùn)行時長。圖5示出了隨著屬性約簡維度的變化算法運(yùn)行時長的變化趨勢。圖6為本文提出的MapReduce-并行PSO相比MapReduce-并行PSO、串行PSO的運(yùn)行時長改進(jìn)比例。

圖5 不同算法運(yùn)行時長隨屬性約簡維度的變化趨勢

圖6 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的運(yùn)行時長改進(jìn)比例

從圖5、圖6可以看出，當(dāng)約簡維度從10變化到57時，串行PSO的運(yùn)行時長增加了75.2%；非MapReduce-并行PSO運(yùn)行時長增長了72.5%；而具有4個計算節(jié)點的并行粒子群算法運(yùn)行時長則僅增加了57.1%，提出的Map-Reduce-并行PSO的初始運(yùn)行時長比串行算法少64.3%。而隨著約簡維度由10變化到57時，對非MapReduce框架下并行PSO算法的改進(jìn)比例由40%增長到63%，而對串行PSO算法的改進(jìn)比例由59%增長到74%。由此可見，隨著屬性約簡維度的上升，提出MapReduce-并行PSO運(yùn)行時長并未顯著增加，展現(xiàn)出了與傳統(tǒng)算法相比更強(qiáng)的運(yùn)行穩(wěn)定性能。

3.3 算法性能影響因素分析

進(jìn)一步討論影響算法性能的其它因素。除去MapReduce框架為屬性約簡提供的計算節(jié)點數(shù)量外，數(shù)據(jù)塊決策表的大小同樣決定了算法的運(yùn)行性能。具體而言，即數(shù)據(jù)塊的屬性數(shù)量以及數(shù)據(jù)塊包含的個體數(shù)量。因此，不失一般性設(shè)置兩組實驗，即分別采用Spam base數(shù)據(jù)集和CDMC2012數(shù)據(jù)集作為實驗算例，采用Weka中的濾波器隨機(jī)形成具有不同大小的5組子數(shù)據(jù)集，分別包括2000、4000、6000、8000和10 000個樣本。并對每個子數(shù)據(jù)集運(yùn)行5次后的算法運(yùn)行時間取其平均值作為對比。圖7示出了不同數(shù)據(jù)規(guī)模下的傳統(tǒng)串行PSO和所提出的并行粒子群算法運(yùn)行時長，圖8為本文提出的MapReduce-并行PSO相比非MapReduce-并行PSO[12]、串行PSO的運(yùn)行時長改進(jìn)比例。

圖7 串行PSO和2個并行PSO運(yùn)行時間比較

圖8 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的運(yùn)行時長改進(jìn)比例

從圖7、圖8可知，初始規(guī)模下，兩個算法之間的運(yùn)行時間相差不大。然而，隨著數(shù)據(jù)規(guī)模由2000增長到10 000，串行PSO的運(yùn)行時長增長了8000 s，非MapReduce-并行PSO運(yùn)行時長增長了5930 s，而提出的并行粒子群算法的運(yùn)行時長則增加了2600 s。對非MapReduce框架下并行PSO算法的改進(jìn)比例和對串行PSO算法的改進(jìn)比例最終分別穩(wěn)定在55%和67.5%左右。因此，本文提出的MapReduce-并行PSO能夠有效減少算法運(yùn)行時間。此外，隨著數(shù)據(jù)規(guī)模的不斷增長，僅設(shè)置4個計算節(jié)點的數(shù)據(jù)存儲和遷移造成的時間開銷已然不能忽視，為節(jié)約計算時間，提高屬性約簡效率，可通過增加計算節(jié)點的方式來分擔(dān)計算任務(wù)量。

4 結(jié)束語

針對大數(shù)據(jù)分析和模式識別過程中的數(shù)據(jù)屬性約簡問題，提出了MapReduce環(huán)境下的并行粒子群算法與粗糙集理論相結(jié)合的約簡算法。通過并行粒子群算法和MapReduce分布式計算兩個層次來實現(xiàn)數(shù)據(jù)集屬性約簡計算的效率提升。算例結(jié)果表明，與傳統(tǒng)串行PSO相比，在相同的迭代次數(shù)和數(shù)據(jù)集規(guī)模下，所提并行計算方法有效節(jié)約了運(yùn)行時長，且對數(shù)據(jù)集屬性的約簡效果也更優(yōu)。此外，實驗結(jié)果還表明，當(dāng)數(shù)據(jù)規(guī)模不斷增大時，采用MapReduce分布式計算和并行粒子群算法的架構(gòu)比傳統(tǒng)串行粒子群算法能夠在更短的時間內(nèi)得到數(shù)據(jù)集屬性約簡結(jié)果，故而所提算法在工程應(yīng)用中更具優(yōu)異性和適用性。

未來將深入研究并行粒子群算法關(guān)鍵參數(shù)對數(shù)據(jù)集屬性約簡性能的影響以及約簡性能，進(jìn)一步提升算法性能。