Spark下的分布式粗糙集屬性約簡算法

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

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

0 引言

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

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

Hu 等［4］提出了一種基于正區域屬性重要性的約簡算法。Hu 等［5］利用可分辨矩陣中的啟發式思想計算屬性的重要性，并提出了一種啟發式的約簡算法。基于正區域和基于條件熵的方法的目的都是選擇一個最小特征子集，且該子集能最大化描述給定數據集中的分類信息。基于可辨矩陣的方法是選擇一個具有高分辨能力的特征子集，從而保證了約簡后的數據集具有最大的類間可分性。這些方法考慮了最佳候選屬性，試圖找到最小約簡。

爬山式的粗糙集約簡方法通常以空集或屬性核為起點，采用正向選擇的方式依次從候選集合中添加最重要的屬性直到無法再添加新的屬性為止，這種方法速度較快，但是在處理存在較多關聯屬性的數據集時易陷入局部最優解。

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

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

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

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

1 粗糙集與依賴度計算

1.1 粗糙集

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

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

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

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

1.2 依賴度計算

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

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

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

表1 決策表Tab.1 Decision table

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

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

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

1.3 快速依賴計算

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

步驟1 對決策表進行預處理，將決策類屬性轉換成整型，并賦予每個對象唯一編號，額外添加一個標記，默認值為0。預處理結果如表2所示。

表2 表1的預處理結果Tab.2 Results after preprocessing for Tab.1

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

步驟3 遍歷決策表，統計標記為0的對象即可求出屬于正的對象數，進而求得依賴度：

表3 執行步驟2后的結果Tab.3 Results after step 2

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

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

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

輸入 搜索代理SearchAgent；

輸出 依賴度Dependency。

2 鯨魚優化算法及其改進

2.1 鯨魚優化算法

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

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

2.1.1 包圍獵物

WOA 假設種群中當前適應度最高的個體所在位置為當前獵物的位置，即本輪迭代中的最優解；在確定獵物之后，種群中的其他鯨魚將根據當前獵物的位置來更新自身位置，數學模型如下：

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

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

其中Max_iter代表最大迭代次數。

2.1.2 泡泡網攻擊

依據座頭鯨的捕獵特點，WOA 設計了收縮包圍以及螺旋更新位置兩種策略來模擬泡泡網攻擊行為。

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

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

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

2.1.3 搜索獵物

當A 滿足 |A |＞1 時，鯨魚通過彼此的位置隨機搜索獵物。通過這種方式可以增強WOA 的全局尋優能力。其數學模型表示如下：

2.2 應用與改進

為了將WOA有效地應用到粗糙集屬性約簡當中，必須對其進行一定的改進。

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

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

在元啟發算法中，需要通過適應度來判斷種群個體的優劣。在本文算法中適應度函數表示如下：

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

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

其中：iter 代表當前迭代次數，maxIter 代表最大迭代次數，| |C代表特征總數。

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

算法2 改進后的WOA（WOAcore）。

輸入 搜索代理數組 searchAgents，最佳搜索代理bestSearchAgent，最大迭代次數maxIter和當前迭代次數iter；

算法3 Mutation。

輸入 搜索代理searchAgent，最大迭代次數maxIter 和當前迭代次數iter；

3 SP-WOFRST算法

將FDC 與改進的WOA 結合來尋找最優屬性子集，并在Spark 平臺上并行實現，得到SP-WOFRST 算法的主要流程如圖1所示。其中：輸入參數table是預處理后的決策表，輸出結果為約簡后的最佳屬性子集。

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

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

算法4 SP-WOFRST。

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

輸出 最終約簡結果Reduct。

4 實驗結果與分析

在分布式環境下對算法SP-WOFRST 與SP-RST 在多種參數設置下分別進行實驗，并對兩種算法在各自最優參數設置下的實驗結果作對比分析。此外還對比了SP-WOFRST 算法在不同節點數下的運行時間。

4.1 數據集

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

表4 實驗數據集Table 4 Experimental datasets

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

1）預先已知最優的特征組合，因此可以精確地評估算法結果的精確性。

2）實驗數據是可控的，可以通過系統地改變所選擇的實驗條件來進行不同的實驗，比如在數據集中添加或減少更多不相關的特征或噪聲，這將有助于得出更有用的結論，并測試現有算法的優缺點。

4.2 實驗配置

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

4.3 度量標準

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

其中：TP（真正例）指約簡結果中選中的必要特征，FP（假正例）指約簡結果中未選中的必要特征，FN（假反例）指約簡結果中未能剔除的冗余/無關特征，TN（真反例）指約簡結果中正確剔除的冗余/無關特征；P 為查準率（Precision），指約簡結果中選中的必要特征占有用特征總數的比例；R 為查全率（Recall），指約簡結果中選中的必要特征占約簡結果總特征數的比例。

4.4 結果分析

第一項實驗中使用3 臺機器分別對SP-RST 與SPWOFRST 在不同的參數設置（算法自身有兩個需要人為調節的參數）下進行實驗，表5～8 中列出了最優的幾項實驗結果，其中加粗項為全局最優的實驗結果。第二項實驗在不同的節點數下對SP-WOFRST算法的運行效率進行了統計分析。

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

表5 與表6 分別為不同參數設置下的SP-RST 算法在arsds1 與arsds2 數據集上的實驗結果。“特征數/分區”指該算法定義的每個分區內的特征數，該參數越大則算法精度越高，速度越慢。由于該算法最后需要對多次迭代得到的多個約簡結果求交集，該算法在執行過程中必然會漏選個別必要特征。

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

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

表7與表8分別為不同參數設置下的SP-WOFRST算法在arsds1 與arsds2 數據集上的實驗結果。由于在適應度函數中取α=0.99，β=0.01，因此算法會優先選擇依賴度高的約簡結果，所以在表中可以看到查準率始終為1。通過對比F1 與時間兩項結果，可以清晰地看出，在相近的運行時間下，SP-WOFRST的精度均優于SP-RST。

第二項實驗的結果如圖2 所示，在不同節點數下，SPWOFRST 算法執行50 次迭代所需的時間隨著節點數的增加呈線性遞減，說明本文提出的算法在小型集群上可擴展性良好。

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

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

圖2 SP-WOFRST算法在不同節點數下的運行時間Fig.2 Running time of SP-WOFRS algorithm under different node numbers

5 結語

本文提出了一種基于Spark 平臺的高效分布式粗糙集屬性約簡算法SP-WOFRST。該算法通過鯨魚優化算法（WOA）尋找最優特征子集，并使用更快速的依賴計算方法FDC 來提高計算速度，在保持較高精度的前提下大大縮短了算法執行時間。實驗結果表明，相較于現有的分布式粗糙集特征選擇算法，在相近的運行時間下本文算法有更高的精度。在后續研究中，我們將嘗試利用變精度粗糙集理論改進本文算法，使算法能夠更好地適應帶噪聲的數據集，進一步提高算法的精確度。我們計劃在未來實現變精度［15］以及基于信息熵［16］的分布式粗糙集約簡算法。