基于頻度的概念漂移檢測算法

侯傳宇，李耀紅，趙 娟，武以敏

分類是有指導(dǎo)的學(xué)習(xí)［1－6］，其目的是構(gòu)造一個(gè)分類模型，來預(yù)測未知類別標(biāo)簽的樣本所屬的類別，分類是數(shù)據(jù)挖掘的一個(gè)重要部分。通過分類可發(fā)現(xiàn)訓(xùn)練數(shù)據(jù)中蘊(yùn)含的概念，概念可以看作是一個(gè)分類規(guī)則或貝葉斯概率表，即從屬性到類別的映射。

由于數(shù)據(jù)流快速、連續(xù)、多變的特性，其所蘊(yùn)含的映射關(guān)系會(huì)或多或少發(fā)生變化，從而導(dǎo)致目標(biāo)概念的變化即出現(xiàn)概念漂移。概念漂移主要有三種形式、突變式、漸進(jìn)式以及取樣變化［7－11］。

1 基于頻度的概念漂移

1.1 數(shù)據(jù)流中概念的頻度

數(shù)據(jù)流中所隱含的概念漂移，存在概念的重復(fù)出現(xiàn)也就是相似的映射關(guān)系的不斷重現(xiàn)，其出現(xiàn)的次數(shù)可稱為概念的頻度，如：季節(jié)中天氣的變化，陰天、多云、晴天等天氣出現(xiàn)的次數(shù)可看作是頻度，頻度小于一定閾值的概念可視為低頻概念，反之則為高頻概念。對于天氣情況：“陰天”、“晴天”可當(dāng)作高頻概念；“六月雪”、“太陽雨”等則可當(dāng)作是低頻概念。

1.2 適用于隱含概念漂移的數(shù)據(jù)流分類算法

很多學(xué)者［12－13］對隱含概念漂移的數(shù)據(jù)流分類算法進(jìn)行了研究，如：CVFDT，WCE等。這些算法在處理數(shù)據(jù)流中的概念漂移問題時(shí)，大多采用不斷更新分類模型，對原始概念與新概念之間的聯(lián)系在未做研究。則在當(dāng)前分類模型不適用而新的分類模型正在構(gòu)造的時(shí)段，分類時(shí)間性能以及準(zhǔn)確度也會(huì)降低。Yang Ying等人提出的RePro算法［14］，根據(jù)數(shù)據(jù)流中概念漂移的特征，用已有的分類模型序列組織概念序列，把每一個(gè)分類模型視為馬氏鏈的一種狀態(tài)，分類模型的改變過程看作是馬爾可夫鏈。通過概念序列構(gòu)建體現(xiàn)概念轉(zhuǎn)移的規(guī)律的概念轉(zhuǎn)移矩陣，用于對新模型進(jìn)行預(yù)測，并用已有分類模型對新訓(xùn)練的分類模型進(jìn)行進(jìn)行檢測判斷是否是已有概念的重現(xiàn)。當(dāng)檢測到概念漂移則根據(jù)概念轉(zhuǎn)移矩陣迅速產(chǎn)生分類模型，這對于基于頻度的概念漂移來說，分類的時(shí)間性能和分類精度得到了提高。

1.3 基于頻度的概念漂移檢測的必要性

對于分類算法，識別一個(gè)原有模型要比新建一個(gè)模型要省時(shí)。而基于頻度的概念漂移的特點(diǎn)是部分已有概念的重現(xiàn)，可利用此特點(diǎn)對概念漂移進(jìn)行檢測，再利用概念變換的規(guī)律來提高分類的時(shí)間性能和分類的精度。RePro算法，在分類的過程中采用滑動(dòng)窗口來檢測觸發(fā)器，每遇到概念漂移，都要檢驗(yàn)訓(xùn)練的概念是否是已有概念的重現(xiàn)。該算法對于基于頻度的概念漂移來說，較為適用。這樣可以充分訓(xùn)練概念轉(zhuǎn)移矩陣，更好的發(fā)現(xiàn)概念漂移的規(guī)律，用以預(yù)測將要出現(xiàn)的概念，能節(jié)省時(shí)間提高分類精度。而對于非基于頻度的概念漂移是耗時(shí)的，且會(huì)導(dǎo)致概念轉(zhuǎn)移矩陣的無限增長，當(dāng)遇到觸發(fā)器時(shí)只需對模型進(jìn)行更新即可，無需對更新的模型進(jìn)行相似度檢驗(yàn)。因此，對概念漂移是否是基于頻度的進(jìn)行檢測是十分必要的。

2 FCD算法

2.1 FCD算法的組成

基于頻度的概念漂移的特點(diǎn)是已有概念的重現(xiàn)，可通過對其變換過程的研究發(fā)現(xiàn)概念變化的規(guī)律，從而能提高分類精度和時(shí)間性能。FCD算法由以下幾部分組成：一是基本分類算法，決策樹分類算法、K－最鄰近分類算法、樸素貝葉斯分類算法等，用來構(gòu)造基礎(chǔ)分類器；二是觸發(fā)器的檢測算法，主要用來判定是否發(fā)生概念漂移；三是概念的等價(jià)度量算法，用來判定新出現(xiàn)的概念是否是已有概念的重現(xiàn)；四是概念頻度檢測模型。

2.2 基于頻度的概念漂移的檢測模型

FCD算法的前3個(gè)組成部分，許多學(xué)者提出了很好的算法，本文主要介紹概念頻度的檢測模型。

基于頻度的概念漂移的主要特點(diǎn)是部分概念重復(fù)出現(xiàn)，概念頻度識別模型由以下組成部分：構(gòu)造歷史概念序列，用于判斷新出現(xiàn)的概念是否是已有概念的重現(xiàn)；同時(shí)訓(xùn)練概念轉(zhuǎn)移矩陣，用于記錄概念漂移的規(guī)律，概念重現(xiàn)則更新其對應(yīng)于概念轉(zhuǎn)移矩陣的行列的值，全新的概念則增加概念轉(zhuǎn)移矩陣的行列并更新矩陣對應(yīng)行列的值；基于頻度的概念漂移的檢測。采用滑動(dòng)窗口的方法，設(shè)定概念序列的長度為Max，互異概念的總數(shù)為n，每個(gè)互異概念出現(xiàn)的次數(shù)為Xi，概念頻度的閾值為ER。若Xi／n＞ER，則可視為基于頻度的概念漂移?；陬l度的概念漂移的檢測模型見圖1。

圖1 基于頻度的概念漂移的檢測模型

3 實(shí)驗(yàn)結(jié)果

Stagger Concept方法廣泛用于測試隱含概念漂移的數(shù)據(jù)流分類算法［15］，采用 Stagger Concept方法產(chǎn)生實(shí)驗(yàn)測試數(shù)據(jù)。為了測試方便，設(shè)置每個(gè)樣本的屬性為5個(gè)，分別為：Fir，Sec，Thi，F(xiàn)ou，F(xiàn)if，每個(gè)屬性取值區(qū)間設(shè)定為｛a，b，c｝。類別標(biāo)簽分別為：0，1?？墒褂靡欢ǖ囊?guī)則產(chǎn)生對應(yīng)的概念，如：Fir＝a∧Sec＝a∧Fou＝c→classify＝0，F(xiàn)ir＝b∧Thi＝b∧Fif＝c→classify＝1等。構(gòu)造概念序列：T1，T2，T1，T2，T1，T2，T1，T2，T1 ，T2，T3，T1，T3，T1，T3，T1，T3，T1；設(shè)定頻度閾值Er為：0.3，用戶可接受的概念序列的最大長度 Max為：40，誤差閾值Cr為：0.4。實(shí)驗(yàn)為檢驗(yàn)?zāi)Ｐ吞幚砀拍钇频哪芰?，添加了噪音?shù)據(jù)在測試數(shù)據(jù)中。

實(shí)驗(yàn)在PC機(jī)上運(yùn)行，操作系統(tǒng)為 Windows XP，CPU為Pentiun（R）3.0GHz的，內(nèi)存為2G。適當(dāng)調(diào)整觸發(fā)器窗口和學(xué)習(xí)窗口的大小，可得到序列如表1所示。

表1 概念識別模型所獲取的序列

經(jīng)比較，概念T1，T2，T3與表1中的概念Y1，Y2，Y9相對應(yīng)，其出現(xiàn)的頻率均大于Er，分別是：0.588，0.529，0.412。分類錯(cuò)誤率小于誤差閾值Cr為0.331。根據(jù)實(shí)驗(yàn)結(jié)果可確定此概念漂移為基于頻度的概念漂移。

表1中出現(xiàn)的概念 Y3，Y4，Y5，Y6，Y7，Y9，Y10，Y11，Y12，Y13，Y14，Y15，Y16，Y17，不是預(yù)先生成的，可視為異常概念。部分異常概念是由于分類誤差所產(chǎn)生的，部分是由于噪音數(shù)據(jù)造成的，而學(xué)習(xí)窗口的大小以及觸發(fā)器窗口的大小對分類精度都有影響，目前分類的絕對準(zhǔn)確沒有好方法來確保。從表1也可看出這些異常概念出現(xiàn)的頻率均為0.059，較低，對概念頻度的檢驗(yàn)不造成影響。

4 結(jié)束語

本文參考RePro算法，設(shè)計(jì)出檢測基于概念頻度的概念漂移的算法FCD，對基于頻度的概念漂移，當(dāng)檢測到觸發(fā)器時(shí)，可通過訓(xùn)練的概念轉(zhuǎn)移矩陣對將要出現(xiàn)的概念進(jìn)行預(yù)測，而對于非基于頻度的概念漂移，當(dāng)檢測到觸發(fā)器時(shí)，只需直接構(gòu)造新的分類模型，這樣可提高分類的時(shí)間性能。

［1］ Littlestone N.Learning quickly when irrelevant attributes abound：a new linear－threshold algorithm［J］.Machine Learning，1988（2）：285－318.

［2］ Fisher D H.Knowledge acquisition via incremental conceptual clustering［J］.Machine Leaning，1987（2）：139－172.

［3］ J.Schlimmer and R.Granger.Beyond incremental processing：Tracking concept drift［C］／／Proceedings of the 5th NationalConference on Artificial Intelligence，Philadelphia：Morgan Kaufmann，1986：502－507.

［4］ Shafer J，Agrawal R，Metha M.SPRINT：A scalable parallel classifier for data mining［R］.IBM Almaden Research Center，San Jose，California，1996.

［5］ Mehta M，Agrawal R，Rissanen J.SLIQ：A fast scalable classifier for data mining［R］.IBM Almaden Research Center，San Jose，California，1995.

［6］ Yang Ying，Wu Xindong，Zhu Xingquan.Combining proactive and reactive predictions for data streams［J］.In SIGKDD，2005，（8）：710－715.

［7］ Lanquillon C，Renz I.Adaptive information filtering：Detec－ting changes in text streams.［C］／／Proc.of 8th ACM Intl＇Conf.on Information and Knowledge Management，Kansas City：ACM Press，1999：538－544.

［8］ Stanley K O.Learning concept drift with a committee of decision trees［R］.Department of Computer Sciences，University of Texas at Austin，USA，2003.

［9］ Tsymbal A.The problem of concept drift：definitionsand related work［R］.Trinity College Dublin，Ireland：Computer Science Department，2004.

［10］ Widmer G，Kubat M.Learning in the presence of concept drift and hidden contexts［J］.Machine Learning，1996，23（1）：69－101.

［11］ Salganicoff M.Tolerating concept and sampling shift in lazy learning using prediction error context switching［J］.Artificial Intelligence Review，1997，11（1）：133－155.

［12］ Domingos P，Hulten G.Mining high－speed data streams［C］／／In Proceedings of the Association for Computing Machinery Sixth International Conference on Knowledge Discovery and Data Mining，Boston：ACM Press ，2000：71－80.

［13］ Wang H，F(xiàn)an W，Han J.Mining concept－drifting data streams using ensemble classifiers［C］／／In Proc.of 9th SIGKDD，Washington DC，USA，2003：226－235.

［14］ Yang，Y.，Wu，X.，and Zhu，X.Dealing with predictive－but－unpredictable attributes in noisy data sources［C］／／In Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases，Pisa，Italy，2004：471－483.

［15］ Kolter J Z，Maloof M A.Dynamic weighted majority：a new ensemble method for tracking concept drift［C］／／In Proceedings of the 3rd International IEEE Conference on Data Mining，Los Alamitos，USA：IEEE，2003：123－130.