高速數(shù)據(jù)流的集成分類器算法.doc

面向高速數(shù)據(jù)流的集成分類器算法摘要:數(shù)據(jù)流挖掘要求算法在占用少量內(nèi)存空間的前提下快速地處理數(shù)據(jù)并且自適應(yīng)概念漂移,據(jù)此提出一種面向高速數(shù)據(jù)流的集成分類器算法。該算法將原始數(shù)據(jù)流沿著時間軸劃分為若干數(shù)據(jù)塊后,在各個數(shù)據(jù)塊上計算所有類別的中心點和對應(yīng)的子空間;此后將各個數(shù)據(jù)塊上每個類別的中心點和對應(yīng)的子空間集成作為分類模型,并利用統(tǒng)計理論的相關(guān)知識檢測概念漂移,動態(tài)地調(diào)整模型。實驗結(jié)果表明,該方法能夠在自適應(yīng)數(shù)據(jù)流概念漂移的前提下對數(shù)據(jù)流進(jìn)行快速的分類,并得到較好的分類效果。關(guān)鍵詞:概念漂移;數(shù)據(jù)流;子空間;分類;集成ensemble classification algorithm for high speed data stream英文作者名li nan1,2, guo gong-de1,2*英文地址(1.school of mathematics and computer science, fujian normal university,fuzhou fujian 350007,china;2.key laboratory of network security and cryptography, fujian normal university,fuzhou fujian 350007,china)abstract: the algorithms for mining data streams have to make fast response and adapt to the concept drift at the premise of light demands on memory resources. this paper proposed an ensemble classification algorithm for high speed data stream. after dividing a given data stream into several data blocks, it computed the central point and subspace for every class on each block which were integrated as the classification model. meanwhile, it made use of statistics to detect concept drift. the experimental results show that the proposed method not only classifies the data stream fast and adapt to the concept drift with higher speed, but also has a better classification performance.key words: concept drift; data stream; subspace; classification; integration0引言隨著信息產(chǎn)業(yè)的發(fā)展,超市交易、電信等眾多應(yīng)用領(lǐng)域每天都產(chǎn)生大量的數(shù)據(jù)流,其中蘊含著豐富的有價值的知識有待挖掘,近年來已成為數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點。由于數(shù)據(jù)流具有快速性、無限性和實時性的特點1,使得傳統(tǒng)的挖掘算法顯得有些力不從心。同時,數(shù)據(jù)流中隱含的概念或知識可能會隨著時間的推移或環(huán)境的改變而發(fā)生變化, 即1996年widmer和kubat2提出的概念漂移問題。因此,數(shù)據(jù)流挖掘要求算法能在有限的計算時間和內(nèi)存資源內(nèi)完成挖掘任務(wù),并且根據(jù)當(dāng)前的概念自適應(yīng)地改變模型3。目前,處理數(shù)據(jù)流上概念漂移的方法有3種4:實例選擇、實例加權(quán)和集成學(xué)習(xí)。hansen等5證明使用集成分類器方法比僅使用單個分類器方法具有更好的適應(yīng)性和精確性。wang等6提出了一個集成學(xué)習(xí)的通用框架用于挖掘概念漂移數(shù)據(jù)流。street等7提出一個可以自適應(yīng)數(shù)據(jù)流概念漂移的集成分類器算法(streaming ensemble algorithm, sea),展示了集成學(xué)習(xí)的有效性。此后,許多學(xué)者深入研究了集成分類器的權(quán)值設(shè)計8-10以及集成策略11-13。然而,上述已存在的數(shù)據(jù)流分類模型不僅構(gòu)建模型耗時多,而且面臨著同一個問題:當(dāng)數(shù)據(jù)流中只有少部分類別發(fā)生概念漂移時,仍必須拋棄現(xiàn)有的整個集成分類模型進(jìn)行重建以適應(yīng)新的概念,降低了分類效率。針對以上問題,本文提出了一種新穎的面向高速數(shù)據(jù)流的集成分類算法(簡稱eca)。1相關(guān)工作1.1eca基分類器構(gòu)建最近鄰分類是一種已經(jīng)被眾多學(xué)者廣泛研究的有監(jiān)督的機器學(xué)習(xí)方法。經(jīng)典的k-最近鄰(k-nearest neighbor, knn)算法14由于簡單但頗為有效被列為十大數(shù)據(jù)挖掘算法之一15。然而,其面臨分類速度較慢和k值難以確定的問題。為了解決分類效率低的問題,近期有學(xué)者通過將同類別數(shù)據(jù)聚類生成若干關(guān)鍵數(shù)據(jù)以減少要搜索的近鄰數(shù),在不失分類精度的前提下提高了分類速度16。受其啟發(fā),本文提出一種基于子空間中心點的分類算法作為eca的基分類器。設(shè)訓(xùn)練數(shù)據(jù)集x由n個樣本組成,即x=(x1,y1),(x2,y2),(xi,yi),(xn,yn)。其中xi表示由d個屬性構(gòu)成的第i個樣本,即xi=xi1,xi2,xid;yi1,2,k表示xi的類別, k(k1)表示訓(xùn)練集中包含的類別個數(shù)。為了進(jìn)一步減少要搜索的近鄰數(shù)目以提高分類效率,將所有同類別的數(shù)據(jù)組成一個中心點,記為:centerk=ck1,ck2,ckd。centerk=1num(k)yi=kxi(1)其中num(k)表示第k類的樣本數(shù)目。顯然,將所有同類別數(shù)據(jù)僅用一個中心數(shù)據(jù)來表示不僅提升了模型對噪聲的魯棒性,同時大大提高了分類效率。但值得注意的是,將所有同類別數(shù)據(jù)僅用一個中心數(shù)據(jù)來表示分類時容易受到數(shù)據(jù)離散程度的影響,圖1就是個例子。在二維空間上空心的橢圓和矩形分別代表兩類不同的樣本,其中心點各自用實心的橢圓和矩形表示。如果簡單地利用各自的中心點來代表所有同類數(shù)據(jù),根據(jù)測試樣本在全空間上距離兩類中心點的距離來進(jìn)行分類(相當(dāng)于用圖中的虛線作為分類標(biāo)準(zhǔn)),顯然不能正確地代表數(shù)據(jù)的分布情況,分類處在全空間類別邊界上的點時精度受到影響。因此,有必要對其進(jìn)行進(jìn)一步改進(jìn)。圖片圖1中心點分類例子數(shù)據(jù)空間中往往存在許多不相關(guān)的屬性,在全空間上表現(xiàn)為同類別的點是“離散的”,只在某些低維的子空間上是“密集的”17。為了減少數(shù)據(jù)離散程度對分類模型所造成的影響,我們將測試樣本投影到每個類別所在的子空間上,即利用加權(quán)的歐氏距離來衡量測試樣本與各個類別中心點的距離。算法基于軟子空間聚類18的普遍假設(shè):“維度權(quán)重大小與同類數(shù)據(jù)點投影到該維度上的分布離散程度成反比”的思想來建立每個類別所在的子空間,記為:1.2基分類器算法空間復(fù)雜度分析設(shè)在大小為s、類別個數(shù)為k的數(shù)據(jù)塊上構(gòu)建基分類器,根據(jù)上述算法流程,其所需的存儲空間為o(k),即存儲k個中心點數(shù)據(jù),通常ks并且k與s無關(guān)。同時,求取中心和權(quán)重的過程時間復(fù)雜度與s的大小成線性關(guān)系,即算法時間復(fù)雜度為o(s)。綜上,相對于數(shù)據(jù)塊大小s,該基分類器算法具有常數(shù)的空間復(fù)雜度和線性的時間復(fù)雜度。因此,該算法適合作為數(shù)據(jù)流集成分類器的基分類器算法。第3期 李南等:面向高速數(shù)據(jù)流的集成分類器算法計算機應(yīng)用 第32卷2eca的設(shè)計與分析本章先介紹eca分類模型的概念漂移檢測機制,然后對算法進(jìn)行具體描述。算法使用滑動窗口模型,將數(shù)據(jù)流沿時間軸組織成固定大小s的數(shù)據(jù)塊序列,每個數(shù)據(jù)塊用d1,d2,dn表示。2.1漂移檢測本文采用假設(shè)檢驗中2擬合檢驗的原理來進(jìn)行漂移檢測。其基本思想是如果相鄰兩個數(shù)據(jù)塊內(nèi)關(guān)于同一類別的數(shù)據(jù)的分類精度在一定的顯著性水平下有顯著改變,那么就有理由認(rèn)為新數(shù)據(jù)塊上的此類數(shù)據(jù)概念發(fā)生變化,需要重構(gòu)該類別的分類模型。2擬合檢驗的原理20是:當(dāng)總體的分布未知時,根據(jù)樣本x1,x2,xn來檢驗關(guān)于總體分布的假設(shè)“h0:總體x的分布函數(shù)是f(x)”。設(shè)x的取值范圍為a1,a2,az。以fi(i=1,2,z)記錄n個樣本觀測值x1,x2,xn落在ai的個數(shù),pi(i=1,2,z)為根據(jù)h0所假設(shè)的x的分布函數(shù)來計算事件ai的概率。那么若樣本個數(shù)n充分大,則當(dāng)h0為真時,統(tǒng)計量2=zi=1fi 2npi-n近似地服從2(z-1)分布。即當(dāng)樣本的觀測值使2值有22(z-1),則在顯著性水平下拒絕h0;否則就接受h0。eca使用上述的原理檢測概念漂移,依次對當(dāng)前數(shù)據(jù)塊上每個類別的分類情況進(jìn)行假設(shè)檢驗,設(shè)置z=2(分類正確與否兩種情況),h0為前若干個概念平穩(wěn)的數(shù)據(jù)塊上該類別的平均分類情況,顯著性水平取0.05。若在新數(shù)據(jù)塊上22(z-1),則該類別分類精度發(fā)生顯著性改變,從而說明發(fā)生了概念漂移;反之認(rèn)為概念分布平穩(wěn)。2.2eca描述eca由為每個類別保存的在不同數(shù)據(jù)塊上建立的多個中心點和對應(yīng)的子空間組成集成模型。同時,當(dāng)使用數(shù)理統(tǒng)計的相關(guān)知識檢測到數(shù)據(jù)流的少部分類別發(fā)生概念漂移時,無需像現(xiàn)有的集成分類算法8-13一樣,耗時耗力地重構(gòu)整個集成分類模型,降低算法的分類效率。新算法只需將新數(shù)據(jù)塊上建立的符合新概念的該類別的中心點和對應(yīng)的子空間替換原有分類模型中的即可,符合數(shù)據(jù)流要求算法能快速處理數(shù)據(jù)并且自適應(yīng)概念漂移的特點。算法流程具體如下:1)當(dāng)新的數(shù)據(jù)塊到來時,eca先利用現(xiàn)有的分類模型,計算新數(shù)據(jù)塊中各待分類樣本與每個類別的距離(距離采用在相應(yīng)的子空間上待分類樣本與為每一個類別保留的不超過num個在各個數(shù)據(jù)塊上建立的中心點的平均距離作為待分類樣本距離此類別的距離),選取距離最近的類別作為待分類樣本的類別。2)在新數(shù)據(jù)塊上利用baset算法建立該數(shù)據(jù)塊上各類樣本的中心點和對應(yīng)的子空間。3)根據(jù)分類情況檢查各類別是否發(fā)生概念漂移。4)一旦檢測出某個類別發(fā)生概念漂移,那么刪除原有分類模型中所有為該類別保存的中心點和對應(yīng)的子空間,保存新數(shù)據(jù)塊上建立的該類別的中心點和對應(yīng)的子空間。如果沒有發(fā)生概念漂移,先保存新數(shù)據(jù)塊上建立的該類別的中心點和相應(yīng)的子空間,再判斷原有分類模型中為該類別保存的中心點和相應(yīng)的子空間個數(shù)是否超過num，如果超過，則刪除最早建立的那個數(shù)據(jù)塊上構(gòu)建的中心點和對應(yīng)的子空間。算法每個數(shù)據(jù)塊上對應(yīng)的處理流程如下:算法eca。輸入集成分類器ecn-1,當(dāng)前數(shù)據(jù)塊dn,為各類別保存的中心點和相應(yīng)的子空間容量num。輸出當(dāng)前分類模型ecn。程序前其中:ec表示eca集成分類模型,ecn 表示第n個數(shù)據(jù)塊時的集成分類模型。通過算法流程可看出：eca中利用現(xiàn)有分類模型對當(dāng)前數(shù)據(jù)塊中的數(shù)據(jù)進(jìn)行分類,顯然只需要相對于數(shù)據(jù)塊大小線性的時間復(fù)雜度,其余時間耗費在使用baset算法在新數(shù)據(jù)塊上建立新的分類模型以對現(xiàn)有模型進(jìn)行更新。在大小為s、類別個數(shù)為k的數(shù)據(jù)塊上,baset算法為每類計算其中心點及其對應(yīng)的子空間需要相對于該類別樣本數(shù)目線性的時間復(fù)雜度,因此整體的時間復(fù)雜度為o(ks),通常ks并且k是獨立于s的常數(shù)。因此,相對于數(shù)據(jù)塊大小s,利用baset算法對分類模型進(jìn)行更新具有線性的時間復(fù)雜度。綜上所述,eca具有相對于數(shù)據(jù)塊大小s線性的時間復(fù)雜度,適合數(shù)據(jù)流分類模型快速處理的要求。3實驗分析與討論為了評估eca的性能,我們在分別在真實數(shù)據(jù)集和實驗數(shù)據(jù)集上對算法的精確度和分類效率進(jìn)行實驗。實驗環(huán)境如下:2.6ghz cpu和2gb ram;操作系統(tǒng)為windows xp;開發(fā)環(huán)境為基于java語言的weka平臺,編譯運行環(huán)境為jdk 1.5。3.1使用的算法為了驗證本文算法的有效性,對比算法使用經(jīng)典的sea、目前比較流行的實例加權(quán)集成分類器(example-weight algorithm for mining data streams, ewamds)算法8以及分類器動態(tài)集成的dwm(dynamic weighted majority)算法11。實驗中各種算法的具體參數(shù)設(shè)置分別參照文獻(xiàn)7-8,11中的實驗參數(shù),eca中為各類別保存最多不超過5個在各數(shù)據(jù)塊上建立的中心點和對應(yīng)的子空間個數(shù),即num=5。3.2數(shù)據(jù)集分別在以下兩個數(shù)據(jù)集上進(jìn)行實驗以檢驗eca解決數(shù)據(jù)流分類問題的有效性。1)移動超平面(hyperplane)21:一個d維超平面上的樣本x滿足形式:di=1aixi=a0。在實驗中,取d為100,并且隨機產(chǎn)生3個不同的權(quán)重集合。實驗使用30000條數(shù)據(jù),蘊含3個概念,2次漂移。其中每個概念含有10000條樣本,并包含5%的噪聲樣本。2)20-newsgroups(http:/mlg.ucd.ie/files/dataset):一個常用的文本數(shù)據(jù)集,它是由20個不同新聞組的文檔組成。本文使用的數(shù)據(jù)集是20-newsgroups來自同一個新聞組的部分樣本集合,一共分為6類:med、baseball、autos、motor、space和politics。實驗中隨機抽取了4498條樣本,各類分布情況見表1所示,每個樣本包含500個特征屬性。為了消除文檔的長度差異帶來的影響,數(shù)據(jù)事先進(jìn)行了單位向量長度變換。為了模擬一個多類別漂移的情況,以驗證算法對真實復(fù)雜數(shù)據(jù)中出現(xiàn)新類問題的快速適應(yīng)性以及對多類分類問題的處理能力,將數(shù)據(jù)集劃分為兩大塊:在第一大塊數(shù)據(jù)中,只有med、baseball、autos和motor 4類;在第二大塊數(shù)據(jù)中,淘汰了motor類的數(shù)據(jù),并添加了space和politics兩個新的類別。表格(有表名)表120-newsgroups中各類分布類別實例個數(shù)類別實例個數(shù)med1162motor600baseball1162space562autos450politics5623.3實驗結(jié)果與分析3.3.1移動超平面數(shù)據(jù)集各種算法在移動超平面數(shù)據(jù)集上每個數(shù)據(jù)塊上的精度對比結(jié)果如圖2所示。由于移動超平面樣本個數(shù)較多,將數(shù)據(jù)塊大小設(shè)置為500。從圖2可看出：在第20和40個數(shù)據(jù)塊時,由于數(shù)據(jù)出現(xiàn)概念漂移的情況,各種算法的分類精度驟然下降。但是,隨著漂移數(shù)據(jù)的增多,分類器逐漸適應(yīng)了新的概念,分類精度也恢復(fù)到了原先的水平。由于sea使用c4.5作為基分類器,在處理維度較高的數(shù)值型屬性數(shù)據(jù)時分類精度會受到影響,因而分類效果最差。同時,我們可以看出,在大部分情況下,eca分類精度優(yōu)于dwm算法,和ewamds算法相當(dāng)。此外,各種算法在移動超平面數(shù)據(jù)集上的處理時間如圖3所示。從圖3可看出：由于基分類器構(gòu)造方式簡單,eca上在處理時間上對比其他3種算法具有相當(dāng)?shù)膬?yōu)勢。圖片圖2含5%噪聲的移動超平面數(shù)據(jù)流上的分類精度比較圖片圖3含5%噪聲的移動超平面數(shù)據(jù)流上的處理時間比較3.3.220-newsgroups數(shù)據(jù)集由于移動超平面是一個二分類問題,為了驗證eca在真實復(fù)雜結(jié)構(gòu)數(shù)據(jù)流中面對出現(xiàn)新類問題的快速適應(yīng)性以及對多類分類問題的處理能力,在20-newsgroups數(shù)據(jù)集上進(jìn)行了測試,此次測試將數(shù)據(jù)塊大小設(shè)置為250。各種算法在每個數(shù)據(jù)塊上的精度對比如圖4所示。從圖4可看出：在第8個數(shù)據(jù)塊時,由于新類別數(shù)據(jù)的出現(xiàn)舊類別數(shù)據(jù)的消失,原有的分類模型已經(jīng)不適應(yīng)新數(shù)據(jù)塊的概念,因而各種算法的分類精度出現(xiàn)不同程度的下降。由于dwm算法僅根據(jù)分類模型中各基分類器的累積錯誤動態(tài)地刪除和新建基分類器,因而分類精度降低的幅度最小。同時,在概念穩(wěn)定以后,eca的分類精度高于其他3種算法。此外,各種算法對20-newsgroups數(shù)據(jù)流中每類數(shù)據(jù)的分類正確率見表2所示。從表2可看出：對于6種類別的判斷,eca都具有較高的分類精度。各種算法在20-newsgroups數(shù)據(jù)流上的處理時間如圖5所示。雖然只有部分類別發(fā)生概念漂移,3種對比算法仍需重建整個分類模型,無需重建整個模型、基分類器構(gòu)建簡單的eca在處理時間上具有明顯的優(yōu)勢。同時ewamds算法需要為新數(shù)據(jù)塊上的每個樣本計算其相應(yīng)的權(quán)重,故需要最長的處理時間。4結(jié)語本文針對現(xiàn)有集成分類方法構(gòu)建分類模型耗時多,在數(shù)據(jù)流僅部分類別發(fā)生概念漂移時仍需重建整個分類模型,分類效率低的缺點,提出一種新的線性時間復(fù)雜度的集成分類算法。新算法在部分類別發(fā)生概念漂移時僅需重建相應(yīng)部分的分類模型,從而提高分類效率。在移動超平面和20-newsgroups數(shù)據(jù)流上的實驗表明,與經(jīng)典的sea、當(dāng)前比較流行的ewamds算法和dwm算法相比,新算法能夠在自適應(yīng)概念漂移的情況下對數(shù)據(jù)流進(jìn)行快速分類,并得到較好的分類效果。下一步工作的重點是研究基分類器的建立方法,從而進(jìn)一步提高分類性能。參考文獻(xiàn):1李燕,張玉紅,胡學(xué)鋼. 基于c4.5和nb混合模型的數(shù)據(jù)流分類算法j.計算機科學(xué),2010,37(12):138-142.2widmer g, kubat m. learning in the presence of concept drift and hidden contexts j. machine learning,1996,23(1):69-101.3王黎明,周馳.自適應(yīng)概念漂移的在線集成分類器j.計算機工程,2011,37(5):74-76.4tsymbal a, pechenizkiy m, cunningham p, et al. dynamic integration of classifiers for handling concept drift j. information fusion, 2008,9(1):56-68.5hansen l k, salamon p. neutral network ensemble j. ieee transactions on pattern analysis and machine