王軍，劉三民，劉濤

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法

王軍，劉三民，劉濤

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241000)

基于集成學(xué)習(xí)的數(shù)據(jù)流分類問(wèn)題已成為當(dāng)前研究熱點(diǎn)之一，而集成學(xué)習(xí)存在集成規(guī)模大、訓(xùn)練時(shí)間長(zhǎng)、時(shí)空復(fù)雜度高等不足，為此提出了一種基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法，用蟻群優(yōu)化算法挑選出優(yōu)秀的基分類器來(lái)構(gòu)建集成分類模型。該方法首先對(duì)所有基分類器采用交叉驗(yàn)證計(jì)算分類精度，同時(shí)采用Gower相似系數(shù)求出基分類器之間的差異性，然后把分類精度和分類器差異性作為分類器挑選標(biāo)準(zhǔn)，從全部基分類器中選出一部分來(lái)構(gòu)建集成模型，最終挑選的基分類器不僅具有良好的分類精度，同時(shí)保持一定差異性。在標(biāo)準(zhǔn)仿真數(shù)據(jù)集上對(duì)構(gòu)建的集成分類模型進(jìn)行仿真試驗(yàn)，結(jié)果表明,該方法與傳統(tǒng)集成方法相比在準(zhǔn)確率和穩(wěn)定性方面均有顯著提高。

數(shù)據(jù)流分類；概念漂移；選擇性集成；蟻群優(yōu)化算法；差異性

隨著信息化技術(shù)的發(fā)展和應(yīng)用需求不斷深入，數(shù)據(jù)流已廣泛存在于各行各業(yè)，如網(wǎng)絡(luò)數(shù)據(jù)、天氣預(yù)測(cè)數(shù)據(jù)、無(wú)線傳感數(shù)據(jù)、金融和電網(wǎng)數(shù)據(jù)等[1]。如何挖掘出這些數(shù)據(jù)流中有價(jià)值的信息，已成為當(dāng)前研究的熱點(diǎn)問(wèn)題。而數(shù)據(jù)流隱含噪聲同時(shí)具有時(shí)序特性和概念漂移現(xiàn)象，導(dǎo)致傳統(tǒng)分類模型難以適應(yīng)數(shù)據(jù)流的分類問(wèn)題。

目前，國(guó)內(nèi)外關(guān)于數(shù)據(jù)流分類已取得較多研究成果，以集成學(xué)習(xí)作為數(shù)據(jù)流分類模型已成為主流。把集成學(xué)習(xí)引入到數(shù)據(jù)流分類中，不僅提高了算法學(xué)習(xí)精度，增強(qiáng)了學(xué)習(xí)能力，同時(shí)還強(qiáng)化了算法在復(fù)雜環(huán)境中的學(xué)習(xí)效果。Street等[2]較早將集成學(xué)習(xí)應(yīng)用到數(shù)據(jù)流分類中，保持集成規(guī)模不變，用新分類器替換舊分類器實(shí)現(xiàn)對(duì)新知識(shí)的學(xué)習(xí)。而概念漂移發(fā)生初期體現(xiàn)新概念的基分類器不足以抗衡其他分類器，導(dǎo)致該算法在概念漂移發(fā)生初期對(duì)樣本無(wú)法準(zhǔn)確分類，鑒于此,Wang等[3]在SEA算法基礎(chǔ)上提出改進(jìn)算法AWE，該算法根據(jù)基分類器對(duì)最新訓(xùn)練樣本的分類準(zhǔn)確率來(lái)設(shè)置分類器權(quán)值，給準(zhǔn)確率高的基分類器分配較高權(quán)重，有效增強(qiáng)集成模型預(yù)測(cè)精度。針對(duì)數(shù)據(jù)流出現(xiàn)概念漂移導(dǎo)致分類模型頻繁變更問(wèn)題，F(xiàn)arid等[4]基于集成學(xué)習(xí)實(shí)現(xiàn)了一種自適應(yīng)數(shù)據(jù)流分類方法，使集成分類模型保持良好的穩(wěn)定性和靈活性。隨后，毛沙沙等[5]利用旋轉(zhuǎn)森林策略獲得樣本子集來(lái)訓(xùn)練分類器，使基分類器之間保持一定差異性，提高集成模型泛化能力。同年，Liao等[6]針對(duì)數(shù)據(jù)流分類問(wèn)題提出一種新的集成分類模型，通過(guò)靈活分配基分類器權(quán)重使集成分類模型快速適應(yīng)數(shù)據(jù)流中概念漂移的發(fā)生。與此同時(shí)，Gogte等[7]結(jié)合聚類思想實(shí)現(xiàn)一種混合集成分類模型，能快速捕獲概念漂移，同時(shí)有效解決已標(biāo)記樣本少難題；鄒權(quán)等[8]基于集成學(xué)習(xí)并結(jié)合分層思想在層級(jí)結(jié)構(gòu)基礎(chǔ)上通過(guò)集成學(xué)習(xí)來(lái)構(gòu)建分類模型，使集成學(xué)習(xí)更加靈活的應(yīng)用于數(shù)據(jù)流分類；針對(duì)含噪動(dòng)態(tài)數(shù)據(jù)流分類,王中心等[9]實(shí)現(xiàn)了一種自適應(yīng)集成分類算法，采用Bayes過(guò)濾噪聲，通過(guò)動(dòng)態(tài)更新分類模型來(lái)快速適應(yīng)概念漂移。從以上研究可以看出，采用集成學(xué)習(xí)進(jìn)行數(shù)據(jù)流分類具有明顯優(yōu)勢(shì)。而從現(xiàn)有文獻(xiàn)分析可知，通常采取增加基分類器數(shù)量來(lái)提高集成模型的分類精度和泛化能力，使集成規(guī)模不斷增大，不僅導(dǎo)致存儲(chǔ)空間急劇增加，同時(shí)集成規(guī)模過(guò)大導(dǎo)致集成模型訓(xùn)練時(shí)間長(zhǎng)、算法時(shí)空復(fù)雜度高等問(wèn)題。為此，筆者提出了一種基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法。

1 蟻群優(yōu)化算法

蟻群算法最早由意大利學(xué)者Dorigo Macro等[10]在人工生命會(huì)議上提出，隨后國(guó)內(nèi)外研究人員對(duì)其不斷進(jìn)行改進(jìn)，開(kāi)發(fā)出多種不同的蟻群算法版本并成功應(yīng)用于優(yōu)化領(lǐng)域。夏小云等[11]對(duì)蟻群優(yōu)化算法理論研究進(jìn)行了系統(tǒng)概述，論述了算法的尋優(yōu)原理、收斂性、復(fù)雜度、近似性等，同時(shí)分析總結(jié)了蟻群優(yōu)化算法在求解和優(yōu)化各類問(wèn)題上的性能。

蟻群優(yōu)化算法是模擬自然界真實(shí)螞蟻覓食行為，螞蟻在走過(guò)的路徑上釋放一種稱為信息素的物質(zhì)同時(shí)能感知信息素，該物質(zhì)對(duì)螞蟻選擇路線起到誘導(dǎo)作用，路徑上走過(guò)的螞蟻越多信息素含量越高，螞蟻選擇該路徑的概率也就越高，最終收斂于最優(yōu)路徑。

蟻群優(yōu)化算法的基本原理可以用最短旅行商問(wèn)題予以說(shuō)明。假設(shè)有n個(gè)城市，螞蟻數(shù)量為m，dij表示城市i、j之間的距離，τij(t)代表t時(shí)刻城市i、j之間的路徑上信息素含量，則在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的概率為：

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

式中,ρ∈(0，1)表示信息素?fù)]發(fā)系數(shù)； Δτij表示該次迭代中路徑ij上信息素的增量，初始時(shí)刻為0，計(jì)算方法如下：

(3)

(4)

式中，Q為常數(shù)表示信息素強(qiáng)度，對(duì)算法收斂速度起作用； Lk是第k只螞蟻在此次循環(huán)中走過(guò)的路徑長(zhǎng)度，經(jīng)過(guò)一定次數(shù)的循環(huán)迭代后，當(dāng)滿足停止條件(收斂或到達(dá)循環(huán)次數(shù))時(shí)，得到最優(yōu)路徑和最短路徑長(zhǎng)度。

2 選擇性集成學(xué)習(xí)

圖1 選擇性集成原理示意圖

選擇性集成學(xué)習(xí)最早由Zhou等[12]提出，其思想是從全部基分類器中剔除作用不大、分類性能不好的分類器，用剩余的分類器構(gòu)建集成模型能得到更好的預(yù)測(cè)效果，即“Many Could Be Better Than All”。目前選擇性集成已成為集成學(xué)習(xí)領(lǐng)域預(yù)測(cè)效果最好的學(xué)習(xí)范式。其原理示意圖如圖1所示。

選擇性集成作為集成學(xué)習(xí)中一種新的學(xué)習(xí)范式提高了集成學(xué)習(xí)的學(xué)習(xí)效果，同時(shí)解決了集成規(guī)模過(guò)大帶來(lái)的困擾。目前選擇性集成數(shù)據(jù)流分類也已取得眾多研究成果。趙勝穎等[13]提出一種基于智能群體的選擇性神經(jīng)網(wǎng)絡(luò)集成方法，利用智能群體的快速收斂提高了算法效率、降低計(jì)算復(fù)雜度。此外，Liu等[14]基于k-means方法提出一種選擇性集成學(xué)習(xí)算法，克服了集成學(xué)習(xí)中存儲(chǔ)空間大、訓(xùn)練時(shí)間長(zhǎng)、反復(fù)訓(xùn)練等問(wèn)題。與此同時(shí)，為保持集成模型中分類器之間的差異性，該團(tuán)隊(duì)又設(shè)計(jì)一種基于k-均值和負(fù)相關(guān)的選擇性集成學(xué)習(xí)方法[15]，該方法有效解決基分類器之間的冗余問(wèn)題，提高了集成模型預(yù)測(cè)效率。綜上可知選擇性集成在數(shù)據(jù)流分類中具有明顯優(yōu)勢(shì)，而根據(jù)挑選規(guī)則不同選擇性集成可分為基于選擇方法、聚類方法、排序方法和優(yōu)化方法的選擇性集成學(xué)習(xí)算法[16]。其核心思想是根據(jù)挑選規(guī)則選擇部分優(yōu)秀的基分類器來(lái)構(gòu)建集成模型，從而提高集成模型的分類精度和預(yù)測(cè)效率同時(shí)節(jié)省存儲(chǔ)空間。其中選擇性集成基本框架如下：

1)Input: 訓(xùn)練集T1，驗(yàn)證集T2，基分類器訓(xùn)練算法C，基分類器集合T，選擇的基分類器集合S，測(cè)評(píng)方法M；

2)初始化：基分類器集合T=?；

3)訓(xùn)練過(guò)程：

Fort=1,2,…,T；

得到基分類器集合T={C1,C2,…，CT}；

EndFor

4)選擇過(guò)程：

在驗(yàn)證集T2上對(duì)各基分類器Ct進(jìn)行測(cè)試，得到測(cè)試結(jié)果Rt,利用測(cè)評(píng)方法M針對(duì)測(cè)試結(jié)果Rt進(jìn)行測(cè)評(píng)；

根據(jù)測(cè)評(píng)結(jié)果，挑選出符合條件的基分類器CS添加到集合S中；

5)Output: 選擇的基分類器集合S={C1,C2,…，CS}；

3 ACOBSE方法

由于構(gòu)建分類精度高和泛化能力好的集成分類模型，不僅基分類器要具有較高的分類準(zhǔn)確率，同時(shí)分類器之間要保持一定差異性。基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法(ACO algorithm Based Selective Ensemble，ACOBSE)就是利用群體智能中經(jīng)典的蟻群優(yōu)化算法ACO來(lái)選擇分類精度高、個(gè)體差異性大的基分類器來(lái)構(gòu)建集成模型。該方法首先對(duì)訓(xùn)練集采用BatchMode方式訓(xùn)練出多個(gè)基分類器，通過(guò)交叉驗(yàn)證計(jì)算出它們的分類精度，同時(shí)采用Gower相似系數(shù)計(jì)算出基分類器之間的差異性，然后把分類精度和分類器差異性作為基分類器挑選標(biāo)準(zhǔn)從全部分類器中選出部分分類精度高、差異性大的分類器來(lái)構(gòu)建集成模型。該方法不僅減小了集成規(guī)模同時(shí)利用蟻群優(yōu)化算法的快速收斂性來(lái)提高算法效率。

為便于描述，對(duì)常用的基本概念給出定義：

2)概念漂移。是指數(shù)據(jù)產(chǎn)生的聯(lián)合概率分布隨時(shí)間變化而發(fā)生不可預(yù)知的變化，即Pt(x,y)≠Pt+1(x,y)，其中,x代表樣本向量，y表示樣本類別。

3)集成學(xué)習(xí)。對(duì)待測(cè)樣本進(jìn)行分類時(shí)，用若干弱分類器對(duì)同一個(gè)樣本進(jìn)行預(yù)測(cè)，再把結(jié)果按照某種策略融合獲得最終預(yù)測(cè)結(jié)果，集成學(xué)習(xí)決策函數(shù)可形式化為：

其中,ht(x)為弱分類器;HT(x)為集成后的強(qiáng)分類器;at表示基分類器權(quán)重。

3.1 交叉驗(yàn)證

交叉驗(yàn)證的基本思想是將數(shù)據(jù)分為2部分：一部分作為訓(xùn)練集用于分類器的訓(xùn)練，另一部分作為測(cè)試集用于分類器預(yù)測(cè)精度的檢驗(yàn)。由于2部分?jǐn)?shù)據(jù)不同，使得對(duì)預(yù)測(cè)精度的估計(jì)也更接近真實(shí)情況。目前常用的交叉驗(yàn)證有K折交叉驗(yàn)證、5×2交叉驗(yàn)證t檢驗(yàn)和F檢驗(yàn)等。筆者采用的是K折交叉驗(yàn)證t檢驗(yàn)方法。

K折交叉驗(yàn)證原理是將數(shù)據(jù)等分為K份，選擇其中K-1份作為訓(xùn)練集用于分類器的訓(xùn)練，剩余一份作為測(cè)試集用于分類器預(yù)測(cè)精度的檢驗(yàn)，將K份數(shù)據(jù)逐一作為測(cè)試集進(jìn)行訓(xùn)練和測(cè)試，最終得到K個(gè)度量值。K折交叉驗(yàn)證t檢驗(yàn)計(jì)算方法如下：

(5)

(6)

(7)

式中，μk表示在第k折交叉驗(yàn)證算法中度量值的差值。

K折交叉驗(yàn)證t檢驗(yàn)主要分為2折交叉驗(yàn)證、5折交叉驗(yàn)證和10折交叉驗(yàn)證t檢驗(yàn)，筆者采用K折交叉驗(yàn)證中最常用的10折交叉驗(yàn)證t檢驗(yàn)來(lái)計(jì)算基分類器的分類精度。把分類器預(yù)測(cè)精度作為挑選基分類器的標(biāo)準(zhǔn)之一，使構(gòu)建的集成模型獲得良好的分類性能。

3.2 分類器差異性

目前對(duì)集成學(xué)習(xí)領(lǐng)域的研究不再局限于對(duì)算法的提出和改進(jìn)，更多關(guān)注對(duì)基分類器關(guān)系的研究，尤其是分類器差異性研究。分類器之間具有差異性是集成分類模型生效的必要條件，同時(shí)也是集成模型具有良好泛化能力的關(guān)鍵因素。若集成模型中進(jìn)行組合的基分類器是相同、無(wú)差異的，分類性能并不會(huì)提高。因此要提高集成模型的分類性能，基分類器之間必須具有一定差異性，即至少存在一些分類器對(duì)其它分類器判斷錯(cuò)誤的樣本作出正確的決策。筆者定義的分類器差異性是結(jié)合Gower相似系數(shù)計(jì)算得到，該計(jì)算模型具有分類模型獨(dú)立和預(yù)測(cè)能力獨(dú)立等優(yōu)點(diǎn)[17]。

為方便描述，假設(shè)e表示測(cè)試樣本，E代表測(cè)試樣本集，符號(hào)de(cx,cy)表示分類器x、y在樣本e上的差異性，符號(hào)se(cx,cy)代表分類器x、y在樣本e上的相似性，二者滿足如下性質(zhì)：

①0≤se(cx,cx),de(cx,cy)≤1；

②de(cx,cy)=1-se(cx,cy)；

結(jié)合Gower相似系數(shù)計(jì)算出分類器基于單個(gè)樣本的相似性，計(jì)算方法見(jiàn)式(8)：

se(cx,cy)=1-δe(cx,cy)

(8)

在式(8)基礎(chǔ)上，基分類器基于單樣本的差異性計(jì)算方法如下：

de(cx,cy)=1-se(cx,cy)=δe(cx,cy)

(9)

(10)

式中, |C|表示樣本類別數(shù)；概率PDxj(e)表示基分類器x在單個(gè)測(cè)試樣本e上關(guān)于類別j的后驗(yàn)概率；PDyi(e)表示基分類器y在單個(gè)測(cè)試樣本e上關(guān)于類別j的后驗(yàn)概率；Rj(e)代表測(cè)試樣本e基于類j的后驗(yàn)概率極差：

Rj(e)=max{PD1j(e),…,PDnj(e)}-min{PD1j(e),…,PDnj(e)}

(11)

綜上，在單個(gè)測(cè)試樣本上基分類器差異性計(jì)算方法的基礎(chǔ)上，可導(dǎo)出在樣本集E上基分類器之間的差異性計(jì)算方法：

(12)

3.3 ACOBSE算法描述

在上述交叉驗(yàn)證和分類器差異性計(jì)算模型基礎(chǔ)上，結(jié)合多分類器動(dòng)態(tài)集成思想，給出選擇性集成數(shù)據(jù)流分類方法的算法描述。其中DS表示訓(xùn)練數(shù)據(jù)流，DB代表驗(yàn)證數(shù)據(jù)集，初始基分類器數(shù)量為n，最大集成規(guī)模為20，α表示信息素對(duì)螞蟻選擇分類器的的作用程度，β表示分類器差異性對(duì)螞蟻選擇分類器的作用程度，則ACOBSE算法的詳細(xì)描述如下：

1)Input: 訓(xùn)練集DS，驗(yàn)證集DB，基分類器數(shù)量n，選擇的基分類器集合S，集成規(guī)模T，參數(shù)α，參數(shù)β；

2)初始化相關(guān)參數(shù)：S=?，T=20；

3)訓(xùn)練過(guò)程：

基于訓(xùn)練集DS，采用批處理方式訓(xùn)練出n個(gè)基分類器，并用10折交叉驗(yàn)證t檢驗(yàn)計(jì)算出各分類器的分類精度；

對(duì)訓(xùn)練出的基分類器根據(jù)式(9)分類器差異性計(jì)算方法，基于驗(yàn)證集DB求出基分類器之間的差異性；

4)挑選過(guò)程：

螞蟻首先基于準(zhǔn)確率選擇一個(gè)基分類器并添加到集合S中，同時(shí)把該基分類器標(biāo)記為已訪問(wèn)；

Fort=1,2,…,T；

根據(jù)轉(zhuǎn)移概率計(jì)算螞蟻下一個(gè)要選擇的分類器，轉(zhuǎn)移概率計(jì)算方法是基于式(1)思想構(gòu)建，把分類精度和分類器差異性兩者作為相關(guān)參數(shù)進(jìn)行基分類器的挑選，具體計(jì)算方法如下：

(13)

5)Output：集成分類模型在測(cè)試數(shù)據(jù)集上的分類準(zhǔn)確率；

其中，tao(i)表示分類器i的信息素濃度，取值為對(duì)應(yīng)基分類器的分類精度值；differ(j)(i)代表集合S中最新基分類器j與目標(biāo)分類器i之間的差異性。

4 仿真試驗(yàn)與結(jié)果分析

4.1 仿真數(shù)據(jù)集

試驗(yàn)所用數(shù)據(jù)集源自平臺(tái)MOA環(huán)境中的移動(dòng)超平面數(shù)據(jù)集[18]。該數(shù)據(jù)集樣本屬性值在[0,1]，并通過(guò)m維度超平面隨機(jī)生成，樣本標(biāo)簽分為正類標(biāo)簽和負(fù)類樣本2類，在形成數(shù)據(jù)集過(guò)程中主要考慮3個(gè)參數(shù)n、s、t的變化：噪聲參數(shù)n表示在數(shù)據(jù)流中引入的噪聲數(shù)據(jù)量；參數(shù)t表示每隔N個(gè)樣本，樣本標(biāo)簽權(quán)值的改變量；參數(shù)s表示每隔一定數(shù)量樣本移動(dòng)超平面方向以概率s發(fā)生翻轉(zhuǎn)。規(guī)定每個(gè)數(shù)據(jù)集含有2W個(gè)樣本，并在參數(shù)t=0.1、s=10%固定條件下，設(shè)置仿真試驗(yàn)數(shù)據(jù)集共有5個(gè)特征屬性，其中2個(gè)特征屬性隨時(shí)間變化發(fā)生概念漂移現(xiàn)象，同時(shí)通過(guò)改變?cè)肼晠?shù)n(0，10%，20%)，即不含噪聲、10%噪聲、20%噪聲，生成3個(gè)數(shù)據(jù)集(記為H0、H1、H2)進(jìn)行測(cè)試。

4.2 試驗(yàn)方案

圖2 數(shù)據(jù)集H0(不含噪聲)試驗(yàn)結(jié)果

仿真試驗(yàn)基于WEKA平臺(tái)在Eclipse環(huán)境下完成，在標(biāo)準(zhǔn)仿真數(shù)據(jù)集上進(jìn)行試驗(yàn)。同時(shí)結(jié)合現(xiàn)有文獻(xiàn)采用基于準(zhǔn)確率選擇集成的簡(jiǎn)單投票方法(Majority Voting，MV)與該集成分類算法進(jìn)行對(duì)比。試驗(yàn)采用Bayes學(xué)習(xí)器作為基分類器，采用BatchMode訓(xùn)練生成，其中數(shù)據(jù)塊大小為1000個(gè)樣本，首先訓(xùn)練40個(gè)基分類器，采用10折交叉驗(yàn)證得出各基分類器的分類精度，集成規(guī)模定為20。2種集成分類模型在3個(gè)數(shù)據(jù)集上分類情況分別如圖2～圖4所示。 從圖2～圖4可知，基于蟻群優(yōu)化的選擇性集成方法是可行的的，分類準(zhǔn)確率比基于傳統(tǒng)準(zhǔn)確率選擇性集成方法要好。這主要是因?yàn)锳COBSE方法用基分類器的分類精度作為信息素濃度，利用蟻群優(yōu)化算法構(gòu)建集成模型時(shí)，挑選的是分類精度相對(duì)較高的基分類器，提高了集成分類模型的預(yù)測(cè)精度。與此同時(shí)，當(dāng)數(shù)據(jù)流含有噪聲時(shí)，ACOBSE算法的分類精度起伏程度相比基于準(zhǔn)確率動(dòng)態(tài)集成方法要低(見(jiàn)圖3和圖4)，說(shuō)明ACOBSE方法能更好地應(yīng)對(duì)概念漂移的發(fā)生，只有當(dāng)數(shù)據(jù)流中概念漂移達(dá)到一定程度之后才會(huì)對(duì)集成模型的分類精度帶來(lái)影響，即算法具有良好的魯棒性。當(dāng)概念漂移發(fā)生之后，ACOBSE方法分類曲線圖出現(xiàn)低峰，但能夠快速恢復(fù)其識(shí)別準(zhǔn)確率，且分類精度下降幅度比MV方法小，說(shuō)明ACOBSE方法能夠很好地適應(yīng)概念漂移，能夠及時(shí)捕捉、快速適應(yīng)概念漂移的出現(xiàn)，使集成模型保持正常分類水平。ACOBSE方法在構(gòu)建集成分類模型時(shí)，用分類器差異性作為基分類器挑選標(biāo)準(zhǔn)之一，保持基分類器之間的多樣性，使集成模型具有良好的泛化能力，這也是該算法在分類初期預(yù)測(cè)效果一般，而一旦發(fā)生概念漂移該算法的分類精度要明顯優(yōu)于傳統(tǒng)集成方法的主要原因。在數(shù)據(jù)流包含噪聲較高的環(huán)境下，ACOBSE算法在進(jìn)行數(shù)據(jù)流分類時(shí)出現(xiàn)尖峰次數(shù)比MV分類方法相比要少(見(jiàn)圖4)，而且尖峰起伏程度相對(duì)比較低。每次出現(xiàn)尖峰即是數(shù)據(jù)流發(fā)生概念漂移現(xiàn)象，數(shù)據(jù)集包含噪聲越大發(fā)生概念漂移的幾率就越大，而ACOBSE方法曲線圖中尖峰較少，說(shuō)明ACOBSE方法比傳統(tǒng)集成方法具有更好的穩(wěn)定性，能夠快速適應(yīng)概念漂移并對(duì)數(shù)據(jù)流中出現(xiàn)的新概念準(zhǔn)確分類。這主要是因?yàn)锳COBSE方法在挑選基分類器時(shí)不僅考慮分類精度，同時(shí)把分類器差異性作為衡量標(biāo)準(zhǔn)之一，保持各基分類器之間的多樣性，使集成模型面對(duì)概念漂移依然具有良好的泛化能力。

圖3 數(shù)據(jù)集H1(10%噪聲)試驗(yàn)結(jié)果 圖4 數(shù)據(jù)集H2(20%噪聲)試驗(yàn)結(jié)果

表3 2種集成模型試驗(yàn)結(jié)果

從表3準(zhǔn)確率統(tǒng)計(jì)分析可知，ACOBSE算法明顯優(yōu)于傳統(tǒng)集成方法MV，分類準(zhǔn)確率約高出12%，在一定噪聲環(huán)境下依然擁有較高的準(zhǔn)確率，說(shuō)明ACOBSE算法能較好的應(yīng)對(duì)數(shù)據(jù)流中隱含的噪聲，且快速適應(yīng)數(shù)據(jù)流中出現(xiàn)的概念漂移現(xiàn)象。當(dāng)數(shù)據(jù)集從不含噪聲變成含有噪聲數(shù)據(jù)時(shí)，ACOBSE方法的分類精度值下降明顯少于MV方法，說(shuō)明ACOBSE方法在面對(duì)含有噪聲的數(shù)據(jù)時(shí)穩(wěn)定性更好，具備較強(qiáng)的抗噪特點(diǎn)。因?yàn)锳COBSE方法在構(gòu)建集成模型時(shí)，用分類器之間的差異性作為挑選標(biāo)準(zhǔn)之一，保持集成分類模型中分類器之間的多樣性，使集成模型面對(duì)隱含噪聲和概念漂移的數(shù)據(jù)流依然具有良好的分類準(zhǔn)確率和泛化能力。與此同時(shí)，ACOBSE方法構(gòu)建的集成模型分類穩(wěn)定性相對(duì)傳統(tǒng)MV方法較好，在一定噪聲環(huán)境下依然能夠準(zhǔn)確對(duì)數(shù)據(jù)流進(jìn)行分類，且隨著噪聲的增加ACOBSE方法依然表現(xiàn)出較好的穩(wěn)定性，說(shuō)明該算法具有較強(qiáng)的魯棒性。

綜上所述，基于蟻群優(yōu)化算法的選擇性集成數(shù)據(jù)流分類方法是可行的，能夠挑選出性能優(yōu)良的基分類器構(gòu)建集成分類模型。

5 結(jié)語(yǔ)

針對(duì)動(dòng)態(tài)數(shù)據(jù)流分類問(wèn)題，筆者提出并實(shí)現(xiàn)了一種基于蟻群優(yōu)化的選擇性集成方法。該算法不僅考慮基分類器的分類精度，同時(shí)計(jì)算分類器之間的差異性，最終挑選的基分類器不僅具有良好的分類精度，同時(shí)保持一定差異性，這也是算法在噪聲環(huán)境下保持分類穩(wěn)定性的關(guān)鍵因素。仿真試驗(yàn)表明，基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法在分類精度和穩(wěn)定性方面均有不錯(cuò)效果，是一種可行的數(shù)據(jù)流分類方法。然而實(shí)際數(shù)據(jù)流中大量數(shù)據(jù)是無(wú)標(biāo)簽的樣本，因此如何在具有不完全標(biāo)記的數(shù)據(jù)流環(huán)境下或樣本不平衡條件下，基于主動(dòng)學(xué)習(xí)和半監(jiān)督學(xué)習(xí)技術(shù)設(shè)計(jì)數(shù)據(jù)流的概念漂移檢測(cè)與分類方法是后續(xù)的主要研究?jī)?nèi)容。

[1]Dietterich T G. Machine learning research:four current directions[J]. AI Magazine, 1997, 18(4):97～136.

[2]Street W N, Kim Y S. A streaming ensemble algorithm (SEA) for large-scale classification[A] .ACM SIGKDD International Conference on Knowledge Discovery & Data Mining[C]. 2001:377～382.

[3]Wang H, Fan W, Yu P S, et al. Mining concept-drifting data streams using ensemble classifiers[A] .ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].2003:226～235.

[4]Farid D M, Zhang L, Hossain A, et al. An adaptive ensemble classifier for mining concept drifting data streams[J]. Expert Systems with Applications, 2013, 40(15):5895-5906.

[5]毛莎莎, 熊霖, 焦李成,等. 利用旋轉(zhuǎn)森林變換的異構(gòu)多分類器集成算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 41(5):48～53.

[6]Liao J W, Dai B R. An ensemble learning approach for concept drift[A] .International Conference on Information Science and Applications (ICISA)[C]. 2014:1～4.

[7]Gogte P S, Theng D P. Hybrid ensemble classifier for stream data[A].International Conference on Communication Systems and Network Technologies (CSNT)[C]. 2014:463～467.

[8]鄒權(quán), 宋莉, 陳文強(qiáng),等. 基于集成學(xué)習(xí)和分層結(jié)構(gòu)的多分類算法[J]. 模式識(shí)別與人工智能, 2015, 28(9):781～787.

[9]王中心, 孫剛, 王浩. 面向噪音和概念漂移數(shù)據(jù)流的集成分類算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(7):1445～1449.

[10]Colorni A, Dorigo M, Maniezzo V. Distributed optimization by Ant Colonies[A] .Ecal91-European Conference on Artificial Life[C]. 1991.

[11]夏小云, 周育人. 蟻群優(yōu)化算法的理論研究進(jìn)展[J]. 智能系統(tǒng)學(xué)報(bào), 2016, 11(1):27～36.

[12]Zhou Z H, Wu J X, Tang W. Ensembling neural networks: many could be better than all[J]. Artificial Intelligence, 2002, 137(1-2):239～263.

[13]趙勝穎, 高廣春. 基于蟻群算法的選擇性神經(jīng)網(wǎng)絡(luò)集成方法[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2009, 43(9):1568～1573.

[14]Liu L, Wang B, Zhong Q, et al. A selective ensemble method based on K-means method[A] .International Conference on Computer Science and Network Technology[C].2015:665～668.

[15]Liu L, Wang B, Yu B, et al. A novel selective ensemble learning based on K-means and negative correlation[M].Cloud Computing and Security,Springer International Publishing, 2016.

[16]張春霞, 張講社. 選擇性集成學(xué)習(xí)算法綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(8):1399～1410.

[17]劉余霞, 呂虹, 劉三民. 一種基于分類器相似性集成的數(shù)據(jù)流分類研究[J]. 計(jì)算機(jī)科學(xué), 2012, 39(12):208～210.

[18]Hulten G, Spencer L, Domingos P. Mining time-changing data streams[A].Acm Sigkdd Intl Conf on Knowledge Discovery & Data Mining[C]. 2001:97～106.

[編輯] 洪云飛

2016-12-10

國(guó)家自然科學(xué)基金項(xiàng)目(61300170)；安徽省自然科學(xué)基金項(xiàng)目(1608085MF147)；安徽省高校省級(jí)優(yōu)秀人才重點(diǎn)項(xiàng)目(2013SQRL034ZD)。

王軍(1992-)，男，碩士生，現(xiàn)在主要從事機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘方面的研究工作。

劉三民(1978-)，男，博士，副教授，現(xiàn)主要從事模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘方面的教學(xué)與研究工作，aqlsm@163.com。

TP391

A

1673-1409(2017)05-0037-07

[引著格式]王軍，劉三民，劉濤.基于蟻群優(yōu)化的選擇性集成數(shù)據(jù)流分類方法[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)，2017,14(5)：37～43.