李 南

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

低代價(jià)的數(shù)據(jù)流分類(lèi)算法①

李 南

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

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

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

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

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

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

1 2SDC算法基分類(lèi)器

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

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

設(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的類(lèi)別. 如果yn=0, 表示該樣本的類(lèi)別未被標(biāo)記.

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

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

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

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

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

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

① 如果x是未標(biāo)記類(lèi)別的樣本,

② 如果x是已標(biāo)記類(lèi)別的樣本,

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

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

?

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

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

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

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

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

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

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

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

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

2 概念漂移檢測(cè)

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

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

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

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

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

表1 20-Newsgroups中各類(lèi)分布

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

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

圖1 20-Newsgroups上分類(lèi)精度比較

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

圖2 不同標(biāo)記比例下平均分類(lèi)精度

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

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

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

3 結(jié)語(yǔ)

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

1 辛軼,郭躬德,陳黎飛,畢亞新.IKnnM-DHecoc:一種解決概念漂移問(wèn)題的方法.計(jì)算機(jī)研究與發(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ù)流概念漂移檢測(cè)算法.計(jì)算機(jī)科學(xué),2012,39(1):152–155.

10 徐文華,覃征,常揚(yáng).基于半監(jiān)督學(xué)習(xí)的數(shù)據(jù)流集成分類(lèi)算法.模式識(shí)別與人工智能,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;收到修改稿時(shí)間:2016-06-01

10.15888/j.cnki.csa.005556