動態(tài)模糊粗糙特征選取算法*

倪 鵬，劉陽明，趙素云+，陳 紅，李翠平

1.中國人民大學 數據工程與知識工程教育部重點實驗室，北京 100872

2.中國人民大學 信息學院，北京 100872

1 引言

近年來，粗糙集理論因不需要太多額外的知識且容易理解，而獲得了較多的關注。大量的基于粗糙集的挖掘技術被提出[1-10]。其中，大部分的方法基于同一個前提：數據是靜態(tài)的。一旦數據隨著時間和空間動態(tài)地更新，這些靜態(tài)方法的學習結果已不適用，需要重新掃描更新后的數據集重新計算。顯然，重新掃描整個數據集的操作導致時間與空間的浪費，甚至數據規(guī)模較大時，這些靜態(tài)方法不再適用[11]。

增量學習是一種適用于增量數據的數據挖掘方法，該方法通過分析新增數據與已有數據的結構及關系來更新已有的學習結果，避免重新掃描整個數據集，從而大大降低了計算量，提高了計算效率[12-17]。近年來，為了解決數據的動態(tài)增長，已有很多學者將增量學習的思想引入粗糙集的應用研究中[4，11，18-22]。

目前，基于粗糙集的增量學習方法分為三種：知識表示的更新、規(guī)則約簡的更新和特征選擇的更新。首先，知識表示的更新方法是指在動態(tài)數據集中快速有效地更新粗糙近似表示。比如，一些學者探索了基于不同粗糙集擴展模型的更新上下近似的方法：粗糙集[20，23]、緊鄰粗糙集[24]、優(yōu)勢關系粗糙集[25]、貝葉斯粗糙集[26]、決策粗糙集[11]和粗糙模糊集[18，27]等。以上這些更新方法針對數據示例的逐個更新、數據示例的批量更新、特征的增減更新等不同的情況，分別討論分析了粗糙近似知識表示的相應增量學習機制。其次，一些學者在規(guī)則約簡更新中提出了增量的更新方法。其中，一些增量的方法只考慮了在一個個添加示例的情況下規(guī)則的更新方法[28-30]?？紤]到數據更新多是批量更新的，一些學者研究了一組組添加示例的過程中學習規(guī)則的更新[31-32]。此外，有一些規(guī)則學習的增量方法針對的是屬性集的更新[11，25，33]。

相較于其他兩種方法，特征選擇的動態(tài)更新的研究較少。一些學者提出了增量約簡算法針對數據集中數據一個個的增加的情況[22]；還有一些學者提出的增量算法解決數據一組組增量的情況[21]。然而這兩種方法只考慮離散值數據集的動態(tài)變化情況。雖然有學者提出的增量算法針對的連續(xù)值數據集[34]，但是該算法針對的是屬性集更新的情況。

通過以上分析可以看出，目前尚沒有針對連續(xù)值數據示例動態(tài)改變的屬性約簡的算法。考慮到模糊粗糙集技術是處理連續(xù)數據的有效工具，本文提出了一個基于模糊粗糙集的增量屬性約簡算法，來解決動態(tài)連續(xù)值數據集上的屬性約簡問題。當前，主要關注在數據集示例的動態(tài)增加。

首先，通過分析添加示例前后模糊正域的變化，提出了模糊正域計算的增量機制。基于這個增量機制可以通過避免在動態(tài)數據集上的冗余計算，顯著地減少計算時間。然后，基于嚴格的理論推導發(fā)現了已有約簡的辨識能力改變的關鍵數據。這些關鍵數據的發(fā)現使得在有限的數據上快速更新已有約簡變得可行。最后，提出了一個增量屬性約簡算法。數據實驗表明了該增量算法是有效且高效的，特別是在高維數據集上效果更加突出。

2 模糊粗糙集相關研究

本章簡單回顧一些模糊粗糙集及其經典的約簡算法。關于該理論的更多細節(jié)，可以參考文獻[35-38]。

2.1 模糊粗糙集簡介

數據集可以描述成一個決策表，表示成一個三元組DT=＜U,R,D＞。這里U是一個非空示例集{x1,x2,…,xn}。每個示例由一組條件屬性R={a1,a2,…,am}以及一組決策屬性D來描述。決策屬性將論域劃分為q個決策類U/D={D1,D2,…,Dq}，這里U=，且任意兩個決策類相交為空。

如果R是可以模糊化的（如連續(xù)值屬性），那么決策表DT=＜U,R,D＞表示一個模糊決策表。在模糊決策表上，粗糙集被推廣為模糊粗糙集。模糊粗糙集是融合了粗糙集和模糊集的概念而提出的理論。模糊粗糙集不僅將近似對象從離散集擴展到了模糊集，而且將等價關系擴展到了模糊相似關系。

定義1對于P?R以及給定的三角模T，屬性子集P的模糊相似關系可定義為P(?,?)。對于任意x,y,z∈U，P(?,?)滿足：（1）自反性(P(x,x)=1)；（2）對稱性(P(x,y)=P(y,x))；（3）T-傳遞性(P(x,y)≥T(P(x,z),P(z,y)))。

例如，模糊相似關系可以按照如下方式計算得到：r∈P,?x,y∈U,P(x,y)=minr∈P(r(x,y))，這 里r(x,y)=1-(max(r(x),r(y))-min(r(x),r(y)))。此時，P(?,?)即為屬性子集P所描述的模糊相似關系，它滿足自反性、對稱性和TL=max{0,x+y-1}三角傳遞性。

模糊粗糙集定義了模糊上下近似概念，如下。

定義2給定模糊決策表DT=＜U,R,D＞，對于A?U，那么模糊上、下近似定義如下：

在模糊粗糙集中，整個論域上的粗糙度量方式之模糊正域定義如下。

定義3給定模糊決策表DT=＜U,R,D＞，示例x∈U的模糊正域定義如下：

繼而，決策屬性D對條件屬性子集P?R的依賴度可以定義如下。

定義4給定模糊決策表DT=＜U,R,D＞和?P?R，決策屬性D對于屬性子集P的依賴度定義如下：

該定義度量了屬性子集P?R相對于決策屬性的依賴程度。

2.2 模糊粗糙集基本性質討論

本節(jié)深入討論了模糊粗糙集的一些性質。

性質1依據定義2，給定模糊決策表DT=＜U,R,D＞和?A?U，示例x∈U相對于A的下近似定義可以簡化為：

證明具體證明，請參考文獻[38]。 □

性質1給出了下近似的幾何意義。即x屬于它所在的決策類的，下近似為離x最近的異類示例點u的距離；x屬于其他決策類的，下近似為0?；诖耍梢缘玫叫再|2。

性質2依據定義3，給定模糊決策表DT=＜U,R,D＞，示例x∈U的正域可以簡化為。這里，[x]D={u∈U|D(x)=D(u)}，即[x]D表示與x屬于同一決策類的示例集。

證明根據性質1和定義3易得。 □

性質2表明了模糊正域和下近似之間的關系。下面的性質進一步討論了依賴度隨著屬性的增加是如何變化的。

性質3給定模糊決策表DT=＜U,R,D＞，如果P?Q?R，那么。

證明對于P?Q?R，有：

性質3表明了依賴度函數隨著屬性的增加是單調不減的。這一結論是設計屬性約簡啟發(fā)式算法的理論根據。

2.3 基于依賴度的屬性約簡

約簡的核心思想是找到一個最小的屬性子集，該子集保持了全屬性集的辨識能力。約簡的定義如下，更多的細節(jié)可以參考文獻[33，37-38]。

定義5給定模糊決策表DT=＜U,R,D＞和?P?R，當P滿足條件：（1）?a∈P,時，稱P是模糊決策表的一個約簡。

基于依賴度經典的非增量屬性約簡算法，簡寫為CAR（classical attribute reduction），已被提出，并得到廣泛的應用。

算法1經典約簡算法(CAR)

輸入：DT=＜U,R,D＞

輸出：red。

3 模糊粗糙集上的增量機制

給定一個動態(tài)的模糊決策表DT=＜U∪ΔU,R,D＞，其中U={x1,x2,…,xn} 為原始實例，ΔU={xn+1,xn+2,…,xn+s}?；诘?章的概念和算法，針對增量數據，需要重新計算模糊正域，既費時又存在重復的計算。因此，本章提出了幾個基本概念的增量機制，從而實現動態(tài)快速更新模糊正域。

3.1 模糊正域增量機制

首先，在動態(tài)數據集上計算更新后的模糊正域POSU∪ΔU(x)很有必要。這是計算依賴度的先決條件。

定理1給定模糊決策表DT=＜U,R,D＞，如果一些新示例ΔU={xn+1,xn+2,…,xn+s}加入進來，那么：

（1）如果x∈U,則：

（2）如果x∈ΔU,則：

證明依據性質2，對于x∈ΔU的情況，很顯然成立。

對于x∈U的情況：

由此，定理1得證。 □

定理1理論分析并給出了一個快速更新模糊正域的方法，從而避免了遞增動態(tài)數據集上的模糊正域的冗余計算。

3.2 增量關鍵示例集

基于定理1，可以很快地得到POSU∪ΔU(x)。并且發(fā)現，對于模糊正域來說，存在一個增量關鍵集。

定義6給定模糊決策表DT=＜U,R,D＞和P?R如果一些新示例ΔU={xn+1,xn+2,…,xn+s}加入進來，那么令，稱之為增量關鍵示例集。

由定義6可知，如果x?ΔS，那么。這意味著已經達到最大。因此，只需要在x∈ΔS如何選擇屬性。

4 基于模糊粗糙集的增量屬性約簡

本章基于以上增量機制，設計了一個增量約簡算法，簡寫為IAR（incremental attribute reduction），見算法2。

算法2基于依賴度的增量約簡算法(IAR)

5 實驗分析

本章構造了一些對比實驗。使用的數據集來自UCI數據庫（https://archive.ics.uci.edu），數據的詳細信息見表1。實驗環(huán)境為Ubuntu release 16.0，Intel?CoreTMi7-4790 CPU@3.60 GHz，8 GB內存。編程語言為C++。

Table 1 Description of datasets表1 數據集信息描述

實驗中對比了一種非增量的Naive依賴度算法，它在新數據到來時并不更新經典依賴度算法，而只是利用之前的約簡作為新約簡的候選，這個算法簡寫為NonIAR，在本章中NonIAR和CAR均被用來與IAR進行對比。實驗中每個數據集被平分為兩份。一份看作是原始數據，另一份看作是新增的示例集。

NonIAR算法設計如下：

算法3非增量的Naive依賴度算法(NonIAR)

5.1 執(zhí)行時間對比分析

三種算法的執(zhí)行時間（單位：s）的比較結果見圖1、圖2。

Fig.1 Execution time on low dimensional data圖1 低維數據上的運行時間圖

Fig.2 Execution time on high dimensional data圖2 高維數據上的運行時間圖

從圖1和圖2中可以觀察到NonIAR相比CAR已經快了不少，但IAR更快。這說明IAR明顯加速了基于依賴度的約簡算法的速度。

進一步分析圖2，發(fā)現在高維數據上IAR加速更加明顯，這表明IAR更適合高維數據的屬性約簡。

5.2 約簡效率對比分析

在本節(jié)中，將比較CAR、NonIAR和IAR的約簡效率。比較的結果呈現在表2與表3中。在表2與表3中，這三個算法的約簡率都是相似的。在低維數據上，例如在表2的數據集上平均約簡率依次為0.532/0.532/0.569；在高維數據上，例如在表3的數據集上平均約簡率依次為0.004/0.005/0.003。這說明這三個算法有著相近的降維能力，甚至在高維數據上，增量算法表現出的能力更強。

Table 2 Comparison of reduction rates on low dimensional data表2 低維數據上約簡率的比較

Table 3 Comparison of reduction rates on high dimensional data表3 高維數據上約簡率的比較

5.3 約簡分類能力對比分析

本節(jié)應用KNN（K取3）分類算法來檢驗CAR、NonIAR和IAR的約簡分類能力[39]，其中采取五折交叉驗證來確保分類結果的公平性與穩(wěn)定性。分類比較的結果在表4、表5中。

在表4和表5中，很容易看出來，這些算法有著相近的平均分類準確度。比起全集屬性來說，差別并不是很大。

綜上所述，本文提出的增量約簡算法可以在節(jié)省時間的同時，獲得與非增量算法相近分類性能的約簡。

Table 4 Comparison of classification accuracy on low dimensional data表4 低維數據上分類準確度的比較 %

Table 5 Comparison of classification accuracy on high dimensional data表5 高維數據上分類準確度的比較 %

6 結束語

本文提出了基于模糊粗糙集增量屬性約簡算法，本文主要有以下特點：

（1）提出了模糊粗糙集中的一些概念的增量機制，并且有著嚴格的理論推導，這是設計增量屬性約簡算法的基礎。

（2）基于增量機制，提出了一個增量約簡算法。算法有效地利用已獲得學習結果，比如模糊正域與約簡，避免大量重復的計算。

（3）實驗結果驗證了提出的增量算法的高效性和有效性，特別是在高維數據集上增量算法表現更為高效。