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

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

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

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

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

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

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

1 相關(guān)知識(shí)

1.1 粗糙集

定義1[5]給定決策表S=〈U,C∪D,V,f〉，對(duì)于每個(gè)屬性子集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的一個(gè)劃分，表示為U/IND(R)，簡(jiǎn)記為U/R.U/R中的任何元素

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

稱為等價(jià)類.不失一般性，假設(shè)決策表S僅有一個(gè)決策屬性D=5pzjzfl，其決策屬性值映射為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)系是一種等價(jià)關(guān)系.

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

1.2 知識(shí)粒度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

則最終約簡(jiǎn)集

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

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

可得

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

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

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

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

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

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

1.3 Spark框架

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

Spark的運(yùn)行流程主要分為如下步驟.

1)首先啟動(dòng) SparkContext，并向Cluster Manager注冊(cè)，申請(qǐng)Executor資源，Cluster Manager為 Execu-

tor分配資源并啟動(dòng)進(jìn)程.

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

3)Executor向SparkContext申請(qǐng)Task，SparkCon-

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

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

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

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

2 并行化增量式動(dòng)態(tài)屬性約簡(jiǎn)算法

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

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

本文改進(jìn)傳統(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 在每個(gè)子節(jié)點(diǎn)slavei上讀取原始決策表，刪除其中含有缺失屬性值的樣本數(shù)據(jù).

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

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

step 4

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

Ifs1.key=s2.key, then

Ifs1.value=s2.value

Removes2；

Else

Removes2；

s1.value←valueMAX+1；

End

End

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

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

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

2.2 基于屬性樹的增量式屬性約簡(jiǎn)算法

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

算法2IARAT

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

原約簡(jiǎn)集B，分支閾值αmax

輸出約簡(jiǎn)子集R

R←B,K←1;

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

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

ReturnR

End

ClusterCinto{C1,C2,…,CN};

/*C聚類成N個(gè)屬性樹根結(jié)點(diǎn)*/

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

For eachtreei:

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

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

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

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

For each attributecbeing evaluated：

/*評(píng)估無(wú)兄弟結(jié)點(diǎn)屬性樹*/

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

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

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

(a)單棵屬性樹

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

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

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

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

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

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

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

4)屬性樹與約簡(jiǎn)集的相關(guān)性度量取決于上一輪中約簡(jiǎn)集是否加入某棵屬性樹中的屬性.每棵樹都是由聚類算法生成的屬性簇群，屬性之間存在較高相關(guān)性，若上一輪評(píng)估過(guò)程中添加某棵樹的屬性進(jìn)入約簡(jiǎn)集，因?yàn)槠渌鼘傩詷渲写嬖诤诵膶傩缘目赡苄暂^高，所以可跳過(guò)對(duì)該樹的屬性評(píng)估，縮小搜索空間，提升檢索效率.

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

2.3 基于屬性樹的并行化增量式動(dòng)態(tài)屬性約簡(jiǎn)

算法

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

圖4 PIARAT流程圖

算法3PIARAT

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

輸出約簡(jiǎn)子集R

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

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

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

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

step 5 對(duì)原決策表S進(jìn)行屬性約簡(jiǎn)計(jì)算，得到原約簡(jiǎn)集B.

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

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

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

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

step 10 對(duì)約簡(jiǎn)子集Bi進(jìn)行并集操作，得到最終約簡(jiǎn)集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ù)集上的并行屬性約簡(jiǎn)，所以主要對(duì)增量數(shù)據(jù)集進(jìn)行約簡(jiǎn)計(jì)算.然后，對(duì)增量數(shù)據(jù)集進(jìn)行二次劃分，劃分成多個(gè)數(shù)據(jù)子集，并分發(fā)到對(duì)應(yīng)的多個(gè)工作節(jié)點(diǎn)上，采用基于屬性樹的增量式屬性約簡(jiǎn)算法，在各子節(jié)點(diǎn)上并行處理數(shù)據(jù).最后，將處理完成的多個(gè)結(jié)果返回主節(jié)點(diǎn)進(jìn)行最終并集操作，得到最終約簡(jiǎn)子集.

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 實(shí)驗(yàn)設(shè)置

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

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

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

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

定義6[41]給定決策表S=〈U,C∪D,V,f〉，決策屬性D對(duì)于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ì)量為：

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

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 計(jì)算時(shí)間對(duì)比

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

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

(a)Qsar

3.3.2 有效性對(duì)比

為了進(jìn)一步驗(yàn)證IARAT的有效性，說(shuō)明其可在不損失分類性能的情況下有效提高搜索速度并找到可行的屬性約簡(jiǎn),進(jìn)行如下對(duì)比實(shí)驗(yàn).

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

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

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

為了更直觀地展示實(shí)驗(yàn)結(jié)果，計(jì)算加速比:

其中，Tmax表示運(yùn)行時(shí)間最長(zhǎng)的算法耗時(shí)，TA表示算法耗時(shí).加速比越高，運(yùn)行時(shí)間越少，效率越高.

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

表3 各算法在5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率對(duì)比

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

3.3.3 加速性能對(duì)比

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

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

表5 IARAT和PIARAT加速性能對(duì)比

3.4 討論與分析

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

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

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

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

4 結(jié) 束 語(yǔ)

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