F-粗糙集視角的概念漂移與屬性約簡(jiǎn)

鄧大勇 李亞楠 黃厚寬

現(xiàn)實(shí)中的數(shù)據(jù)往往隨著時(shí)間推移而變化,例如,證券交易數(shù)據(jù)、微博、微信、視頻、傳感器數(shù)據(jù)等,這種類型的數(shù)據(jù)稱為數(shù)據(jù)流[1].數(shù)據(jù)流具有按照時(shí)間順序排列、快速變化、海量甚至無限,并且可能出現(xiàn)概念漂移現(xiàn)象等特征[2?3].概念漂移目前尚無統(tǒng)一定義,是指數(shù)據(jù)流中概念(或目標(biāo)變量的統(tǒng)計(jì)特性)的不穩(wěn)定性、不確定性,以及隨著時(shí)間變化而變化的特征.數(shù)據(jù)流挖掘是當(dāng)前數(shù)據(jù)挖掘研究的一個(gè)熱點(diǎn),數(shù)據(jù)流分類和概念漂移探測(cè)是當(dāng)前數(shù)據(jù)流挖掘的主要研究方向.

數(shù)據(jù)流的分類策略主要有:單一分類器[4?6]和集成分類器[3,7?11].概念漂移的探測(cè)準(zhǔn)則主要有:分類準(zhǔn)確率和聯(lián)合概率.無論是單一分類器還是集成分類器都常用分類準(zhǔn)確率(或分類錯(cuò)誤率)判斷概念漂移,將分類準(zhǔn)確率低的分類器進(jìn)行淘汰或改進(jìn),從而提高分類效率.除了分類準(zhǔn)確率外,聯(lián)合概率也常用于探測(cè)概念漂移[12?14].分類準(zhǔn)確率往往用于通過實(shí)驗(yàn)分析探測(cè)概念漂移,聯(lián)合概率則往往用于從理論上對(duì)概念漂移進(jìn)行分析或探測(cè).

粗糙集理論[15?17]是一種處理不精確、不完全、含糊數(shù)據(jù)的有效數(shù)學(xué)工具,是數(shù)據(jù)挖掘和分類的重要方法.屬性約簡(jiǎn)與不確定性分析是粗糙集理論的兩個(gè)重要應(yīng)用.傳統(tǒng)的粗糙集理論不太適合研究海量的、動(dòng)態(tài)變化的數(shù)據(jù),也不太適合研究數(shù)據(jù)流;F-粗糙集[18?19]是第一個(gè)動(dòng)態(tài)粗糙集模型,它將粗糙理論從單個(gè)信息表或決策表推廣到多個(gè).與F-粗糙集相對(duì)應(yīng)的屬性約簡(jiǎn)方法是并行約簡(jiǎn).F-粗糙集和并行約簡(jiǎn)比較適合研究動(dòng)態(tài)變化的數(shù)據(jù),能夠研究數(shù)據(jù)流和概念漂移.

利用粗糙集理論研究數(shù)據(jù)流和概念漂移比較少見.文獻(xiàn)[20?21]利用粗糙集上下近似的變化去度量概念漂移,這種從數(shù)據(jù)的結(jié)構(gòu)角度度量概念漂移的方法,難以進(jìn)行移植和擴(kuò)展,也難以推廣應(yīng)用;文獻(xiàn)[22]把每個(gè)滑動(dòng)窗口看成是一個(gè)決策子表,利用F-粗糙集和并行約簡(jiǎn)的方法整體刪除冗余屬性,通過比較不同子表之間的屬性重要性變化探測(cè)概念漂移,不受上下近似結(jié)構(gòu)的限制,具有很好的移植性和擴(kuò)展性.除了并行約簡(jiǎn)之外,粗糙集理論中還有很多種類的約簡(jiǎn),例如,Pawlak約簡(jiǎn)、互信息約簡(jiǎn)[23]、條件熵約簡(jiǎn)[24?25]等.粗糙集屬性約簡(jiǎn)準(zhǔn)則往往是不確定性分析的有力工具,例如,對(duì)應(yīng)Pawlak約簡(jiǎn)、互信息約簡(jiǎn)、條件熵約簡(jiǎn)等的屬性依賴度、互信息、條件熵等,都是粗糙集理論分析數(shù)據(jù)不確定性的有力工具.但是,能否直接用粗糙集屬性約簡(jiǎn)準(zhǔn)則探測(cè)概念漂移？屬性約簡(jiǎn)與概念漂移有什么關(guān)系？受文獻(xiàn)[22]啟發(fā),本文努力揭示粗糙集理論的屬性約簡(jiǎn)和概念漂移之間的內(nèi)在聯(lián)系.

本文首先從概念漂移的角度討論了粗糙集的屬性約簡(jiǎn)與概念漂移之間的聯(lián)系和區(qū)別;其次,探討粗糙集屬性約簡(jiǎn)觀點(diǎn)下的概念漂移準(zhǔn)則與傳統(tǒng)的概念漂移準(zhǔn)則(包括分類準(zhǔn)確率和聯(lián)合概率)之間的區(qū)別與聯(lián)系.在此基礎(chǔ)上,提出了屬性依賴度和條件熵的概念漂移探測(cè)準(zhǔn)則,分析了條件熵和聯(lián)合概率在探測(cè)概念漂移方面的聯(lián)系.理論分析和實(shí)驗(yàn)結(jié)果顯示,與分類準(zhǔn)確率一樣,屬性依賴度和條件熵能有效地探測(cè)概念漂移.屬性依賴度和條件熵具有聯(lián)合概率進(jìn)行理論分析的優(yōu)點(diǎn),又具有分類準(zhǔn)確率進(jìn)行實(shí)驗(yàn)分析比較的優(yōu)點(diǎn),并且可以增加可重用性、減少工作量.

1 基礎(chǔ)知識(shí)

本節(jié)簡(jiǎn)單介紹粗糙集[15?17]、F-粗糙集和并行約簡(jiǎn)[18?19]的基本知識(shí).

1.1 粗糙集

IS=(U,A)是一個(gè)信息系統(tǒng),其中U是論域,A是論域U上的條件屬性集.對(duì)于每個(gè)屬性a∈A都對(duì)應(yīng)一個(gè)函數(shù)a:U→Va,Va稱為屬性a的值域,U中每個(gè)元素稱為個(gè)體、對(duì)象或行.

對(duì)于每一個(gè)屬性子集B?A和任何個(gè)體x∈U都對(duì)應(yīng)一個(gè)如下的信息函數(shù):

B-不分明關(guān)系(或稱為不可區(qū)分關(guān)系)定義為

任何滿足關(guān)系IND(B)的兩個(gè)元素x,y都不能由屬性子集B區(qū)分,[x]B表示由x引導(dǎo)的IND(B)等價(jià)類.

對(duì)于信息系統(tǒng)IS=(U,A)、屬性子集B?A和概念X?U,有

分別稱為B-下近似和B-上近似.B-下近似也稱為正區(qū)域,記為POSB(X).序偶稱為粗糙集.

在決策系統(tǒng)DS=(U,A,d)中,決策屬性d將論域U劃分為塊,U/j5i0abt0b={Y1,Y2,···,YM},其中Yi(i=1,2,···,M) 是等價(jià)類. 決策系統(tǒng)DS=(U,A,d)的正區(qū)域定義為POSA(d)

有時(shí)決策系統(tǒng)DS=(U,A,d)的正區(qū)域POSA(d)也記為POSA(DS,d)或POS(DS,A,d).

定義1[15?17].在決策系統(tǒng)DS=(U,A,d)中,稱決策屬性d以程度h(0≤h≤1)依賴條件屬性集A,其中,

符號(hào)|·|表示集合的勢(shì).

1.2 F-粗糙集

F-粗糙集[18?19]和其他任何粗糙集模型不同,它是關(guān)于信息系統(tǒng)簇或決策系統(tǒng)簇的粗糙集模型,這個(gè)粗糙集模型比較適合并行計(jì)算,也適合研究事物的動(dòng)態(tài)變化.

下面用FIS={ISi}(i=1,2,···,n) 表示與決策系統(tǒng)簇F={DTi}相對(duì)應(yīng)的信息系統(tǒng)簇,其中ISi=(Ui,A),DTi=(Ui,A,d).

定義2[18?19].假設(shè)X是一個(gè)在不同情形下可能發(fā)生變化的概念(即X是一個(gè)概念變量),N是一種情形,X|N表示在情形N下的概念X.在一個(gè)信息系統(tǒng)簇中,.如果不引起混淆,X|N可以縮寫為X.

假設(shè)X是信息系統(tǒng)簇FIS中的一個(gè)概念,那么X關(guān)于屬性子集B?A的上近似、下近似、邊界線區(qū)域和負(fù)區(qū)域的定義如下:

概念X關(guān)于信息系統(tǒng)簇FIS的上下近似、邊界線區(qū)域、負(fù)區(qū)域分別是FIS中的信息子系統(tǒng)關(guān)于概念X的上下近似、邊界線區(qū)域、負(fù)區(qū)域組成的集合.序偶稱為F-粗糙集.如果則稱序偶是精確的.

定義3[18?19].設(shè)F是一個(gè)決策系統(tǒng)簇,F的正區(qū)域定義如下:

定義4[18?19].設(shè)F是一個(gè)決策系統(tǒng)簇,稱B?A為F的并行約簡(jiǎn)當(dāng)且僅當(dāng)滿足下面條件:

1)POS(F,B,d)=POS(F,A,d);

2)對(duì)任意S?B,都有.

2 概念漂移準(zhǔn)則分析與比較

概念漂移的評(píng)判準(zhǔn)則主要分析比較以下三種:

1)分類準(zhǔn)確率(或分類錯(cuò)誤率).如果分類器對(duì)數(shù)據(jù)集的分類準(zhǔn)確率有較大的變化,一般情況下是指分類準(zhǔn)確率下降,而且超過了一定的閾值,則稱發(fā)生了概念漂移.分類準(zhǔn)確率是最常用的一種概念漂移探測(cè)準(zhǔn)則,常常用于實(shí)驗(yàn)分析中.

使用分類準(zhǔn)確率的變化判斷是否發(fā)生概念漂移,是一種使用概念漂移的結(jié)果進(jìn)行判斷的方法,也是使用最廣泛的方法.這種方法依賴實(shí)驗(yàn)或?qū)嶋H應(yīng)用,能夠從總體上把握概念漂移,無論是在單一分類器還是集成分類器中都使用最廣泛.但是,對(duì)于同一訓(xùn)練集得到的分類器,對(duì)于同一測(cè)試集,如果特征選擇不同,則實(shí)驗(yàn)結(jié)果可能不同.

2)聯(lián)合概率.聯(lián)合概率p(X,Y)=p(X)p(Y|X)(其中,X表示由條件屬性誘導(dǎo)的概念,Y表示由決策屬性誘導(dǎo)的概念)發(fā)生變化,而且超過一定的閾值.用聯(lián)合概率作為概念漂移檢測(cè)準(zhǔn)則又分為虛擬漂移和真實(shí)漂移.虛擬漂移[12,14]是指在聯(lián)合概率中p(Y|X)不發(fā)生變化,僅p(X)變化;真實(shí)漂移[13?14]是指在聯(lián)合概率中p(X)不發(fā)生變化,而p(Y|X)發(fā)生變化.

聯(lián)合概率的準(zhǔn)則也較常用.這種準(zhǔn)則因?yàn)橛休^強(qiáng)的數(shù)學(xué)理論基礎(chǔ)(統(tǒng)計(jì)理論與概率論),所以,從理論方面研討概念漂移,人們喜歡使用聯(lián)合概率的準(zhǔn)則.但是,這個(gè)準(zhǔn)則局限于某些概念,缺乏靈活性,對(duì)于整個(gè)數(shù)據(jù)集而言就不太實(shí)用.這是因?yàn)槁?lián)合概率p(X,Y)只能針對(duì)某些特定的研究其變化,而整個(gè)數(shù)據(jù)集可能是一系列的有序?qū)?它們的概率分布并不相同,也很難用同一個(gè)表達(dá)式表示,如果用聯(lián)合概率p(X,Y)研究其變化,難以從總體上把握概念漂移.

3)屬性重要性.用屬性重要性變化探測(cè)概念漂移是文獻(xiàn)[22]新提出來的.屬性重要性是數(shù)據(jù)的內(nèi)部屬性,是概念的內(nèi)涵.用屬性重要性準(zhǔn)則探測(cè)概念漂移,分析屬性重要性隨著數(shù)據(jù)的變化而變化,不直接依賴于概念的外延,而且用并行約簡(jiǎn)進(jìn)行特征選擇,統(tǒng)一了比較準(zhǔn)則,避免了特征選擇不同對(duì)概念漂移探測(cè)產(chǎn)生的負(fù)面影響,所以,用屬性重要性準(zhǔn)則探測(cè)概念漂移,既有確定性,又有靈活性;既能用于實(shí)驗(yàn)檢測(cè),又能用于理論分析,兼具有分類準(zhǔn)確率準(zhǔn)則和聯(lián)合概率準(zhǔn)則的優(yōu)點(diǎn).

文獻(xiàn)[22]定義的基于屬性重要性的概念漂移準(zhǔn)則,探測(cè)了并行約簡(jiǎn)后各個(gè)屬性重要性的變化而引起的概念漂移,但是文獻(xiàn)[22]中單個(gè)屬性重要性的變化不能全面反映數(shù)據(jù)流中的概念漂移.為了更好地與分類準(zhǔn)確率、聯(lián)合概率分布進(jìn)行比較,本文定義和使用屬性依賴度和條件熵作為概念漂移探測(cè)準(zhǔn)則.

3 屬性約簡(jiǎn)與概念漂移的對(duì)比與分析

粗糙集中有很多種類的屬性約簡(jiǎn),其中最常用的是基于正區(qū)域的屬性約簡(jiǎn)和基于互信息的屬性約簡(jiǎn).這些屬性約簡(jiǎn)的準(zhǔn)則,從概念漂移的角度看,就是在同一數(shù)據(jù)集中保持在屬性約簡(jiǎn)準(zhǔn)則下不發(fā)生概念漂移的最小屬性子集.但是各種準(zhǔn)則并不一定兼容,有時(shí)一個(gè)準(zhǔn)則可能違背另一個(gè)準(zhǔn)則,也就是說,在一個(gè)準(zhǔn)則下不發(fā)生概念漂移的約簡(jiǎn),在另一個(gè)準(zhǔn)則下可能發(fā)生概念漂移.實(shí)際上,基于互信息的屬性約簡(jiǎn)等價(jià)于基于條件熵的屬性約簡(jiǎn),但是因?yàn)闂l件熵比互信息更接近聯(lián)合概率,所以,本文以基于正區(qū)域的屬性約簡(jiǎn)和基于條件熵的屬性約簡(jiǎn)為例進(jìn)行闡述.

定義5[15?17].給定一個(gè)決策系統(tǒng)DS=(U,A,d),B?A稱作決策系統(tǒng)DS的一個(gè)約簡(jiǎn)當(dāng)且僅當(dāng)B滿足如下兩個(gè)條件:

1)POS(DS,B,d)=POS(DS,A,d);

2)對(duì)任意S?B,都有POS(DS,S,d)(DS,A,d).

定義6[15?17].給定一個(gè)決策系統(tǒng)DS=(U,A,d),B?A稱作決策系統(tǒng)DS的一個(gè)約簡(jiǎn),當(dāng)且僅當(dāng)B滿足如下兩個(gè)條件:

1)γ(DS,B,d)=γ(DS,A,d);

2)對(duì)任意的S?B,均有γ(DS,S,d)(DS,A,d).

定義5從正區(qū)域的結(jié)構(gòu)出發(fā)定義了屬性約簡(jiǎn),定義6從屬性依賴度角度定義了屬性約簡(jiǎn);定義5適合理解,定義6適合計(jì)算.從概念漂移角度看,定義5的條件屬性約簡(jiǎn)保證決策系統(tǒng)正區(qū)域不發(fā)生改變,保證正區(qū)域部分的條件概率p(Y|X)=1,即正區(qū)域部分不發(fā)生真實(shí)概念漂移;定義6的條件屬性約簡(jiǎn)保證了決策系統(tǒng)的屬性依賴度不發(fā)生概念漂移;定義5只適合于單個(gè)決策表本身,不適合推廣.定義6可以從決策子表簇角度進(jìn)行推廣,適合于探測(cè)決策子表簇中概念漂移.所以,在決策子表簇中可以將基于屬性依賴性的概念漂移準(zhǔn)則定義如下:

定義7.在決策子表簇F中,DTi,DTj∈F相對(duì)于屬性依賴度的概念漂移定義為

定義8[24?25].給定一個(gè)決策系統(tǒng)DS=(U A,d),設(shè)A和j5i0abt0b在論域U上導(dǎo)出的劃分分別為X和Y,其中,的信息熵分別定義為

j5i0abt0b相對(duì)于A的條件熵定義為

定義9[24?25].給定一個(gè)決策系統(tǒng)DS=(U,A,d),若B?A滿足下列兩個(gè)條件:

1)H(DS,j5i0abt0b|A)=H(DS,j5i0abt0b|B);

2)對(duì)任意b∈B,都有H(DS,j5i0abt0b|B)

則稱B是A的一個(gè)基于條件熵的相對(duì)約簡(jiǎn).

定理1.給定一個(gè)決策系統(tǒng)DS=(U,A,d),B1?B2?A,由B1,B2導(dǎo)出的劃分分別為U/B1={X1,X2,···,XN},U/B2={X1',X2',···,XM'},則聯(lián)合概率有如下關(guān)系:p(Xl',Yj)≤p(Xk,Yj),其中Xl'=[x]B2∈U/B2,Xk=[x]B1∈U/B1,Yj∈U/j5i0abt0b.

證明.對(duì)于中的每一塊,要么等于中的某一塊,要么是某幾塊的并.不失一般性,有,所以有,即

關(guān)于在一個(gè)系統(tǒng)中的條件熵隨條件屬性的變化,有下面引理:

引理1[25].給定一個(gè)決策系統(tǒng)DS=(U,A,d),B1?B2?A,則有

成立.

定理1和引理1說明,在一個(gè)決策系統(tǒng)中,聯(lián)合概率與條件熵都是隨著條件屬性的增加而單調(diào)不增.根據(jù)文獻(xiàn)[26]的屬性約簡(jiǎn)準(zhǔn)則,條件熵可以作為屬性約簡(jiǎn)的準(zhǔn)則,聯(lián)合概率也可以作為屬性約簡(jiǎn)的準(zhǔn)則;類似地,聯(lián)合概率可以作為概念漂移的準(zhǔn)則,條件熵也可以作為概念漂移的準(zhǔn)則.

定義10.在決策子表簇F中,DTi,DTj∈F相對(duì)于條件熵的概念漂移定義為

定理2.在決策子表簇F中,B?A是F相對(duì)于條件熵的并行約簡(jiǎn),DTi,DTj∈F,則約簡(jiǎn)后相對(duì)于條件熵的概念漂移等于約簡(jiǎn)前的概念漂移,即

定理3.在決策子表簇F中,B?A是F相對(duì)于屬性依賴度的并行約簡(jiǎn),DTi,DTj∈F,則約簡(jiǎn)后相對(duì)于屬性依賴度的概念漂移等于約簡(jiǎn)前的概念漂移,即

定理2和定理3根據(jù)相關(guān)定義可以非常容易證明.定理2和定理3說明,在條件熵和屬性依賴度等屬性約簡(jiǎn)的條件下,并行約簡(jiǎn)不會(huì)影響概念漂移的度量和探測(cè),并且并行約簡(jiǎn)可以將冗余屬性刪除,減少計(jì)算量,彰顯對(duì)概念漂移發(fā)生起作用的條件屬性.

通過以上分析和論述,粗糙集和F-粗糙集的屬性約簡(jiǎn)準(zhǔn)則可以推廣用于概念漂移的度量和探測(cè).概念漂移和屬性約簡(jiǎn)存在一定的內(nèi)在聯(lián)系,屬性約簡(jiǎn)是保證單個(gè)決策表或決策表簇內(nèi)部不發(fā)生概念漂移的最小屬性子集,而一般情況下的概念漂移則是不同的數(shù)據(jù)集或變化的數(shù)據(jù)集之間某種度量發(fā)生變化而產(chǎn)生的.

定義11.在決策子表簇F中,,其中,并設(shè)內(nèi)涵相同(即它們對(duì)應(yīng)的屬性值相等),則的條件熵概念漂移定義為

下面討論聯(lián)合概率與條件熵在探測(cè)概念漂移方面的關(guān)系.

定理4.在決策子表簇F中,,其中,并設(shè)X與X'、Y與Y'內(nèi)涵相同(對(duì)應(yīng)的屬性值相等).用聯(lián)合概率準(zhǔn)則探測(cè)發(fā)生虛擬概念漂移,則用條件熵準(zhǔn)則也發(fā)生虛擬概念漂移;若用聯(lián)合概率準(zhǔn)則發(fā)生真實(shí)概念漂移,則用條件熵準(zhǔn)則也同樣發(fā)生真實(shí)概念漂移.

證明.反設(shè)用聯(lián)合概率準(zhǔn)則沒有發(fā)生概念漂移,即,

1)在p(X)不變,即的情況下:

2)在p(Y|X)不變,即的情況下.

定理4說明,用聯(lián)合概率分布能探測(cè)到的虛擬概念漂移和真實(shí)概念漂移都能用條件熵探測(cè).從上述推理過程可知,定理4的逆定理也成立.

例1.設(shè)F={DT1,DT2},如表1和表2所示.a,b,c是條件屬性,d是決策屬性.

表1 決策子系統(tǒng)DT1Table 1 A decision subsystemDT1

表2 決策子系統(tǒng)DT2Table 2 A decision subsystemDT2

顯然,F的并行約簡(jiǎn)為

于是,

從例1可以看出,無論是從屬性依賴度還是從條件熵的角度,只要選取的參數(shù)δ<1/3,兩種標(biāo)準(zhǔn)都發(fā)生了概念漂移.

由此可見,概念漂移和屬性約簡(jiǎn)具有內(nèi)在的聯(lián)系.概念漂移探測(cè)的有些準(zhǔn)則(例如聯(lián)合概率)能夠用于屬性約簡(jiǎn),反過來,屬性約簡(jiǎn)的準(zhǔn)則(例如屬性依賴度和條件熵)也能用于概念漂移探測(cè).屬性約簡(jiǎn)就是保證某種準(zhǔn)則下不發(fā)生概念漂移的刪除冗余屬性過程.然而,作為不確定性度量指標(biāo)的屬性依賴度僅考慮正區(qū)域部分的數(shù)據(jù),不考慮非正區(qū)域部分的數(shù)據(jù),無論是在屬性約簡(jiǎn)方面還是在探測(cè)概念漂移方面都忽略了非正區(qū)域數(shù)據(jù)的變化;而條件熵則把所有的數(shù)據(jù)都考慮在內(nèi),在屬性約簡(jiǎn)和概念漂移探測(cè)上全盤考慮了數(shù)據(jù)的變化.所以,我們推測(cè),大部分條件屬性約簡(jiǎn)準(zhǔn)則能夠用于概念漂移探測(cè),能夠用于數(shù)據(jù)流概念漂移探測(cè)的屬性約簡(jiǎn)準(zhǔn)則應(yīng)該滿足不依賴于數(shù)據(jù)的結(jié)構(gòu),但不同的不確定性指標(biāo)在屬性約簡(jiǎn)和概念漂移探測(cè)方面各具特色.深入分析其他的屬性約簡(jiǎn)準(zhǔn)則是否能夠用于概念漂移探測(cè),以及研究它們?cè)诟拍钇铺綔y(cè)方面的區(qū)別與聯(lián)系,是我們下一步研究的內(nèi)容.

下一節(jié)將通過實(shí)驗(yàn)比較屬性依賴度、條件熵和兩種特征選擇(屬性約簡(jiǎn))后的分類準(zhǔn)確率作為概念漂移探測(cè)準(zhǔn)則.這兩種特征選擇分別是基于屬性依賴度的屬性約簡(jiǎn)和基于條件熵的屬性約簡(jiǎn).

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)為KDD-CUP991http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)10%的子集.該數(shù)據(jù)包含494021條記錄,42個(gè)屬性.實(shí)驗(yàn)中滑動(dòng)窗口的大小分別為5000和10000,相鄰窗口之間有或無10%的重復(fù)率,實(shí)驗(yàn)中將第一個(gè)數(shù)據(jù)集(滑動(dòng)窗口)當(dāng)成訓(xùn)練集,其余的數(shù)據(jù)集都是測(cè)試集.

理論分析和實(shí)驗(yàn)結(jié)果顯示,分類準(zhǔn)確率和屬性依賴度都屬于[0,1],而條件熵的值可以大于1,實(shí)驗(yàn)結(jié)果也證實(shí)了這一點(diǎn).

圖1～4雖然只是顯示了這幾種準(zhǔn)則相對(duì)于訓(xùn)練集的值,沒有直接顯示概念漂移,但只要這些指標(biāo)數(shù)值和訓(xùn)練集相應(yīng)的指標(biāo)數(shù)值相減,然后取絕對(duì)值,并與閾值(可以根據(jù)需要自己設(shè)定)進(jìn)行比較,就可以很容易判定是否發(fā)生概念漂移.而且圖1～4非常明顯地顯示,特征選擇不同,對(duì)同一個(gè)數(shù)據(jù)集的分類準(zhǔn)確率不同.

圖1～4顯示基于屬性重要度/條件熵的分類準(zhǔn)確率和屬性依賴度的整體變化趨勢(shì)不如條件熵明顯,所以條件熵能更加準(zhǔn)確地探測(cè)概念漂移.

圖1顯示在第10～27個(gè)滑動(dòng)窗口,基于屬性重要度/條件熵的分類準(zhǔn)確率的值為0,屬性依賴度的值接近于0,變化趨勢(shì)不明顯,均不利于探測(cè)概念漂移;在第10～22個(gè)滑動(dòng)窗口,條件熵的變化也不明顯,但在探測(cè)概念漂移過程中,條件熵優(yōu)于分類準(zhǔn)確率和屬性依賴度.

圖2顯示在第25～43個(gè)滑動(dòng)窗口,基于屬性重要度/條件熵的分類準(zhǔn)確率的值為0,屬性依賴度的值接近于0,變化趨勢(shì)很不明顯,不利于探測(cè)概念漂移;雖然在第32～38個(gè)滑動(dòng)窗口,條件熵的變化趨勢(shì)很小,但是在探測(cè)概念漂移的過程中,條件熵優(yōu)于上述三種方法.

圖3顯示在第30～50個(gè)滑動(dòng)窗口,基于屬性重要度/條件熵的分類準(zhǔn)確率的值為0;在第35～65個(gè)滑動(dòng)窗口,屬性依賴度的值趨近于0,且變化趨勢(shì)不大;在第40～50個(gè)滑動(dòng)窗口,條件熵的變化趨勢(shì)也不明顯.但是,條件熵變化不明顯的滑動(dòng)窗口數(shù)目較少,因此,條件熵作為概念漂移的探測(cè)準(zhǔn)則較優(yōu).

圖4顯示在第15～33個(gè)滑動(dòng)窗口,基于屬性重要度/條件熵的分類準(zhǔn)確率的值為0,屬性依賴度的變化較小,均不利于探測(cè)是否發(fā)生了概念漂移;條件熵的變化能有效的探測(cè)概念漂移.

圖1 滑動(dòng)窗口的大小為10000,且相鄰窗口之間沒有重復(fù)Fig.1 The size of sliding windows is 10000 without repeat

圖2 滑動(dòng)窗口的大小為5000,且相鄰窗口之間沒有重復(fù)Fig.2 The size of sliding windows is 5000 without repeat

圖3 滑動(dòng)窗口的大小為5000,且相鄰窗口之間有10%的重復(fù)Fig.3 The size of sliding windows is 5000 with 10%repeat

圖4 滑動(dòng)窗口的大小為10000,且相臨窗口之間有10%的重復(fù)Fig.4 The size of sliding windows is 10000 with 10%repeat

從圖1～4可以看出,使用這些指標(biāo)都可以在一定的程度上判定是否發(fā)生概念漂移,但分類準(zhǔn)確率只能與訓(xùn)練集比較,相鄰兩個(gè)滑動(dòng)窗口(數(shù)據(jù)集)之間相對(duì)于分類準(zhǔn)確率是否發(fā)生概念漂移,只能以一個(gè)為訓(xùn)練集,另一個(gè)為測(cè)試集,工作量相當(dāng)大,而且沒有對(duì)稱性;如果將兩個(gè)相鄰滑動(dòng)窗口相對(duì)于訓(xùn)練集的分類準(zhǔn)確率之差進(jìn)行概念漂移探測(cè),那么很多時(shí)候都不利于探測(cè)概念漂移.然而使用屬性依賴度和條件熵作為概念漂移的判定標(biāo)準(zhǔn),在元素個(gè)數(shù)和屬性集不發(fā)生變化的情況下,每個(gè)決策表的屬性依賴度和條件熵都是不變的,屬性約簡(jiǎn)也不影響它們的值,任何兩個(gè)數(shù)據(jù)集(滑動(dòng)窗口)之間都可以進(jìn)行比較,而且具有對(duì)稱性和可重用性,從而可以減少工作量.

5 結(jié)論與展望

本文從F-粗糙集和概念漂移的角度,揭示了概念漂移和粗糙集屬性約簡(jiǎn)之間的區(qū)別與聯(lián)系.屬性約簡(jiǎn)是在一個(gè)信息表內(nèi)部保持不發(fā)生概念漂移的最小屬性子集.本文提出了基于屬性依賴度和條件熵的概念漂移探測(cè)準(zhǔn)則,理論分析顯示粗糙集的屬性約簡(jiǎn)準(zhǔn)則大部分都可用于度量概念漂移,屬性依賴度和條件熵具有聯(lián)合概率分布可進(jìn)行理論分析的優(yōu)點(diǎn),又具有分類準(zhǔn)確率可進(jìn)行實(shí)驗(yàn)分析的優(yōu)點(diǎn),即將粗糙集的屬性約簡(jiǎn)準(zhǔn)則用于概念漂移的探測(cè)兼具兩種傳統(tǒng)的的概念漂移準(zhǔn)則的優(yōu)點(diǎn).此外,屬性依賴度和條件熵作為概念漂移探測(cè)準(zhǔn)則還具有對(duì)稱性和可重用性,從而可以減少工作量.所以,F-粗糙集是研究數(shù)據(jù)流分類和概念漂移,進(jìn)行數(shù)據(jù)流分析的非常好的理論和實(shí)踐工具.將F-粗糙集和粗糙集屬性約簡(jiǎn)準(zhǔn)則用于數(shù)據(jù)流挖掘及概念漂移探測(cè),豐富了數(shù)據(jù)流挖掘和概念漂移探測(cè)的工具,同時(shí),對(duì)粗糙集及粒計(jì)算理論的發(fā)展與應(yīng)用將起促進(jìn)作用.

下一步研究重點(diǎn)是將F-粗糙集進(jìn)一步運(yùn)用于概念漂移探測(cè)和數(shù)據(jù)流分類,特別是集成分類器的分類研究,并深入研究這些概念漂移準(zhǔn)則之間的關(guān)系.