張照星　劉威　張鵬　范英　康凱　劉陽明　施一琳　徐驍

摘要：屬性約簡作為粗糙集理論的一個重要應(yīng)用被較多學(xué)者關(guān)注。然而，由于其計算復(fù)雜度與數(shù)據(jù)的規(guī)模成平方級增長，基于粗糙集的屬性約簡在大規(guī)模數(shù)據(jù)上的應(yīng)用效率較低?？紤]到隨機抽樣是降低大規(guī)模數(shù)據(jù)的計算的一種有效的統(tǒng)計方法，因而我們將其引入約簡算法中，提出一種隨機約簡算法，從而大幅提升了屬性約簡的效率。該算法的主要貢獻是基于最小冗余和最大相關(guān)的選擇屬性過程中引入了隨機抽樣的思想。首先，在每次選擇最重要屬性時，并不需要在所有的示例上計算依賴度，而是隨機選了部分示例，從而既選擇了最大相關(guān)的屬性，又大大降低了算法的計算復(fù)雜度。其次，在選擇屬性的過程中，每次迭代的樣本是不同的，而且樣本之間具有較少的信息交叉，從而選取了最小冗余的屬性。最后，通過數(shù)值實驗，我們比較了隨機約簡算法與非隨機約簡算法的性能。

關(guān)鍵詞：隨機抽樣；模糊粗糙集；屬性約簡

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）33-0013-03

數(shù)據(jù)的爆炸性增長，帶來了數(shù)據(jù)挖掘技術(shù)的飛快進步。而在實際問題中，數(shù)據(jù)缺失，數(shù)據(jù)收集不精確，數(shù)據(jù)粒度過于粗糙等都會導(dǎo)致不確定數(shù)據(jù)的產(chǎn)生。不確定數(shù)據(jù)挖掘成為一個熱門的研究方向。波蘭科學(xué)家Z.Pawlak提出的粗糙集理論，其不需要太多的專業(yè)知識也能很容易地被人理解，是集合理論的一般化擴展[1-2]。

文獻[9]主要利用增量學(xué)習(xí)的方式提高執(zhí)行速度。在[9]中，提出了基于粗糙集理論的增強式學(xué)習(xí)方法，將數(shù)據(jù)集分為幾塊，依次把數(shù)據(jù)塊加入運算，從而原始的大規(guī)模數(shù)據(jù)的運算量可以有效地降低?；诖嗽隽康乃枷?，約簡在每次數(shù)據(jù)塊加入的過程中被更新。這種基于已獲得約簡結(jié)果學(xué)習(xí)新的數(shù)據(jù)集的約簡方法，即避免的重復(fù)運算，又使得大規(guī)模數(shù)據(jù)集上的約簡成為可能。不同與增量學(xué)習(xí)算法，有不少學(xué)者研究了按照分布式的思路來解決大規(guī)模數(shù)據(jù)集中的粗糙集問題。但是，從統(tǒng)計學(xué)的角度出發(fā)，隨機抽樣可以在基于粗糙集理論的大規(guī)模數(shù)據(jù)應(yīng)用中發(fā)揮作用。

本文將模糊粗糙集和隨機抽樣的基本方法結(jié)合，提出了基于抽樣的隨機約簡算法，來解決大規(guī)模數(shù)據(jù)的屬性約簡問題。本文的主要安排如下。第一節(jié)我們回顧了模糊粗糙集及其約簡；第二節(jié)構(gòu)造了基于隨機抽樣的隨機粗糙模型，并理論分析了樣本與總體的依賴度統(tǒng)計意義上的差別與聯(lián)系，并據(jù)此提出了隨機約簡的定義。第三節(jié)基于最大相關(guān)和最小冗余的思想設(shè)計了隨機約簡的算法。第四節(jié)我們給出算法的數(shù)值實驗評估。最后在第五節(jié)總結(jié)了全文。

1 模糊粗糙集及其約簡

在本節(jié)中，我們簡單回顧一些模糊粗糙集和其經(jīng)典的約簡算法。關(guān)于該理論的更多細節(jié)，可以參考文獻[3-7]。

1.1 模糊粗糙集

數(shù)據(jù)集可以描述成一個決策表，表示成一個三元組[DT=]。這里U是一個非空示例集[{x1，x2，…，xn}]。每個示例用一組條件屬性[{a1，a2，…，am}]來描述，記為A，另外有一組決策屬性，記為D。決策屬性將論域劃分為m個決策類[UD]=[{D1，D2，…，Dq}]，這里[U=i=1qDi]，且任意兩個決策類[Di]與[Dj]相交為空。特別地，如果[x∈Di]，則記[Di=Dx]。即[Dx]表示[x]屬于該決策類。

假設(shè)B是A的一個子集。兩個示例的相似度和距離定義如下。

定義1.1：給定決策表[DT=]，[?B?A]和[xi，xj∈U]，[xi]和[xj]的相似度記為[rB（xi ，xj）]，[xi]和[xj]的距離記為[dBxi，xj]。它們的定義如下：

[dBxi，xj=maxkak（xi）-ak（xj），ak∈B]；

[rB（xi，xj）=1-dB（xi，xj）]。

[rB（?，?）]即為屬性子集B所描述的模糊相似關(guān)系，它滿足自反性、對稱性和三角傳遞性。

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

定義1.2：給定模糊決策表DT=和[?B?A]，示例[x∈U]屬于[Dk]類的上、下近似定義如下：

[BDkx=infu∈Umax1-rBx，u，Dku，x∈U]

[BDkx=supu∈UminrBx，u，Dku，x∈U]

上述定義是一般化的模糊糙集的定義在特定的模糊相似關(guān)系[rB（?，?）]下的具體的形式，它的幾何意義為示例的下近似是距離其最近的異類點的距離，上近似是距離其最遠的同類點的相似度。為了便于理解，本文的接下來的工作均是基于定義2的模糊粗糙集展開。采用類似的方法，本文的工作可以推廣至一般化的模糊粗糙集。

傳統(tǒng)粗糙集理論中，正域是下近似的并。在模糊粗糙集中，模糊正域的定義如下。

定義1.3：給定模糊決策表DT=和[?B?A]，示例[x∈U]的模糊正域定義如下

[POSUBx=sup0

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

定義1.4：給定模糊決策表DT=和[?B?A]，決策屬性D對于屬性子集B的依賴度定義如下：

[γUB=x∈UPOSUB（x）|U|]

該定義可以度量屬性子集[B?A]在整個決策表中的重要性程度，有如下性質(zhì)。

性質(zhì)1.1：[γUB≤γUA]；[limB→AγUB=γUA].

1.2 基于依賴度的屬性約簡算法

約簡的核心思想是找到一個最小的屬性子集，該屬性子集可以區(qū)分所有的具有不同決策類的示例對。即約簡擁有和全集相同的辨識信息。約簡的定義如下，更多的細節(jié)，可以參考[6-8]。

定義1.5：給定模糊決策表DT=和[?B?A]，當(dāng)B滿足以下條件時，

（1） [?a∈B，γU（B-a）<γUB]；

（2）[γUB=γUA；]

此時，我們稱B是模糊決策表的一個約簡。

基于依賴度經(jīng)典的非增量屬性約簡算法，簡寫為CAR，已被提出得到廣泛的應(yīng)用[1，2]。

[算法1：經(jīng)典約簡算法（CAR） 輸入：[DT=] 輸出：redu 1： LET[lef=A；B=?； γUB=0]； 2： 計算[γUA] 3： WHILE[γUB<γUA]，DO 4：[a={a∈lef|γUB∪a=maxγUB∪ai，ai∈lef}；] 5：[B=B∪a；]

6： [lef=lef-a] 7： ENDWHILE 8： LET[redu=B， i=0] 9： WHILE[ i

在該算法中，第一個while循環(huán)中每次迭代找到一個具有最大依賴度增量的屬性，在第二個while循環(huán)中刪除其中的冗余屬性。不管是一個while循環(huán)，還是第二個while循環(huán)。每次迭代均需在整個數(shù)據(jù)集的所有的示例上計算依賴度，該計算的復(fù)雜度為[O（n2）]。因此，當(dāng)數(shù)據(jù)規(guī)模巨大時，該經(jīng)典的約簡算法效率低下甚至不可行。

2 隨機粗糙集

經(jīng)典的模糊粗糙集的下近似的幾何意義為：對于[? x∈U]，其下近似值是到異類點的最小距離。而這意味著計算任意示例的下近似值的計算需要遍歷整個數(shù)據(jù)集的所有示例。當(dāng)數(shù)據(jù)規(guī)模變得巨大時，計算開銷巨大。因此本文拚棄遍歷所有的示例的做法，而是隨機抽取一定的示例，構(gòu)成樣本集，計算樣本集上的隨機近似值。并討論其性質(zhì)，分析隨機近似算子與經(jīng)典算子之間的關(guān)系。

定義 2.1：給定一個決策表[DT=]，從[U]中隨機抽取[n]個示例構(gòu)成一個樣本S， 則[?B?A]，[?x∈S]，x屬于[Di]的隨機下、上近似的定義如下：

[RBDix=infu∈Smax1-rBx，u，Diu]；

[RBDix=supu∈Smin {rBx，u，Di（u）}].

備注：為保持類標的分布不變，在本文隨機抽樣一般采用比例分層抽樣法。即樣本S上的類標比例與總體[U]上的類標比例一致。

隨機約簡可以定義為如下形式：

定義 2.2：給定決策表[DT=]，在論域中隨機抽樣得到若干樣本[S={S1，S2，…，Sn}]；已知屬性子集[B?A]，若B滿足下述條件，那么，稱B為一個隨機約簡（其中[α∈[0，1]]）。

（1） [?Si∈S，γSiA-γSiB<α]；

（2） [?Bi∈B，?Si∈S，γSiA-γSiB-Bi<α]

定義2.2定義了一個使得辨識信息在多個樣本上依賴度幾乎不變的最小條件屬性子集。

3 隨機約簡算法

在經(jīng)典算法中，每次迭代中添加屬性需要在U上做全量的計算，找到某一個屬性使得依賴度增加最大。如果U規(guī)模很大，那么在每次迭代的時間代價很大，針對這一問題，基于以上提出的隨機粗糙約簡的定義，我們提出一個隨機約簡算法（RAR）。

在RAR中，從論域中按照分層比例抽樣的方式抽取了足夠大的樣本集，在這個樣本集上前向搜索。找到使得依賴度增加最大的那個屬性，添加到約簡中；最終在N次抽樣后，基于約簡的隨機依賴度和基于全部屬性的隨機依賴度相差不大時，我們認為找到了一個隨機約簡。具體過程如下算法 2。

[算法2：隨機約簡算法（RAR） 輸入：[DT=]， [N]（終止輪次），[ k]（樣本數(shù)），

[f1]（樣本合格閾值），[f2]（結(jié)果合格閾值） 輸出：redu 1：LET[lef=A；redu=?；repeat=0；γp=0]； 2：WHILE [repeatγp and |γc-γpγc|

9：End IF 10：ELSE 11：[redu=redu∪a；] 12：[lef=lef-a；] 13：[γp=γc；]

14：[repeat=0]；

15：ENDIF 16：ENDWHILE 17：RETURNredu； ]

算法2（RAR）的設(shè)計基于最大相關(guān)和最小冗余的思想。最大相關(guān)通過尋找在每次迭代中依賴度增量最大的屬性實現(xiàn)。最小冗余通過選擇信息交叉最小的樣本來實現(xiàn)。

RAR算法區(qū)別于CAR的不同之處在于，其兩者有著不同的終止條件，并且在每次迭代的過程中，只是在抽樣所得的樣本上進行計算，這就大大減少了每次迭代的計算；在CAR中，計算[γUB]的時間復(fù)雜度為[O（U2）]。在每迭代中，都需要遍歷全部的候選屬性集lef=A。因此，在每次迭代中找到一個候選屬性的時間復(fù)雜[O（|A|U2]）。而在RAR中，計算[γSB]的時間復(fù)雜度為[O（S2]），因而，在RAR中，每次迭代找到一個候選屬性的時間復(fù)雜度為[O（AS2）]。