基于模糊并行約簡(jiǎn)的模糊概念漂移探測(cè)

張　任

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

?

基于模糊并行約簡(jiǎn)的模糊概念漂移探測(cè)

張任

(浙江師范大學(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è)，并且通過(guò)實(shí)例驗(yàn)證其探測(cè)模糊概念漂移的可行性和有效性。

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

引用格式：張任. 基于模糊并行約簡(jiǎn)的模糊概念漂移探測(cè)[J].微型機(jī)與應(yīng)用，2016,35(12)：55-58.

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ù)塊或單棵決策樹(shù)進(jìn)行冗余屬性刪除，沒(méi)有從整體上考慮刪除冗余屬性問(wèn)題，再檢測(cè)概念漂移。參考文獻(xiàn)[7]從整體上考慮刪除冗余屬性問(wèn)題，但是未能解決數(shù)據(jù)流中模糊屬性約簡(jiǎn)問(wèn)題。

粗糙集理論[8]是一種處理不相容、不精確或不完全數(shù)據(jù)的強(qiáng)有力工具。模糊粗糙集是粗糙集理論的擴(kuò)展研究，它解決了粗糙集約簡(jiǎn)處理之前必需的離散化過(guò)程，使得粗糙集也適用于模糊概念和模糊知識(shí)的屬性約簡(jiǎn)。基于模糊粗糙集的屬性約簡(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í)。本文若未特別說(shuō)明,屬性均表示模糊條件屬性。

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

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

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

其中,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);(1)P=?;(2)對(duì)于任意a∈A,如果σ(A,a)>0,那么P=P∪{a};(3)M=A-a;(4)重復(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};③選擇F-屬性重要度非零且最大的元素a∈E,P=P∪{a},M=M-{a}(添加屬性集M中F-屬性重要度非零且最大的屬性到并行約簡(jiǎn)P中);(5)輸出并行約簡(jiǎn)P。

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

通過(guò)模糊并行約簡(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)系：

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

(2)若屬性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ù)流的模糊概念漂移問(wèn)題。下面運(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的模糊概念漂移量定義為：

定理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說(shuō)明冗余屬性的存在干擾了概念漂移的探測(cè)，刪除了一些冗余屬性后模糊概念漂移更明顯。下面利用基于模糊并行約簡(jiǎn)的模糊概念漂移量來(lái)探測(cè)概念漂移。

通過(guò)算法2可知,模糊并行約簡(jiǎn)將模糊決策子表簇作為一個(gè)整體考慮，刪除了模糊決策子表簇中對(duì)分類不起作用的冗余屬性，使得在模糊概念漂移的探測(cè)和分類的時(shí)候減少了計(jì)算量，并將注意力真正集中到對(duì)分類起關(guān)鍵作用的屬性集合上。基于模糊并行約簡(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所示。

表1　模糊決策表DS

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

表4　在子表IS1、IS2中對(duì)象對(duì)模糊正域的隸屬度

模糊屬性重要性矩陣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

因?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)

[1] 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.

[2] 王濤, 李舟軍, 顏躍進(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.

[4] 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.

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

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

[7] 鄧大勇, 徐小玉, 黃厚寬. 基于并行約簡(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.

[9] 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].微型機(jī)與應(yīng)用,2015,34(23):14-15.

[11] 程昳,苗奪謙,馮琴榮.基于模糊粗糙集的粒度計(jì)算[J]. 計(jì)算機(jī)科學(xué),2007,34(7):142-149.

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

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

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

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

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

[17] Yao Yiyu. Three-way decision with probabilistic rough sets[J].Information Sciences, 2010, 180:341-353.

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358/j.issn.1674- 7720.2016.12.018

(收稿日期：2015-12-18)

作者簡(jiǎn)介：

張任(1989-),男,碩士研究生,主要研究方向:粗糙集、模糊集、數(shù)據(jù)挖掘。

Algorithms of fuzzy concept drifting detection for categorical evolving data based on fuzzy parallel reducts

Zhang Ren

(College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China)

Abstract:Data stream mining is one of hot topics of data mining,and the types of data flow are different. Based on basic principles of fuzzy rough sets and F-fuzzy rough sets, this paper presents a new method of fuzzy parallel reducts to reduce redundant attributes from fuzzy data stream, and detect fuzzy concept drifting according to the attribute significance of fuzzy parallel reducts. Different from other classical methods，the inner properties of data stream are used to detect concept drifting.Through examples it verifies its feasibility and validity.

Key words:fuzzy data streams; concept drift; fuzzy rough sets; F-fuzzy rough sets; fuzzy parallel reducts