秦廷楨 丁衛(wèi)平 鞠恒榮 李 銘 黃嘉爽 陳悅鵬 王海鵬

近年來，隨著信息技術(shù)的發(fā)展，科學(xué)和工業(yè)等現(xiàn)實領(lǐng)域產(chǎn)生大量的數(shù)據(jù)，而許多應(yīng)用程序處理的數(shù)據(jù)量通常大幅超過其承受閾值，計算需求也隨之增加.現(xiàn)代化信息技術(shù)蓬勃發(fā)展使記錄和數(shù)據(jù)收集變得越來越細粒度和多維度[1-2]，導(dǎo)致海量數(shù)據(jù)的數(shù)據(jù)處理和知識發(fā)現(xiàn)一直是數(shù)據(jù)挖掘領(lǐng)域的研究熱點.大數(shù)據(jù)可定義為超出傳統(tǒng)系統(tǒng)存儲和處理能力的數(shù)據(jù)，包含巨大的潛在價值.然而，這些龐大而復(fù)雜的數(shù)據(jù)集往往伴隨著顯著的數(shù)據(jù)冗余[3-4]，浪費存儲空間.這種大規(guī)模數(shù)據(jù)集的產(chǎn)生也帶來數(shù)據(jù)存儲、計算效率和計算精度等諸多挑戰(zhàn).

粗糙集理論(Rough Set Theory, RST)[5]是一種常用的分析決策不確定性信息的數(shù)學(xué)工具.粗糙集可通過不可辨識關(guān)系劃分不確定性知識概念，得到不同等價關(guān)系下的等價類集合，從而建立一個近似空間.RST現(xiàn)已成功應(yīng)用于圖像處理[6]、聚類分析[7]、模式識別[8]、機器學(xué)習(xí)[9-10]、特征選擇[11]、決策支持和數(shù)據(jù)挖掘[12-14]等多個研究領(lǐng)域.屬性約簡是粗糙集理論中的一個重要概念，成為近年來備受關(guān)注的一種重要的數(shù)據(jù)預(yù)處理工具，在知識發(fā)現(xiàn)、專家系統(tǒng)、決策支持、機器學(xué)習(xí)等研究領(lǐng)域中，可提高識別精度，發(fā)現(xiàn)潛在有用的知識.

經(jīng)典的屬性約簡算法，如基于正區(qū)域的屬性約簡算法[15-16]、基于信息熵的屬性約簡算法[17-18]、基于差別矩陣的屬性約簡算法[19-20]等，是一次性將小數(shù)據(jù)集裝入單機主存中進行約簡計算，因此無法處理海量數(shù)據(jù).隨著Hadoop[21]、MapReduce[22]等大數(shù)據(jù)技術(shù)的發(fā)展，使利用大數(shù)據(jù)技術(shù)進行并行屬性約簡的研究成為人們關(guān)注的焦點.為了解決串行算法的局限性，Zhang等[23]在MapReduce基礎(chǔ)上提出PLAR(Parall Large-Scale Attribute Reduction)，得到與傳統(tǒng)方法相同的屬性約簡.Raza等[24]提出基于正區(qū)域的并行屬性約簡算法，可并行搜索所有正區(qū)域，大幅提升計算效率.Qian等[25-26]深入研究MapReduce框架中的屬性約簡過程，在并行階段計算等價類，經(jīng)過shuffle過程后，再通過約簡聚合相同鍵值的等價類，提出基于MapReduce的并行知識約簡算法.

上述算法表明，在MapReduce上并行化傳統(tǒng)的屬性約簡算法，實現(xiàn)海量數(shù)據(jù)的屬性約簡是可行的.但是，由于MapReduce和傳統(tǒng)約簡算法存在一些固有的局限性，所以需要進一步改進.近年來，對于解決靜態(tài)決策系統(tǒng)[27-28]的屬性約簡問題，學(xué)者們提出很多非增量約簡算法.然而，如今許多決策系統(tǒng)的對象集是動態(tài)變化的，決策系統(tǒng)可能也會隨著時間變化而變化.由于對象集是動態(tài)變化的，為了得到新的約簡，需要對決策系統(tǒng)進行重新計算，耗費大量的計算時間.

顯然，這些屬性約簡算法在處理動態(tài)決策系統(tǒng)時效率低下，如何更新約簡是提高數(shù)據(jù)預(yù)處理效率的關(guān)鍵問題.增量學(xué)習(xí)是一種利用原有決策系統(tǒng)的結(jié)果以提高知識發(fā)現(xiàn)效率的有效方法.針對不同情形，學(xué)者們提出許多增量算法，用于處理動態(tài)數(shù)據(jù).對于對象集不斷變化的動態(tài)不完備決策表，Shu等[29]提出通過更新正區(qū)域以獲取約簡的增量方法.Liu等[30]提出通過構(gòu)造3個新矩陣(支持矩陣、精度矩陣和覆蓋矩陣)以獲取屬性約簡的增量方法.通過計算更新后的知識粒度，Jing等[31]提出相應(yīng)的增量式屬性約簡算法.錢進等[32]根據(jù)屬性集的可辨識性和不可辨識性，給出可辨識對象對和不可辨識對象對的定義和相關(guān)性質(zhì)，結(jié)合MapReduce技術(shù)，設(shè)計適合大規(guī)模數(shù)據(jù)集的并行計算等價類的算法.Liang等[33]系統(tǒng)研究添加到?jīng)Q策表中一組對象的熵的性質(zhì)，并提出有效的增量屬性約簡算法.

顯然，上述方法主要側(cè)重于更新近似的角度進行約簡，對大規(guī)模決策系統(tǒng)的簡化是低效的.因此本文深入研究Spark并行技術(shù)，分析現(xiàn)有增量式約簡算法，同時融合Chen等[34]提出屬性組的概念與二叉樹的機制，結(jié)合Spark并行框架，設(shè)計增量式屬性約簡算法.首先，從屬性組概念入手，引入二叉樹機制尋找約簡，將所有條件屬性通過聚類劃分為多棵屬性樹.再在每輪屬性樹分支中挑選合適屬性樹進行屬性評估，并在計算過程中加入分支閾值系數(shù)α，避免冗余計算，有效減少屬性評估數(shù)量，提高屬性約簡效率和精度.同時當多個增量對象加入決策系統(tǒng)時，可利用增量機制更新約簡，提出基于屬性樹的增量式屬性約簡算法(Incremental Dynamic Attribute Re-duction Algorithm Based on Attribute Tree， IARAT).在上述基礎(chǔ)上，結(jié)合Spark并行技術(shù)，并行化數(shù)據(jù)處理，加快搜索效率，利用Spark框架進行經(jīng)典屬性約簡算法并行化優(yōu)勢，提出基于屬性樹的并行化增量式動態(tài)屬性約簡算法(Parallel IARAT， PIARAT).在多個數(shù)據(jù)集上的實驗表明，PIARAT在保持分類性能的同時，提高動態(tài)變化數(shù)據(jù)集約簡的搜索效率，具有較好的性能優(yōu)勢.

1 相關(guān)知識

1.1 粗糙集

定義1[5]給定決策表S=〈U,C∪D,V,f〉，對于每個屬性子集R?A，定義不可分辨關(guān)系：

IND(R)={(x,y)∈U×U|?a∈R,f(x,a)=f(y,a)}.

關(guān)系IND(R)構(gòu)成U的一個劃分，表示為U/IND(R)，簡記為U/R.U/R中的任何元素

[x]R={y|?a∈R,f(x,a)=f(y,a)}

稱為等價類.不失一般性，假設(shè)決策表S僅有一個決策屬性D=syggg00，其決策屬性值映射為1,2,…,k，由D導(dǎo)出的U上的劃分為U/D={Z1,Z2,…,Zk}，其中

Zi={x∈U|f(x,D)=i},i=1,2,…,k.

不可分辨關(guān)系是一種等價關(guān)系.

定義2[35]給定決策表S=〈U,C∪D,V,f〉，對于每個子集X?U和不可分辨關(guān)系R，X的下近似集與上近似集分別可由R定義如下：

1.2 知識粒度

定義3[28]給定決策表S=〈U,C∪D,V,f〉，條件屬性集C對于U的劃分為

U/C={X1,X2,…,Xn′}，

n′為劃分后的子集數(shù)量，則條件屬性集C的知識粒度定義為

屬性集(C∪D)對于U的劃分為

U/(C∪D)={Y1,Y2,…,Yh}，

h為劃分后的子集數(shù)量，則條件屬性集C相對于決策屬性集D的知識粒度定義為

GPU(D|C)=GPU(C)-GPU(C∪D).

定義4[28]給定決策表S=〈U,C∪D,V,f〉，條件屬性集C對于U的劃分為

U/C={X1,X2,…,Xn′}，

n′為劃分后的子集數(shù)量，屬性集B?C，?a∈B，屬性a在B中相對于決策屬性集D的內(nèi)部屬性重要度定義為

若?a∈(C-B)，則屬性a在(C-B)中相對于決策屬性集D的外部屬性重要度定義為

定義5[28]給定決策表S=〈U,C∪D,V,f〉，屬性集B?C.當且僅當滿足

1)GPU(D|B)=GPU(D|C),

2)?a∈B,GPU(D|(B-a))≠GPU(D|B),

則稱B為決策表S的相對約簡.條件1)表示約簡后的屬性集B與所有條件屬性集C關(guān)于D的知識粒度相等，表現(xiàn)的意義是屬性集B與條件屬性集C對數(shù)據(jù)樣本U的分類能力相同，即找到的約簡集是合格的.條件2)表示若從B中剔除某個屬性之后，會降低分類能力，這意味著B中無任何冗余的屬性.這兩個條件共同作為屬性約簡的正確性標準.

定理1[25]給定決策表S=〈U,C∪D,V,f〉，令A(yù)?C，U/A表示為{A1,A2,…,Ar}，U被劃分成多個數(shù)據(jù)子集{U1,U2,…,UL}，

Ui/A={Ai1,Ai2,…,Air}，

則最終約簡集

證明如果關(guān)于A的任意兩個對象相同，可將它們合并為一個等價類.不同數(shù)據(jù)拆分之間的相同等價類可組合為更大的等價類.因此，對于

U/A={A1,A2,…,Ar},Ui/A={Ai1,Ai2,…,Air}，

可得

定理2[25]并行屬性約簡算法得到的約簡與相應(yīng)的串行方法得到的約簡相同.

證明傳統(tǒng)的屬性約簡算法主要分為4個基本步驟:子集生成、子集評估、停止標準、結(jié)果驗證.并行算法和串行算法之間的唯一區(qū)別是屬性子集評估過程，主要包括等價類和屬性重要度的計算.

1)根據(jù)定理1，

這意味著串行算法中的等價類與相應(yīng)并行算法中的等價類相同.

2)由于串行算法中的等價類與相應(yīng)并行算法中的等價類相同，則它們計算所得的屬性重要度也相同.

因此，并行算法得到的約簡與相應(yīng)的串行算法得到的約簡相同.

1.3 Spark框架

Hadoop MapReduce[36]是一個分布式計算框架，允許開發(fā)人員使用簡單的代碼在巨大的集群上實現(xiàn)大規(guī)模的數(shù)據(jù)計算.但由于磁盤I/O和網(wǎng)絡(luò)傳輸過多，不適合迭代計算和在線計算任務(wù).為了克服MapReduce的不足，學(xué)者們提出新一代集群計算引擎Spark.Apache Spark[37]是在MapReduce基礎(chǔ)上改進的分布式計算框架，具有快速、易用、通用、兼容等優(yōu)點.

Spark的運行流程主要分為如下步驟.

1)首先啟動 SparkContext，并向Cluster Manager注冊，申請Executor資源，Cluster Manager為 Execu-

tor分配資源并啟動進程.

2)SparkContext構(gòu)建有向無環(huán)圖(Directed Acyclic Graph， DAG)，將DAG圖分解成多個階段，并發(fā)送給Task Scheduler.

3)Executor向SparkContext申請Task，SparkCon-

text將應(yīng)用程序代碼發(fā)放給Executor.

4)Task在Executor上運行完畢后，把執(zhí)行結(jié)果反饋給Task Scheduler和DAG Scheduler，并寫入數(shù)據(jù).最后，SparkContext注銷并釋放所有資源.

彈性分布式數(shù)據(jù)集(Resilient Distributed Data-

set, RDD)是Spark中基本的數(shù)據(jù)抽象.在代碼中是一個抽象類，表示一個彈性、不可變、可分區(qū)、里面的元素可并行計算的集合.RDD表示只讀的分區(qū)的數(shù)據(jù)集，改動RDD，只能通過RDD的轉(zhuǎn)換操作，然后得到新的RDD，并不會對原RDD有任何的影響.

2 并行化增量式動態(tài)屬性約簡算法

本文分析現(xiàn)有增量式約簡算法，同時融合屬性組[34]的概念與二叉樹的概念，并結(jié)合Spark并行框架，設(shè)計基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT).首先，對原始數(shù)據(jù)進行預(yù)處理操作，滿足算法的輸入要求，然后，提出基于屬性樹的增量式屬性約簡算法(IARAT)，刪除冗余屬性，提出核心屬性，最后，將IARAT結(jié)合Spark并行機制，提出PIARAT，可有效加快動態(tài)屬性約簡的過程.

2.1 原始數(shù)據(jù)并行預(yù)處理算法

本文改進傳統(tǒng)的并行數(shù)據(jù)預(yù)處理算法，使其更滿足后續(xù)算法的數(shù)據(jù)輸入要求，提出原始數(shù)據(jù)并行預(yù)處理算法，處理原始數(shù)據(jù)集,具體流程圖如圖1所示.具體算法步驟如下所示.

圖1 原始數(shù)據(jù)并行預(yù)處理算法流程圖

算法1原始數(shù)據(jù)并行預(yù)處理算法

輸入原始決策表S_raw

輸出處理后的決策表S

step 1 在每個子節(jié)點slavei上讀取原始決策表，刪除其中含有缺失屬性值的樣本數(shù)據(jù).

step 2 調(diào)用Spark計算引擎中的mapPartitions算子，將刪除后的數(shù)據(jù)對象轉(zhuǎn)換為鍵值對RDD數(shù)據(jù)集合.

step 3 調(diào)用Spark計算引擎中的mapValues算子，對RDD數(shù)據(jù)集中的value部分進行step 4的操作，消除決策表中重復(fù)樣本和不一致部分.

step 4

/*存在2個數(shù)據(jù)樣本的key值相同時*/

Ifs1.key=s2.key, then

Ifs1.value=s2.value

Removes2；

Else

Removes2；

s1.value←valueMAX+1；

End

End

step 5 調(diào)用Spark計算引擎中的sortByKey算子,并對數(shù)據(jù)按屬性值進行由小到大的排序，方便后續(xù)計算.

step 6 返回處理后的決策表S.

算法1的執(zhí)行過程具體如下.首先，由于原始數(shù)據(jù)集中包含許多無法參與計算的含有缺失值的數(shù)據(jù)，而包含缺失值的數(shù)據(jù)會對后續(xù)約簡計算產(chǎn)生影響，需要刪除此類缺失值數(shù)據(jù).然后，將數(shù)據(jù)集轉(zhuǎn)化為所有條件屬性為key值，決策屬性為value值的k-v鍵值對.遍歷所有樣本，對于key和value相同的重復(fù)數(shù)據(jù)樣本，選擇刪除其一；而對于key相同、value不同的一對樣本(決策表不一致部分)，刪除key值，并將后者的value值修改為決策表中最大value值加1.最后，對整個數(shù)據(jù)子集按屬性值進行由小到大的sort排序，方便后續(xù)計算.

2.2 基于屬性樹的增量式屬性約簡算法

如今許多決策系統(tǒng)是隨著時間而動態(tài)變化的，為了得到新的約簡，需要重新對決策系統(tǒng)進行約簡計算，耗費大量時間.為了解決該問題，本文從屬性組的概念入手，引入二叉樹的機制，設(shè)計搜索策略尋找約簡，并且借助基于知識粒度的增量約簡算法[31]，將知識粒度加入迭代停止準則中，提出基于屬性樹的增量式屬性約簡算法(IARAT)，具體算法步驟如下所示.

算法2IARAT

輸入原始樣本數(shù)據(jù)U，增量樣本數(shù)據(jù)U′，

原約簡集B，分支閾值αmax

輸出約簡子集R

R←B,K←1;

計算知識粒度GPU′(D|R)和GPU′(D|C);

IfGPU′(D|R)=GPU′(D|C), then

ReturnR

End

ClusterCinto{C1,C2,…,CN};

/*C聚類成N個屬性樹根結(jié)點*/

WhileGPU′(D|R)≠GPU′(D|C) andK<αmax:

For eachtreei:

treei.right.data←treei.data∩R;

/*存在原約簡屬性,置于右節(jié)點*/

treei.left.data←treei.data-treei.right.data；

/*剩下的屬性置于左節(jié)點*/

For each attributecbeing evaluated：

/*評估無兄弟結(jié)點屬性樹*/

Ifc是核心屬性 then

treei.right.data←c；

R←(R∪c)；

treei.left.data←treei.data-c；

Break

Else

C←(C-c)；

End

End

End

For eachtreei:

Iftreei.left≠? then

treei=treei.left;

Else

remove the tree;

/*移除該樹*/

K=K+1;

End

End

End

ReturnR

IARAT首先需要對決策表進行預(yù)先判斷：加入增量數(shù)據(jù)集后是否需要進一步的約簡計算.若在增量數(shù)據(jù)集上，決策屬性D分別關(guān)于原約簡子集R與條件屬性集C的知識粒度相等(GPU′(D|R)和GPU′(D|C))，即在增量數(shù)據(jù)集上，約簡子集R依然可保持與條件屬性集C相同的分類能力，可知增量數(shù)據(jù)集的加入未影響原約簡結(jié)果，無需進一步計算；若不相等，需要進一步計算，得到新的約簡.根據(jù)相應(yīng)聚類算法，將所有條件屬性劃分為多個屬性樹根結(jié)點并進行分支操作，在進行每輪的屬性評估過程中，跳過與約簡集相關(guān)性較高的屬性樹，對剩下的屬性樹加以評估，同時根據(jù)評估結(jié)果的不同，進行不同子結(jié)點的分支.在計算過程中引入分支系數(shù)α并設(shè)定閾值，方便跳出循環(huán)，避免冗余計算和陷入死循環(huán).

屬性樹結(jié)構(gòu)如下.根節(jié)點包含聚類算法劃分的條件屬性簇，在每輪屬性樹分支中，將核心屬性置于樹的右子結(jié)點，其余部分劃分為左子結(jié)點，在下次分支中，根據(jù)相應(yīng)策略對左子結(jié)點進行再劃分.屬性樹的結(jié)構(gòu)及分支策略如圖2和圖3所示.

圖2 單棵屬性樹結(jié)構(gòu)

(a)單棵屬性樹

在屬性樹的初始判別階段，通過增量機制減少屬性評估數(shù)量，提高屬性約簡的效率和精度，當多個增量對象加入決策系統(tǒng)時，可利用增量機制更新約簡.在屬性評估階段，采用Yin等[38]設(shè)計的核心屬性約簡算法代替?zhèn)鹘y(tǒng)的屬性重要度約簡算法，不僅在計算效率上擁有優(yōu)勢，而且避免二次循環(huán)評估，提高計算效率.該算法的優(yōu)化策略每次只判斷一個屬性是否為核心屬性，避免時間復(fù)雜度較高的正區(qū)域計算，減少獲取約簡子集所需的時間，時間復(fù)雜度僅為|C|.

核心屬性約簡算法機制如下.在決策表S=〈U,C∪D,V,f〉中，對于某條件屬性ci，若刪除ci，存在2個數(shù)據(jù)樣本x、y的條件屬性值(即C-ci)相等，而決策屬性值不相等，則認定屬性ci為核心屬性，否則，ci不是核心屬性.

屬性樹分支策略如下.在預(yù)先判斷后得知決策屬性D分別關(guān)于原約簡子集R與條件屬性集C的知識粒度不相等，說明增量數(shù)據(jù)集的加入影響原約簡結(jié)果，原數(shù)據(jù)的約簡集已無法對現(xiàn)有增量數(shù)據(jù)保持有效的分類性能，所以需要進一步進行如下計算.

1)對加入的增量數(shù)據(jù)集S′的條件屬性C執(zhí)行相應(yīng)的聚類算法.根據(jù)屬性與屬性之間相關(guān)性及屬性與屬性簇之間的相關(guān)性，將所有條件屬性集C劃分成多個屬性簇群{C1,C2,…,CN}，目的是聚集具有較大依賴關(guān)系(冗余度高)的屬性，具有高相關(guān)性的每個屬性子集轉(zhuǎn)換成一棵屬性樹treei的根節(jié)點.

2)進行逐棵屬性樹treei的分支.為了避免重復(fù)計算，利用原約簡集B，參與到分支過程中，把多棵屬性樹的根節(jié)點與原約簡集B中相交的部分置于右子結(jié)點treei.right.這一步是為了找出與原約簡集B存在相關(guān)性的屬性樹，在下輪分支時跳過該樹的屬性評估，其余部分劃分為左子結(jié)點treei.left，后續(xù)的分支計算在該結(jié)點上進行.同時設(shè)置分支系數(shù)α并初始化為1，在每次分支之后進行遞增，當達到最大閾值時跳出循環(huán)，閾值即屬性樹的最大分支深度.基于最壞的打算，為了避免冗余計算和陷入死循環(huán)，一般設(shè)置為屬性樹根結(jié)點中最大的屬性數(shù)量.

3)在每次分支過程中運用核心屬性約簡算法逐個評估無兄弟結(jié)點屬性樹(即評估本輪與約簡集相關(guān)性較低的屬性樹).如果不是核心屬性，直接從節(jié)點中刪除，不再參與后續(xù)計算，繼續(xù)評估下一屬性，直到找出該屬性樹中第一個核心屬性；如果是核心屬性，加入約簡集R并停止本棵樹余下屬性的評估.

直到所有屬性樹評估完成，該輪分支結(jié)束.

4)屬性樹與約簡集的相關(guān)性度量取決于上一輪中約簡集是否加入某棵屬性樹中的屬性.每棵樹都是由聚類算法生成的屬性簇群，屬性之間存在較高相關(guān)性，若上一輪評估過程中添加某棵樹的屬性進入約簡集，因為其它屬性樹中存在核心屬性的可能性較高，所以可跳過對該樹的屬性評估，縮小搜索空間，提升檢索效率.

5)在分支過程中，如果遇到某棵樹左節(jié)點為空，說明該屬性樹分支完成，所有屬性樹全部分支完成后，輸出新約簡集.

2.3 基于屬性樹的并行化增量式動態(tài)屬性約簡

算法

本節(jié)首先引入IARAT，在此基礎(chǔ)上，融入Spark并行機制，實現(xiàn)分布式的內(nèi)存計算任務(wù)，在不犧牲性能的情況下找出不同數(shù)據(jù)子集中的冗余屬性并行化數(shù)據(jù)處理，降低數(shù)據(jù)規(guī)模和計算時間，提高效率.由此，設(shè)計基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT)，流程圖如圖4所示.PIARAT具體步驟如下所示.

圖4 PIARAT流程圖

算法3PIARAT

輸入原始數(shù)據(jù)集S_raw

輸出約簡子集R

step 1 將原始數(shù)據(jù)集S_raw存入HDFS文件系統(tǒng).

step 2 在主節(jié)點master中讀取文件系統(tǒng)中的數(shù)據(jù)集.

step 3 將數(shù)據(jù)集S_raw以1∶1的比例劃分成原決策表S和增量決策表S′.

step 4 調(diào)用算法1對增量決策表S′進行并行預(yù)處理操作.

step 5 對原決策表S進行屬性約簡計算，得到原約簡集B.

step 6 將原決策表S和原約簡集B發(fā)送到所有子節(jié)點slavei上.

step 7 將增量數(shù)據(jù)集切分成n份，分別發(fā)送到n個工作節(jié)點上.

step 8 在所有子節(jié)點slavei上調(diào)用算法2進行基于屬性樹的增量式屬性約簡，返回，得到各約簡子集{R1,R2,…,Rn}.

step 9 將各個子節(jié)點slavei上得到的約簡子集{R1,R2,…,Rn}發(fā)送到主節(jié)點master上.

step 10 對約簡子集Bi進行并集操作，得到最終約簡集R.

step 11 返回R.

PIARAT首先將搜集的海量大規(guī)模數(shù)據(jù)集存入HDFS(Hadoop Distributed File System)文件系統(tǒng)[39].再按照比例將數(shù)據(jù)集劃分為原始數(shù)據(jù)集和增量數(shù)據(jù)集，PIARAT主要側(cè)重于增量數(shù)據(jù)集上的并行屬性約簡，所以主要對增量數(shù)據(jù)集進行約簡計算.然后，對增量數(shù)據(jù)集進行二次劃分，劃分成多個數(shù)據(jù)子集，并分發(fā)到對應(yīng)的多個工作節(jié)點上，采用基于屬性樹的增量式屬性約簡算法，在各子節(jié)點上并行處理數(shù)據(jù).最后，將處理完成的多個結(jié)果返回主節(jié)點進行最終并集操作，得到最終約簡子集.

2.4 時間復(fù)雜度分析

為了進一度凸顯算法優(yōu)勢，對IARAT和PIARAT進行時間復(fù)雜度分析.給定決策表S=〈U,C∪D,V,f〉，設(shè)定U表示原始數(shù)據(jù)集樣本，U′表示增量數(shù)據(jù)集樣本，C表示所有條件屬性并聚集成k棵屬性樹，k?C，最終的約簡子集為R，并設(shè)置n個并行計算節(jié)點.

PIARAT在算法的初始判別階段，需要計算知識粒度并判斷是否需要進一步約簡，時間復(fù)雜度為O(|C||U′|2).在step 8的屬性遍歷過程中，傳統(tǒng)算法是逐個計算屬性的重要性，導(dǎo)致大部分屬性的重復(fù)計算，時間復(fù)雜度為

而PIARAT的時間復(fù)雜度僅為O(|C|)，有效提升計算效率.

最后， IARAT和PIARAT的時間復(fù)雜度分別為

由此可得出，PIARAT的時間復(fù)雜度遠低于傳統(tǒng)串行算法，具有良好的加速性能.

3 實驗及結(jié)果分析

本文采用的實驗平臺為PC(Intel(R) Core(TM) i5-10400H CPU@2.30 GHz，RAM 16 GB)，Windows 10家庭中文版操作系統(tǒng)，開發(fā)工具為JetBrains PyCharm，使用Python語言實現(xiàn)實驗中相關(guān)算法.

在Windows 10系統(tǒng)上搭建MapReduce Hadoop-2.7.1和Spark-3.0.0-preview的模擬環(huán)境平臺，集群運行模式采用本地模式“l(fā)ocal”.

在實驗過程中，通過Spark框架中的Python API進行編寫，將本地模式中的參數(shù)設(shè)置為local[*].

3.1 實驗數(shù)據(jù)集

本文從UCI機器學(xué)習(xí)知識庫上選擇8個數(shù)據(jù)集作為實驗數(shù)據(jù)集，分為5個小型數(shù)據(jù)集和3個較大數(shù)據(jù)集.所有數(shù)據(jù)集的詳細信息如表1所示.

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

小型數(shù)據(jù)集分別為Qsar、Mushroom、Nursery、Shuttle、Letter數(shù)據(jù)集，樣本量由幾千至幾萬不等.較大數(shù)據(jù)集為Poker Hand、KDD Cup、HIGGS數(shù)據(jù)集，擁有幾十個屬性，但包含百萬級的樣本量.

3.2 實驗設(shè)置

首先對數(shù)據(jù)集進行原始數(shù)據(jù)和增量數(shù)據(jù)的劃分，從表1中的每個決策系統(tǒng)中選取50%初始的數(shù)據(jù)樣本量作為原始數(shù)據(jù)集，然后從剩余的50%數(shù)據(jù)樣本量中分別選取20%，40%，60%，80%，100%的數(shù)據(jù)作為增量數(shù)據(jù)集填充.在原始決策系統(tǒng)中添加增量對象集時，采用不同的增量約簡算法對各決策系統(tǒng)的約簡進行更新并進行對比討論.

在屬性聚類階段，采用的聚類算法為K-means，對數(shù)據(jù)集采用肘部法則[40]分別確定K值.肘部法則使用的聚類評價指標為：數(shù)據(jù)集上所有樣本點到其簇中心的距離之和的平方.肘部法則會畫出不同值的成本函數(shù).隨著值的增大，每類包含的樣本數(shù)會減少，于是樣本離其重心會更近，平均畸變程度會更小.而分支系數(shù)α的引入是為了引導(dǎo)算法達到最大閾值時跳出循環(huán)，避免冗余計算和陷入死循環(huán).閾值的確定也就是屬性樹的最大分支深度，基于最壞的打算，一般設(shè)置為屬性樹根結(jié)點中最大的屬性數(shù)量.K值和分支系數(shù)α的選取如表2所示.

表2 參數(shù)設(shè)置

本文采用粗糙集中兩種常用指標評估尋找的約簡子集質(zhì)量，分別為近似分類質(zhì)量(Approximate Classified Quality， AQ)和近似分類精度(Approximate Classified Precision, AP)，并通過運行時間和分類準確率評估算法的加速性能和分類性能.

定義6[41]給定決策表S=〈U,C∪D,V,f〉，決策屬性D對于U的劃分為U/D={Z1,Z2,…,Zm′}，m′為劃分后的子集數(shù)量,則條件屬性集C關(guān)于決策屬性集D的近似分類精度為：

定義7[41]給定決策表S=〈U,C∪D,V,f〉，條件屬性集C關(guān)于決策屬性集D的近似分類質(zhì)量為：

如果約簡子集的AQ值和AP值與原決策系統(tǒng)相同，認為該約簡子集與原決策系統(tǒng)具有相同的區(qū)分能力.

3.3 實驗結(jié)果

3.3.1 計算時間對比

為了驗證IARAT在運行時間和分類精度上的高效性和有效性，在表1所示的前5個不同的小型數(shù)據(jù)集上對比算法的計算時間.實驗中選取的對比算法分別為IARC(An Incremental Algorithm for Redu-ct Computation Based on Knowledge Granularity)[31]、GIARC(A Group Incremental Algorithm for Reduct Computation)[33]、文獻[34]算法(Bucket and Attri-bute Group for Obtaining Reduct)、IARM(Incremen-

tal Attribute Reduction Algorithm)[42]和文獻[43]算法.各算法在5個數(shù)據(jù)集上的運行時間對比如圖5所示.由圖可見，隨著動態(tài)數(shù)據(jù)集的增加，各算法的運行時間都在增加，而IARAT的運行時間在各數(shù)據(jù)集上增幅均最小，在一定范圍內(nèi)隨著增量數(shù)據(jù)占比的增大，IARAT的運行時間也在可控范圍內(nèi)平穩(wěn)增加.這表明IARAT可有效提高屬性約簡的計算效率，減少運行時間.

(a)Qsar

3.3.2 有效性對比

為了進一步驗證IARAT的有效性，說明其可在不損失分類性能的情況下有效提高搜索速度并找到可行的屬性約簡,進行如下對比實驗.

本文設(shè)置數(shù)據(jù)集上50%的樣本為增量數(shù)據(jù)，并且通過CART(Classification and Regression Tree)和10倍交叉驗證的方式計算分類準確率.將樣本劃分為10個不相交的樣本組，在第一輪中設(shè)置第一組為測試集，剩下的樣本為訓(xùn)練集，第二輪中設(shè)置第二組為測試集，以此類推.這里的分類準確率表現(xiàn)為：在多種約簡算法分別進行屬性約簡之后，每種算法保留下來的核心屬性集各不相同，此時CART利用不同的核心屬性集對樣本進行分類以計算分類準確率.

分類準確率由CART預(yù)測正確的樣本數(shù)量在全部樣本中的占比決定，計算公式如下：

其中，NCS表示算法預(yù)測正確樣本的數(shù)量，NAS表示所有預(yù)測樣本的總數(shù).

為了更直觀地展示實驗結(jié)果，計算加速比:

其中，Tmax表示運行時間最長的算法耗時，TA表示算法耗時.加速比越高，運行時間越少，效率越高.

各算法在5個數(shù)據(jù)集上的分類準確率和加速比如表3和表4所示.由表可看出，在大多數(shù)情況下，IARAT分類準確率未下降，并且略高于其它算法.由于數(shù)據(jù)集的差異，IARAT的分類準確率在個別情況下略有下降，但在可接受的范圍內(nèi)，這表明該算法可在不犧牲分類準確率的情況下有效減少耗時.由此得到如下結(jié)論：IARAT是有效且高效的.

表3 各算法在5個數(shù)據(jù)集上的分類準確率對比

表4 各算法在5個數(shù)據(jù)集上的加速比對比

3.3.3 加速性能對比

為了更直觀地展現(xiàn)PIARAT在并行屬性約簡方面的加速效果，選取含有百萬數(shù)據(jù)樣本量的Pokerhand、KDD Cup、HIGGS這3個較大型數(shù)據(jù)集進行對比實驗.

IARAT和PIARAT的加速性能對比如表5所示，表中“-”表示IARAT無法運行或運行時間太長.由表可看出，相比IARAT，PIARAT在處理大規(guī)模數(shù)據(jù)集時總體運行時間大幅縮短，對于IARAT無法運行的數(shù)據(jù)集也可在可控的時間內(nèi)計算出約簡結(jié)果，這表明PIARAT具有良好的加速能力.在向決策系統(tǒng)中添加一些對象時，IARAT和PIARAT劃分屬性子集的AP值和AQ值非常接近或相同，表現(xiàn)為1或0.99.這說明，經(jīng)過Spark并行機制加速后的增量算法生成的約簡與原算法生成的約簡具有幾乎相同的分辨能力，即算法3找到的約簡是可行的.

表5 IARAT和PIARAT加速性能對比

3.4 討論與分析

本文在8組UCI數(shù)據(jù)集上進行運行時間、分類性能及加速性能的對比實驗.

由圖5可看出，IARAT的運行時間在不同數(shù)據(jù)集上均小于對比算法，而且在一定范圍內(nèi)隨著增量數(shù)據(jù)規(guī)模的增大，運行時間也在可控范圍內(nèi)平穩(wěn)增加.例如，在Qsar數(shù)據(jù)集上，IARAT和GIRAC在增量數(shù)據(jù)不斷增大的過程中運行時間始終保持平穩(wěn)，而IARC和IARM在后半段運行時間漲幅均存在明顯變大趨勢.而在樣本數(shù)最大的Letter數(shù)據(jù)集上，IARAT的計算優(yōu)勢更明顯，這主要是因為在屬性樹每輪分支過程中只需要評估少量的候選屬性(取決于屬性樹的數(shù)量)，由于搜索空間的減小，可縮短相應(yīng)的運行時間.同時，使用核心屬性約簡算法替代傳統(tǒng)約簡算法，避免每輪循環(huán)中非常耗時的屬性重要性的計算過程，進一步縮短運行時間.

由表3和表4可得出，IARAT在縮短運行時間的同時，也保持算法的分類質(zhì)量及分類精度.這樣的結(jié)果表明，IARAT通過構(gòu)建屬性樹并進行分支的策略可在不犧牲分類準確率的情況下有效減少屬性約簡的計算時間.然而如下問題值得考慮：1)在屬性聚類階段，選擇K-means，不同聚類算法的選取是否會影響分類精度；2)在IARAT中，對于不同的數(shù)據(jù)集，并未相應(yīng)調(diào)整屬性樹的數(shù)量，如何找到最優(yōu)的聚類中心數(shù)量以達到最低的耗時.這些問題依然值得繼續(xù)研究.

由表5可看出，相比IARAT，PIARAT在處理大規(guī)模數(shù)據(jù)集時的總體運行時間大幅縮短，IARAT無法運行或運行時間太長的數(shù)據(jù)也可進行有效約簡計算，因此，通過Spark并行計算機制可有效提高算法2的計算效率，減少運行時間.這主要是因為Spark計算引擎可對屬性約簡算法進行并行化，以分布式計算的機制替代傳統(tǒng)的串行機制，由此實現(xiàn)海量數(shù)據(jù)的并行約簡計算.但是，在并行處理方面，本文算法的多棵樹分支策略和多節(jié)點并行機制的深度契合值得進一步優(yōu)化，對于不同的數(shù)據(jù)集(不同樣本數(shù)量、不同屬性數(shù)量)，如何進行數(shù)據(jù)集的最優(yōu)劃分和子集的最優(yōu)分配將是今后工作的重點.

4 結(jié) 束 語

本文針對傳統(tǒng)屬性約簡算法在處理大規(guī)模數(shù)據(jù)集時時間復(fù)雜度較高、效率較低等問題，從屬性組概念入手，引入二叉樹機制尋找約簡，提出基于屬性樹的增量式屬性約簡算法(IARAT).同時根據(jù)評估結(jié)果的不同進行不同子結(jié)點分支，在計算過程中加入分支系數(shù)，提高屬性約簡的效率和精度.同時結(jié)合Spark并行技術(shù)，利用Spark框架在經(jīng)典屬性約簡算法上的并行優(yōu)勢，提出基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT).實驗表明本文算法在處理大規(guī)模動態(tài)數(shù)據(jù)集時是有效且高效的.今后工作重點是面對屬性增加和屬性值變化的增量問題時，如何更新屬性約簡，在屬性聚類階段選擇更好的聚類算法及尋找最優(yōu)聚類中心數(shù)量，進一步降低時間損耗，并對本文算法的多棵樹分支策略和多節(jié)點并行機制的深度契合進行進一步優(yōu)化.