尹春勇，陳雙雙

南京信息工程大學(xué) 計(jì)算機(jī)學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，南京 210044

隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)的增長(zhǎng)速度逐漸加快。來自生活中各領(lǐng)域的數(shù)據(jù)每時(shí)每刻都在以流的形式產(chǎn)生，例如社交平臺(tái)的多媒體數(shù)據(jù)流、金融行業(yè)的交易數(shù)據(jù)流、交通領(lǐng)域的監(jiān)控視頻數(shù)據(jù)流。對(duì)這些數(shù)據(jù)流的挖掘和分析能夠?yàn)檫M(jìn)一步的管理提供重要的決策支持。與傳統(tǒng)靜態(tài)數(shù)據(jù)不同，數(shù)據(jù)流被定義為是高速連續(xù)的、無限的、動(dòng)態(tài)變化的數(shù)據(jù)序列[1-2]，因此需要特殊的處理和挖掘算法。其中，數(shù)據(jù)流分類是數(shù)據(jù)流挖掘領(lǐng)域中一項(xiàng)關(guān)鍵技術(shù)。

數(shù)據(jù)流分類通常面臨著概念漂移[3-4]的問題，即數(shù)據(jù)的潛在分布會(huì)隨著時(shí)間的推移而發(fā)生不可預(yù)知的變化，而產(chǎn)生這種變化的原因有很多，例如季節(jié)的更替、溫濕度的改變、設(shè)備線材的損耗。概念漂移問題會(huì)導(dǎo)致已有的分類模型無法適應(yīng)新的數(shù)據(jù)分布，從而造成分類準(zhǔn)確率的驟降。為了解決概念漂移問題，專家學(xué)者提出了一系列的解決辦法。Ditzler 等[5]總結(jié)了兩類解決方法，主動(dòng)檢測(cè)方法和被動(dòng)適應(yīng)方法。Brzezinski 等[6]利用最新到達(dá)的數(shù)據(jù)塊創(chuàng)建基分類器，將其添加到集成中，通過更新基分類器權(quán)值應(yīng)對(duì)漸變漂移。這種方法未考慮到數(shù)據(jù)塊內(nèi)發(fā)生概念漂移的情況，因此難以應(yīng)對(duì)突變漂移，而且數(shù)據(jù)塊的大小會(huì)影響分類性能，數(shù)據(jù)塊過大，塊中可能包含多個(gè)概念，導(dǎo)致對(duì)漂移的適應(yīng)能力較弱；數(shù)據(jù)塊過小，會(huì)由于塊中樣本不足導(dǎo)致無法很好地?cái)M合數(shù)據(jù)分布，影響分類器的準(zhǔn)確率。徐清妍等[7]利用滑動(dòng)窗口檢測(cè)概念漂移，窗口大小會(huì)影響概念漂移的檢測(cè)，窗口過小容易受到噪聲影響，造成誤報(bào)；窗口過大會(huì)增加檢測(cè)時(shí)間，且容易造成漏報(bào)[8]。

大多數(shù)應(yīng)對(duì)概念漂移的分類方法處理的都是數(shù)據(jù)被完全標(biāo)記的情況，在真實(shí)場(chǎng)景中，很多樣本是無標(biāo)記的，獲取所有樣本的真實(shí)標(biāo)簽既費(fèi)時(shí)又費(fèi)資源。針對(duì)這個(gè)問題，基于聚類的半監(jiān)督方法[9-12]被提出。Masud等[10]提出了基于聚類的半監(jiān)督分類器集成方法，首先數(shù)據(jù)流被劃分為多個(gè)固定大小的塊，每個(gè)部分標(biāo)記的數(shù)據(jù)塊利用聚類方法劃分為多個(gè)簇，在新的數(shù)據(jù)塊中訓(xùn)練分類器替換集成中性能最差的分類器，再使用標(biāo)簽傳播算法標(biāo)記未標(biāo)記的聚類。Li 等[13]提出了一種基于優(yōu)先標(biāo)簽數(shù)據(jù)流的半監(jiān)督學(xué)習(xí)算法。該方法選擇決策樹作為分類器，在構(gòu)造決策樹的過程中，采用基于k-means 的聚類算法生成概念簇并標(biāo)記無標(biāo)簽數(shù)據(jù)。通過比較之前和當(dāng)前的概念簇判斷是否發(fā)生概念漂移。Din等[14]提出了一種在線半監(jiān)督學(xué)習(xí)方法（ORSL）。該方法利用在線微聚類實(shí)現(xiàn)對(duì)流數(shù)據(jù)的匯總，利用K最近鄰（K-nearest neighbor，KNN）分類器預(yù)測(cè)傳入的新實(shí)例：為每個(gè)分類器分配一個(gè)權(quán)重，選擇權(quán)重最大的分類器作為最佳分類器，實(shí)現(xiàn)對(duì)新實(shí)例的標(biāo)簽預(yù)測(cè)，用這些實(shí)例更新模型。

雖然有很多方法用來處理非平穩(wěn)環(huán)境下的有限標(biāo)記數(shù)據(jù)流，仍然有一些問題需要解決。在半監(jiān)督環(huán)境下檢測(cè)概念漂移，檢測(cè)效果會(huì)受到標(biāo)記樣本的影響。當(dāng)標(biāo)記樣本過少時(shí)，僅僅利用有限標(biāo)記樣本的分類準(zhǔn)確率檢測(cè)概念漂移是不可靠的。如何在半監(jiān)督環(huán)境下，同時(shí)考慮到無標(biāo)記樣本和有標(biāo)記樣本檢測(cè)概念漂移，及時(shí)對(duì)模型進(jìn)行更新，提高模型的分類性能是當(dāng)前需要解決的問題。

主動(dòng)學(xué)習(xí)是處理缺少類標(biāo)簽數(shù)據(jù)流的有效方法[15]，因?yàn)樗梢赃x擇信息最豐富的樣本添加標(biāo)簽，構(gòu)建最佳預(yù)測(cè)模型，節(jié)約標(biāo)注成本[16]。目前，在線分類技術(shù)與主動(dòng)學(xué)習(xí)相結(jié)合已成為數(shù)據(jù)流分類的有效方法之一[17]。結(jié)合主動(dòng)學(xué)習(xí)，開發(fā)出穩(wěn)定高效的，并且能在有限內(nèi)存下工作的在線分類模型是當(dāng)前基于主動(dòng)學(xué)習(xí)的分類算法所面臨的嚴(yán)峻挑戰(zhàn)。

本文提出了一種基于聚類的主動(dòng)學(xué)習(xí)方法（CALC）實(shí)現(xiàn)數(shù)據(jù)流分類。CALC框架有三個(gè)模塊，初始模型構(gòu)建、分類、在線更新。在初始模型構(gòu)建階段，利用k均值聚類算法將初始訓(xùn)練數(shù)據(jù)劃分為k組，計(jì)算它們的聚類特征形式的統(tǒng)計(jì)匯總，然后利用微聚類（MC）保存這些特征。在分類階段，為了應(yīng)對(duì)概念漂移和類標(biāo)簽不足問題，提出了一種基于聚類距離和聚類純度的微聚類主動(dòng)學(xué)習(xí)框架，利用新的混合標(biāo)注策略選擇部分實(shí)例標(biāo)記后重新訓(xùn)練模型。在模型更新階段，定義了指數(shù)衰減函數(shù)，計(jì)算模型中的微聚類隨時(shí)間變化后的權(quán)重公式，并通過合并或刪除操作創(chuàng)建新的微聚類空間，從而得到新的分類模型。

本文的主要貢獻(xiàn)如下：

（1）針對(duì)概念漂移和樣本標(biāo)記不足的數(shù)據(jù)流分類任務(wù)，提出了一個(gè)基于聚類的主動(dòng)學(xué)習(xí)框架。

（2）采用基于微聚類的距離與純度的惰性學(xué)習(xí)框架進(jìn)行分類，利用微聚類中心與實(shí)例之間的距離設(shè)計(jì)一種新的不確定性策略，與隨機(jī)策略結(jié)合得到混合查詢策略，查詢最值得標(biāo)記的數(shù)據(jù)，更好地應(yīng)對(duì)概念漂移。

（3）提出基于微聚類的模型自適應(yīng)調(diào)整方法，設(shè)計(jì)一種相似性規(guī)則合并微聚類，刪除過時(shí)微聚類，通過維護(hù)微聚類權(quán)重實(shí)現(xiàn)模型的動(dòng)態(tài)更新。

1 相關(guān)工作

本文主要研究對(duì)于概念漂移數(shù)據(jù)流的一種基于聚類的主動(dòng)學(xué)習(xí)方法。接下來對(duì)概念漂移數(shù)據(jù)流的分類方法、基于主動(dòng)學(xué)習(xí)的數(shù)據(jù)流分類方法以及一些半監(jiān)督分類方法進(jìn)行回顧。

1.1 概念漂移

數(shù)據(jù)流中概念的經(jīng)典定義是一組對(duì)象的集合，這并不符合數(shù)據(jù)流的特點(diǎn)?，F(xiàn)有的大部分文獻(xiàn)用概率定義概念。Gama等[18]用數(shù)據(jù)的聯(lián)合概念分布p(x,y)表示概念，x表示d維特征向量，y表示相應(yīng)的標(biāo)簽。數(shù)據(jù)分布由于某些因素的影響會(huì)隨著時(shí)間的推移而變化，為了具體地描述這種變化，將Pt(x,y)定義為t時(shí)刻的聯(lián)合概率分布。如果Pt(x,y)≠Pt+1(x,y)，說明在t和t+1 以內(nèi)的時(shí)間段發(fā)生了概念漂移。聯(lián)合分布用貝葉斯理論表示為Pt(x,y)=Pt(x)Pt(y|x)。從概率論的方面來分析為何會(huì)產(chǎn)生這種現(xiàn)象，原因可分為兩類：（1）先驗(yàn)概率P(x)發(fā)生了變化，而條件概率P(y|x)沒有改變，此時(shí)決策邊界并沒有發(fā)生變化，這種現(xiàn)象稱為虛擬概念漂移；（2）條件概率P(y|x)發(fā)生了變化，無論先驗(yàn)概率P(x)有沒有發(fā)生變化，決策邊界都會(huì)改變，降低分類器的分類準(zhǔn)確率，這種現(xiàn)象是真實(shí)概念漂移。Zliobaite 等[15]根據(jù)數(shù)據(jù)分布如何變化，將概念漂移分成了漸變式、突變式、增量式和重現(xiàn)式概念漂移四種類型。

（1）漸變漂移：漸變漂移的變化范圍比較小，需要長(zhǎng)時(shí)間才能觀察到發(fā)生了改變，在概念漂移發(fā)生前后，概念是極為相似的，所以對(duì)分類模型的準(zhǔn)確率影響較小。

（2）突變漂移：突變漂移是在較短時(shí)間內(nèi)，數(shù)據(jù)流中的數(shù)據(jù)分布突然改變，這種變化具有瞬時(shí)性，會(huì)導(dǎo)致分類模型的準(zhǔn)確率迅速降低甚至失效。這就需要模型能夠及時(shí)應(yīng)對(duì)這種漂移，更新模型以適應(yīng)變化后的環(huán)境。

（3）增量漂移：增量漂移意味著概念以增量式變化。與漸變漂移類似，短時(shí)間內(nèi)數(shù)據(jù)分布變化不大，當(dāng)發(fā)生變化時(shí)，數(shù)據(jù)由多個(gè)數(shù)據(jù)分布產(chǎn)生，各個(gè)數(shù)據(jù)分布之間差異性較小。

（4）重現(xiàn)漂移：重現(xiàn)漂移是經(jīng)過一段時(shí)間后，以前出現(xiàn)過的概念重新出現(xiàn)?，F(xiàn)實(shí)生活中有很多例子，例如以前人們關(guān)注的一個(gè)話題，在某一個(gè)特定的時(shí)間，又重新變成熱點(diǎn)話題。歷史數(shù)據(jù)可以作為處理這種概念漂移的有效方式，重新利用以前學(xué)習(xí)過的模型而不用重復(fù)訓(xùn)練，避免了資源的浪費(fèi)。

Bifet 等[19]提出基于可變大小滑動(dòng)窗口的概念漂移主動(dòng)檢測(cè)方法（adaptive windowing，ADWIN），通過比較兩個(gè)子窗口之間的錯(cuò)誤率均值的不同來判斷是否發(fā)生概念漂移。Nishida 等[20]提出了基于統(tǒng)計(jì)檢驗(yàn)理論（statistical test of equal proportions，STEPD）檢測(cè)概念漂移的方法，通過比較局部訓(xùn)練樣本的分類準(zhǔn)確率和全部樣本的分類準(zhǔn)確率來檢測(cè)漂移，準(zhǔn)確率一樣則數(shù)據(jù)分布穩(wěn)定，反之則發(fā)生了漂移。還有一些方法通過更新分類器適應(yīng)概念漂移。Street 等[21]提出了流集成算法（streaming ensemble algorithm，SEA），該方法是一種基于數(shù)據(jù)塊的集成分類算法，不斷用最新的數(shù)據(jù)塊去訓(xùn)練新基分類器，集成中的最大基分類器數(shù)量是固定的，一旦達(dá)到這個(gè)數(shù)量，將用新的分類器替換集成中最差的分類器。Wang等[22]提出了一種基于準(zhǔn)確率加權(quán)集成算法（accuracy weighted ensemble，AWE），與SEA 不同的是，AWE 更新基分類器的權(quán)值是利用最近到達(dá)數(shù)據(jù)塊上的分類準(zhǔn)確率。

上述方法屬于有監(jiān)督分類方法，所有訓(xùn)練樣本都是被完全標(biāo)記的，并且這些標(biāo)簽立即可用，真實(shí)標(biāo)簽可用來判斷分類是否正確，從而得到分類準(zhǔn)確率，利用分類準(zhǔn)確率檢測(cè)概念漂移。但是在現(xiàn)實(shí)情況下，只有少量標(biāo)記的樣本存在，大量樣本都是無標(biāo)記的。由于數(shù)據(jù)流高速、海量的特性，人工標(biāo)注所有樣本是不切實(shí)際的，于是很多半監(jiān)督分類方法被提出以解決該類問題。

1.2 基于聚類的分類方法

Widyantoro 等[23]提出了一種用于擴(kuò)展不完全標(biāo)記數(shù)據(jù)流的新計(jì)算框架。將少量帶有標(biāo)記的數(shù)據(jù)流作為輸入，然后應(yīng)用半監(jiān)督技術(shù)對(duì)未標(biāo)記數(shù)據(jù)流進(jìn)行標(biāo)記，由此擴(kuò)展之前的少數(shù)標(biāo)記數(shù)據(jù)流形成新數(shù)據(jù)流。概念漂移檢測(cè)器是在新數(shù)據(jù)流進(jìn)行檢測(cè)的。Masud 等[10]提出基于聚類的分類模型（realistic stream classifier，ReaSC），數(shù)據(jù)流被劃分為若干個(gè)塊，塊中的標(biāo)記樣本是有限的。利用聚類創(chuàng)建k個(gè)簇，對(duì)這些簇進(jìn)行統(tǒng)計(jì)信息匯總得到微聚類，在微聚類上應(yīng)用標(biāo)簽傳播技術(shù)標(biāo)記沒有標(biāo)簽的微聚類，微聚類的集合構(gòu)成了分類器。這些方法利用半監(jiān)督技術(shù)自動(dòng)標(biāo)記無標(biāo)簽樣本，并未獲取這些樣本的真實(shí)標(biāo)簽，無法判斷賦予樣本的標(biāo)簽與真實(shí)標(biāo)簽之間的關(guān)系。從而這些方法只適用于類條件分布不變的情況，即無法處理真正的概念漂移。

基于聚類的數(shù)據(jù)流分類方法利用聚類算法獲得聚簇集合（或者將這些聚簇進(jìn)一步劃分為微簇），樣本的統(tǒng)計(jì)信息可以通過聚簇來反映，這些信息體現(xiàn)了數(shù)據(jù)分布的局部特征和全局特征[4]。所以聚類適用于數(shù)據(jù)流中的樣本標(biāo)簽不足的情況。為了應(yīng)對(duì)概念漂移，研究者們?cè)诰垲惖幕A(chǔ)上提出了很多新的算法。

Hosseini等[24]提出一種對(duì)半監(jiān)督環(huán)境中非平穩(wěn)數(shù)據(jù)流的實(shí)例進(jìn)行分類的集成算法（semi-supervised pool and accuracy-based stream classification，SPASC），旨在識(shí)別數(shù)據(jù)流中重現(xiàn)概念漂移。該算法維護(hù)一個(gè)分類器池，將聚類獲得的簇集合作為基分類器保存在分類器池中并賦予權(quán)值。通過計(jì)算新到達(dá)數(shù)據(jù)塊與每個(gè)基分類器的相似性判斷是否發(fā)生概念漂移。Casalino等[25]提出一種基于增量自適應(yīng)模糊聚類的數(shù)據(jù)流半監(jiān)督分類算法（dynamic incremental semi-supervised FCM，DISSFCM）。該算法基于模糊C-均值（fuzzyC-means algorithm，F(xiàn)CM）對(duì)數(shù)據(jù)進(jìn)行聚類，利用聚類提取數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類。對(duì)于新到達(dá)數(shù)據(jù)塊中的每個(gè)樣本，預(yù)測(cè)類別為距離該樣本最近的簇的類別。為了更好地應(yīng)對(duì)概念漂移，利用半監(jiān)督模糊C-均值（semi-supervised FCM，SSFCM）將已經(jīng)得到的聚類原型與新數(shù)據(jù)塊相結(jié)合，得到新的模型并計(jì)算每個(gè)簇的重構(gòu)誤差，如果重構(gòu)誤差值超過容差值時(shí)，表明當(dāng)前簇的數(shù)量不足以有效地表示當(dāng)前數(shù)據(jù)，將相應(yīng)的簇劃分為兩個(gè)簇。Zheng等[26]提出了一種處理重現(xiàn)概念漂移和新類數(shù)據(jù)流的半監(jiān)督分類框架（semisupervised classification on data streams with recurring concept drift and concept evolution，ESCR），框架建立在由多個(gè)基于聚類的分類器組成的集成模型上。當(dāng)檢測(cè)到不是重現(xiàn)概念漂移時(shí)，通過部分標(biāo)記實(shí)例更新模型，根據(jù)分類器置信度分?jǐn)?shù)選擇少數(shù)實(shí)例標(biāo)記：（1）置信度分?jǐn)?shù)小于等于閾值，獲取該實(shí)例的真實(shí)標(biāo)簽并將其添加到已標(biāo)記數(shù)據(jù)實(shí)例集合中；（2）置信度分?jǐn)?shù)大于閾值，模型預(yù)測(cè)該實(shí)例的標(biāo)簽并將其添加到未標(biāo)記數(shù)據(jù)實(shí)例集合中。根據(jù)這兩個(gè)集合訓(xùn)練新的模型。

上述聚類方法都是用于數(shù)據(jù)流分類的半監(jiān)督方法，數(shù)據(jù)在以塊到來的過程中，少量數(shù)據(jù)含有標(biāo)記，某些簇所包含的數(shù)據(jù)可能全部無標(biāo)記，不能體現(xiàn)出數(shù)據(jù)流的數(shù)據(jù)分布，從而影響模型的分類性能，所以需要某種策略查詢能夠體現(xiàn)數(shù)據(jù)分布的最有價(jià)值樣本，利用這些有價(jià)值的樣本更新分類器，提高分類性能。

1.3 基于主動(dòng)學(xué)習(xí)的半監(jiān)督分類

主動(dòng)學(xué)習(xí)是利用采樣策略，挑選一些重要的無標(biāo)簽樣本交給專家標(biāo)記，利用標(biāo)記后的樣本訓(xùn)練模型。標(biāo)簽請(qǐng)求策略的好壞決定了主動(dòng)學(xué)習(xí)方法的性能[17]。主動(dòng)學(xué)習(xí)中經(jīng)典的標(biāo)簽請(qǐng)求策略包括不確定性策略、隨機(jī)策略和混合策略[16]。不確定策略基于模型對(duì)實(shí)例預(yù)測(cè)的不確定性程度選擇實(shí)例，重點(diǎn)是不確定度的計(jì)算。隨機(jī)策略是從數(shù)據(jù)流中隨機(jī)選擇實(shí)例進(jìn)行標(biāo)注，代表著實(shí)例空間中任何區(qū)域的實(shí)例都有可能被選中，與不確定策略結(jié)合可以用來提高不確定策略的準(zhǔn)確性。混合策略是結(jié)合隨機(jī)策略和不確定策略的標(biāo)注策略，是用來檢測(cè)潛在概念漂移的有效方法。

李南[27]提出了一種基于聚類假設(shè)的數(shù)據(jù)流分類算法（a clustering assumption based classification algorithm for stream data，CASD），該算法利用主動(dòng)學(xué)習(xí)，當(dāng)新實(shí)例x被分類后，判斷x是否被任意一個(gè)模型簇覆蓋，如果沒有被覆蓋或者是處在模型簇邊界時(shí)，對(duì)x進(jìn)行標(biāo)記。Haque 等[28]提出了一個(gè)半監(jiān)督框架（efficent concept drift and concept evolution handling over stream data，ECHO），利用基于k-NN 類型的聚類組成集成分類器，提出關(guān)聯(lián)和純度來計(jì)算分類器的置信度，置信度的大小決定是否對(duì)樣本進(jìn)行標(biāo)記。如果分類器對(duì)樣本分類的置信度小于指定閾值，則請(qǐng)求該樣本的真實(shí)標(biāo)簽，否則，將分類器預(yù)測(cè)的標(biāo)簽作為該樣本的標(biāo)簽。這些具有標(biāo)簽的樣本集合作為訓(xùn)練數(shù)據(jù)，用來訓(xùn)練新的分類器，替換集成分類器中最舊的分類器。

這些方法只選擇決策邊界附近的實(shí)例進(jìn)行標(biāo)注，這對(duì)發(fā)生概念漂移的數(shù)據(jù)流來說似乎不太準(zhǔn)確，因?yàn)楦拍钇茣?huì)出現(xiàn)在實(shí)例空間的任何區(qū)域。如果漂移的實(shí)例不在決策邊界附近，該策略選擇的就不是變化的實(shí)例，從而不能充分應(yīng)對(duì)數(shù)據(jù)分布的變化。

結(jié)合分類方法設(shè)計(jì)的標(biāo)簽請(qǐng)求策略可以有效提高分類性能。Ienco 等[29]提出了一種基于聚類的主動(dòng)學(xué)習(xí)方法（active clustering learning for data streams，ACLStream）。當(dāng)一批數(shù)據(jù)來臨時(shí)，使用聚類方法將它們劃分為n個(gè)簇。通過宏觀步驟對(duì)簇進(jìn)行排序，通過微觀步驟對(duì)簇中的實(shí)例進(jìn)行排序，以便從每個(gè)簇中選取不確定的實(shí)例即最有用的實(shí)例進(jìn)行標(biāo)記。最新到達(dá)的一批數(shù)據(jù)首先利用分類器c1 分類，然后利用ACLStream策略選取將要被標(biāo)記的數(shù)據(jù)，最后利用被標(biāo)記的樣本集合更新c1。Zgraja 等[30]提出了一種新的用于漂移數(shù)據(jù)流分類的主動(dòng)學(xué)習(xí)算法，該方法利用了聚類增量思想并且為每個(gè)簇分配權(quán)重，對(duì)于權(quán)重最高的簇，根據(jù)標(biāo)記預(yù)算，從中隨機(jī)選擇實(shí)例進(jìn)行標(biāo)記，然后用標(biāo)記樣本集合訓(xùn)練分類器。

上述這些方法通過將數(shù)據(jù)流分類方法和主動(dòng)學(xué)習(xí)方法相結(jié)合，即針對(duì)在線學(xué)習(xí)、概念漂移這些分類問題來設(shè)計(jì)標(biāo)簽請(qǐng)求策略[17]，考慮了不確定性和數(shù)據(jù)分布，避免了查詢策略只關(guān)注某些特定區(qū)域的問題，驗(yàn)證了良好的標(biāo)簽查詢策略能提高分類性能。

2 基于聚類的主動(dòng)學(xué)習(xí)框架

在本章中，具體介紹了提出的基于聚類的主動(dòng)學(xué)習(xí)框架，CALC 框架有三個(gè)模塊，初始模型構(gòu)建、分類、在線更新。第2.1 節(jié)介紹了初始化模型的過程，將初始訓(xùn)練數(shù)據(jù)存儲(chǔ)在微聚類MC中。第2.2 節(jié)介紹了在線主動(dòng)學(xué)習(xí)的分類過程，利用聚類距離和聚類純度，提出了基于微聚類的主動(dòng)學(xué)習(xí)框架。第2.3節(jié)介紹了模型的更新過程，考慮到時(shí)間效應(yīng)給分類準(zhǔn)確率帶來的影響，計(jì)算微聚類隨時(shí)間變化后的權(quán)重，移除權(quán)重為負(fù)或者近似為0 的微聚類，當(dāng)模型中微聚類的數(shù)量達(dá)到設(shè)定值時(shí)，對(duì)微聚類進(jìn)行合并或者刪除操作。下面將逐步介紹每個(gè)模塊。

2.1 初始模型構(gòu)建

CALC 在算法1 中定義了初始化學(xué)習(xí)模型的函數(shù)。當(dāng)初始訓(xùn)練數(shù)據(jù)(Dinit)到達(dá)時(shí)，利用k均值聚類算法將其劃分為k組，不存儲(chǔ)這k個(gè)聚類，而是計(jì)算它們的聚類特征形式的統(tǒng)計(jì)匯總，然后利用MC保存這些特征。MC由多個(gè)特征組成，定義為MC=(LS,SS,S,N,W,T)。其中LS和SS是分別存儲(chǔ)聚類中帶有標(biāo)簽的每個(gè)類的線性和、平方和，見式（1）；S對(duì)應(yīng)N項(xiàng)類的向量，每項(xiàng)存儲(chǔ)聚類中每個(gè)類中的實(shí)例數(shù)量；N是聚類中實(shí)例的總數(shù)量；W是微聚類在模型更新過程中的權(quán)重；T的初始值為0，存儲(chǔ)微聚類從上次更新到此刻的時(shí)間。為了更好地對(duì)微聚類進(jìn)行處理，利用這些聚類特征計(jì)算模型中每個(gè)微聚類的半徑和中心。見式（2）和式（3）。

算法1初始模型構(gòu)建

2.2 在線主動(dòng)學(xué)習(xí)的分類過程

為了應(yīng)對(duì)概念漂移和類標(biāo)簽不足問題，提出了一種基于聚類距離和聚類純度的微聚類主動(dòng)學(xué)習(xí)框架。

2.2.1 在線主動(dòng)學(xué)習(xí)

針對(duì)標(biāo)簽稀缺問題，提出了一種新的混合標(biāo)注策略，將不確定策略與隨機(jī)策略相結(jié)合，處理新到來的實(shí)例，對(duì)微聚類學(xué)習(xí)模型進(jìn)行動(dòng)態(tài)更新使其適應(yīng)數(shù)據(jù)流的漸變概念漂移和突變概念漂移。

混合標(biāo)注策略如圖1和算法2所示。當(dāng)對(duì)新到達(dá)的未標(biāo)記實(shí)例x利用微聚類學(xué)習(xí)模型進(jìn)行標(biāo)簽預(yù)測(cè)后，判斷實(shí)例x是否通過混合標(biāo)記策略請(qǐng)求真實(shí)標(biāo)簽。在不確定性策略中，判斷x到最近微聚類中心的距離是否大于該微聚類的半徑。如果大于半徑，說明x不符合當(dāng)前擬合的數(shù)據(jù)分布，可能發(fā)生了概念漂移；如果等于半徑，x可能剛好處于決策邊界上，難以對(duì)x進(jìn)行分類。所以需要對(duì)這兩種情況的x進(jìn)行標(biāo)記。在隨機(jī)策略中，生成0 到1 范圍內(nèi)均勻分布的隨機(jī)變量ξ，如果ξ小于閾值σ，對(duì)沒有被不確定性策略標(biāo)記的實(shí)例進(jìn)行標(biāo)記，因?yàn)楦拍钇瓶赡軙?huì)出現(xiàn)在實(shí)例空間的任何區(qū)域，不僅是決策邊界附近，利用混合標(biāo)注策略，可以更好地應(yīng)對(duì)概念漂移。后續(xù)的標(biāo)記方法將考慮不平衡數(shù)據(jù)流的分類，不僅對(duì)不確定的樣本進(jìn)行標(biāo)記，還基于類不平衡比率實(shí)現(xiàn)對(duì)少數(shù)類樣本的標(biāo)記。利用基于邊際閾值矩陣的不確定性策略，結(jié)合不平衡率動(dòng)態(tài)調(diào)整閾值，篩選出難以標(biāo)記的實(shí)例，將其與隨機(jī)標(biāo)記策略相結(jié)合，提高模型的分類性能。

圖1 混合標(biāo)注策略Fig.1 Mixed labeling strategy

算法2混合標(biāo)注策略

2.2.2 分類

為了預(yù)測(cè)新到達(dá)實(shí)例的類標(biāo)簽，使用了基于微聚類結(jié)構(gòu)距離和微聚類純度的惰性學(xué)習(xí)框架。聚類假設(shè)表明，距離相近的實(shí)例更有可能具有相同的類標(biāo)簽。通過計(jì)算微聚類的結(jié)構(gòu)距離，可以得到新到達(dá)實(shí)例x的k個(gè)距離最近的微聚類。純度是聚類的一種評(píng)價(jià)指標(biāo)，通過計(jì)算這k個(gè)微聚類的純度，即微聚類中的實(shí)例屬于同種類標(biāo)簽的情況，可以選擇一個(gè)相對(duì)最優(yōu)的微聚類。本文定義微聚類的權(quán)重為純度與距離之比，純度越大，距離越小，則該微聚類的重要性越強(qiáng)，從而為每個(gè)新到達(dá)的實(shí)例選擇最合適的微聚類。對(duì)于新到達(dá)的未標(biāo)記實(shí)例x，搜索離x最近的k個(gè)微聚類，利用k個(gè)微聚類進(jìn)行惰性學(xué)習(xí)（即基于微聚類的k近鄰法）?；谖⒕垲惤Y(jié)構(gòu)距離和微聚類純度的惰性學(xué)習(xí)框架對(duì)原始的k近鄰策略進(jìn)行了改進(jìn)，原始的k近鄰是給定訓(xùn)練一個(gè)數(shù)據(jù)集，對(duì)于新到達(dá)實(shí)例x，從訓(xùn)練數(shù)據(jù)集中找到距離x最近的k個(gè)實(shí)例，這些實(shí)例中占據(jù)多數(shù)的類別即作為x的預(yù)測(cè)類別。原始的k近鄰方法需要存儲(chǔ)用于預(yù)測(cè)的整個(gè)數(shù)據(jù)集，然后得到最近鄰域上的最頻繁的類標(biāo)簽，由于數(shù)據(jù)流的潛在無窮特性，存儲(chǔ)所有用于預(yù)測(cè)的數(shù)據(jù)是不現(xiàn)實(shí)的。本文的模型是動(dòng)態(tài)維護(hù)一組固定數(shù)量的微聚類，從模型中找出距離x最近的k個(gè)微聚類。除結(jié)構(gòu)距離以外，本文加入了微聚類的純度指標(biāo)，可以進(jìn)一步找出相對(duì)最優(yōu)的微聚類。通過計(jì)算k個(gè)微聚類的純度和結(jié)構(gòu)距離，可以得到相應(yīng)的權(quán)重，即該微聚類在整個(gè)模型中的重要性，并選擇權(quán)重最大的微聚類對(duì)新到達(dá)實(shí)例進(jìn)行分類。x到微聚類的距離定義為x到微聚類中心的距離，即MCD(x,MCi)，如式（4），微聚類的純度定義為pur(MCi)，如式（5）。定義微聚類的權(quán)重為微聚類的純度與距離之比。此時(shí)該實(shí)例的標(biāo)記label(x)為權(quán)重最大的微聚類中類頻率最大的類標(biāo)簽，如式（6）。

其中，dist(x,)是給定實(shí)例與微聚類中心的歐幾里德距離。

其中，表示x的k個(gè)最近距離的微聚類。

分類過程如算法3 所示。第4 行利用2.2.2 小節(jié)的分類方法對(duì)實(shí)例分類，第6～19 行判斷是否通過混合標(biāo)記策略請(qǐng)求真實(shí)標(biāo)簽。第7～9行請(qǐng)求真實(shí)標(biāo)簽，并且預(yù)測(cè)正確，則增加參與預(yù)測(cè)的微聚類的權(quán)重，并用x與其真實(shí)標(biāo)簽y更新參與預(yù)測(cè)的微聚類Ci，第11～12行如果預(yù)測(cè)錯(cuò)誤，減少參與預(yù)測(cè)的微聚類權(quán)重并將實(shí)例及其真實(shí)標(biāo)簽存儲(chǔ)在緩沖區(qū)中。第14～15 行如果實(shí)例x到參與預(yù)測(cè)的微聚類的距離小于微聚類的半徑，則用來更新參與預(yù)測(cè)的微聚類，第17～19 行如果大于微聚類半徑，則將x與其預(yù)測(cè)標(biāo)簽y存儲(chǔ)在緩沖區(qū)。存儲(chǔ)在緩沖區(qū)的實(shí)例也形成微聚類，并添加到模型中，當(dāng)只有一個(gè)實(shí)例時(shí)，該微聚類的半徑是以啟發(fā)式的方式設(shè)置的，即把最近的微聚類半徑的值分配給緩沖區(qū)中微聚類的半徑。

算法3創(chuàng)建分類模型

2.3 模型的更新

本文提出的模型動(dòng)態(tài)維護(hù)一組微聚類實(shí)現(xiàn)數(shù)據(jù)流分類。隨著新實(shí)例x到達(dá)，需要對(duì)分類模型進(jìn)行動(dòng)態(tài)更新以適應(yīng)可能發(fā)生的概念漂移。同時(shí)隨著時(shí)間的增長(zhǎng)，舊的微聚類不能預(yù)測(cè)此時(shí)的數(shù)據(jù)流分布，所以必須考慮到時(shí)間變化給分類準(zhǔn)確率帶來的影響。在數(shù)據(jù)流中，隨著時(shí)間的不斷增長(zhǎng)，數(shù)據(jù)流的分布可能會(huì)由于概念漂移而發(fā)生改變，新到達(dá)的實(shí)例參與模型的更新，從而適應(yīng)數(shù)據(jù)流發(fā)生的概念漂移。當(dāng)模型中的某個(gè)微聚類長(zhǎng)時(shí)間沒有更新時(shí)，說明它與當(dāng)前的數(shù)據(jù)流分布不匹配，無法正確地預(yù)測(cè)當(dāng)前實(shí)例的類標(biāo)簽，模型需要減少過時(shí)的微聚類占整個(gè)分類模型的權(quán)重，以適應(yīng)當(dāng)前的數(shù)據(jù)流環(huán)境。因此本文利用指數(shù)衰減函數(shù)計(jì)算模型中的微聚類距離上次更新后的權(quán)重，定義如式（7）。其中λ是衰減率，eT是微聚類從上次更新起經(jīng)過的時(shí)間。當(dāng)模型中的微聚類的權(quán)重小于0 或者是近似為0 時(shí)，則從該模型中刪除該微聚類。本文通過賦予權(quán)重動(dòng)態(tài)調(diào)整微聚類在模型中的重要性，通常僅有兩種情況會(huì)觸發(fā)微聚類權(quán)重的降低，即微聚類對(duì)實(shí)例的標(biāo)簽分類錯(cuò)誤，對(duì)模型綜合性能產(chǎn)生負(fù)面影響；或微聚類長(zhǎng)時(shí)間未被更新，已無法適應(yīng)當(dāng)前數(shù)據(jù)流的分布情況。當(dāng)微聚類的權(quán)重減少到近似為0 或者為負(fù)時(shí)，表明這些微聚類已經(jīng)過時(shí)，存儲(chǔ)的信息不再適用，甚至對(duì)模型的正確分類造成干擾，移除它們可以提高模型的執(zhí)行效率，減少模型的時(shí)空開銷，而不會(huì)對(duì)有效信息造成損失。當(dāng)對(duì)x的標(biāo)記預(yù)測(cè)正確時(shí)，此時(shí)距離x最近的微聚類MC的特征更新：

緩沖區(qū)形成的微聚類在插入到模型中之前，判斷模型中的微聚類數(shù)量是否達(dá)到了給定的最大邊界MaxMC，設(shè)置最大邊界可以避免由于計(jì)算機(jī)內(nèi)存不足而中斷對(duì)數(shù)據(jù)流的處理。如果微聚類的數(shù)量達(dá)到MaxMC時(shí)，需要空間來存儲(chǔ)新的微聚類。按照微聚類的新舊程度排序，即微聚類最后一次更新起經(jīng)過的時(shí)間大小排序。采用合并或者是刪除操作來創(chuàng)建新的空間，搜索距離最近的未標(biāo)記和已標(biāo)記的兩個(gè)微聚類進(jìn)行合并，如果在分類模型中不存在沒有標(biāo)記的微聚類，則搜索具有最多數(shù)量相同標(biāo)記的微聚類，找到其中最近的兩個(gè)微聚類，判斷兩個(gè)微聚類的距離與其中最大半徑的大小，如果距離比最大半徑小，則合并兩個(gè)微聚類，如果距離比最大半徑大，將模型中最舊的微聚類刪除。當(dāng)檢測(cè)到需要合并時(shí)，MC的特征更新如下：

算法4 將所有部分結(jié)合得到了CALC 模型。整體框架如圖2所示。

圖2 CALC模型框架Fig.2 CALC model framework

算法4基于聚類的主動(dòng)學(xué)習(xí)方法實(shí)現(xiàn)數(shù)據(jù)流分類

2.4 算法復(fù)雜度分析

（1）時(shí)間復(fù)雜度。CALC 具有三個(gè)部分：初始化模塊、分類模塊，更新模塊。初始化模塊是把初始訓(xùn)練數(shù)據(jù)(Dinit)劃分為k個(gè)聚類，初始化模塊的運(yùn)行時(shí)間是O(Nk|xc),N是模型中類的總數(shù)，k是劃分為聚類的數(shù)量，|xc|是c類實(shí)例的總數(shù)。初始化模塊只運(yùn)行一次。分類模塊算法3 中第4 行的復(fù)雜度為O(maxMC)，算法4中4～6行的時(shí)間復(fù)雜度為O(maxMC)，8～16行的時(shí)間復(fù)雜度為O(maxMC2)，因?yàn)樵撨^程涉及到兩個(gè)微聚類的合并問題。因此本文提出的算法的時(shí)間復(fù)雜度為O(NK|xc|+maxMC+maxMC2)，約等于O(maxMC2)。

（2）空間復(fù)雜度。模型中維護(hù)了一組微聚類，每個(gè)微聚類由多個(gè)特征組成：MC=(LS,SS,S,N,W,T)，其中LS和SS是分別存儲(chǔ)聚類中帶有標(biāo)簽的每個(gè)類的線性和、平方和的d維矢量，S對(duì)應(yīng)N項(xiàng)類的向量，N、W、T是用來存儲(chǔ)單個(gè)值，每個(gè)微聚類MC的空間復(fù)雜度為O(2×V1×d+3),V1×d為維度為1×d的矩陣。本文提出的算法的空間復(fù)雜度為O(maxMC×MC),maxMC是模型中微聚類的最大數(shù)量。

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

本文對(duì)CALC算法進(jìn)行了實(shí)驗(yàn)評(píng)估，在真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集上驗(yàn)證了提出方法的有效性。在這一部分中介紹了使用的數(shù)據(jù)集以及CALC 算法與其他算法的比較結(jié)果。

3.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

本文使用了6 種不同的數(shù)據(jù)流作為數(shù)據(jù)集。它們具有不同的特征，包括真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集，它們?cè)诟拍钇频男再|(zhì)、速度和數(shù)量方面具有不同的屬性。如表1所示。

表1 實(shí)驗(yàn)中使用的數(shù)據(jù)集Table 1 Datasets used in experiment

（1）真實(shí)數(shù)據(jù)集

Electricity數(shù)據(jù)集[31]由45 312個(gè)樣本組成，每個(gè)樣本包含8個(gè)特征，這些樣本分布在2個(gè)類別中。8個(gè)特征描述了電力需求、市場(chǎng)供應(yīng)、時(shí)間、天氣和季節(jié)等信息，其類別屬性代表了當(dāng)前時(shí)刻的電價(jià)對(duì)于過去24小時(shí)內(nèi)的平均電價(jià)是上漲還是下跌。

CoverType數(shù)據(jù)集[32]的全稱是森林覆蓋類型。該數(shù)據(jù)集包含581 012 個(gè)數(shù)據(jù)樣本，這些樣本分布在7 個(gè)類別中，每個(gè)樣本有54個(gè)特征，描述了土壤和其他相關(guān)信息。

Weather數(shù)據(jù)集[33]全稱是內(nèi)布拉斯加天氣預(yù)報(bào)數(shù)據(jù)集，收集了50 年的每日天氣測(cè)量氣象數(shù)據(jù)。由18 159個(gè)樣本組成，這些樣本分為兩類，其中31%為下雨，69%是無雨，每個(gè)樣本包含了8 個(gè)與天氣相關(guān)的特征，例如溫度、壓力、風(fēng)速等。

（2）人工合成數(shù)據(jù)集

人工合成數(shù)據(jù)集均由在線分析開源平臺(tái)（massive online analysis，MOA）[34]生成。

SEA 數(shù)據(jù)集是由MOA 平臺(tái)上的SEA 生成器生成的包含100 000個(gè)數(shù)據(jù)樣本的數(shù)據(jù)集，有3個(gè)屬性對(duì)應(yīng)4個(gè)類別。該數(shù)據(jù)集上有三次突變漂移，在2.5×104、4.5×104、7.5×104個(gè)實(shí)例處。

HyperPlane數(shù)據(jù)集是由超平面生成器在MOA平臺(tái)上生成的100 000個(gè)數(shù)據(jù)樣本的數(shù)據(jù)集，有10個(gè)屬性對(duì)應(yīng)4 個(gè)類別，該數(shù)據(jù)集上有三次增量漂移，在2.5×104、4.5×104、7.5×104個(gè)實(shí)例處。

RBF 數(shù)據(jù)集是由MOA 平臺(tái)上的RandomRBF 生成器生成的包含100 000個(gè)數(shù)據(jù)樣本的數(shù)據(jù)集，有20個(gè)屬性對(duì)應(yīng)4 個(gè)類別，該數(shù)據(jù)集包含兩個(gè)漸進(jìn)的概念漂移，在3.5×104、6.5×104個(gè)實(shí)例處，其中數(shù)據(jù)流的概念漂移的變化率為0.01。

本文利用準(zhǔn)確率和內(nèi)存消耗對(duì)算法進(jìn)行評(píng)價(jià)，分類準(zhǔn)確率通常是評(píng)估分類器性能的一個(gè)重要的標(biāo)準(zhǔn)，統(tǒng)計(jì)的是將樣本正確分類的比率。實(shí)時(shí)準(zhǔn)確率反映了模型在某個(gè)時(shí)刻的分類性能，平均準(zhǔn)確率反映了模型在整體樣本上的分類性能，除了準(zhǔn)確率，模型的內(nèi)存消耗作為輔助的評(píng)價(jià)指標(biāo)。

3.2 比較方法

為了驗(yàn)證提出算法的性能，本文把該算法與一些經(jīng)典的數(shù)據(jù)流分類算法和最近兩年的算法進(jìn)行比較。下面對(duì)這些比較的算法進(jìn)行了簡(jiǎn)單的介紹。

在線精度更新集成（online accuracy updated ensemble，OAUE）[35]是一種集成分類方法，將基于精度的加權(quán)機(jī)制與Hoeffding 樹的增量性質(zhì)結(jié)合在一起，該方法對(duì)基分類器進(jìn)行加權(quán)，不限制基分類器的大小，也不使用任何窗口，可以對(duì)不同類型的概念漂移做出處理。

非平穩(wěn)環(huán)境中概念漂移的增量學(xué)習(xí)（incremental learning of concept drift in nonstationary environments，LNSE）[36]是另一種分類器集成方法。從連續(xù)的數(shù)據(jù)流中學(xué)習(xí)，對(duì)于新到來的一組數(shù)據(jù)建立一個(gè)基分類器，并將這些分類器與動(dòng)態(tài)加權(quán)的多數(shù)相結(jié)合，不需要考慮概念漂移的性質(zhì)以及速度。

DWM 是一種集成方法，利用模型分類性能，在集成中動(dòng)態(tài)調(diào)整加權(quán)基分類器，因此在概念漂移發(fā)生時(shí)具有更強(qiáng)的響應(yīng)能力[37]。

Khezri 等[38]提出了一種新的基于性能選擇度量的半監(jiān)督集成算法（a novel semi-supervised ensemble algorithm using a performance-based selection metric to data streams，SSE-PBS）。算法維護(hù)一個(gè)分類器池，為每個(gè)基分類器提供一個(gè)權(quán)重因子，使用多數(shù)加權(quán)投票策略對(duì)未標(biāo)記的數(shù)據(jù)點(diǎn)進(jìn)行分類。模型更新過程：（1）利用數(shù)據(jù)塊中標(biāo)記的樣本計(jì)算基分類器的錯(cuò)誤率，從而更新基分類器的權(quán)值。并利用新到達(dá)數(shù)據(jù)塊訓(xùn)練新的基分類器加入池中，若池滿，則替換池中權(quán)值最低的分類器。（2）利用集成分類器給未標(biāo)記樣本加偽標(biāo)記并計(jì)算置信度，基于性能的標(biāo)準(zhǔn)選擇偽標(biāo)記數(shù)據(jù)的子集，添加到當(dāng)前塊的標(biāo)記數(shù)據(jù)中以增量更新基分類器。

ORSL是近兩年來一種新的數(shù)據(jù)流分類方法，通過動(dòng)態(tài)維護(hù)一組微聚類對(duì)傳入的數(shù)據(jù)實(shí)例分類，該方法可以在有限的內(nèi)存下工作。

具有概念漂移的多類不平衡數(shù)據(jù)流的綜合主動(dòng)學(xué)習(xí)方法（a comprehensive active learning method for multiclass imbalanced data streams with concept drift，CALMID）是Liu 等[39]在2021 年提出的解決多類不平衡和概念漂移數(shù)據(jù)流的分類方法。提出一種基于不對(duì)稱邊界閾值矩陣的新型不確定性策略，將該策略與不確定性策略、隨機(jī)策略相結(jié)合解決真實(shí)標(biāo)簽不足的問題。使用自適應(yīng)窗口算法判斷是否發(fā)生概念漂移，當(dāng)檢測(cè)到概念漂移時(shí)，利用樣本滑動(dòng)窗口中緩存的樣本創(chuàng)建類平衡的訓(xùn)練樣本序列，用這些樣本訓(xùn)練新的基分類器添加到集成分類器中。

OAUE、DWM、LNSE是有監(jiān)督學(xué)習(xí)算法，使用100%標(biāo)記的數(shù)據(jù)集，ORSL、CALMID、SSE-PBS、CALC 算法是半監(jiān)督學(xué)習(xí)算法，使用20%標(biāo)記的數(shù)據(jù)集。

3.3 參數(shù)選擇

從第2部分可以看出，該算法有3個(gè)主要參數(shù)：隨機(jī)標(biāo)記閾值σ，模型中微聚類的最大數(shù)量m，衰減率λ。針對(duì)這3 個(gè)參數(shù)在6 個(gè)數(shù)據(jù)集上分別實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)重復(fù)10 次，取10 次結(jié)果的平均值，以確保結(jié)果更加準(zhǔn)確，找到參數(shù)最合適的取值。

隨機(jī)標(biāo)記閾值σ的取值由0.01 到0.50，從表2 可以看出，隨著閾值的增大，準(zhǔn)確率逐漸增大且波動(dòng)幅度較小，當(dāng)σ達(dá)到0.50 時(shí)，分類準(zhǔn)確率最高。隨機(jī)策略中生成0 到1 范圍內(nèi)均勻分布的隨機(jī)變量，當(dāng)隨機(jī)變量小于閾值時(shí)進(jìn)行人工標(biāo)記，閾值較大代表更大概率得到真實(shí)標(biāo)簽，利用真實(shí)標(biāo)簽?zāi)軌虬l(fā)現(xiàn)潛在的概念漂移，及時(shí)更新模型適應(yīng)當(dāng)前的數(shù)據(jù)分布。但是實(shí)例被人工標(biāo)記的概率越大，標(biāo)記成本越高，考慮到標(biāo)記成本，本文選擇σ=0.02 為默認(rèn)值。

表2 不同參數(shù)σ 下的準(zhǔn)確率比較Table 2 Accuracy under different σ 單位：%

λ的取值由0.000 001 到0.000 005，從表3 可以看出，λ的最佳取值為0.000 002，從0.000 002 以后，分類準(zhǔn)確率呈下降趨勢(shì)，這是由于隨著衰減率的增大，微聚類權(quán)重受時(shí)間的影響也就越大，過多考慮時(shí)間因素，弱化了其他因素對(duì)權(quán)重的影響，從而影響模型分類準(zhǔn)確率，本文將λ的取值設(shè)置為0.000 002。

表3 不同參數(shù)λ 下的準(zhǔn)確率比較Table 3 Accuracy under different λ 單位：%

m的取值由500 到2 500，由圖3 可以看出，隨著m值的不斷增加，分類準(zhǔn)確率逐漸增加，當(dāng)m值達(dá)到1 500 時(shí)，分類準(zhǔn)確率增加趨勢(shì)放緩。這是由于隨著模型中的微聚類數(shù)量增多，數(shù)據(jù)流的變化狀態(tài)可以得到很好的檢測(cè)，但是微聚類的數(shù)量增多也造成了處理時(shí)間變長(zhǎng)。為了減少模型的處理時(shí)間，本文將最大微聚類的取值設(shè)置成1 500。

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

本文從實(shí)時(shí)準(zhǔn)確率、整個(gè)過程的平均準(zhǔn)確率和內(nèi)存消耗的角度在6個(gè)數(shù)據(jù)集上比較了提出的方法與3.2節(jié)中的對(duì)比算法。對(duì)于SEA、HyperPlane、RBF 數(shù)據(jù)集，實(shí)時(shí)準(zhǔn)確率是指測(cè)試點(diǎn)前后10 000個(gè)實(shí)例的平均準(zhǔn)確率，對(duì)于CoverType 數(shù)據(jù)集，實(shí)時(shí)準(zhǔn)確率是指測(cè)試點(diǎn)前后50 000個(gè)實(shí)例的平均準(zhǔn)確率，對(duì)于Electricity數(shù)據(jù)集，是前后5 000 個(gè)實(shí)例的平均準(zhǔn)確率，如第10 000 個(gè)實(shí)例的實(shí)時(shí)準(zhǔn)確率是5 000個(gè)實(shí)例到第15 000個(gè)實(shí)例的平均準(zhǔn)確率。不同模型的實(shí)時(shí)準(zhǔn)確率比較如圖4～圖9所示。

圖4 顯示了在SEA 數(shù)據(jù)集上，CALC 模型與其他6種模型的實(shí)時(shí)準(zhǔn)確率比較。OAUE的準(zhǔn)確率較高，波動(dòng)幅度比CALC稍大，因?yàn)镺AUE算法使用固定窗口的實(shí)例創(chuàng)建新分類器，以替代模型中最差的基分類器，但是窗口大小并不會(huì)根據(jù)數(shù)據(jù)分布的變化而變化，在突變漂移處無法較好地適應(yīng)概念漂移。CALC、SSE-PBS、ORSL、CALMID 分類性能相對(duì)穩(wěn)定，CALC 與ORSL、DWM 相比，前期準(zhǔn)確率相差不大，隨著數(shù)據(jù)流實(shí)例的增多，CALC 的分類準(zhǔn)確率高于這兩種模型，在發(fā)生突變概念漂移時(shí)，CALC準(zhǔn)確率處于平穩(wěn)或上升狀態(tài)。因?yàn)镃LAC不斷更新微聚類的權(quán)重，使模型能夠快速適應(yīng)當(dāng)前的數(shù)據(jù)流環(huán)境。

如圖5所示，在HyperPlane數(shù)據(jù)集上，CALC和ORSL基本上沒有受到增量漂移的影響，分類準(zhǔn)確率呈上升趨勢(shì)。因?yàn)镃ALC 將預(yù)測(cè)錯(cuò)誤的實(shí)例或者在模型邊界之外的實(shí)例移動(dòng)到緩沖區(qū)中，緩沖區(qū)的實(shí)例形成微聚類參與模型的更新，可以適應(yīng)概念的逐漸變化，保證分類準(zhǔn)確率的穩(wěn)定。其他五種模型的分類準(zhǔn)確率都有不同程度的波動(dòng)。雖然DWM 算法的分類準(zhǔn)確率隨著數(shù)據(jù)流實(shí)例的增長(zhǎng)時(shí)而產(chǎn)生優(yōu)于CALC的結(jié)果，但是DWM的分類準(zhǔn)確率不斷波動(dòng)。因?yàn)镈WM逐個(gè)處理到達(dá)實(shí)例，能夠及時(shí)捕捉到數(shù)據(jù)分布的變化，在處理突變漂移方面具有優(yōu)勢(shì)，但是缺少周期更新機(jī)制，無法適應(yīng)增量式概念漂移。

圖5 在HyperPlane數(shù)據(jù)集上的實(shí)時(shí)準(zhǔn)確率Fig.5 Real-time accuracy on HyperPlane

從圖6可以看出，在RBF數(shù)據(jù)集上，CALC、OAUE、ORSL、CALMID不受漸進(jìn)漂移的影響，始終保持較高的分類準(zhǔn)確率，并且CALC的分類準(zhǔn)確率略高于OAUE和ORSL。OAUE 能較好地適應(yīng)概念漂移，DWM 和LNSE的分類準(zhǔn)確率較低。CALC動(dòng)態(tài)維護(hù)一組微聚類，根據(jù)微聚類的權(quán)重，能檢測(cè)到數(shù)據(jù)流的長(zhǎng)期變化情況，刪除過時(shí)的微聚類，保證模型的周期更新。LNSE 對(duì)新到來的一組數(shù)據(jù)建立一個(gè)基分類器添加到模型中，數(shù)據(jù)塊的大小會(huì)影響概念漂移的判斷，而且沒有增量訓(xùn)練已有的基分類器，導(dǎo)致模型處理漸進(jìn)漂移時(shí)存在不穩(wěn)定的缺陷。

圖6 在RBF數(shù)據(jù)集上的實(shí)時(shí)準(zhǔn)確率Fig.6 Real-time accuracy on RBF

從圖7 可以看出，CALC 模型的分類準(zhǔn)確率一直比較穩(wěn)定且屬于較高水平，而LNSE模型的分類準(zhǔn)確率波動(dòng)嚴(yán)重，因?yàn)長(zhǎng)NSE 沒有對(duì)集成采用剪枝技術(shù)，當(dāng)數(shù)據(jù)流中概念漂移頻繁出現(xiàn)時(shí)，模型中的無關(guān)舊數(shù)據(jù)逐漸增多，影響分類性能。

圖7 在CoverType數(shù)據(jù)集上的實(shí)時(shí)準(zhǔn)確率Fig.7 Real-time accuracy on CoverType

從圖8 可以看出，在Electricity 數(shù)據(jù)集上，CALC 算法始終保持較高準(zhǔn)確率，當(dāng)模型中微聚類的權(quán)重較低時(shí)，刪除所有不符合要求的微聚類，模型更新速度快，對(duì)概念漂移適應(yīng)力更強(qiáng)。OAUE模型剛開始占優(yōu)勢(shì)，隨著數(shù)據(jù)流實(shí)例的增長(zhǎng)，CALC 的分類準(zhǔn)確率高于OAUE。圖9 是Weather 數(shù)據(jù)集上各個(gè)模型的實(shí)時(shí)準(zhǔn)確率比較，CALC分類準(zhǔn)確率基本高于其他模型。

圖8 在Electricity數(shù)據(jù)集上的實(shí)時(shí)準(zhǔn)確率Fig.8 Real-time accuracy on Electricity

圖9 在Weather數(shù)據(jù)集上的實(shí)時(shí)準(zhǔn)確率Fig.9 Real-time accuracy on Weather

為了更加準(zhǔn)確地比較各個(gè)模型，考慮到模型的整體分類性能，表4顯示了不同數(shù)據(jù)集上不同模型的平均分類準(zhǔn)確率。從表4 能看出CALC 的整體分類性能高于其他模型。所以，不管是在整體分類性能還是實(shí)時(shí)分類性能上，CALC與其他6種模型相比都有一定的優(yōu)勢(shì)。

表4 平均準(zhǔn)確率比較Table 4 Average accuracy comparison 單位：%

3.5 內(nèi)存消耗比較

由于數(shù)據(jù)流快速實(shí)時(shí)的不斷產(chǎn)生，存儲(chǔ)所有的數(shù)據(jù)是不現(xiàn)實(shí)的，所以需要在有限內(nèi)存下對(duì)新到達(dá)實(shí)例進(jìn)行分類。為了進(jìn)一步判斷模型的分類性能，實(shí)驗(yàn)比較了模型在6個(gè)數(shù)據(jù)集上的平均內(nèi)存消耗。如表5所示，DWM內(nèi)存消耗最少，其次是CALC。DWM 是一種在線集成算法，根據(jù)最新到達(dá)的實(shí)例在線更新基分類器的權(quán)值，不需要新建基分類器，內(nèi)存消耗較低。CALC利用了緩沖區(qū)機(jī)制，緩沖區(qū)形成的微聚類會(huì)添加到模型中，所以內(nèi)存消耗比DWM 略高，但是從3.4 節(jié)“實(shí)驗(yàn)結(jié)果”可以看出，CALC能更好地應(yīng)對(duì)概念漂移，分類準(zhǔn)確率更高，用少量?jī)?nèi)存換取更高的分類準(zhǔn)確率是可取的。OAUE內(nèi)存消耗最大，因?yàn)镺AUE 是基于每個(gè)數(shù)據(jù)塊創(chuàng)建一個(gè)基分類器，增加了構(gòu)建分類器的頻率和內(nèi)存消耗。CALMID維持集成分類器、標(biāo)簽滑動(dòng)窗口和樣本滑動(dòng)窗口，滑動(dòng)窗口的大小對(duì)內(nèi)存消耗有一定的影響。CALC設(shè)置了可存儲(chǔ)微聚類的最大數(shù)量，當(dāng)微聚類的數(shù)量達(dá)到最大值時(shí)，對(duì)模型中的微聚類進(jìn)行合并或者刪除操作，利用新到達(dá)實(shí)例在線更新模型，相比于其他的對(duì)比方法內(nèi)存消耗更低。

表5 內(nèi)存消耗比較Table 5 Memory consumption comparison

4 結(jié)語

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，數(shù)據(jù)增長(zhǎng)速度越來越快，數(shù)據(jù)流挖掘面臨著理論和技術(shù)上的挑戰(zhàn)。本文針對(duì)數(shù)據(jù)流概念漂移的問題，設(shè)計(jì)了基于聚類的數(shù)據(jù)流分類模型和對(duì)應(yīng)的算法。進(jìn)一步，考慮到數(shù)據(jù)類標(biāo)簽不足的問題，設(shè)計(jì)了主動(dòng)學(xué)習(xí)混合查詢策略，減少了標(biāo)注成本。本文提出了基于聚類的主動(dòng)學(xué)習(xí)算法，改進(jìn)了在線半監(jiān)督學(xué)習(xí)算法，與其他的集成分類算法相比，分類準(zhǔn)確率更高而且面對(duì)概念漂移時(shí)更穩(wěn)定。

在未來的工作中，將針對(duì)數(shù)據(jù)流中存在的類別不平衡問題進(jìn)行研究。不平衡數(shù)據(jù)流中的少數(shù)類樣本會(huì)突然出現(xiàn)，嚴(yán)重影響模型的準(zhǔn)確構(gòu)建。在半監(jiān)督情況下，少數(shù)類樣本可能出現(xiàn)全部無法獲取真實(shí)標(biāo)簽的情況，影響這類樣本的學(xué)習(xí)，無法反映數(shù)據(jù)的真實(shí)分布。接下來將實(shí)現(xiàn)不平衡數(shù)據(jù)流的分類模型，考慮如何設(shè)計(jì)一種標(biāo)簽查詢策略對(duì)少數(shù)類樣本進(jìn)行標(biāo)記。