一種基于UFFT的數(shù)據(jù)流分類器

甄田甜, 張玉紅, 李 燕, 王海平, 胡學(xué)鋼

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥 230009)

一種基于UFFT的數(shù)據(jù)流分類器

甄田甜, 張玉紅, 李 燕, 王海平, 胡學(xué)鋼

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥 230009)

文章提出一種基于極速?zèng)Q策森林(UFFT)的加權(quán)裝袋算法(UFFT-w b),它采用加權(quán)裝袋算法模型,以UFFT算法構(gòu)建基分類器。實(shí)驗(yàn)表明,該算法具有確定分割點(diǎn)及選擇分割屬性花費(fèi)時(shí)間少、構(gòu)建新結(jié)點(diǎn)占用空間小及可以增量式構(gòu)建等特點(diǎn),與基于C4.5算法的加權(quán)裝袋算法模型相比,在保持相似精度的基礎(chǔ)上,時(shí)間性能有一定程度的改進(jìn)。

數(shù)據(jù)流;集成分類器;極速?zèng)Q策森林;加權(quán)裝袋算法

隨著計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展和信息存儲(chǔ)技術(shù)的不斷進(jìn)步,眾多應(yīng)用領(lǐng)域如網(wǎng)絡(luò)入侵檢測(cè)、股票實(shí)時(shí)分析、衛(wèi)星氣象監(jiān)控、信用卡交易以及電子商務(wù)管理等[1-3]擁有了大量的數(shù)據(jù)流,數(shù)據(jù)流具有無(wú)限性、快速性等特點(diǎn),如何在數(shù)據(jù)流上及時(shí)有效地進(jìn)行實(shí)時(shí)分類預(yù)測(cè),給數(shù)據(jù)挖掘領(lǐng)域帶來(lái)了極大的挑戰(zhàn)。

數(shù)據(jù)挖掘領(lǐng)域中常用決策樹進(jìn)行分類預(yù)測(cè)。最早的決策樹系統(tǒng)要追溯到文獻(xiàn)[4]中ID 3算法,而C4.5算法[5]是ID3的改進(jìn)版,加入了對(duì)連續(xù)性屬性和窗口處理,但時(shí)間花費(fèi)較大。近些年,面向數(shù)據(jù)流領(lǐng)域出現(xiàn)一些新的發(fā)展,如文獻(xiàn)[6]提出了VFDT,文獻(xiàn)[7]提出了 VFDT的改進(jìn)算法VFDTc,兩者不足在于由用戶確定何時(shí)決定分裂葉子結(jié)點(diǎn)的閾值,不同的閾值會(huì)影響分類精度。文獻(xiàn)[8]提出了Random forests,森林中生成每棵樹都是基于同一個(gè)由隨機(jī)樣本構(gòu)成的容器,且彼此獨(dú)立,多棵樹以投票進(jìn)行分類決策;文獻(xiàn)[9]提出了UFFT,該算法并不使用Random forests的隨機(jī)方法,而是將類標(biāo)號(hào)是k類的問(wèn)題化為k(k-1)/2個(gè)二叉樹問(wèn)題。它采取二次判別式來(lái)選擇分割值,用信息熵來(lái)評(píng)價(jià)分割屬性,使用Hoeffding邊界決定何時(shí)分裂葉子結(jié)點(diǎn),該算法在處理大中型數(shù)據(jù)集時(shí),與其它算法相比,在時(shí)間性能方面具有優(yōu)勢(shì)。

以上使用單分類器預(yù)測(cè)未知樣本,而集成方法是通過(guò)聚集多個(gè)分類預(yù)測(cè)來(lái)提高分類準(zhǔn)確率,如文獻(xiàn)[10]設(shè)計(jì)的SEA算法,它按到達(dá)時(shí)間將訓(xùn)練數(shù)據(jù)劃分成大小相等、互不重疊的“有序數(shù)據(jù)塊”,并分別對(duì)每塊數(shù)據(jù)構(gòu)造基分類器;當(dāng)基分類器個(gè)數(shù)達(dá)到最大值時(shí),采用啟發(fā)式的替換機(jī)制選擇基分類器;文獻(xiàn)[11]設(shè)計(jì)了weighted-bagging算法,考慮不同基分類器性能間的差異,提出了根據(jù)分類器分類錯(cuò)誤率動(dòng)態(tài)改變權(quán)值的技術(shù);文獻(xiàn)[12]設(shè)計(jì)了adaptive boosting算法等,提出了自適應(yīng)集成分類器綜合挖掘方法,將boosting思想應(yīng)用于數(shù)據(jù)流分類中;文獻(xiàn)[13]設(shè)計(jì)了一種基于相反分類器的數(shù)據(jù)流分類算法IWB,通過(guò)從期望分類能力較低的分類器中分析并驗(yàn)證相反分類器,若和當(dāng)前概念相近時(shí)更新集成模型獲得高精度;文獻(xiàn)[14]設(shè)計(jì)的Ewamds算法,是通過(guò)減小被基分類器正確分類的實(shí)例的權(quán)值以增強(qiáng)具有不相似概念的實(shí)例對(duì)新分類器的影響,從而使算法能快速發(fā)現(xiàn)和適應(yīng)新概念;以上這些工作都是以C4.5作為基分類器來(lái)研究集成分類技術(shù)的。

C4.5作為功能強(qiáng)大的算法,本身也具有一些弱點(diǎn),如時(shí)間開銷,即在每個(gè)決策點(diǎn),連續(xù)型屬性要被分段,并排序求得分割點(diǎn)和分割屬性;C4.5是非增量式構(gòu)樹,即生成一棵樹后不能利用隨后到來(lái)的新數(shù)據(jù)對(duì)樹進(jìn)行繼續(xù)生長(zhǎng)。這些弱點(diǎn)具有很大的局限性,不適合處理數(shù)據(jù)量大、要求實(shí)時(shí)性的數(shù)據(jù)流。

因此,本文提出一種基于 UFFT的weighted-bagging集成分類器算法(UFFT-w b)[11],它是將UFFT作為基分類器應(yīng)用到weighted-bagging算法中,通過(guò)實(shí)驗(yàn)可知,基于UFFT的集成分類器精度相近,在時(shí)空性能上更具有優(yōu)勢(shì)。

1 UFFT算法

UFFT[9]算法是一種有監(jiān)督的學(xué)習(xí)算法,它將多類問(wèn)題轉(zhuǎn)化為多個(gè)二叉問(wèn)題,由多個(gè)二叉樹組成森林。UFFT與C4.5比較,在以下方面做了改進(jìn):①使用二次判別式來(lái)確定分割點(diǎn),只需統(tǒng)計(jì)各屬性的樣本均值和方差,無(wú)需占用較大空間和消耗大量時(shí)間排序,這是該算法相對(duì)C4.5及其它算法的最大優(yōu)點(diǎn);②使用Hoeffding[15]不等式?jīng)Q定分裂結(jié)點(diǎn)個(gè)數(shù),使得分裂結(jié)點(diǎn)個(gè)數(shù)的取值對(duì)算法性能影響降至最低;③葉子結(jié)點(diǎn)帶有貝葉斯與最大類的混合分類方法來(lái)測(cè)試數(shù)據(jù),這既考慮到貝葉斯方法可以充分使用葉子結(jié)點(diǎn)信息,又兼顧到最大類方法在小樣本數(shù)據(jù)下,相對(duì)較高分類精度的優(yōu)點(diǎn)。

UFFT采用二次判別式分析方法來(lái)確定分割點(diǎn),二次判別式方法是指假設(shè)各個(gè)屬性均滿足正態(tài)分布。將 X軸劃分為(-∞,d1)、(d1,d2)、(d2,+∞)3部分。其中,d1和 d2是表示p(-)φ{(diào)(x-,σ-)}=p(+)φ{(diào)(x+,σ+)}的 2 個(gè)根,p(-)是負(fù)類估計(jì),p(+)是正類估計(jì),x和σ分別是樣本期望和方差,從d1和d2中選擇一個(gè)更接近樣本均值的(用di表示)。將樣本按屬性Atti分為 2類 ,即“Atti＜=di”和“Atti＞di”。

UFFT使用信息熵作為評(píng)判標(biāo)準(zhǔn)選擇最佳的分裂屬性,根據(jù)期望和方差,結(jié)合概率密度公式計(jì)算出每個(gè)屬性在大于和小于分割點(diǎn)di時(shí)的正負(fù)類別分布概率。而屬性i對(duì)應(yīng)的信息熵H(Atti)的計(jì)算方法為:

其中,p+是屬性類標(biāo)號(hào)為正時(shí)的概率;p-是屬性類標(biāo)號(hào)為負(fù)時(shí)的概率。選取最大熵對(duì)應(yīng)的屬性作為分裂屬性,將該屬性的分割點(diǎn)作為該分支結(jié)點(diǎn)的分割。

葉子結(jié)點(diǎn)進(jìn)行分裂時(shí),當(dāng)且僅當(dāng)從上次分裂后到達(dá)該結(jié)點(diǎn)的實(shí)例數(shù)大于 N(min)值時(shí)才允許分裂,本文N(m in)值是通過(guò)計(jì)算Hoeffding不等式推導(dǎo)出來(lái)的表達(dá)式計(jì)算得到。由于樹高限制或者未達(dá)到分裂實(shí)例個(gè)數(shù),葉子結(jié)點(diǎn)會(huì)出現(xiàn)不純性,即其中有不同類標(biāo)號(hào)的記錄。針對(duì)這種不純性,UFFT采用樸素貝葉斯和最大類相結(jié)合的方法。采用貝葉斯,則使用了更多的葉子結(jié)點(diǎn)信息,即考慮類別分布的先驗(yàn)概率和各屬性值對(duì)應(yīng)的條件概率。而采用最大類,則在小樣本下性能較好,彌補(bǔ)貝葉斯方法在這點(diǎn)上的不足。

2 一種基于UFFT的數(shù)據(jù)流分類器

本文提出一種基于極速?zèng)Q策森林(UFFT)的加權(quán)裝袋算法,簡(jiǎn)稱UFFT_wb分類器。本文采用的加權(quán)裝袋(weighted-bagging)思想凸出代表新概念的分類器,而淘汰不適合當(dāng)前到來(lái)數(shù)據(jù)的分類器,以此來(lái)適應(yīng)當(dāng)前數(shù)據(jù)變化的方向,獲得較高精度。UFFT_wb分類器采用 UFFT算法構(gòu)造基分類器,與基于C4.5的 weighted-bagging數(shù)據(jù)流分類器(簡(jiǎn)寫為C4.5_wb分類器)比較,該方法建樹所需時(shí)間較少,且具有增量式增長(zhǎng)樹結(jié)構(gòu)的特性。

2.1 UFFT_wb算法流程

首先對(duì)算法中用到的符號(hào)說(shuō)明如下:EC表示集成分類器,初始值為Null;K為EC的基分類器最大個(gè)數(shù);Ci表示EC中第i個(gè)分類器;數(shù)據(jù)流DS;S表示當(dāng)前數(shù)據(jù)塊;b lock表示當(dāng)前數(shù)據(jù)塊大小;weight[i]表示Ci的權(quán)值。

在新數(shù)據(jù)塊S到來(lái)時(shí),利用 S先構(gòu)建新的UFFT基分類器C num,并刷新EC中原有的各個(gè)分類器權(quán)值。當(dāng)EC中的分類器個(gè)數(shù)達(dá)到K+1時(shí),刪除EC中權(quán)值最小的那個(gè)基分類器,保持EC中均為高權(quán)重基分類器。

具體過(guò)程描述如下:

2.2 基分類器權(quán)值更新

考慮到隨機(jī)模型不包含有用的知識(shí),拋棄誤差等于或大于E r的分類器。為計(jì)算方便,使用公式wi=E r-Ei對(duì)Ci進(jìn)行加權(quán)。

2.3 算法分析

(1)時(shí)間復(fù)雜度。假設(shè)使用block大小的數(shù)據(jù)塊S構(gòu)建一個(gè)基分類器的時(shí)間復(fù)雜度為O(f(block)),為計(jì)算其權(quán)值而分類測(cè)試數(shù)據(jù)的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于新建分類器的時(shí)間復(fù)雜度,故忽略不計(jì),那么,數(shù)據(jù)流可分割成n個(gè)block大小數(shù)據(jù)塊,時(shí)間復(fù)雜度為O(n f(b lock))。由此可知,一個(gè)集成分類器的時(shí)間復(fù)雜度取決于構(gòu)建一單個(gè)分類器的時(shí)間復(fù)雜度。已知UFFT算法構(gòu)建基分類器的時(shí)間復(fù)雜度為O(n),C4.5的為O(n lb n)。在相同的基分類器個(gè)數(shù)條件下,UFFT_wb時(shí)間性能將遠(yuǎn)小于C4.5_wb時(shí)間復(fù)雜度。

(2)空間復(fù)雜度。葉子結(jié)點(diǎn)在計(jì)算信息增益率求分割屬性時(shí),C4.5需預(yù)留一段存儲(chǔ)空間存放到達(dá)該結(jié)點(diǎn)的所有實(shí)例,并對(duì)實(shí)例進(jìn)行排序,計(jì)算求得分割點(diǎn)和分割屬性。而UFFT利用新到來(lái)的實(shí)例更新每個(gè)葉子結(jié)點(diǎn)的期望和方差,結(jié)合概率密度公式計(jì)算得出信息增益率,無(wú)需占用空間專門用于計(jì)算分割點(diǎn)和分割屬性。UFFT在初始化一個(gè)結(jié)點(diǎn)時(shí),也僅僅需要一段公共的存儲(chǔ)池,存放當(dāng)前到來(lái)的一段數(shù)據(jù),用于對(duì)新結(jié)點(diǎn)進(jìn)行更新,一旦更新完畢,該存儲(chǔ)池清空。

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

為驗(yàn)證 UFFT_wb,本節(jié)用實(shí)驗(yàn)評(píng)估算法。實(shí)驗(yàn)工作采用 UCI數(shù)據(jù)庫(kù)中Waveform數(shù)據(jù)和Hyperp lane數(shù)據(jù)[16]。W aveform具有3類類標(biāo)號(hào),按屬性維數(shù)分為21維、40維2種Waveform數(shù)據(jù)集(簡(jiǎn)稱waveform_21、waveform_40)。設(shè)定UFFT基分類器的參數(shù)初始值為δ=0.05,τ=0.01,N(min)=300,實(shí)驗(yàn)硬件為CPU1.83GH z、2G內(nèi)存的PC機(jī),系統(tǒng)環(huán)境為W indow s XP+Visual C++。

3.1 參數(shù)討論

為了考察單個(gè)分類器樹高h(yuǎn)、分類器最大個(gè)數(shù)K、數(shù)據(jù)塊b lock取值的變化對(duì)算法性能的影響,分別在waveform_21、waveform_40上進(jìn)行實(shí)驗(yàn),2種數(shù)據(jù)集均取100 k個(gè)實(shí)例(1 k=1 000)。

樹高影響單個(gè) UFFT分類器的分類精度變化,由圖1所示可知,樹高高度越高,單個(gè)UFFT分類器的精度逐漸降低。在waveform_21、waveform_40數(shù)據(jù)上,高度保持在1～5左右,精度一般在0.78以上,高度超過(guò)6以上,精度降至0.76左右。其原因是單個(gè)分類器樹高過(guò)高會(huì)造成過(guò)擬合。樹高為1的樹是樹樁,即單個(gè)UFFT轉(zhuǎn)化為若干個(gè)貝葉斯分類器組。在文獻(xiàn)[17]中也證明了h為5對(duì)于決策森林較合適,故本文選擇為5。

圖1 樹高取值對(duì)單UFFT精度影響

由于在硬件條件限制下,分類器個(gè)數(shù)不可能無(wú)限制增加,故需討論合適的分類器個(gè)數(shù),達(dá)到最優(yōu)分類精度。如圖2所示,當(dāng)數(shù)據(jù)塊block取1 k時(shí),UFFT_wb分別在4、6、8個(gè)基分類器條件下,分類精度比較高;C4.5_wb在分類器個(gè)數(shù)取10時(shí),分類效果最佳。為了在隨后的比較試驗(yàn)中,能夠使得C4.5_wb達(dá)到最佳的分類效果,這里選擇10作為UFFT_wb基分類器數(shù)。

圖2 K取值對(duì)集成分類器精度影響

由表1所列可知,當(dāng)數(shù)據(jù)塊大小 b lock取0.8、1、2 k時(shí),UFFT_wb分類效果更優(yōu)。由于block較小會(huì)導(dǎo)致過(guò)擬合,b lock較大又會(huì)使基分類器對(duì)新概念不夠敏感,比較試驗(yàn)時(shí),選擇1 k作為block取值。

表1 數(shù)據(jù)塊b lock取值對(duì)UFFT分類精度影響

3.2 與C4.5_wb對(duì)比試驗(yàn)

根據(jù)上述討論,UFFT_w b的參數(shù)分別是:單個(gè)基分類器樹高h(yuǎn)為5,數(shù)據(jù)塊b lock大小為1 k,基分類器個(gè)數(shù) K為10,確定參數(shù)后,進(jìn)行比較試驗(yàn)。

UFFT_wb和C4.5_wb處理w aveform_21、waveform_40數(shù)據(jù)集,數(shù)據(jù)量分別從 100～1 000 k的時(shí)間開銷,如圖3所示。從圖3可以看出,C4.5_wb的運(yùn)行時(shí)間開銷隨著數(shù)據(jù)量的增長(zhǎng)逐漸高于 UFFT_wb。在waveform_21數(shù)據(jù)集上,UFFT_wb的所有大小數(shù)據(jù)集的平均運(yùn)行時(shí)間開銷是 C4.5_w b的 81.5%;在 waveform_40數(shù)據(jù)集上,UFFT_wb的所有大小數(shù)據(jù)集的平均運(yùn)行時(shí)間開銷是C4.5_wb的83%。因waveform數(shù)據(jù)集是3個(gè)類標(biāo)號(hào),每個(gè)基分類器生成3個(gè)二叉樹。UFFT_wb系統(tǒng)共有10個(gè)基分類器,新建了30個(gè)樹,雖然樹結(jié)構(gòu)復(fù)雜,但仍然表現(xiàn)出較好的時(shí)間性能。

圖3 對(duì)waveform_21和w avefo rm_40分類的時(shí)間節(jié)省比

UFFT_wb和C4.5_wb處理w aveform_21、waveform_40數(shù)據(jù)集,數(shù)據(jù)量分別從 100～1 000 k的精度,見表2所列。UFFT_w b在精度上要高于C4.5_wb,在waveform_21數(shù)據(jù)集上,所有大小數(shù)據(jù)集的平均精度相差約1%,在waveform_40數(shù)據(jù)集上,所有大小數(shù)據(jù)集的平均精度相差約 1.6%,總體上,UFFT_wb略高,和 C4.5_wb在精度上相似。

表2 在waveform_21、w aveform_40分類精度比較

同時(shí),本文也對(duì)Hyperp lane的數(shù)據(jù)集做了實(shí)驗(yàn),其時(shí)間、精度性能比較見表3、表 4所列。所用的Hyperp lane參數(shù)設(shè)置如下:num driftatts=2,m agchange=1,nosie=5%,Si∈{10,-10},數(shù)據(jù)量為500～1 500 k;UFFT_wb的參數(shù)設(shè)置:樹高 h=5,數(shù)據(jù)塊 block=1 000,分類器個(gè)數(shù)K=10。由表3可知,隨著數(shù)據(jù)量的增加,UFFT_wb的時(shí)間性能依然保持較高優(yōu)勢(shì),UFFT_wb的平均運(yùn)行時(shí)間開銷是C4.5_wb的64.74%。雖然精度偏低,略低于C4.5_wb,而時(shí)間性能較好,平均節(jié)約時(shí)間約35.26%。

通過(guò)以上幾組實(shí)驗(yàn)表明,UFFT_wb在保持精度的同時(shí)提高了時(shí)間效率,總體上滿足了處理大數(shù)據(jù)量數(shù)據(jù)集的實(shí)時(shí)性要求。

表3 在Hpyerplane時(shí)間性能比較 s

表4 在Hpyerplane精度性能比較

4 結(jié)束語(yǔ)

本文提出一種基于UFFT的weighted-bagging的數(shù)據(jù)流分類算法(UFFT_wb),它是采用UFFT算法來(lái)替代C4.5算法構(gòu)建基分類器。與C4.5_wb算法相比,UFFT_wb在處理大數(shù)據(jù)集具有相似分類精度,一定程度降低了時(shí)間開銷,進(jìn)一步滿足大型數(shù)據(jù)的實(shí)時(shí)處理要求。但是算法在處理概念漂移數(shù)據(jù)和抗噪性上存在劣勢(shì),如何提高算法檢測(cè)概念漂移能力和解決抗噪性問(wèn)題將是下一步研究的目標(biāo)和方向。

[1] Golab L,¨Ozsu M T.Issues in data stream managemen t[J].SIGMOD Rec,2003,32(2):5-14.

[2] Supratik B,Sue M.Netw ork performance monitoring and m easurement:techniques and experience[C]//MMNS Tutorial,2002:461-470.

[3] 倪志偉,黃 玲,李鋒剛,等.數(shù)據(jù)流管理與挖掘研究[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2005,28(9):1157-1162.

[4] Quinlan JR.Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[5] Quinlan JR.C 4.5:programs formachine learning[M].San Francisco,CA:Morgan Kaufmann Pub lishers Inc,1993:68-70.

[6] Dom ingos P,Hu lten G.Mining high-speed data stream s[C]//Proceedings of the 6 th ACM SIGKDD International Con feren ce on Know ledge Discovery and Data M ining,2000:71-80.

[7] Gama J,Rocha R,M edas P.Accuratedecision trees form ining high-speed data streams[C]//Proceedings of the 9th ACM SIGKDD International Conferece on Know ledge Dis-covery and Data M ining,2003:523-528.

[8] Breiman L.Random forests[J].Machine Learning,2001,45(1):5-32.

[9] Gama J,M edas P,Rocha R.Forest trees for on-line data[C]//Proceedingsof the 2004 ACM Symposium on Applied Com puting,2004:632-636.

[10] StreetW,K im Y.A stream ing ensemble algorithm(sea)for large-scale classification[C]//P roceedings of the 7th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,2001:377-382.

[11] W ang H,Fan W ei,Yu P,et al.M ining concep t-drifting data stream s using ensemb le classifiers[C]//Proceedings of 9 th ACM SIGKDD InternationalConferen ce on Know ledge Discovery and Data M ining,2003:226-235.

[12] Chu Fang,Zaniolo C.Fast and ligh t boosting for adap tive mining of data stream s[C]//Proceeding of the 5th Pacific-Asia Conference on Know ledge Discovery and Data M ining,2004:282-292.

[13] 王 勇,李戰(zhàn)懷,張 陽(yáng),等.基于相反分類器的數(shù)據(jù)流分類方法[J].計(jì)算機(jī)科學(xué),2006,33(8):206-209.

[14] 胡學(xué)鋼,潘春香.基于實(shí)例加權(quán)方法的概念漂移問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(21):188-191.

[15] Loh W Y,Shih Y S.Split selection method s for c lassification trees[J].Statistica Sinica,1997,7:815-840.

[16] H u Xuegang,Li Peipei.A sem i-random m ultiple decisiontree algorithm for m ining data streams[J].Jou rnal of Com puter Science and Technology,2007,22(5):711-724.

[17] Hu lten G,Spencer L,Domingos P.M ining time changing data stream s[C]//Proceedings of the 7th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,2001:97-106.

A data stream classifier based on UFFT

ZHEN Tian-tian, ZHANG Yu-hong, LIYan, WANG Hai-ping, HU Xue-gang

(School of Compu ter and Inform ation,Hefei University of Technology,H efei 230009,China)

In this paper,a new data stream m iningmethod called UFFT-wb is proposed,which isbased on the weighted-bagging m odel and uses the u ltra fast forest tree(UFFT)algorithm to build the base classifier.Experiment results show thatUFFT-w b hasitsown characteristics,such as the less time to choose the cutpoint for splitting tests,the little space to build new node,the incrementalconstruction and so on.Compared w ith thew eighted-bagging algorithm based on C4.5,thismethod is superior in the time consumption w hilem aintaining the sim ilar accuracy.

data stream;ensemble classifier;ultra fast forest tree(UFFT);weighted-bagging algorithm

TP181

A

1003-5060(2011)01-0065-06

10.3969/j.issn.1003-5060.2011.01.016

2009-12-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(60975034);安徽省自然科學(xué)基金資助項(xiàng)目(090412044)和合肥工業(yè)大學(xué)科學(xué)研究發(fā)展基金資助項(xiàng)目(2010HGXJ0013)

甄田甜(1983-),女,安徽合肥人,合肥工業(yè)大學(xué)碩士生;

胡學(xué)鋼(1961-),男,安徽當(dāng)涂人,博士,合肥工業(yè)大學(xué)教授,博士生導(dǎo)師.

(責(zé)任編輯 張秋娟)