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

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

0 引言

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

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

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

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

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

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

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

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

1 粗糙集與依賴度計算

1.1 粗糙集

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

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

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

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

1.2 依賴度計算

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

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

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

表1 決策表Tab.1 Decision table

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

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

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

1.3 快速依賴計算

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

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

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

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

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

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

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

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

算法1 快速依賴計算（FDC）。

輸入 搜索代理SearchAgent；

輸出 依賴度Dependency。

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

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

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

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

2.1.1 包圍獵物

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

其中：t 表示當(dāng)前迭代數(shù)；X*代表當(dāng)前群體中最優(yōu)解的位置向量；X(t)表示鯨魚當(dāng)前所在的位置向量，Α ?D 表示包圍的步長，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ù)座頭鯨的捕獵特點，WOA 設(shè)計了收縮包圍以及螺旋更新位置兩種策略來模擬泡泡網(wǎng)攻擊行為。

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

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

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

2.1.3 搜索獵物

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

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

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

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

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

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

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

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

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

改進(jìn)后的鯨魚優(yōu)化算法如算法2所示。其中：第2）～9）行為初始化相關(guān)參數(shù)；第6）、7）行為搜索獵物階段，對應(yīng)式（8）、（9）；第9）、10）行描述包圍階段，對應(yīng)式（1）、（2）；第15）～17）行描述螺旋更新，對應(yīng)式（6）。另外，在收縮包圍與螺旋更新完畢后加入了變異算子，如算法3 所示，通過式（11）計算出本輪迭代的變異率，對種群個體的部分值做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é)合來尋找最優(yōu)屬性子集，并在Spark 平臺上并行實現(xiàn)，得到SP-WOFRST 算法的主要流程如圖1所示。其中：輸入?yún)?shù)table是預(yù)處理后的決策表，輸出結(jié)果為約簡后的最佳屬性子集。

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

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

算法4 SP-WOFRST。

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

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

4 實驗結(jié)果與分析

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

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

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

表4 實驗數(shù)據(jù)集Table 4 Experimental datasets

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

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

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

4.2 實驗配置

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

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

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

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

4.4 結(jié)果分析

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

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

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

表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ù)集上的實驗結(jié)果。由于在適應(yīng)度函數(shù)中取α=0.99，β=0.01，因此算法會優(yōu)先選擇依賴度高的約簡結(jié)果，所以在表中可以看到查準(zhǔn)率始終為1。通過對比F1 與時間兩項結(jié)果，可以清晰地看出，在相近的運行時間下，SP-WOFRST的精度均優(yōu)于SP-RST。

第二項實驗的結(jié)果如圖2 所示，在不同節(jié)點數(shù)下，SPWOFRST 算法執(zhí)行50 次迭代所需的時間隨著節(jié)點數(shù)的增加呈線性遞減，說明本文提出的算法在小型集群上可擴(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é)點數(shù)下的運行時間Fig.2 Running time of SP-WOFRS algorithm under different node numbers

5 結(jié)語

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