并行PSO結合粗糙集的大數據屬性約簡算法

李 華，劉占偉，郭育艷

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

0 引 言

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

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

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

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

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

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

基于幾個公開數據集，通過實驗對提出的方法和其它現有方法進行比較分析，驗證了提出方法的優越性。

1 提出的數據屬性約簡方法

1.1 粗糙集理論

數據集中隱藏的信息可用四元組(U,A,V,f)表示，其中U={u1,u2,…,uN}為N個對象或實例的非空有限集合，稱為論域，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中均能找到對應的值Va，從而屬性值集合V即為A的值域。四元組(U,A,V,f)又稱為決策表。

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

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

(1)

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

[u]P∈U/P

(2)

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

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

(3)

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

集合X關于不可分辨關系P的上逼近定義為

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

(4)

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

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

(5)

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

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

(6)

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

1.2 基于粗糙集的大數據屬性約簡建模

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

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

(7)

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

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

(8)

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

(9)

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

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

2.1 MapReduc框架下總體求解方案

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

圖1 MapReduce并行數據集屬性約簡框架

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

2.2 驅動程序

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

算法1：驅動程序

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

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

(3)whilecount≤Kdo%程序在計算節點數量內運行

(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 映射程序

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

(10)

(11)

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

算法2： 映射程序

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

(2)whiler

(3)i←r+1;

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

(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 匯總程序

計算節點的輸出結果可供所有的匯總節點使用，每個匯總節點負責收集各計算節點的決策表作為初始粒子群并執行并行粒子群算法操作。粒子群算法的程序同樣由驅動程序執行，包含粒子數量、適應值計算、最優個體極值、最優全局極值[10]。

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

(12)

(13)

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

圖2 粒子群優化算法流程

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

算法3： 匯總程序

(1)gen ← 0;

(2)MaxFitness ← -In finity;

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

(4)while Fitness≤finialvalue do %當適應度數值<終止條件時執行

(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 實驗結果及討論

3.1 實驗設置和數據集

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

表1 實驗數據集

3.2 算法運行時長與數據屬性約簡性能對比

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

圖3 3種算法對不同數據集的運行時長

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

圖4 3種算法對不同數據集的屬性約簡效果

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

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

圖6 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的運行時長改進比例

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

3.3 算法性能影響因素分析

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

圖7 串行PSO和2個并行PSO運行時間比較

圖8 提出的MapReduce-并行PSO相比非MapReduce-并行PSO、串行PSO的運行時長改進比例

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

4 結束語

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

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