茹 蓓

(新鄉(xiāng)學(xué)院計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453003)

0 引 言

近年來(lái)出現(xiàn)了許多數(shù)據(jù)流的實(shí)時(shí)分類(lèi)應(yīng)用，例如：金融市場(chǎng)通過(guò)對(duì)證券股指、期貨數(shù)據(jù)進(jìn)行實(shí)時(shí)分類(lèi)和預(yù)測(cè)，能夠快速察覺(jué)市場(chǎng)行情的變化，有助于提高投資收益和降低風(fēng)險(xiǎn)[1]；社交媒體用戶(hù)每天需要發(fā)布大量的圖像數(shù)據(jù)流，通過(guò)對(duì)圖像進(jìn)行實(shí)時(shí)分類(lèi)和預(yù)測(cè)，能夠快速檢測(cè)出非法圖像[2]。對(duì)數(shù)據(jù)流的實(shí)時(shí)分類(lèi)和預(yù)測(cè)存在巨大的應(yīng)用價(jià)值[3]，而圖像、文檔等高維數(shù)據(jù)是數(shù)據(jù)流的一個(gè)重要組成部分，其高維特性嚴(yán)重影響了分類(lèi)器的計(jì)算效率和分類(lèi)性能，成為實(shí)時(shí)數(shù)據(jù)流分類(lèi)的一個(gè)難點(diǎn)[4]。

增量學(xué)習(xí)思想是當(dāng)前數(shù)據(jù)流實(shí)時(shí)分類(lèi)的一個(gè)重要手段，文獻(xiàn)[5]提出了噪聲消除的增量學(xué)習(xí)分類(lèi)器，使用互信息近鄰來(lái)檢測(cè)噪聲樣本，通過(guò)增量學(xué)習(xí)檢測(cè)數(shù)據(jù)流的類(lèi)標(biāo)簽。文獻(xiàn)[6]提出基于樣本不確定性選擇策略的增量數(shù)據(jù)流分類(lèi)模型，從相鄰訓(xùn)練集中按照樣本不確定性值選出“富信息”樣本代表新概念樣本集。增量學(xué)習(xí)主要通過(guò)一些評(píng)價(jià)指標(biāo)檢測(cè)出某些判別能力強(qiáng)的新到達(dá)樣本，然后結(jié)合這些樣本對(duì)分類(lèi)器進(jìn)行更新，此類(lèi)方法主要以上一個(gè)時(shí)間窗口的模型為基礎(chǔ)，導(dǎo)致變化劇烈窗口的訓(xùn)練集存在明顯的偏差，難以實(shí)現(xiàn)理想的分類(lèi)準(zhǔn)確率。文獻(xiàn)[7]將回歸系統(tǒng)應(yīng)用于時(shí)變環(huán)境，實(shí)現(xiàn)了回歸神經(jīng)網(wǎng)絡(luò)，該方法通過(guò)回歸模型主動(dòng)學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)的模型參數(shù)，實(shí)現(xiàn)了較為理想的性能，雖然采用了簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，但該模型的回歸模型依然存在訓(xùn)練時(shí)間長(zhǎng)的問(wèn)題。

基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)流分類(lèi)器一般通過(guò)增量學(xué)習(xí)機(jī)制動(dòng)態(tài)地更新神經(jīng)網(wǎng)絡(luò)的參數(shù)，采用多層神經(jīng)網(wǎng)絡(luò)處理高維數(shù)據(jù)流才能獲得更好的效果，但多層神經(jīng)網(wǎng)絡(luò)的參數(shù)量較多，實(shí)時(shí)學(xué)習(xí)的難度較大[8]。本文從一個(gè)新的角度出發(fā)，對(duì)高維數(shù)據(jù)流進(jìn)行分析和分類(lèi)處理。采用超網(wǎng)絡(luò)建模高維數(shù)據(jù)流的數(shù)據(jù)空間，利用基于高斯核的投影技術(shù)將高維數(shù)據(jù)投影到低維空間。利用貝葉斯模型的先驗(yàn)分布、后驗(yàn)分布和似然信息擬合數(shù)據(jù)流的動(dòng)態(tài)特性，設(shè)計(jì)了貝葉斯模型的實(shí)時(shí)更新方法，實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)流的實(shí)時(shí)分類(lèi)處理。

1 高階模型的超網(wǎng)絡(luò)

超圖[9]是離散數(shù)學(xué)中有限集合的子系統(tǒng)結(jié)構(gòu)，超圖的邊為高階邊，稱(chēng)為超邊，超邊連接兩個(gè)以上的頂點(diǎn)。將超圖表示為G=(V,E)，其中V和E分別是頂點(diǎn)集和超邊集。一條超邊是V的一個(gè)子集，超邊的權(quán)重滿(mǎn)足w(e)≥0。頂點(diǎn)的度和超邊的度d(v)和δ(e)分別定義為：

(1)

δ(e)=|e|

(2)

式中：|e|為邊e的基數(shù)，將度等于k的超邊簡(jiǎn)稱(chēng)為k-超邊。超邊的度值越高，則該超邊的模式判別能力越強(qiáng)。如果一個(gè)超圖的超邊均為k-超邊，則稱(chēng)其為k-均勻超圖，所以2-均勻超圖即為傳統(tǒng)意義的圖，3-均勻超圖即為三元組的集合，以此類(lèi)推。

超網(wǎng)絡(luò)[10]是超圖結(jié)構(gòu)的高階表示，超網(wǎng)絡(luò)的頂點(diǎn)定義為一個(gè)變量及其取值，超邊定義為頂點(diǎn)間的高階連接，超邊的權(quán)重表示連接的強(qiáng)度。超網(wǎng)絡(luò)是大量超邊的集合，可表征高維數(shù)據(jù)特征之間的高階關(guān)系。

將超網(wǎng)絡(luò)定義為一個(gè)三元組形式H=(V,E,W)，其中W表示超邊的權(quán)重集。超邊是兩個(gè)以上頂點(diǎn)的集合，表示為：

ei={vi1,vi2,vi3,…,vi|ei|,yi}

(3)

式中：yi表示第i個(gè)超邊ei的類(lèi)標(biāo)簽。超邊的權(quán)重反映了超邊對(duì)于類(lèi)標(biāo)簽的判別能力，所以可將超邊考慮為一個(gè)弱學(xué)習(xí)機(jī)，學(xué)習(xí)分類(lèi)器所需的特征子集。圖1為一個(gè)超網(wǎng)絡(luò)及超圖結(jié)構(gòu)的示意圖。

(a)超網(wǎng)絡(luò)實(shí)例

給定一個(gè)數(shù)據(jù)點(diǎn)集x(n)、一個(gè)類(lèi)標(biāo)簽集Y和一個(gè)超網(wǎng)絡(luò)H，選擇x(n)超邊加權(quán)調(diào)和值最大的標(biāo)簽，將該極大值標(biāo)簽作為x(n)的類(lèi)標(biāo)簽。超網(wǎng)絡(luò)模型的分類(lèi)步驟如下：

步驟1計(jì)算超邊集E中所有y∈Y超邊的權(quán)重之和：

(4)

式中：w(ei)表示ei的權(quán)重。

步驟2選擇總權(quán)重最大的標(biāo)簽作為x(n)的標(biāo)簽：

(5)

定義兩個(gè)指示函數(shù)f(x(n),ei)和φ(y(n),yi)，如果ei匹配x(n)，則f(x(n),ei)=1；如果y(n)=yi，則φ(y(n),yi)=1，即：

(6)

(7)

式中：c(x(n),ei)表示匹配的數(shù)量；θ為匹配的閾值，用于增強(qiáng)對(duì)噪聲數(shù)據(jù)的魯棒性。

超網(wǎng)絡(luò)的模型結(jié)構(gòu)對(duì)分類(lèi)算法的性能具有極大的影響，學(xué)習(xí)程序的目標(biāo)是尋找最優(yōu)的超邊集，即從一個(gè)特征集選出特征子集。該問(wèn)題主要分為3個(gè)子問(wèn)題：(1)選擇構(gòu)建超邊的變量子集;(2)確定超邊的度;(3)確定模型的超邊數(shù)量。子問(wèn)題(1)和(2)影響分類(lèi)器的分類(lèi)性能，子問(wèn)題(2)和(3)影響模型的計(jì)算復(fù)雜度。如果特征為二進(jìn)制值，那么特征集的規(guī)模為22|x|，|x|為數(shù)據(jù)的維度，超網(wǎng)絡(luò)模型對(duì)于高維數(shù)據(jù)的計(jì)算復(fù)雜度較高，因此為超網(wǎng)絡(luò)設(shè)計(jì)一個(gè)高效的模型學(xué)習(xí)方法，即基于貝葉斯模型的超網(wǎng)絡(luò)更新機(jī)制。

2 基于貝葉斯模型更新超網(wǎng)絡(luò)

圖2為超網(wǎng)絡(luò)數(shù)據(jù)流分類(lèi)算法的結(jié)構(gòu)框圖，使用貝葉斯更新方法學(xué)習(xí)超網(wǎng)絡(luò)的結(jié)構(gòu)，學(xué)習(xí)的內(nèi)容包括生成超邊、更新超邊權(quán)重和評(píng)估超網(wǎng)絡(luò)模型。首先，從訓(xùn)練數(shù)據(jù)集提取超邊，構(gòu)建初始化超網(wǎng)絡(luò)，將超邊和訓(xùn)練數(shù)據(jù)匹配計(jì)算超邊的權(quán)重。然后，將訓(xùn)練集分類(lèi)估算模型的適應(yīng)度，將低權(quán)重超邊替換為新生成的超邊，動(dòng)態(tài)地修改模型。

圖2 超網(wǎng)絡(luò)高維分類(lèi)算法的結(jié)構(gòu)框圖

2.1 貝葉斯模型的學(xué)習(xí)方法

引入貝葉斯模型學(xué)習(xí)超網(wǎng)絡(luò)，貝葉斯模型假設(shè)后驗(yàn)分布和先驗(yàn)分布分別為當(dāng)前種群(當(dāng)前超網(wǎng)絡(luò))和上一代種群(上一代超網(wǎng)絡(luò))。模型的適應(yīng)度定義為后驗(yàn)概率，適應(yīng)度同時(shí)反映了數(shù)據(jù)的判別能力和模型的復(fù)雜度。

(8)

式中:p(Y|X,Ht)和p(Ht|X)分別為似然信息和先驗(yàn)分布；p(Y|X)是一個(gè)正則常量。后驗(yàn)分布關(guān)于似然信息和先驗(yàn)分布的乘積成正比例關(guān)系：

p(Ht|X,Y)∝p(Y|X,Ht)p(Ht|X)

(9)

定義Ht的適應(yīng)度函數(shù)Ft為后驗(yàn)分布的對(duì)數(shù)，目標(biāo)函數(shù)變?yōu)樽畲蠡?10)：

Ft=logp(Y|X,Ht)+logp(Ht|X)

(10)

即

(11)

2.2 采用貝葉斯模型學(xué)習(xí)超網(wǎng)絡(luò)結(jié)構(gòu)

計(jì)算超網(wǎng)絡(luò)的適應(yīng)度需要定義模型的先驗(yàn)信息和似然信息，將經(jīng)驗(yàn)先驗(yàn)分布p(Ht|X)定義為目標(biāo)問(wèn)題的先驗(yàn)知識(shí)。超網(wǎng)絡(luò)的先驗(yàn)信息包括兩點(diǎn)：(1)變量和類(lèi)標(biāo)簽之間的相似性矩陣，采用基于投影的相似性矩陣選擇數(shù)據(jù)，產(chǎn)生初始化超邊；(2)縮小模型的規(guī)模，從上一次的后驗(yàn)分布p(Ht-1|Y,X)計(jì)算當(dāng)前迭代的經(jīng)驗(yàn)先驗(yàn)分布：

p(Ht|X)∝p(Ht-1|Y,X)

(12)

(13)

式中：Et為Ht的超邊集；P(e)表示超邊e的產(chǎn)生概率；PI(xi)表示選擇變量xi的概率；PI(xi)關(guān)于xi和類(lèi)標(biāo)簽之間的相似性成正比例關(guān)系。僅需要對(duì)每個(gè)新到達(dá)時(shí)間窗口計(jì)算一次PI(xi)，在更新過(guò)程中無(wú)需改變?cè)摳怕手?。通過(guò)上述方法可確定超網(wǎng)絡(luò)模型的3個(gè)主要參數(shù)：超邊包含的變量、超邊的度和超邊數(shù)量。

似然定義為從Ht正確分類(lèi)Y的條件概率，X表示了Ht的判別能力。統(tǒng)計(jì)模型對(duì)訓(xùn)練數(shù)據(jù)正確匹配和錯(cuò)誤匹配的數(shù)量，再計(jì)算每個(gè)超邊的加權(quán)調(diào)和值，通過(guò)評(píng)估超邊的判別能力估算似然信息。如果超邊和一個(gè)數(shù)據(jù)實(shí)例的標(biāo)簽匹配，則認(rèn)為該超邊正確匹配，否則匹配失敗?？偹迫挥?jì)算為各個(gè)數(shù)據(jù)實(shí)例似然的乘積：

(14)

將經(jīng)驗(yàn)似然定義為：

p(y(n)|x(n),Ht)≡

(15)

式中:w(ei)為第i個(gè)超邊的權(quán)重；Et為Ht的超邊集合。如果經(jīng)驗(yàn)似然小于0，則將其設(shè)為一個(gè)小的正數(shù)來(lái)防止出現(xiàn)負(fù)似然的情況。可獲得：

(16)

在訓(xùn)練程序中，如果正確匹配一條超邊，那么fi(n)·φi(n)和fi(n)(1-φi(n))分別等于1和0；如果錯(cuò)誤匹配，則分別為0和1；如果匹配失敗，則兩個(gè)值都為0。

超邊的權(quán)重是關(guān)于正確匹配情況和錯(cuò)誤匹配情況的函數(shù)：

(17)

式中：α是小于1的常量，用來(lái)增加正確預(yù)測(cè)的概率；β是一個(gè)小的正常量。因?yàn)槎刃〉某吰ヅ渎矢?，所以如果兩個(gè)超邊的度接近，則選擇度小的超邊，β不僅減少了模型的復(fù)雜度，而且增加了模型的泛化效果。如果w(e)小于0，則設(shè)為0，防止出現(xiàn)負(fù)權(quán)重。

結(jié)合式(13)的經(jīng)驗(yàn)先驗(yàn)和式(16)估算的似然，將超網(wǎng)絡(luò)的適應(yīng)度修改為：

Ft=logp(Y|X,Ht)+logp(Ht|X)≈

(18)

式中:λ和ζ均為正常量，λ負(fù)責(zé)調(diào)節(jié)模型的大小，ζ負(fù)責(zé)調(diào)節(jié)先驗(yàn)信息的變量選擇能力。

綜上所述，提高適應(yīng)度的措施有三點(diǎn)：(1)每次迭代保留權(quán)值高的超邊；(2)選擇PI(x)概率大的變量生成超邊；(3)在保持模型判別能力的情況下，盡量減少超邊的數(shù)量。超網(wǎng)絡(luò)更新的結(jié)束條件是在連續(xù)幾次迭代后，F(xiàn)t均不大于Fmax，或者達(dá)到最大迭代次數(shù)Imax。

2.3 基于高斯核投影的相似性度量

直接度量高維數(shù)據(jù)的相似性不僅準(zhǔn)確率低而且計(jì)算復(fù)雜度也較高，因此本文采用高斯核的投影技術(shù)計(jì)算高維數(shù)據(jù)之間的相似性矩陣。設(shè)S(xi,xj)為數(shù)據(jù)xi和xj間的相似性，其投影矩陣定義為[P]i,j=S(fDR(xi),fDR(xj))，其中：i和j是矩陣的行和列，fDR為投影函數(shù)。本文的目標(biāo)是將高維空間的數(shù)據(jù)點(diǎn)投影到低維空間，設(shè)目標(biāo)相似性矩陣是一個(gè)方陣T，則需要優(yōu)化以下的目標(biāo)函數(shù)：

(19)

表示矩陣M的l1范數(shù)。如果每對(duì)數(shù)據(jù)點(diǎn)超過(guò)了目標(biāo)相似性，此時(shí)的目標(biāo)函數(shù)則是最小值。

(20)

設(shè)c(x)為低維空間的相似性度量(例如：歐氏距離)，可將目標(biāo)矩陣T中的元素定義為：

(21)

式中:σc為縮放因子。

采用核方法實(shí)現(xiàn)投影處理，設(shè)Φ=φ(X)為Hilbert高維空間[12]的數(shù)據(jù)矩陣，φ(X)為高維空間的投影函數(shù)，然后學(xué)習(xí)從高維空間到低維空間的線(xiàn)性映射。將矩陣W重新定義為：

W=φ(X)TA=ΦTA

(22)

式中:A∈Rn×m為系數(shù)矩陣。將投影定義為數(shù)據(jù)點(diǎn)的線(xiàn)性組合，可獲得以下的投影方法：

YT=WTΦT=ATΦΦT=ATK

(23)

式中:K=ΦΦT∈Rn×n是數(shù)據(jù)的核矩陣，表示Hilbert空間數(shù)據(jù)點(diǎn)的內(nèi)積，即Kij=φ(xi)Tφ(xj)T。

核方法學(xué)習(xí)系數(shù)矩陣A，采用梯度下降法優(yōu)化目標(biāo)：

(24)

(25)

2.4 學(xué)習(xí)超網(wǎng)絡(luò)的方法設(shè)計(jì)

貝葉斯更新模型包括：生成超邊、選擇超邊和更新超邊。生成超邊需要確定兩個(gè)屬性：(1)超邊的數(shù)據(jù)變量；(2)超邊的度。圖3為生成超邊的示意圖。

圖3 生成超邊的示意圖

根據(jù)變量之間的投影相似性矩陣選擇相似的變量，相似的變量組成一條超邊。式(13)的PI(xi)計(jì)算為：

(26)

式中:I(xi;y)表示變量xi和類(lèi)y間的相似性(基于投影計(jì)算高維數(shù)據(jù)的相似性);η為一個(gè)非負(fù)常量，該常量防止相似性過(guò)小。將η和式(18)的ζ設(shè)為反比例關(guān)系。

根據(jù)Ht-1超邊度的概率決定Ht超邊的度：

(27)

算法1生成超邊的程序

輸入：數(shù)據(jù)集S={S1,S2,…,SN}。

輸出：超邊e。

/*初始化程序*/

n←從|D|隨機(jī)選擇數(shù)據(jù)樣本；

d←D[n]；

K←通過(guò)式(27)計(jì)算邊的度；

For eachkfrom 1 toKdo

idx←式(26)選擇變量;

val←d數(shù)據(jù)的xidx;

v←(idx,val)；

e←e∪{y(n)};

end for

e←e∪{y(n)}；

w(e)←0；

在迭代過(guò)程中刪除低權(quán)重的超邊，增加新的超邊，但可能存在相似的冗余超邊，導(dǎo)致計(jì)算復(fù)雜度升高。因此式(18)的適應(yīng)度有效維護(hù)了超網(wǎng)絡(luò)的大小，如果Ft大于Ft-1，則縮小超網(wǎng)絡(luò)，否則擴(kuò)大超網(wǎng)絡(luò)。

設(shè)Rt和Gt分別表示在第t次迭代刪除的超邊數(shù)量和新產(chǎn)生的超邊數(shù)量。將Rt定義為一個(gè)關(guān)于t的函數(shù)，Gt定義為一個(gè)關(guān)于Rt的函數(shù)，Rt和Gt分別定義為：

(28)

Gt=γt·Rt

(29)

式中:Rmax和Rmin分別表示Rt值的上界和下界；κ為一個(gè)常量，控制Rmax到Rmin的變化速率;γt為泛化模型的比例系數(shù)，定義為：

(30)

式中:ΔFt=Ft-Ft-1；τ控制種群縮小的速度，如果τ=0，那么種群規(guī)模保持不變。

圖4為基于貝葉斯的超邊更新算法流程圖，根據(jù)數(shù)據(jù)集的先驗(yàn)知識(shí)生成初始化超網(wǎng)絡(luò)，將超標(biāo)權(quán)重和特征的判別能力作為貝葉斯的似然信息，將超網(wǎng)絡(luò)的復(fù)雜度和適應(yīng)度作為貝葉斯的后驗(yàn)分布，貝葉斯迭代地學(xué)習(xí)最優(yōu)的超網(wǎng)絡(luò)結(jié)構(gòu)?；谪惾~斯的超邊更新算法偽代碼如算法2所示。

圖4 基于貝葉斯的超邊更新算法流程示意圖

算法2基于貝葉斯的超邊更新程序

輸入：訓(xùn)練集D，所有變量的相似性矩陣SM，第t次迭代刪除的超邊數(shù)量Rt，第t次迭代新生成的超邊數(shù)量Gt，第t次迭代的超邊集Et，第t次迭代的超網(wǎng)絡(luò)Ht，最大迭代次數(shù)Imax，H0的初始化超邊數(shù)量Hinit。

1.E0←NULL,H0←NULL;

//初始化

2.計(jì)算SM(D,SM)；

//式(26)

3.for eachifrom 1 toHinitdo

//建立初始化模型

4.ei←生成超邊；

//式(27)

5.wi←評(píng)價(jià)權(quán)重；

//式(17)

6.E0←E0∪ei；

7.end for

8.利用式(18)評(píng)估當(dāng)前模型的適應(yīng)度；

9.E1←利用式(22)刪除低權(quán)重超邊；

10.for eachtfrom 1 toTdo

//超邊迭代更新模塊

11. forifrom 1 toGtdo

12.ei←生成超邊；

//式(27)

13.wi←評(píng)價(jià)權(quán)重；

//式(17)

14.E0←E0∪ei；

15. end for

16. 以式(18)評(píng)估當(dāng)前模型的適應(yīng)度；

17. if未滿(mǎn)足結(jié)束條件then

18.H←H×Ht；

19. eles

20. break;

21. end if

22.Et+1←刪除低權(quán)重超邊；

//式(28)

23.數(shù)據(jù)流分類(lèi)

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)方法

實(shí)驗(yàn)環(huán)境為PC機(jī)，處理器為Intel Core i5-4570，內(nèi)存為16 GB，操作系統(tǒng)為Ubuntu 14.04 LTS，軟件的編譯環(huán)境為MATLAB R2017a。

將數(shù)據(jù)集排列成序列形式，每個(gè)到達(dá)數(shù)據(jù)首先用來(lái)測(cè)試在線(xiàn)分類(lèi)器的分類(lèi)性能，再用來(lái)更新分類(lèi)器的模型。每組實(shí)驗(yàn)將每個(gè)數(shù)據(jù)集做10次置亂處理，置亂數(shù)據(jù)集作為輸入數(shù)據(jù)，獨(dú)立完成10次實(shí)驗(yàn)，統(tǒng)計(jì)10次實(shí)驗(yàn)的平均誤差率和標(biāo)準(zhǔn)偏差值。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

采用10個(gè)UCI高維數(shù)據(jù)集作為實(shí)驗(yàn)的benchmark數(shù)據(jù)集，表1為benchmark數(shù)據(jù)集的基本屬性。數(shù)據(jù)集排列成序列形式來(lái)模擬數(shù)據(jù)流。

表1 10個(gè)高維benchmark數(shù)據(jù)集的基本屬性

3.3 對(duì)比實(shí)驗(yàn)方法

選擇4個(gè)近期的數(shù)據(jù)流在線(xiàn)分類(lèi)器作為對(duì)比方法：

(1)基于演化的在線(xiàn)貝葉斯分類(lèi)器[13]，簡(jiǎn)稱(chēng)為OnlineBayes，該方法與本算法同屬于采用貝葉斯分類(lèi)器的在線(xiàn)分類(lèi)方案。

(2)基于元神經(jīng)元的脈沖神經(jīng)網(wǎng)絡(luò)分類(lèi)器[14]，簡(jiǎn)稱(chēng)為OnlineSpikingNeural，該方法是基于神經(jīng)網(wǎng)絡(luò)的在線(xiàn)分類(lèi)器。

(3)基于混合分類(lèi)回歸樹(shù)和模糊自適應(yīng)諧振網(wǎng)絡(luò)的在線(xiàn)分類(lèi)器[15]，簡(jiǎn)稱(chēng)為FAM-CART，該方法較為新穎，且性能較為突出。

(4)在線(xiàn)的廣義分類(lèi)器[16]，簡(jiǎn)稱(chēng)為onlineuniversal，該分類(lèi)器支持多種類(lèi)型的數(shù)據(jù)流。

本文算法簡(jiǎn)稱(chēng)為HypernetworksBayes。

3.4 分類(lèi)器性能實(shí)驗(yàn)結(jié)果

1)高維數(shù)據(jù)流的分類(lèi)錯(cuò)誤率。首先評(píng)估5個(gè)分類(lèi)器對(duì)于10個(gè)高維數(shù)據(jù)流的分類(lèi)準(zhǔn)確率，采用分類(lèi)誤差率作為度量指標(biāo)，圖5為總體的統(tǒng)計(jì)結(jié)果?？梢钥闯?，HypernetworksBayes對(duì)于Biodeg和Spambase 2個(gè)數(shù)據(jù)集的分類(lèi)錯(cuò)誤率高于FAM-CART，HypernetworksBayes對(duì)于Ring數(shù)據(jù)集的分類(lèi)錯(cuò)誤率也高于onlineuniversal算法，但結(jié)果也較為接近。對(duì)于數(shù)據(jù)流的二分類(lèi)問(wèn)題，本文算法與其他優(yōu)秀的分類(lèi)器較為接近，但對(duì)于其他高維數(shù)據(jù)的多分類(lèi)問(wèn)題，本文算法的優(yōu)勢(shì)則較為明顯。FAM-CART對(duì)于10個(gè)高維數(shù)據(jù)流均表現(xiàn)出較低的分類(lèi)錯(cuò)誤率，F(xiàn)AM-CART采用分類(lèi)回歸樹(shù)和模糊自適應(yīng)諧振網(wǎng)絡(luò)2項(xiàng)技術(shù)，模糊自適應(yīng)諧振網(wǎng)絡(luò)具有較強(qiáng)的自適應(yīng)和自調(diào)節(jié)能力，而分類(lèi)回歸樹(shù)對(duì)于連續(xù)性數(shù)據(jù)流具有較強(qiáng)的處理能力，因此實(shí)現(xiàn)了較好的效果。比較OnlineBayes和HypernetworksBayes可見(jiàn)，HypernetworksBayes的分類(lèi)錯(cuò)誤率遠(yuǎn)低于OnlineBayes分類(lèi)器，即本文的超圖理論和基于高斯核投影的降維處理有效地提高了分類(lèi)器的性能。總體而言，本文算法的分類(lèi)錯(cuò)誤率低于其他4種算法。

圖5 5個(gè)分類(lèi)器對(duì)高維數(shù)據(jù)流的分類(lèi)錯(cuò)誤率的比較

2)分類(lèi)器統(tǒng)計(jì)檢驗(yàn)。通過(guò)Friedman檢驗(yàn)[17]測(cè)試分類(lèi)器對(duì)于10個(gè)數(shù)據(jù)集分類(lèi)結(jié)果的差異，F(xiàn)riedman檢驗(yàn)的顯著性設(shè)為0.05。Friedman檢驗(yàn)獲得的排名如圖6所示。本文算法排名第一，且遠(yuǎn)高于第二名，再次驗(yàn)證了HypernetworksBayes分類(lèi)器的性能優(yōu)勢(shì)。

圖6 分類(lèi)器的Friedman檢驗(yàn)結(jié)果

Friedman檢驗(yàn)?zāi)軌虮容^多個(gè)分類(lèi)器之間的性能，而驗(yàn)后比較檢驗(yàn)(post-hoc test)能夠詳細(xì)比較多個(gè)分類(lèi)器和單一分類(lèi)器的性能。通過(guò)驗(yàn)后比較檢驗(yàn)進(jìn)一步分析分類(lèi)器的性能，根據(jù)文獻(xiàn)[18-19]的討論，Hommel檢驗(yàn)適合評(píng)估數(shù)據(jù)流的在線(xiàn)分類(lèi)器的性能，所以采用hommel post-hoc對(duì)分類(lèi)器進(jìn)行驗(yàn)后比較檢驗(yàn)分析，結(jié)果如表2所示。觀(guān)察表中各個(gè)分類(lèi)器的p-value值，HypernetworksBayes明顯優(yōu)于其他4個(gè)分類(lèi)器，而對(duì)比方案中OnlineSpikingNeural和FAM-CART的性能也較為理想。

表2 分類(lèi)器的hommel post-hoc檢驗(yàn)

3.5 分類(lèi)器的時(shí)間效率

時(shí)間效率是數(shù)據(jù)流在線(xiàn)分類(lèi)器的一個(gè)重要性能指標(biāo)，直接決定了分類(lèi)器的應(yīng)用價(jià)值。為了評(píng)估在線(xiàn)分類(lèi)器的時(shí)間效率，統(tǒng)計(jì)了5個(gè)分類(lèi)器每組實(shí)驗(yàn)分類(lèi)程序的平均時(shí)間，結(jié)果如圖7所示?？梢钥闯?，OnlineSpikingNeural和FAM-CART的處理時(shí)間遠(yuǎn)高于其他3個(gè)算法，這2個(gè)算法均為基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)器，在訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過(guò)程中難以同時(shí)在網(wǎng)絡(luò)性能和時(shí)間效率兩方面均取得理想的平衡。受益于貝葉斯模型的高計(jì)算效率，OnlineBayes的時(shí)間效率最高。Onlineuniversal分類(lèi)器不包含復(fù)雜的計(jì)算和模型，也實(shí)現(xiàn)了極高的時(shí)間效率。HypernetworksBayes的時(shí)間效率略低于OnlineBayes分類(lèi)器和Onlineuniversal分類(lèi)器，但是也足以滿(mǎn)足處理實(shí)時(shí)數(shù)據(jù)流的時(shí)間需求。

圖7 5個(gè)在線(xiàn)分類(lèi)器的平均處理時(shí)間的比較

3.6 噪聲數(shù)據(jù)流的分類(lèi)實(shí)驗(yàn)結(jié)果

在實(shí)際的數(shù)據(jù)流應(yīng)用中，數(shù)據(jù)流均伴隨著不可忽略的噪聲數(shù)據(jù)，因此測(cè)試了在線(xiàn)分類(lèi)器對(duì)于噪聲數(shù)據(jù)流的性能。隨機(jī)選擇一個(gè)錯(cuò)誤類(lèi)標(biāo)簽，替換訓(xùn)練數(shù)據(jù)集的正確標(biāo)簽，訓(xùn)練集的噪聲數(shù)據(jù)比例分別設(shè)為10%、20%和30%。訓(xùn)練集為噪聲數(shù)據(jù)集，測(cè)試數(shù)據(jù)集為無(wú)噪聲數(shù)據(jù)集，使用10折交叉驗(yàn)證完成每組數(shù)據(jù)集的實(shí)驗(yàn)，計(jì)算10次獨(dú)立實(shí)驗(yàn)分類(lèi)錯(cuò)誤率的平均值。因?yàn)镺ptdigits和Penbased兩個(gè)高維數(shù)據(jù)集的分類(lèi)錯(cuò)誤率較低，所以重點(diǎn)測(cè)試并統(tǒng)計(jì)了噪聲數(shù)據(jù)對(duì)于Optdigits和Penbased兩個(gè)高維數(shù)據(jù)集的影響。

圖8為Optdigits和Penbased兩個(gè)高維數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果?？梢钥闯?，隨著噪聲比例的增加，本文算法分類(lèi)錯(cuò)誤率略有升高，但上升幅度較小。OnlineBayes和onlineuniversal兩個(gè)分類(lèi)器受噪聲的影響較大，幾乎不具備噪聲魯棒性，因此可得結(jié)論：本文的改進(jìn)措施有效地增強(qiáng)了分類(lèi)器的魯棒性。

(a)Optdigits數(shù)據(jù)集

4 結(jié) 語(yǔ)

本文設(shè)計(jì)了基于超網(wǎng)絡(luò)和投影降維的高維數(shù)據(jù)流在線(xiàn)分類(lèi)算法，利用貝葉斯模型的先驗(yàn)分布、后驗(yàn)分布和似然信息擬合數(shù)據(jù)流的動(dòng)態(tài)特性，設(shè)計(jì)了貝葉斯模型的實(shí)時(shí)更新方法，實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)流的實(shí)時(shí)分類(lèi)處理。本文算法利用高斯核將高維空間的數(shù)據(jù)點(diǎn)投影到低維空間，實(shí)現(xiàn)了較高的高維數(shù)據(jù)流分類(lèi)準(zhǔn)確率，并且對(duì)于噪聲也具有較好的魯棒性。

本文模型依然存在一些限制：無(wú)法處理不平衡數(shù)據(jù)流，而不平衡數(shù)據(jù)流也是實(shí)時(shí)數(shù)據(jù)流領(lǐng)域的一個(gè)細(xì)分領(lǐng)域；僅支持?jǐn)?shù)據(jù)維度權(quán)重相等的情況。未來(lái)將嘗試引入分級(jí)的超網(wǎng)絡(luò)模型，解決特征維度權(quán)重不相等的問(wèn)題，從而可將本方案運(yùn)用到推薦系統(tǒng)等多屬性度量的應(yīng)用中。