Spark下的分布式粗糙集屬性約簡(jiǎn)算法

章夏杰，朱敬華，2*，陳 楊

（1.黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱150080；2.黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室，哈爾濱150080）

0 引言

在高速信息化的時(shí)代，由于數(shù)據(jù)集的體積、多樣性和復(fù)雜性都在不斷增加，特征選擇作為從大量無(wú)意義的數(shù)據(jù)中提取有價(jià)值信息的一種重要手段已然成為一個(gè)研究熱點(diǎn)［1-2］。將粗糙集理論［3］應(yīng)用于特征選擇，是一種先進(jìn)又有效的技術(shù)。

找到最小約簡(jiǎn)的最基本解決方案是生成所有可能的約簡(jiǎn)并選擇具有最大依賴度、最小屬性數(shù)的約簡(jiǎn)，這可以通過(guò)從數(shù)據(jù)集構(gòu)建一種可辨別函數(shù)并簡(jiǎn)化來(lái)實(shí)現(xiàn)。顯然，這種解決方案非常昂貴，僅適用于非常小的數(shù)據(jù)集。結(jié)果表明，最小約簡(jiǎn)生成是一個(gè)NP-hard 問(wèn)題，因此目前的粗糙集約簡(jiǎn)算法一般都與爬山式算法或隨機(jī)算法相結(jié)合。

Hu 等［4］提出了一種基于正區(qū)域?qū)傩灾匾缘募s簡(jiǎn)算法。Hu 等［5］利用可分辨矩陣中的啟發(fā)式思想計(jì)算屬性的重要性，并提出了一種啟發(fā)式的約簡(jiǎn)算法?；谡齾^(qū)域和基于條件熵的方法的目的都是選擇一個(gè)最小特征子集，且該子集能最大化描述給定數(shù)據(jù)集中的分類信息。基于可辨矩陣的方法是選擇一個(gè)具有高分辨能力的特征子集，從而保證了約簡(jiǎn)后的數(shù)據(jù)集具有最大的類間可分性。這些方法考慮了最佳候選屬性，試圖找到最小約簡(jiǎn)。

爬山式的粗糙集約簡(jiǎn)方法通常以空集或?qū)傩院藶槠瘘c(diǎn)，采用正向選擇的方式依次從候選集合中添加最重要的屬性直到無(wú)法再添加新的屬性為止，這種方法速度較快，但是在處理存在較多關(guān)聯(lián)屬性的數(shù)據(jù)集時(shí)易陷入局部最優(yōu)解。

因此一些研究者嘗試將隨機(jī)方法與粗糙集屬性約簡(jiǎn)相結(jié)合。Wroblewski［6］嘗試結(jié)合遺傳算法來(lái)搜索最小約簡(jiǎn)并得到了精度較高的約簡(jiǎn)結(jié)果；Jensen等［7］使用另一種隨機(jī)策略——蟻群優(yōu)化算法來(lái)尋找最小屬性約簡(jiǎn)，在速度與精度上有一定的提升；Wang 等［8］使用了一種元啟發(fā)算法——粒子群算法來(lái)尋找最小屬性約簡(jiǎn)，在精度上得到了進(jìn)一步提高。然而該類方法需要大量的迭代計(jì)算，因此在處理大數(shù)據(jù)集時(shí)非常耗時(shí)。

為了在合理時(shí)間內(nèi)得到較高精度的結(jié)果，有必要使用分布式技術(shù)。Spark是一種嶄新的大數(shù)據(jù)并行計(jì)算框架，它基于內(nèi)存計(jì)算，提高了在大數(shù)據(jù)環(huán)境下數(shù)據(jù)處理的實(shí)時(shí)性，同時(shí)保證了高容錯(cuò)性和高可伸縮性，允許用戶將Spark部署在大量廉價(jià)硬件之上，形成集群。與Hadoop 的MapReduce 相比，Spark基于內(nèi)存的運(yùn)算要快100倍以上。

Dagdia 等［9］在2017 年提出了一種基于Spark 平臺(tái)的分布式粗糙集算法SP-RST。該算法通過(guò)將屬性分區(qū)后求得局部約簡(jiǎn)，再將局部約簡(jiǎn)結(jié)果合并的方式有效減少了屬性約簡(jiǎn)所需的時(shí)間。該算法中的分區(qū)數(shù)會(huì)直接影響算法的精度與執(zhí)行速度。我們?cè)趯?shí)驗(yàn)中發(fā)現(xiàn)：增大分區(qū)數(shù)量雖然能提高執(zhí)行速度，但是能夠約簡(jiǎn)掉的冗余屬性將會(huì)越少，導(dǎo)致精度下降；而且該算法在可接受的運(yùn)行時(shí)間內(nèi)，約簡(jiǎn)質(zhì)量較低。

綜上，為了能夠在合理的時(shí)間內(nèi)處理大數(shù)據(jù)集并得到較高精度的結(jié)果，在Spark平臺(tái)上實(shí)現(xiàn)了一種元啟發(fā)式的分布式粗糙集屬性約簡(jiǎn)算法SP-WOFRST，該算法結(jié)合了筆者新提出的一種依賴計(jì)算方法——快速依賴計(jì)算（Fast Dependence Computing，F(xiàn)DC）來(lái)計(jì)算屬性子集的依賴度，并通過(guò)改進(jìn)的鯨魚(yú)優(yōu)化算法（Whale Optimization Algorithm，WOA）來(lái)尋找最優(yōu)屬性子集。最后在兩組人工合成的大數(shù)據(jù)集上對(duì)本文算法的性能進(jìn)行了驗(yàn)證，結(jié)果表明本文算法相比SP-RST 算法在精度和速度上都有明顯的性能提升。

1 粗糙集與依賴度計(jì)算

1.1 粗糙集

定義1不可分辨關(guān)系［10］。給定決策表S=(U，A，V，f)，對(duì)于每個(gè)屬性子集R ?A，定義了一個(gè)不可分辨關(guān)系IND(R)，即顯然，不可分辨關(guān)系是一種等價(jià)關(guān)系。

定義2上下近似集［10］。給定決策表S=(U，A，V，f)，對(duì)于每個(gè)子集X ?U 和一個(gè)不可分辨關(guān)系R ∈ind(K)，定義X 的R上下近似集分別為：

定義3相對(duì)正區(qū)域［10］。設(shè)P 與Q 為U 上的兩個(gè)等價(jià)關(guān)系，Q的P正域POSp(Q)，定義為

定義4k 度依賴。設(shè)P 與Q 為U 上的兩個(gè)等價(jià)關(guān)系，若依賴度，則稱Q 是k(0 ≤k ≤1)度依賴于P的。

1.2 依賴度計(jì)算

傳統(tǒng)計(jì)算依賴度的方法分為三步：第一步計(jì)算以決策屬性構(gòu)建的等價(jià)類U/D，第二步計(jì)算以條件屬性構(gòu)建的等價(jià)類U/C，第三步通過(guò)計(jì)算相對(duì)正域求出依賴度。下面以表1為例加以說(shuō)明。

設(shè)表1 中的膚色與瞳色為條件屬性，出生地（birthplace）為決策屬性。

第一步 通過(guò)決策屬性進(jìn)行分類可以得到等價(jià)類U/D={D1，D2，D3，D4}，其 中：D1={X1，X2}；D2={X3，X5}；D3={X4，X6}；D4={X7，X8}。

表1 決策表Tab.1 Decision table

第二步 通過(guò)條件屬性｛膚色，瞳色｝進(jìn)行分類可得到等價(jià)類U/C={C1，C2，C3}，其中：C1={X1，X2}；C2={X3，X5}；C3={X4，X6，X7，X8}。

第三步 需要求出相對(duì)正域，即從P 中篩選出Q 的子集：C1 ?D1；C2 ?D2。

因此，最終求得的依賴度為：

1.3 快速依賴計(jì)算

與傳統(tǒng)的通過(guò)正域求依賴的方法不同，快速依賴計(jì)算（FDC）通過(guò)直接比較不同類別對(duì)象的屬性來(lái)分辨對(duì)象是否屬于唯一類，最后統(tǒng)計(jì)該類對(duì)象即可求出依賴度。仍以表1 中的數(shù)據(jù)為例進(jìn)行講解。

步驟1 對(duì)決策表進(jìn)行預(yù)處理，將決策類屬性轉(zhuǎn)換成整型，并賦予每個(gè)對(duì)象唯一編號(hào)，額外添加一個(gè)標(biāo)記，默認(rèn)值為0。預(yù)處理結(jié)果如表2所示。

表2 表1的預(yù)處理結(jié)果Tab.2 Results after preprocessing for Tab.1

步驟2 讓每個(gè)對(duì)象Xi（即編號(hào)為i的對(duì)象）與表中其余對(duì)象Xj作比較，若Xi的決策屬性大于Xj，則比較Xi與Xj的條件屬性。若條件屬性完全相同，將Xi與Xj的標(biāo)記改為1；若存在不同屬性值，則直接進(jìn)入下一輪比較。執(zhí)行結(jié)果如表3所示。

步驟3 遍歷決策表，統(tǒng)計(jì)標(biāo)記為0的對(duì)象即可求出屬于正的對(duì)象數(shù)，進(jìn)而求得依賴度：

表3 執(zhí)行步驟2后的結(jié)果Tab.3 Results after step 2

算法1 描述了在Spark 平臺(tái)下FDC 算法的實(shí)現(xiàn)。由于Spark 中的廣播變量是不可修改的，因此需額外創(chuàng)建一個(gè)sign數(shù)組保存標(biāo)記信息，其長(zhǎng)度等于樣本總數(shù)。

循環(huán)遍歷廣播變量TD，對(duì)滿足條件obj1.lable ＞obj2.lable的對(duì)象比較條件屬性，若條件屬性完全相同，則以對(duì)象id為索引，將sign 數(shù)組指定下標(biāo)位置上的數(shù)值變更為1。最后統(tǒng)計(jì)sign數(shù)組中值為0的總個(gè)數(shù)即可求出依賴度。

算法1 快速依賴計(jì)算（FDC）。

輸入 搜索代理SearchAgent；

輸出 依賴度Dependency。

2 鯨魚(yú)優(yōu)化算法及其改進(jìn)

2.1 鯨魚(yú)優(yōu)化算法

鯨魚(yú)優(yōu)化算法（WOA）［11］通過(guò)模擬座頭鯨捕食行為實(shí)現(xiàn)對(duì)目標(biāo)問(wèn)題的求解。經(jīng)相關(guān)實(shí)驗(yàn)證明，WOA 在收斂速度以及全局搜索能力上都要優(yōu)于粒子群優(yōu)化算法［12］和遺傳算法等經(jīng)典算法，并且在特征選擇領(lǐng)域也得到了更高的精度［13］，因此本文將該算法應(yīng)用到粗糙集屬性約簡(jiǎn)中，以提高約簡(jiǎn)效率。

WOA 主要可分為包圍獵物、泡泡網(wǎng)攻擊以及搜索獵物三個(gè)不同階段。

2.1.1 包圍獵物

WOA 假設(shè)種群中當(dāng)前適應(yīng)度最高的個(gè)體所在位置為當(dāng)前獵物的位置，即本輪迭代中的最優(yōu)解；在確定獵物之后，種群中的其他鯨魚(yú)將根據(jù)當(dāng)前獵物的位置來(lái)更新自身位置，數(shù)學(xué)模型如下：

其中：t 表示當(dāng)前迭代數(shù)；X*代表當(dāng)前群體中最優(yōu)解的位置向量；X(t)表示鯨魚(yú)當(dāng)前所在的位置向量，Α ?D 表示包圍的步長(zhǎng)，A和C為系數(shù)向量，其定義如式（3）、（4）。

其中：r1與r2為［0，1］范圍內(nèi)的隨機(jī)數(shù)；a的取值隨迭代次數(shù)增加而減小，由2遞減為0，表示如式（5）。

其中Max_iter代表最大迭代次數(shù)。

2.1.2 泡泡網(wǎng)攻擊

依據(jù)座頭鯨的捕獵特點(diǎn)，WOA 設(shè)計(jì)了收縮包圍以及螺旋更新位置兩種策略來(lái)模擬泡泡網(wǎng)攻擊行為。

1）收縮包圍機(jī)制通過(guò)減小式（3）中a 的取值來(lái)實(shí)現(xiàn)。由式（3）可知，A的取值在[-a，a]區(qū)間，A隨著a減小而減小。

2）螺旋更新位置首先需計(jì)算鯨魚(yú)與獵物之間的距離，然后在鯨魚(yú)與獵物之間創(chuàng)建螺旋方程以模仿座頭鯨的螺旋運(yùn)動(dòng)，數(shù)學(xué)模型如下：

為了模擬鯨魚(yú)在收縮包圍的同時(shí)，還沿著螺旋路徑移動(dòng)，算法假設(shè)鯨魚(yú)在進(jìn)行狩獵的過(guò)程中選擇兩種策略的概率都為0.5，其數(shù)學(xué)模型可表示為：

2.1.3 搜索獵物

當(dāng)A 滿足 |A |＞1 時(shí)，鯨魚(yú)通過(guò)彼此的位置隨機(jī)搜索獵物。通過(guò)這種方式可以增強(qiáng)WOA 的全局尋優(yōu)能力。其數(shù)學(xué)模型表示如下：

2.2 應(yīng)用與改進(jìn)

為了將WOA有效地應(yīng)用到粗糙集屬性約簡(jiǎn)當(dāng)中，必須對(duì)其進(jìn)行一定的改進(jìn)。

在屬性約簡(jiǎn)（或稱特征選擇）中對(duì)于每個(gè)特征只有“選”與“不選”兩種情況。使用一個(gè)長(zhǎng)度為特征總數(shù)的一維數(shù)組來(lái)表示種群中的個(gè)體，每個(gè)個(gè)體即為問(wèn)題的一個(gè)解。數(shù)組中的每個(gè)單元格都有一個(gè)值“1”或“0”。值“1”表示選擇了相應(yīng)的特征，值“0”表示未選擇相應(yīng)的特征。

以兩個(gè)特征子集向量相減后的非0 元素個(gè)數(shù)作為特征子集之間的距離。比如［0，1，0，1］與［1，0，1，1］之間的距離為3。

在元啟發(fā)算法中，需要通過(guò)適應(yīng)度來(lái)判斷種群個(gè)體的優(yōu)劣。在本文算法中適應(yīng)度函數(shù)表示如下：

其中：α和β 的值在［0，1］范圍內(nèi)，且α+β=1；|R |為選中的特征個(gè)數(shù)；|C |為總特征數(shù)；γp(Q)為依賴度。本文取α=0.99，β=0.01。

在初期實(shí)驗(yàn)中發(fā)現(xiàn)將WOA 應(yīng)用于粗糙集屬性約簡(jiǎn)時(shí)會(huì)出現(xiàn)過(guò)早收斂的現(xiàn)象，因此在收縮包圍與螺旋更新操作后加入了變異算子來(lái)提高算法的全局搜索能力。其中變異率為：

其中：iter 代表當(dāng)前迭代次數(shù)，maxIter 代表最大迭代次數(shù)，| |C代表特征總數(shù)。

改進(jìn)后的鯨魚(yú)優(yōu)化算法如算法2所示。其中：第2）～9）行為初始化相關(guān)參數(shù)；第6）、7）行為搜索獵物階段，對(duì)應(yīng)式（8）、（9）；第9）、10）行描述包圍階段，對(duì)應(yīng)式（1）、（2）；第15）～17）行描述螺旋更新，對(duì)應(yīng)式（6）。另外，在收縮包圍與螺旋更新完畢后加入了變異算子，如算法3 所示，通過(guò)式（11）計(jì)算出本輪迭代的變異率，對(duì)種群個(gè)體的部分值做0-1變換。

算法2 改進(jìn)后的WOA（WOAcore）。

輸入 搜索代理數(shù)組 searchAgents，最佳搜索代理bestSearchAgent，最大迭代次數(shù)maxIter和當(dāng)前迭代次數(shù)iter；

算法3 Mutation。

輸入 搜索代理searchAgent，最大迭代次數(shù)maxIter 和當(dāng)前迭代次數(shù)iter；

3 SP-WOFRST算法

將FDC 與改進(jìn)的WOA 結(jié)合來(lái)尋找最優(yōu)屬性子集，并在Spark 平臺(tái)上并行實(shí)現(xiàn)，得到SP-WOFRST 算法的主要流程如圖1所示。其中：輸入?yún)?shù)table是預(yù)處理后的決策表，輸出結(jié)果為約簡(jiǎn)后的最佳屬性子集。

首先，將table 以廣播變量的形式送到每一個(gè)計(jì)算節(jié)點(diǎn)，即每個(gè)計(jì)算節(jié)點(diǎn)上僅保留一份預(yù)處理后的決策表。然后初始化種群并轉(zhuǎn)化為RDD 對(duì)象，通過(guò)Spark 的map 算子將種群中的個(gè)體分發(fā)到各個(gè)計(jì)算節(jié)點(diǎn)，使用FDC 算法在每一個(gè)計(jì)算節(jié)點(diǎn)上并行求解每一個(gè)個(gè)體的依賴度。一輪迭代結(jié)束后，收集各個(gè)節(jié)點(diǎn)的個(gè)體依賴度計(jì)算結(jié)果，選出本輪最佳個(gè)體，通過(guò)WOA 的搜尋機(jī)制更新其余個(gè)體后再次進(jìn)入新一輪的迭代。經(jīng)過(guò)指定迭代次數(shù)后算法結(jié)束，獲得全局最佳個(gè)體，即最終的約簡(jiǎn)結(jié)果。

圖1 SP-WOFRST流程Fig.1 Flowchart of SP-WOFRST

算法4 SP-WOFRST。

輸入 預(yù)處理后的決策表table，種群個(gè)體數(shù)量searchAgentsNum，WOA最大迭代次數(shù)maxIter；

輸出 最終約簡(jiǎn)結(jié)果Reduct。

4 實(shí)驗(yàn)結(jié)果與分析

在分布式環(huán)境下對(duì)算法SP-WOFRST 與SP-RST 在多種參數(shù)設(shè)置下分別進(jìn)行實(shí)驗(yàn)，并對(duì)兩種算法在各自最優(yōu)參數(shù)設(shè)置下的實(shí)驗(yàn)結(jié)果作對(duì)比分析。此外還對(duì)比了SP-WOFRST 算法在不同節(jié)點(diǎn)數(shù)下的運(yùn)行時(shí)間。

4.1 數(shù)據(jù)集

算法SP-WOFRST 與SP-RST 都基于經(jīng)典粗糙集理論（Pawlak 粗糙集模型［3］），它們所處理的分類必須是完全正確的或肯定的，因?yàn)樗菄?yán)格按照等價(jià)類來(lái)分類的，因而它的分類是精確的，亦即“包含”或“不包含”，而沒(méi)有某種程度上的“包含”或“屬于”，因此對(duì)噪聲的處理能力較弱。UCI 上的高維數(shù)據(jù)集大部分無(wú)法滿足上述要求，并不適合用于本文的算法測(cè)試，而低維數(shù)據(jù)集雖然符合要求，但由于數(shù)據(jù)量過(guò)少，難以展現(xiàn)實(shí)驗(yàn)結(jié)果。因此使用了兩個(gè)人工數(shù)據(jù)集arsds1 與arsds2 來(lái)測(cè)試算法的性能，數(shù)據(jù)集相關(guān)屬性見(jiàn)表4。arsds1 是一個(gè)高冗余度的數(shù)據(jù)集，其中包含50 個(gè)互不冗余的必要特征，400 個(gè)冗余特征以及50 個(gè)無(wú)關(guān)特征；arsds2 中包含250 個(gè)互不冗余的必要特征，200 個(gè)冗余特征以及50 個(gè)無(wú)關(guān)特征。即在理想情況下，對(duì)兩個(gè)數(shù)據(jù)集作特征選擇的結(jié)果中應(yīng)當(dāng)分別包含50個(gè)或250個(gè)必要特征。

表4 實(shí)驗(yàn)數(shù)據(jù)集Table 4 Experimental datasets

在檢驗(yàn)特征選擇算法的有效性時(shí)，使用人工數(shù)據(jù)集有以下兩個(gè)優(yōu)勢(shì)［14］：

1）預(yù)先已知最優(yōu)的特征組合，因此可以精確地評(píng)估算法結(jié)果的精確性。

2）實(shí)驗(yàn)數(shù)據(jù)是可控的，可以通過(guò)系統(tǒng)地改變所選擇的實(shí)驗(yàn)條件來(lái)進(jìn)行不同的實(shí)驗(yàn)，比如在數(shù)據(jù)集中添加或減少更多不相關(guān)的特征或噪聲，這將有助于得出更有用的結(jié)論，并測(cè)試現(xiàn)有算法的優(yōu)缺點(diǎn)。

4.2 實(shí)驗(yàn)配置

硬件方面使用3 臺(tái)搭載I5-4590，主頻3.30 GHz 的CPU，8 GB 內(nèi)存的計(jì)算機(jī)，算法均在Spark 2.1.1 平臺(tái)上用Scala 2.11實(shí)現(xiàn)。

4.3 度量標(biāo)準(zhǔn)

由于使用人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，預(yù)先已知特征之間的相關(guān)性以及各個(gè)特征的有用性，因此無(wú)需使用其他分類算法來(lái)測(cè)量約簡(jiǎn)結(jié)果的精確度。本文采用F1-Measure作為約簡(jiǎn)結(jié)果的質(zhì)量指標(biāo)，計(jì)算公式定義如下：

其中：TP（真正例）指約簡(jiǎn)結(jié)果中選中的必要特征，F(xiàn)P（假正例）指約簡(jiǎn)結(jié)果中未選中的必要特征，F(xiàn)N（假反例）指約簡(jiǎn)結(jié)果中未能剔除的冗余/無(wú)關(guān)特征，TN（真反例）指約簡(jiǎn)結(jié)果中正確剔除的冗余/無(wú)關(guān)特征；P 為查準(zhǔn)率（Precision），指約簡(jiǎn)結(jié)果中選中的必要特征占有用特征總數(shù)的比例；R 為查全率（Recall），指約簡(jiǎn)結(jié)果中選中的必要特征占約簡(jiǎn)結(jié)果總特征數(shù)的比例。

4.4 結(jié)果分析

第一項(xiàng)實(shí)驗(yàn)中使用3 臺(tái)機(jī)器分別對(duì)SP-RST 與SPWOFRST 在不同的參數(shù)設(shè)置（算法自身有兩個(gè)需要人為調(diào)節(jié)的參數(shù)）下進(jìn)行實(shí)驗(yàn)，表5～8 中列出了最優(yōu)的幾項(xiàng)實(shí)驗(yàn)結(jié)果，其中加粗項(xiàng)為全局最優(yōu)的實(shí)驗(yàn)結(jié)果。第二項(xiàng)實(shí)驗(yàn)在不同的節(jié)點(diǎn)數(shù)下對(duì)SP-WOFRST算法的運(yùn)行效率進(jìn)行了統(tǒng)計(jì)分析。

在Spark 平臺(tái)下，算法的最大實(shí)際并行度等于CPU 的總核心數(shù)，即第一項(xiàng)實(shí)驗(yàn)中共有12 個(gè)核心在并行執(zhí)行算法，并且SP-WOFRST算法中需要網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量非常少，因此在增加節(jié)點(diǎn)時(shí)，執(zhí)行效率接近線性提升。

表5 與表6 分別為不同參數(shù)設(shè)置下的SP-RST 算法在arsds1 與arsds2 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。“特征數(shù)/分區(qū)”指該算法定義的每個(gè)分區(qū)內(nèi)的特征數(shù)，該參數(shù)越大則算法精度越高，速度越慢。由于該算法最后需要對(duì)多次迭代得到的多個(gè)約簡(jiǎn)結(jié)果求交集，該算法在執(zhí)行過(guò)程中必然會(huì)漏選個(gè)別必要特征。

表5 不同參數(shù)設(shè)置下的SP-RST在arsds1數(shù)據(jù)集上的性能Tab.5 Performance of SP-RST on arsds1 dataset with different parameter settings

表6 不同參數(shù)設(shè)置下的SP-RST在arsds2數(shù)據(jù)集上的性能Tab.6 Performance of SP-RST on arsds2 dataset with different parameter settings

表7與表8分別為不同參數(shù)設(shè)置下的SP-WOFRST算法在arsds1 與arsds2 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。由于在適應(yīng)度函數(shù)中取α=0.99，β=0.01，因此算法會(huì)優(yōu)先選擇依賴度高的約簡(jiǎn)結(jié)果，所以在表中可以看到查準(zhǔn)率始終為1。通過(guò)對(duì)比F1 與時(shí)間兩項(xiàng)結(jié)果，可以清晰地看出，在相近的運(yùn)行時(shí)間下，SP-WOFRST的精度均優(yōu)于SP-RST。

第二項(xiàng)實(shí)驗(yàn)的結(jié)果如圖2 所示，在不同節(jié)點(diǎn)數(shù)下，SPWOFRST 算法執(zhí)行50 次迭代所需的時(shí)間隨著節(jié)點(diǎn)數(shù)的增加呈線性遞減，說(shuō)明本文提出的算法在小型集群上可擴(kuò)展性良好。

表7 不同參數(shù)設(shè)置下的SP-WOFRST在arsds1數(shù)據(jù)集上的性能Tab.7 Performance of SP-WOFRST on arsds1 dataset with different parameter settings

表8 不同參數(shù)設(shè)置下的SP-WOFRST在arsds2數(shù)據(jù)集上的性能Tab.8 Performance of SP-WOFRST on arsds2 dataset with different parameter settings

圖2 SP-WOFRST算法在不同節(jié)點(diǎn)數(shù)下的運(yùn)行時(shí)間Fig.2 Running time of SP-WOFRS algorithm under different node numbers

5 結(jié)語(yǔ)

本文提出了一種基于Spark 平臺(tái)的高效分布式粗糙集屬性約簡(jiǎn)算法SP-WOFRST。該算法通過(guò)鯨魚(yú)優(yōu)化算法（WOA）尋找最優(yōu)特征子集，并使用更快速的依賴計(jì)算方法FDC 來(lái)提高計(jì)算速度，在保持較高精度的前提下大大縮短了算法執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，相較于現(xiàn)有的分布式粗糙集特征選擇算法，在相近的運(yùn)行時(shí)間下本文算法有更高的精度。在后續(xù)研究中，我們將嘗試?yán)米兙却植诩碚摳倪M(jìn)本文算法，使算法能夠更好地適應(yīng)帶噪聲的數(shù)據(jù)集，進(jìn)一步提高算法的精確度。我們計(jì)劃在未來(lái)實(shí)現(xiàn)變精度［15］以及基于信息熵［16］的分布式粗糙集約簡(jiǎn)算法。