張任

　?。ㄕ憬瓗煼洞髮W(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004）

　　摘要：數(shù)據(jù)流挖掘是當(dāng)前數(shù)據(jù)挖掘研究的一個(gè)熱點(diǎn)，并且數(shù)據(jù)流的類型也不盡相同。利用模糊粗糙集和F-粗糙集的基本原理和基本方法，提出了一種對(duì)模糊型數(shù)據(jù)流進(jìn)行模糊并行約簡(jiǎn)、刪除冗余屬性的方法，并運(yùn)用模糊并行約簡(jiǎn)中屬性重要性的變化探測(cè)模糊概念漂移現(xiàn)象。有別于傳統(tǒng)方法，該方法利用模糊數(shù)據(jù)的內(nèi)部本質(zhì)特性對(duì)模糊概念漂移進(jìn)行探測(cè)，并且通過實(shí)例驗(yàn)證其探測(cè)模糊概念漂移的可行性和有效性。

　　關(guān)鍵詞：模糊數(shù)據(jù)流；概念漂移；模糊粗糙集；F-模糊粗糙集；模糊并行約簡(jiǎn)

0引言

　　信息爆炸的今天,現(xiàn)實(shí)中的數(shù)據(jù)往往隨著時(shí)間的變化而變化，例如，電商銷售數(shù)據(jù)、微博數(shù)據(jù)、傳感器數(shù)據(jù)等，這種類型的數(shù)據(jù)稱為數(shù)據(jù)流［1］。數(shù)據(jù)流具有按照時(shí)間順序排列、快速變化、連續(xù)、海量甚至無(wú)限且可能出現(xiàn)概念漂移現(xiàn)象等特征［2-3］。探測(cè)概念漂移常用的技術(shù)是滑動(dòng)窗口技術(shù)［1］。參考文獻(xiàn)［4-6］對(duì)單個(gè)的數(shù)據(jù)塊或單棵決策樹進(jìn)行冗余屬性刪除，沒有從整體上考慮刪除冗余屬性問題，再檢測(cè)概念漂移。參考文獻(xiàn)［7］從整體上考慮刪除冗余屬性問題，但是未能解決數(shù)據(jù)流中模糊屬性約簡(jiǎn)問題。

　　粗糙集理論［8］是一種處理不相容、不精確或不完全數(shù)據(jù)的強(qiáng)有力工具。模糊粗糙集是粗糙集理論的擴(kuò)展研究，它解決了粗糙集約簡(jiǎn)處理之前必需的離散化過程，使得粗糙集也適用于模糊概念和模糊知識(shí)的屬性約簡(jiǎn)?；谀：植诩膶傩约s簡(jiǎn)取得了一定的研究成果［9-12］。傳統(tǒng)的模糊粗糙集理論不太適合研究海量的、動(dòng)態(tài)變化的數(shù)據(jù)，也不太適合研究數(shù)據(jù)流；F-粗糙集［13-14］將粗糙理論從單個(gè)信息表或決策表推廣到多個(gè)，適合研究海量的、動(dòng)態(tài)變化的數(shù)據(jù)，也適合研究數(shù)據(jù)流,F-模糊粗糙集［15］是該理論的擴(kuò)展研究。模糊并行約簡(jiǎn)是與F-模糊粗糙集合相對(duì)應(yīng)的屬性約簡(jiǎn)理論和方法。模糊并行約簡(jiǎn)和F-模糊粗糙集比較適合研究海量的、動(dòng)態(tài)變化的數(shù)據(jù)，也應(yīng)該能夠研究模糊數(shù)據(jù)流和模糊概念漂移。

　　本文首先利用F模糊粗糙集的模糊并行約簡(jiǎn)理論，將模糊數(shù)據(jù)流的各個(gè)滑動(dòng)窗口(子決策表)中對(duì)分類不起作用的冗余模糊屬性整體刪除，然后運(yùn)用各個(gè)子表(滑動(dòng)窗口)中屬性重要性的變化探測(cè)模糊概念漂移。傳統(tǒng)方法主要依靠分類準(zhǔn)確率的變化利用外部特性進(jìn)行比較，探測(cè)概念漂移現(xiàn)象。本文方法與傳統(tǒng)的概念漂移探測(cè)方法不同，利用數(shù)據(jù)的內(nèi)部特性——模糊并行約簡(jiǎn)后屬性重要性的變化探測(cè)模糊概念漂移現(xiàn)象。

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

　　本節(jié)介紹F-模糊粗糙集和模糊并行約簡(jiǎn)［15］的基礎(chǔ)知識(shí)。本文若未特別說明,屬性均表示模糊條件屬性。

　　下面用FIS={ISi}(i=1,2,…,n)表示與模糊決策系統(tǒng)簇DS=(U,A,d)相對(duì)應(yīng)模糊信息系統(tǒng)簇，A是條件屬性集,d是決策屬性集，且屬性對(duì)應(yīng)的是模糊等價(jià)關(guān)系(或簡(jiǎn)寫為關(guān)系)。其中ISi=(Ui,A)，而DSi=(Ui,A,d)。在模糊子信息表ISi中,設(shè)P是論域U的一個(gè)模糊等價(jià)關(guān)系（簡(jiǎn)寫為關(guān)系P），Eij是屬于UiP的模糊等價(jià)類,UiP=GD(P|Ui)={Ei1,Ei2,…,Eici} 表示論域Ui上的一個(gè)模糊劃分(j=1,2,…，ci,ci是由p劃分論域Ui所得模糊等價(jià)類的數(shù)目)。

　　定義1在信息系統(tǒng)簇FIS中,模糊概念X在關(guān)系P下的模糊粗糙上下近似(簡(jiǎn)寫為上下近似)分別為：

　　下近似:μFISX(x)={μPX|U1(x),μPX|U2(x),…,μPX|Un(x)}

　　上近似:μFISX(x)={μPX|U1(x),μPX|U2(x),…,μPX|Un(x)}

　　序偶(P(FIS,X),P(FIS,X))稱為F模糊粗糙集。

　　如果P(FIS,X)=P(FIS,X),則稱序偶(P(FIS,X),P(FIS,X))是精確的。

　　定義2在ISi中條件屬性的模糊等價(jià)類E的模糊正域?yàn)椋?/p>

　　μPOSP(d)(E)=supqj∈U/dμqj(E)

　　x對(duì)模糊正域的隸屬度為：

　　μPOSP(d)(x)=supx∈Uimin{μE(x),μPOSP(d)(E)}

　　其中,j={1,2,…,cj}，cj是由d劃分論域U所得模糊等價(jià)類的數(shù)目,E∈GD(P|Ui)。

　　定義3設(shè)DS=(U,A,d)是一個(gè)決策系統(tǒng)，P(DS)是DS的冪集，F(xiàn)P(DS)，則PA稱為F模糊并行約簡(jiǎn)，當(dāng)且僅當(dāng)PA滿足下面條件：

　　(1)μPOS(F,A,d)=μPOS(F,P,d)；

　　(2)對(duì)任意SP，都有μPOS(F,S,d)≠μPOS(F,A,d)。

2模糊并行約簡(jiǎn)方法對(duì)概念漂移的探測(cè)

　　在F-模糊粗糙集［15］中決策子系統(tǒng)簇F中的元素可以是大數(shù)據(jù)中的一部分，也可以是模糊數(shù)據(jù)流中的一部分或是一個(gè)滑動(dòng)窗口。本文假設(shè)模糊決策子系統(tǒng)簇F中的元素是數(shù)據(jù)流中的一部分，每一個(gè)子表可以看做一個(gè)滑動(dòng)窗口。在探測(cè)模糊概念漂移之前，先用模糊并行約簡(jiǎn)算法刪除對(duì)分類不起作用的冗余模糊屬性，以減少計(jì)算量，并探測(cè)真正使模糊概念發(fā)生漂移的屬性之變化。

　　2.1模糊并行約簡(jiǎn)算法

　　在F-模糊粗糙集中依賴度與屬性重要性的定義如下［15］。

　　定義4在FIS={ISi}(i=1,2,…,n)中決策屬性對(duì)條件屬性集P的依賴度為：

　　定義5給定一個(gè)決策子系統(tǒng)簇F,DTi=(Ui,A,d)∈F(i=1,2,…,n),定義F中屬性a∈P或a∈A－P相對(duì)于P的重要度分別為:

　　σ(P,a)=γ(F,P,d)－γ(F,P－{a},d)或σ′(P,a)=γ(F,P∪a,d)－γ(F,P,d)

　　運(yùn)用屬性重要度可以比較容易地求出并行約簡(jiǎn)，算法如下。算法1基于F模糊屬性重要度的模糊并行約簡(jiǎn)算法(簡(jiǎn)稱FPRAS)輸入：FP(DS);

　　輸出：F的一個(gè)模糊并行約簡(jiǎn);

　?。?）P=;

　　（2）對(duì)于任意a∈A,如果σ(A,a)>0,那么P=P∪{a}；

　　（3）M=A－a；

　?。?）重復(fù)進(jìn)行如下步驟,直到M=:

　?、賹?duì)任意a∈M,計(jì)算σ′(P,a) //σ′(P,a)=γ(F,P∪a,d)－γ(F,P,d);

　　②對(duì)任意a∈M,如果σ′(P,a)≤ξ//1>ξ≥0為給定的閾值，那么M=M－{a};

　?、圻x擇F屬性重要度非零且最大的元素a∈E,P=P∪{a},M=M－{a}(添加屬性集M中F屬性重要度非零且最大的屬性到并行約簡(jiǎn)P中);

　?。?）輸出并行約簡(jiǎn)P。

　　2.2模糊概念漂移探測(cè)

　　通過模糊并行約簡(jiǎn)刪除了數(shù)據(jù)流中對(duì)分類不起作用的冗余模糊屬性。受參考文獻(xiàn)［7，1314］中屬性重要性矩陣的啟發(fā)，建立數(shù)據(jù)流約簡(jiǎn)后的屬性重要性矩陣，用于描述在不同的模糊決策子表(滑動(dòng)窗口)中模糊并行約簡(jiǎn)中的每個(gè)模糊屬性對(duì)分類的貢獻(xiàn)，它的定義如下。

　　定義6DS=(U,A,d)是一個(gè)模糊數(shù)據(jù)流決策系統(tǒng)，P(DS)是DS的冪集，F(xiàn)P(DS)是數(shù)據(jù)流DS=(U,A,d)的若干個(gè)滑動(dòng)窗口的集合，PA是F的模糊并行約簡(jiǎn)，模糊并行約簡(jiǎn)PA關(guān)于F的屬性重要度矩陣定義為：

　　根據(jù)屬性重要性矩陣的定義，很容易證明屬性重要性矩陣的下列屬性。

　　定理1模糊數(shù)據(jù)流決策子表簇FP(DS)中，PA為并行約簡(jiǎn)，模糊屬性重要性矩陣T(P,F)中的元素與模糊屬性重要性矩陣T(A,F)中相應(yīng)的元素有如下關(guān)系：

　?。?）若屬性p∈PA為模糊并行約簡(jiǎn)的核屬性，則p在T(P,F)中對(duì)應(yīng)的元素值小于等于p在T(A,F)中對(duì)應(yīng)的元素值。

　?。?）若屬性p∈PA為模糊并行約簡(jiǎn)的非核屬性，則p在T(P,F)中對(duì)應(yīng)的元素值大于等于p在T(A,F)中對(duì)應(yīng)的元素值。

　　推論模糊數(shù)據(jù)流決策子表簇FP(DS)中，PA為模糊并行約簡(jiǎn)，屬性重要性矩陣T(P,F)中非零元素的個(gè)數(shù)大于等于T(A,F)中非零元素的個(gè)數(shù)。

　　運(yùn)用粗糙集理論對(duì)概念漂移進(jìn)行度量的指標(biāo)［1617］往往依賴于上下近似，這種度量不太適合大小不一致的滑動(dòng)窗口。參考文獻(xiàn)［7］的并行約簡(jiǎn)探測(cè)算法不適合探測(cè)模糊型數(shù)據(jù)流的模糊概念漂移問題。下面運(yùn)用屬性重要性的變化對(duì)模糊概念漂移進(jìn)行度量，它獨(dú)立于上下近似的變化，也獨(dú)立于滑動(dòng)窗口的大小。它的定義如下。

　　定義7模糊數(shù)據(jù)流決策子表簇FP(DS)中，PA為模糊并行約簡(jiǎn)，兩個(gè)滑動(dòng)窗口DTi、DTk∈F相對(duì)于屬性b∈PA的概念漂移定義為：

　　FPRCDb(DTk,DTi)=|σkj－σij|

　　其中，j為屬性b∈PA在T(P,F)中所對(duì)應(yīng)的列。

　　定義8模糊數(shù)據(jù)流決策子表簇FP(DS)中，PA為模糊并行約簡(jiǎn)，DTi、DTk∈F,基于模糊并行約簡(jiǎn)PA的模糊概念漂移量定義為：

　　FPRCDP(DTk,DTi)=1|P|∑|P|j=1|σkj－σij|

　　定理2基于模糊并行約簡(jiǎn)的屬性重要性的模糊概念漂移量FPRCDb(DTk,DTi)和FPRCDp(DTk,DTi)對(duì)稱、非負(fù)、滿足三角不等式。

　　定理3模糊數(shù)據(jù)流決策子表簇FP(DS)中，DTi，DTk∈F,PA為模糊并行約簡(jiǎn)，則T(P,F)中相鄰兩行對(duì)應(yīng)屬性重要性變化的元素個(gè)數(shù)大于等于T(A,F)中相鄰兩行對(duì)應(yīng)屬性重要性變化的元素個(gè)數(shù)。

　　定理1、定理3說明冗余屬性的存在干擾了概念漂移的探測(cè)，刪除了一些冗余屬性后模糊概念漂移更明顯。下面利用基于模糊并行約簡(jiǎn)的模糊概念漂移量來(lái)探測(cè)概念漂移。算法2模糊概念漂移檢測(cè)算法輸入：模糊數(shù)據(jù)流FP(DS)，閾值δ;

　　輸出：模糊數(shù)據(jù)流FP(DS)中是否發(fā)生概念漂移;

　　(1)調(diào)用算法1，求出F的模糊并行約簡(jiǎn)PA；

　　(2)計(jì)算約簡(jiǎn)后F中各個(gè)模糊屬性的重要性，形成模糊屬性重要性矩陣T(P,F)；

　　(3)計(jì)算相鄰兩行之間任意模糊屬性重要性的差異FPRCDb(DTk,DTi)，并算出FPRCDP(DTk,DTi)；

　　(4)模糊概念漂移值FPRCDb(DTk,DTi)、FPRCDp(DTk,DTi)與給定的閾值δ比較，判定是否發(fā)生了概念漂移。

　　閾值δ∈［0,1)的最優(yōu)選取將是下一步的研究方向。通過算法2可知,模糊并行約簡(jiǎn)將模糊決策子表簇作為一個(gè)整體考慮，刪除了模糊決策子表簇中對(duì)分類不起作用的冗余屬性，使得在模糊概念漂移的探測(cè)和分類的時(shí)候減少了計(jì)算量，并將注意力真正集中到對(duì)分類起關(guān)鍵作用的屬性集合上?；谀：⑿屑s簡(jiǎn)探測(cè)概念漂移時(shí)，提供了同樣的模糊屬性和同樣的標(biāo)準(zhǔn)，得到結(jié)論的可理解性與可靠性就會(huì)更加可信。

　　例1模糊決策系統(tǒng)DS=(U,A,d)(如表1所示),U={1,2…,10}為論域,P1、P2、P3為模糊條件屬性,d為模糊決策屬性。F={DSi}(i=1,2)是DS的模糊決策子系統(tǒng) ,FIS={ISi}(i=1,2)是與F相對(duì)應(yīng)的模糊決策系統(tǒng)簇，如表2、表3所示?！　?/p>

　　調(diào)用算法1，很容易得到F的模糊并行約簡(jiǎn)為P={P2,P3}，子表中對(duì)象對(duì)模糊正域的隸屬度如表4所示。表4在子表IS1、IS2中對(duì)象對(duì)模糊正域的隸屬度P1P2P3P1P2P1P3P2P3P1P2P3IS1H1(P)1.82.92.22.92.43.22.7IS2H2(P)1.53.42.83.52.83.83.5

　　模糊屬性重要性矩陣T(A,F)與T(P,F)分別為：

　　DT1與DT2之間的概念漂移為：

　　FPRCDp2(DT2,DT1)=|0.20－0.20|=0

　　FPRCDp3(DT2,DT1)=|0.06－0.10|=0.04

　　FPRCDp(DT2,DT1)=1m∑mj=1|σ2,j－σ1,j|

　　=12(|0.20－0.20|+|0.06－0.10|)=0.02

　　因?yàn)闂l件屬性P1對(duì)分類不起作用，是冗余的屬性，刪除之后，對(duì)分類起作用的屬性P2、P3的概念漂移就彰顯出來(lái)了。如果取δ=0.01，那么相對(duì)于單個(gè)屬性P2、P3具有概念漂移，相對(duì)于整個(gè)并行約簡(jiǎn)P也具有概念漂移；如果取δ=0.05，那么相對(duì)于單個(gè)屬性P2、P3及相對(duì)于并行約簡(jiǎn)P都不具有概念漂移。實(shí)際的數(shù)據(jù)流中，滑動(dòng)窗口一般情況下是多個(gè)，可以類似地求出兩個(gè)相鄰窗口之間的基于模糊并行約簡(jiǎn)的概念漂移量。

3結(jié)論

　　傳統(tǒng)的概念漂移探測(cè)方法不能探測(cè)模糊數(shù)據(jù)流中模糊概念漂移,并且其主要利用分類準(zhǔn)確率的變化對(duì)概念漂移現(xiàn)象進(jìn)行探測(cè)。本文提出了一種基于模糊并行約簡(jiǎn)的概念漂移探測(cè)方法。本文方法利用模糊數(shù)據(jù)的內(nèi)部特性——模糊并行約簡(jiǎn)后的屬性重要性的變化探測(cè)模糊概念漂移現(xiàn)象。

　　下一步的工作是研究模糊并行約簡(jiǎn)探測(cè)模糊概念漂移中δ的最佳取值，以及具體運(yùn)用模糊并行約簡(jiǎn)構(gòu)建分類器，與傳統(tǒng)的概念漂移方法進(jìn)行深入的分析比較。

參考文獻(xiàn)

　?。?］ BABCOCK B, BABU S, DATER M,et al. Models and issues in data stream systems［C］. Proceedings of the 21st ACM SIGACTSIGMODSIGART Sympsium on Principles Database Systems, Madison, USA, 2002:16.

　?。?］ 王濤, 李舟軍, 顏躍進(jìn), 等. 數(shù)據(jù)流挖掘分類技術(shù)綜述［J］. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(11):18091815.

　　［3］ 徐文華, 覃征, 常揚(yáng). 基于半監(jiān)督學(xué)習(xí)的數(shù)據(jù)流集成分類算法［J］. 模式識(shí)別與人工智能, 2012, 25(2): 292299.

　?。?］ Jin Ruoming, AGRAWAL G. Efficient decision tree construction on streaming data［C］.Proceedings of the ACM SIGKDD the 9th International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003:571576.

　?。?］ 辛軼, 郭躬德, 陳黎飛,等. IKnnMDHecoc:一種解決概念漂移問題的方法［J］.計(jì)算機(jī)研究與發(fā)展, 2011, 48(4):592601.

　?。?］ 琚春華，帥朝謙，封毅，基于粒計(jì)算的商業(yè)數(shù)據(jù)流概念漂移特征選擇［J］.南京大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，47(4):391397.

　?。?］ 鄧大勇, 徐小玉, 黃厚寬. 基于并行約簡(jiǎn)的概念漂移探測(cè)［J］. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(5):10711079

　　［8］ PAWLAK Z. Rough sets［J］. International journal of Information and Computer Science, 1982,11(5): 341356.

　?。?］ JENSEN R , Shen Qiang. Fuzzy–rough sets for descriptive dimensionality reduction［C］.Proceedings of 11th International Conference on Fuzzy Systems, Hawaii, 2002: 2934.

　　［10］ 李興寬.集值信息下的粗集與知識(shí)獲?。跩］.微型機(jī)與應(yīng)用,2015,34(23):1415.

　?。?1］ 程昳,苗奪謙,馮琴榮.基于模糊粗糙集的粒度計(jì)算［J］. 計(jì)算機(jī)科學(xué),2007,34(7):142149.

　　［12］ 徐菲菲,苗奪謙,魏萊,等.基于互信息的模糊粗糙集屬性約簡(jiǎn)［J］. 電子與信息學(xué)報(bào)，2008,30(6):13721375.

　?。?3］ 王國(guó)胤, 李德毅, 姚一豫，等.云模型與粒計(jì)算［M］.北京：科學(xué)出版社, 2012.

　　［14］ 陳林. 粗糙集中不同粒度層次下的模糊并行約簡(jiǎn)及決策［D］. 金華：浙江師范大學(xué)，2013.

　?。?5］ 鄧大勇, 徐小玉, 裴明華. F模糊粗糙集及其并行約簡(jiǎn)［J］. 浙江師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 38(1):5866.

　?。?6］ 鄧大勇, 裴明華, 黃厚寬. F粗糙集方法對(duì)概念漂移的度量［J］. 浙江師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 36(3):303308.

　?。?7］ Yao Yiyu. Threeway decision with probabilistic rough sets［J］.Information Sciences, 2010, 180:341353.