低代價的數(shù)據(jù)流分類算法①

李 南

(福建農(nóng)林大學(xué) 計算機與信息學(xué)院, 福州 350002)

低代價的數(shù)據(jù)流分類算法①

李 南

(福建農(nóng)林大學(xué) 計算機與信息學(xué)院, 福州 350002)

現(xiàn)有數(shù)據(jù)流分類算法大多使用有監(jiān)督學(xué)習(xí), 而標記高速數(shù)據(jù)流上的樣本需要很大的代價, 因此缺乏實用性. 針對以上問題, 提出了一種低代價的數(shù)據(jù)流分類算法2SDC. 新算法利用少量已標記類別的樣本和大量未標記樣本來訓(xùn)練和更新分類模型, 并且動態(tài)監(jiān)測數(shù)據(jù)流上可能發(fā)生的概念漂移. 真實數(shù)據(jù)流上的實驗表明, 2SDC算法不僅具有和當(dāng)前有監(jiān)督學(xué)習(xí)分類算法相當(dāng)?shù)姆诸惥? 并且能夠自適應(yīng)數(shù)據(jù)流上的概念漂移.

概念漂移; 數(shù)據(jù)流; 分類; 低代價; 監(jiān)督學(xué)習(xí)

數(shù)據(jù)流分類現(xiàn)已成為數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點, 涉及的實際應(yīng)用包括網(wǎng)絡(luò)入侵檢測以及垃圾郵件過濾等. 數(shù)據(jù)流上的樣本持續(xù)、快速地到來, 使得傳統(tǒng)的一次性靜態(tài)學(xué)習(xí)的數(shù)據(jù)挖掘算法無法適用. 此外,數(shù)據(jù)流上隱含的知識也有可能隨著時間的推移而發(fā)生變化, 出現(xiàn)概念漂移[1]現(xiàn)象. 例如, 某些特定商品(如冷飲)的銷量隨著季節(jié)會呈現(xiàn)周期性的變化, 大家在網(wǎng)上關(guān)注的熱點話題會不斷變化等. 如何捕獲數(shù)據(jù)流上的當(dāng)前概念也為處理數(shù)據(jù)流分類問題帶來了新的挑戰(zhàn).

目前對數(shù)據(jù)流進行分類, 單一分類模型和集成分類模型是學(xué)者們主要采用的兩種方式. 單一分類模型首先在訓(xùn)練樣本集合上建立初始分類模型, 然后為了擬合當(dāng)前數(shù)據(jù)流樣本的分布情況, 用隨后到來的樣本對現(xiàn)有模型進行增量式更新. 然而, 這種模型通常結(jié)構(gòu)復(fù)雜, 并且需要頻繁地對模型進行繁瑣的更新. 在將數(shù)據(jù)流上的樣本按照到來的時間劃分為大小相同的數(shù)據(jù)塊后, 集成分類模型用新數(shù)據(jù)塊上建立的基分類器, 替換當(dāng)前模型中分類性能較差或者已經(jīng)過時的基分類器. 由于基分類器的訓(xùn)練速度通常比單一模型的更新速度快[2], 因此集成分類模型更適合對高速持續(xù)產(chǎn)生的數(shù)據(jù)流進行分類.

本文提出一種采用集成分類模型方式的低代價的數(shù)據(jù)流分類算法(Semi-supervised learning algorithm for Stream Data Classification, 簡稱2SDC). 無論是采用單一分類模型還是集成分類模型, 現(xiàn)有絕大部分數(shù)據(jù)流上的分類算法重點只關(guān)注模型的分類效果, 進而假設(shè)所有待分類樣本一旦被分類其類別信息即可立刻獲得,然后馬上利用這些類別信息對模型進行更新以最大限度地提高模型的分類精度, 這無疑人為忽略了標記數(shù)據(jù)流上樣本所需的高昂代價. 本文的創(chuàng)新主要在于采用半監(jiān)督學(xué)習(xí)的思想來降低更新現(xiàn)有模型所需要的有類別標記樣本的使用量, 因此更符合實際應(yīng)用中的要求. 此外, 算法主動檢測概念漂移的發(fā)生, 這也加快了算法對數(shù)據(jù)流上當(dāng)前概念的適應(yīng)速度.

1 2SDC算法基分類器

現(xiàn)有絕大部分數(shù)據(jù)流上的分類算法使用全部樣本的真實類別來擬合樣本的當(dāng)前分布情況, 而標記高速數(shù)據(jù)流上的所有樣本需要很高的代價. 為了減少擬合數(shù)據(jù)當(dāng)前分布所需要樣本的數(shù)量, 2SDC算法首先使用類似于半監(jiān)督學(xué)習(xí)的聚類算法, 將給定數(shù)據(jù)塊劃分為若干個簇. 然后, 挑選中其中有代表性的簇, 保存每個簇的中心、半徑、所在子空間以及相應(yīng)的類別作為集成分類模型的基分類器, 進而用其來擬合數(shù)據(jù)流上當(dāng)前樣本的分布情況.

1.1 無監(jiān)督學(xué)習(xí)的K-means聚類算法

設(shè)固定大小的數(shù)據(jù)塊D由N條樣本組成, 即D={(x1,y1),(x2,y2),...,(xN,yN)}. 其中,xn=(xn1,xn2,...,xnM)表示由M維屬性構(gòu)成的第n條樣本,yn∈{0,1,2,...,L}表示xn的類別. 如果yn=0, 表示該樣本的類別未被標記.

要將數(shù)據(jù)塊D中的樣本劃分為K個簇{C1,C2,...,C K}, 無監(jiān)督的K-means聚類算法的目標是最小化所有樣本到各自簇中心的距離之和, 即最小化目標函數(shù):其中,ck表示第k個簇的中心,dis(x,ck)表示樣本x與ck的相異度.

1.2 2SDC算法基分類器構(gòu)建

為了降低標記樣本所需要的代價, 訓(xùn)練集中應(yīng)該只有少部分樣本已標記類別. 此時, 聚類的目標應(yīng)是在最小化所有樣本到各自簇中心的距離之和的同時,使得已標記類別的來自同一類的樣本盡可能的在相同的簇中, 即最小化目標函數(shù):

公式(1)中的impk表示第k個簇的“不純凈”程度,算法中使用信息熵來衡量, 即表示第k個簇中屬于第l類樣本的先驗概率, 即其中表示被劃分到第k個簇的樣本個數(shù), |Ck(l)|表示Ck中屬于第l類的樣本個數(shù). 顯然, 如果被劃分到Ck中的已標記類別的樣本均來自同一個類, 那么impk=0, 此時impk最小. 相反, 若第k個簇中的已標記樣本均勻地來自各個類別, 那么impk=log(L), 此時impk最大.

公式(1)中的vk表示第k個簇的權(quán)值.為了平衡“簇間相異度”(公式(1)中的前半部分)和“簇內(nèi)純凈度”(公式(1)中的后半部分)的影響,取綜合以上考慮, 2SDC算法中使用的聚類算法的目標函數(shù)為:

這樣, 給定樣本x以及簇中心{c1,c2...,cK},當(dāng)前條件下的最優(yōu)聚類為:

① 如果x是未標記類別的樣本,

② 如果x是已標記類別的樣本,

此外, 數(shù)據(jù)空間中往往存在與特定類別無關(guān)或者次要的屬性[3]. 因此在聚類前, 需要先將樣本投影到各個簇對應(yīng)的子空間上, 然后再考慮其與各個簇中心的相異度. 這樣也能減少聚類算法的迭代次數(shù), 加快算法的收斂速度. 因此, 給定當(dāng)前樣本xi,xi和第k個簇的中心ck的相異度dis(xi,ck)應(yīng)該采用加權(quán)的歐式距離來計算, 即算法中使用一個對角矩陣表示簇Ck中各個屬性的權(quán)重(即所在的子空間), 其滿足值得注意的是,即使是為來自同一類別的樣本所建立的聚類, 也有可能在不同的子空間上. 以文本數(shù)據(jù)流分類為例, 來自“體育”類別的樣本可能來自 “電子競技”或者“傳統(tǒng)項目”, 而這兩個部分每個屬性的權(quán)重顯然應(yīng)該是不一樣的. 因此, 2SDC算法中為每個簇獨立地設(shè)置一個屬性權(quán)重.

此外, 如果各個簇的初始中心是隨機選取的, 這會對算法最終的結(jié)果造成較大的影響. 因此, 為了保證模型分類效果, 2SDC算法選取初始中心的方法為:設(shè)為每個類別樣本建立的簇的個數(shù)為num(即選取K=num·L), 那么在數(shù)據(jù)塊D中已標記的屬于第l類的樣本里, 依次選取num條最不相似的樣本作為初始的簇中心. 綜上所述, 2SDC算法基分類器構(gòu)建過程如算法1.

?

Step3. 初始化迭代次數(shù)h=1. Step4. 根據(jù)公式(3)或公式(4), 依次將N條樣本分配到各個簇中.h++. Step5. 更新每個簇的中心. Step6. 根據(jù)公式(5), 更新各個簇每個屬性的權(quán)重. Step7. 如果≤ε-h+1ChC并且≤ε-h+1WhW,算法停止. 否則, 隨機重新排列N條樣本的順序, 轉(zhuǎn)向Step4. End

如果每次劃分都只是將當(dāng)前樣本劃分到當(dāng)前最優(yōu)的聚類中, 那么聚類結(jié)果和樣本的排列順序緊密相關(guān).然而, 嘗試所有的排列順序以獲得最優(yōu)解是不現(xiàn)實的.因此算法1中在每次聚類后, 重新排列N條樣本的順序, 以接近最優(yōu)解. 文獻[4]中證明這種方式是收斂的.

在將數(shù)據(jù)塊D劃分為K個簇后, 2SDC算法將進行篩選, 選取其中有代表性的簇, 以四元組cluster={center,radius,weight,label} 的形式保存下來, 用來擬合D上各類別樣本的分布情況. 其中,center表示cluster的中心,radius表示半徑,weight表示所在的子空間,label表示類別. 具體過程如算法2.

Begin Step1. 在被劃分到K個簇的已標記樣本中, 依次選取各個類別標記樣本最多的簇, 加入集合S. Step2. 在剩下的K-L個簇中, 刪除已標記各類別樣本之和過少(小于ε·labPer·N)的簇, 將剩下簇的加入S. Step3. 對于S中的簇, 構(gòu)建相應(yīng)的cluster. 其中,用xi表示簇Ck中距離中心最遠的樣本, 那么保存簇Ck的中心ck作為centerk, 屬性權(quán)重Wk作為weightk,已標記類別樣本里數(shù)量最多的類標簽作為labelk,radiusk=dis(xi,centerk). End

2SDC算法基于普遍的聚類假設(shè)[5]: “屬于同一聚類的樣本很可能具有同樣的類別”來對未知樣本進行有效分類. 給定待分類樣本x和一個基分類器Base,依次計算x和Base中所有cluster中心的加權(quán)距離. 如果(即x被覆蓋), 那么根據(jù)聚類假設(shè),x和建立clusterk的樣本形成一個聚類,因此將x分類為labelk. 如果x被多個cluster覆蓋, 那么選取其中類別數(shù)量最多的, 作為x類別的估計值.如果x不被任何cluster覆蓋或者數(shù)量最多的類別不是唯一的, 那么說明x是難處理樣本,Base不對其進行判斷.

1.3 集成分類器構(gòu)造

2SDC算法集成分類器E由p個基分類器和一個仲裁分類器構(gòu)成. 其中仲裁分類器使用增量樸素Bayes分類器. 給定待分類樣本x, 分類過程如算法3.

算法3: 2SDC算法分類輸 入: 集成分類模型E, 待分類樣本x輸 出: x類別的估計值yBegin Step1. 依次使用基分類器對x進行分類. Step2. 設(shè)各基分類器對x類別的估計值分別為} ,..., {y1,y2yp Y=. 如果Y中出現(xiàn)次數(shù)最多的類別不唯一, 或者各基分類器均不對x進行判斷, 那么使用仲裁分類器對x進行分類. 否則, 返回Y中出現(xiàn)次數(shù)最多的類別. End

每當(dāng)新的數(shù)據(jù)塊到來, 首先利用算法3, 使用現(xiàn)有分類模型E對樣本進行分類. 然后, 訓(xùn)練一個新的基分類器. 如果E中現(xiàn)有的基分類器個數(shù)不超過p, 那么保存新的基分類器. 否則, 將原來基分類器中建立時間最早的替換出來. 最后, 用新數(shù)據(jù)塊上的有標記類別的樣本對仲裁分類器進行增量更新. 這樣, 2SDC算法具有對cluster覆蓋的樣本高分類精度的同時, 對不被任何cluster覆蓋的樣本的分類精度也有了保證.

2 概念漂移檢測

現(xiàn)有集成分類算法大多沒有概念漂移檢測機制,被動的使用新基分類器逐步替換過時基分類器的方式來適應(yīng)概念漂移, 這會導(dǎo)致概念漂移發(fā)生后需要較長時間才能將過時的基分類器全部替換, 表現(xiàn)為模型的分類精度會出現(xiàn)較長時間的持續(xù)下降. 2SDC算法采用概念漂移檢測機制, 當(dāng)檢測到概念漂移發(fā)生時, 立刻拋棄現(xiàn)有整個已經(jīng)過時的集成分類模型, 因此能夠更快地適應(yīng)數(shù)據(jù)流上的最新概念.

文獻[6]認為概念漂移產(chǎn)生的來源于樣本與其類別的聯(lián)合概率隨著時間或者環(huán)境的改變而發(fā)生變化. 無論是某類的先驗概率發(fā)生變化、某類的類概率發(fā)生變化還是樣本后驗概率發(fā)生變化, 都會導(dǎo)致已經(jīng)穩(wěn)定的現(xiàn)有模型的分類精度出現(xiàn)較大范圍的波動. 即當(dāng)數(shù)據(jù)流保持穩(wěn)定時, 分類模型對于有標記類別樣本的分類精度應(yīng)該保持在一個比較穩(wěn)定的水平. 因此, 2SDC算法使用一個高斯分布來擬合分類精度的分布情況. 設(shè)前t個數(shù)據(jù)塊上有標記樣本的平均分類精度為μ, 方差為σ. 如果t+1個數(shù)據(jù)塊上有標記樣本的分類精度低于μ-1.96σ, 那么說明出現(xiàn)概念漂移, 需要刪除當(dāng)前的基分類器和仲裁分類器, 重建分類模型以適應(yīng)數(shù)據(jù)流上的現(xiàn)有概率. 此外, 數(shù)據(jù)流上不可避免的新類別樣本的出現(xiàn)也是一種特殊的概念漂移. 因此, 如果當(dāng)前數(shù)據(jù)塊上標記樣本中出現(xiàn)新類別的樣本, 那么同樣也需要重建分類模型.

3 實驗結(jié)果與分析

本節(jié)在真實的文本數(shù)據(jù)流上對2SDC算法的分類效果進行測試. 實驗環(huán)境為Intel(R) Core i5 2.5GHz CPU、4G RAM PC機. 比較算法使用數(shù)據(jù)流上常用的對比算法(Streaming Ensemble Algorithm , 簡稱SEA)[7]、比較具有代表性的加權(quán)集成分類算法(Aggregate Ensemble, 簡稱AE)[8]、基于決策樹和Bayes混合模型的集成分類算法(Weight Ensemble Classifier -Decision Tree and Bayes, 簡稱WE-DTB)[9]以及基于半監(jiān)督學(xué)習(xí)的數(shù)據(jù)流集成分類算法(Semi-Supervised Learning Based Ensemble Classifier, 簡稱SEClass)[10].值得注意的是, 前三種對比算法使用的所有樣本均是有類別標記的, 而SEClass算法和2SDC算法使用的樣本是部分標記類別的, 其中有標記類別的樣本占所有樣本數(shù)量的20%. 各種算法的參數(shù)分別參照對應(yīng)文獻中的設(shè)置, 數(shù)據(jù)塊大小500, 2SDC算法中基分類器個數(shù)為5, 為各類樣本保存的簇個數(shù)為3.

實驗中使用的文本數(shù)據(jù)流來自20-Newsgroups數(shù)據(jù)集. 數(shù)據(jù)集的屬性個數(shù)為500, 類別數(shù)為6, 樣本的分布情況見表1. 實驗中將數(shù)據(jù)集劃分為兩個部分來模擬數(shù)據(jù)流多類別出現(xiàn)概念漂移的情況. 在前半部分,只有來自med, baseball, autos, motor四個類別的樣本;在后半部分中, motor類的樣本消失, 并新出現(xiàn)了space和politics類的樣本. 各種算法在20-Newsgroups數(shù)據(jù)集上的平均分類精度如表2所示. 由于2SDC算法基分類器初始中心選擇的不同會對分類結(jié)果造成影響,因此結(jié)果采用10次實驗的平均值, 并且在表2中給出方差.

表1 20-Newsgroups中各類分布

表2 各種算法在文本數(shù)據(jù)流上的平均分類精度

從表2中可以看出, 只使用少量有類別標記樣本的2SDC算法分類效果優(yōu)于使用全部有標記樣本的WE-DTB算法和SEA算法, 達到和AE算法相當(dāng)?shù)乃? 并且優(yōu)于基于半監(jiān)督學(xué)習(xí)的SEClass算法. 雖然2SDC算法初始中心的不同會對分類結(jié)果造成一定的影響, 但是方差并不太大. 由于AE算法使用的所有樣本都是有類別的, 而且算法在當(dāng)前數(shù)據(jù)塊上使用多種分類算法建立相應(yīng)的多個分類器以構(gòu)成集成分類模型,因此分類精度是所有算法中最高的. 為了檢測本文使用的概念漂移機制的有效性, 不同算法在測試數(shù)據(jù)集上每連續(xù)500條樣本的分類精度如圖1所示.

圖1 20-Newsgroups上分類精度比較

從圖1可以很清晰的看出, 在某一時刻, 由于新類別樣本的出現(xiàn)以及原來類別樣本的消失, 各種算法的精度均出現(xiàn)了不同程度的下降. 隨著新類別樣本的不斷出現(xiàn), 在一定時間后, 分類精度又都逐漸恢復(fù)到了之前的水平. 本文提出的2SDC算法的恢復(fù)速度較快, 這也證實了本文使用的概念漂移檢測機制的有效性. 此外, 不同標記比例下算法的平均分類精度見圖2.

圖2 不同標記比例下平均分類精度

從圖2中可以看出, 隨著有標記類別樣本數(shù)量的增多, 基分類器的邊界更加準確, 也有更多的樣本參與到仲裁分類器的更新, 因此2SDC算法的分類精度逐漸增高. 當(dāng)標記樣本比例較低時, 模型的分類精度還是穩(wěn)定在一個相當(dāng)?shù)乃? 不同類別樣本保存的簇個數(shù)下算法的平均分類精度見圖3.

圖3 不同簇個數(shù)下平均分類精度比較

從圖3可以看出, 當(dāng)為每個類別樣本保存3個簇時, 分類效果最佳. 當(dāng)簇個數(shù)過低時, 基分類器無法準確擬合各類別樣本的分布情況, 導(dǎo)致分類精度較低.然而, 過高的簇個數(shù)降低了分類模型的泛化能力, 同樣會降低模型的分類效果.

3 結(jié)語

本文提出了一種低代價的數(shù)據(jù)流分類算法2SDC.區(qū)別于使用所有待分類樣本的真實類別來更新分類模型的現(xiàn)有大部分數(shù)據(jù)流分類算法, 新算法使用半監(jiān)督學(xué)習(xí)的思想, 利用數(shù)據(jù)塊上大量的未標記類別的樣本,通過動態(tài)調(diào)整權(quán)值, 為每個類別建立不同的簇來擬合各類別樣本的分布情況. 仲裁分類器的引入也保證了難處理樣本的分類效果. 概念漂移檢測機制的使用能夠使得分類模型更快地適應(yīng)數(shù)據(jù)流上的當(dāng)前概念. 真實數(shù)據(jù)流上的實驗證明了該算法的有效性. 下一步的工作方向是研究如何讓算法自動調(diào)整各類別的初始簇個數(shù).

1 辛軼,郭躬德,陳黎飛,畢亞新.IKnnM-DHecoc:一種解決概念漂移問題的方法.計算機研究與發(fā)展,2011,48(4):592–601.

2 Turner K, Ghosh J. Error collection and error reduction in ensemble classifiers. Connenction Science, 1996, 18(3): 385–403.

3 Aggarwal CC, Procopiuc C, Wolf JL, et al. Fast algorithm for projected clustering. Proc. of the ACM-SIGMOD. New York. ACM Press. 1999. 61–71.

4 Masud MM, Woolam C, Gao J, et al. Facing the reality of data stream classification: coping with scarcity of labeled data. Knowledge and Information System, 2012, 33(1): 213–244.

5 Zhou D, Bosquet O, Lal T N. Learning with local and global consistency. Advances in Neural Information Processing Systems, 2003, 16(1): 321–328.

6 Keller JM, Hand D. The impact of changing populations on classifier performance. Proc. of the 5th International Conference on Knowledge Discovery and Data Mining. New York. ACM Press. 1999. 367–371.

7 Street WN, Kim YS. A streaming ensemble algorithm (SEA) for large-scale classification. Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York. ACM Press. 2001. 377–382.

8 Zhang P, Zhu X, Shi Y, et al. An aggregate ensemble for mining concept drifting data streams with noise. Proc. of the 13th Pacific-Asia Conference on Knowledge Discovery. Bangkok. 2009. 1021–1029.

9 桂林,張玉紅,胡學(xué)剛.一種基于混合集成方法的數(shù)據(jù)流概念漂移檢測算法.計算機科學(xué),2012,39(1):152–155.

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

Low-Cost Algorithm for Stream Data Classification

LI Nan
(College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China)

Existing classification algorithms for data stream are mainly based on supervised learning, while manual labeling instances arriving continuously at a high speed requires much effort. A low-cost learning algorithm for stream data classification named 2SDC is proposed to solve the problem mentioned above. With few labeled instances and a large number of unlabeled instances, 2SDC trains the classification model and then updates it. The proposed algorithm can also detect the potential concept drift of the data stream and adjust the classification model to the current concept. Experimental results show that the accuracy of 2SDC is comparable to that of state-of-the-art supervised algorithm.

concept drift; data stream; classification; low-cost; supervised learning

福建省自然科學(xué)基金(2013J01216,2016J01280)

2016-03-29;收到修改稿時間:2016-06-01

10.15888/j.cnki.csa.005556