基于抽樣的隨機(jī)約簡(jiǎn)算法

張照星　劉威　張鵬　范英　康凱　劉陽(yáng)明　施一琳　徐驍

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）33-0013-03

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

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

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

1 模糊粗糙集及其約簡(jiǎn)

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

1.1 模糊粗糙集

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

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

定義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)系，它滿足自反性、對(duì)稱性和三角傳遞性。

如果A是可以模糊化的（如連續(xù)值屬性），那么決策表DT=表示的是一個(gè)模糊決策表。在模糊決策表上，粗糙集被推廣為模糊粗糙集。模糊粗糙集是融合了粗糙集和模糊集的概念而提出的理論。模糊粗糙集不僅將近似對(duì)象從離散集擴(kuò)展到了模糊集，而且將等價(jià)關(guān)系擴(kuò)展到了模糊相似關(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（?，?）]下的具體的形式，它的幾何意義為示例的下近似是距離其最近的異類點(diǎn)的距離，上近似是距離其最遠(yuǎn)的同類點(diǎn)的相似度。為了便于理解，本文的接下來(lái)的工作均是基于定義2的模糊粗糙集展開(kāi)。采用類似的方法，本文的工作可以推廣至一般化的模糊粗糙集。

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

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

[POSUBx=sup0

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

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

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

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

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

1.2 基于依賴度的屬性約簡(jiǎn)算法

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

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

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

（2）[γUB=γUA；]

此時(shí)，我們稱B是模糊決策表的一個(gè)約簡(jiǎn)。

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

[算法1：經(jīng)典約簡(jiǎn)算法（CAR） 輸入：[DT=] 輸出：redu 1： LET[lef=A；B=?； γUB=0]； 2： 計(jì)算[γ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

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

2 隨機(jī)粗糙集

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

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

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

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

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

隨機(jī)約簡(jiǎn)可以定義為如下形式：

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

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

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

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

3 隨機(jī)約簡(jiǎn)算法

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

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

[算法2：隨機(jī)約簡(jiǎn)算法（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è)計(jì)基于最大相關(guān)和最小冗余的思想。最大相關(guān)通過(guò)尋找在每次迭代中依賴度增量最大的屬性實(shí)現(xiàn)。最小冗余通過(guò)選擇信息交叉最小的樣本來(lái)實(shí)現(xiàn)。

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