基于局部敏感哈希的改進(jìn)堆疊算法

王俊杰，溫雪巖*，徐克生，于 鳴

(1.東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040；2.國(guó)家林業(yè)局哈爾濱林業(yè)機(jī)械研究所, 黑龍江 哈爾濱 150086)

堆疊泛化(stacking)是機(jī)器學(xué)習(xí)領(lǐng)域中一種突出和流行的元學(xué)習(xí)方法，適用于計(jì)算機(jī)視覺(jué)和計(jì)算生物學(xué)等領(lǐng)域的各種機(jī)器學(xué)習(xí)任務(wù)[1]。Stacking與Bagging、Boosting等算法類似，是一種采用異質(zhì)集成策略的集成學(xué)習(xí)方法，其在更高假設(shè)空間具有更好的表達(dá)能力，并且可獲得比單學(xué)習(xí)器更好的學(xué)習(xí)效果。隨著Stacking方法在解決數(shù)據(jù)挖掘、文本分類、信息安全和圖像處理[2-5]等方面問(wèn)題的日益普及，它也在諸如kaggle、天池等之類的各大競(jìng)賽平臺(tái)中成為一種不可缺少的關(guān)鍵技術(shù)。

Wolpert[6]提出的堆疊算法巧妙地使用了交叉驗(yàn)證來(lái)生成高層數(shù)據(jù)，再通過(guò)訓(xùn)練高層數(shù)據(jù)進(jìn)而得到結(jié)果。Ting等[7]將交叉驗(yàn)證替換成了Bagging和Disjoint方法來(lái)生成高階數(shù)據(jù)以求得更精準(zhǔn)的結(jié)果，并且發(fā)現(xiàn)Bagging方法對(duì)不穩(wěn)定算法和穩(wěn)定算法都有效，但尚未對(duì)存在的幾種堆疊方式的時(shí)間復(fù)雜度做對(duì)比，以及對(duì)算法穩(wěn)定性作出有效證明；Sill等[8]提出了一種線性技術(shù)，即特征加權(quán)線性疊加(FWLS)，它使用元特征(描述數(shù)據(jù)集中每個(gè)示例的附加輸入)可以提高集成方法的性能，其最大收益來(lái)自需要大量調(diào)整和訓(xùn)練時(shí)間的非線性過(guò)程；吳擋平等[9]針對(duì)Bagging、Adaboost算法對(duì)穩(wěn)定性分類算法集成效果不好的問(wèn)題，提出基于Stacking的穩(wěn)定分類器組合算法，以得到更高分類準(zhǔn)確率的效果；Arsov等[10]分析了Stacking、bag-stacking(BAG)和dag-stacking(DAG)的假設(shè)穩(wěn)定性，并建立了堆袋和加重堆袋之間的聯(lián)系，最后證明了疊加的假設(shè)穩(wěn)定性是每個(gè)基本模型和合并器的假設(shè)穩(wěn)定性的乘積。

然而，目前對(duì)堆疊的工作原理、方式等技術(shù)領(lǐng)域的研究相對(duì)較少，僅有少量研究人員發(fā)表了罕見(jiàn)的博客或文章，其中的解釋往往基于直覺(jué)，沒(méi)有更具說(shuō)服力的理論支撐，缺乏理論洞察力。堆疊泛化作為交叉驗(yàn)證的“復(fù)雜版本”,有著與生俱來(lái)的高復(fù)雜性以及“數(shù)據(jù)泄露”問(wèn)題。堆疊泛化的高時(shí)間復(fù)雜度來(lái)源于交叉驗(yàn)證，它將分組后的數(shù)據(jù)交替進(jìn)行訓(xùn)練與測(cè)試，與其他機(jī)器學(xué)習(xí)算法相比，其復(fù)雜性不言而喻。堆疊算法在適應(yīng)模型特征時(shí)，使用了本不可見(jiàn)的測(cè)試集信息，出現(xiàn)了數(shù)據(jù)泄露的問(wèn)題。分析學(xué)習(xí)算法泛化能力的一種常見(jiàn)方法是看它對(duì)訓(xùn)練集中的小變化的敏感程度，用不同的穩(wěn)定性概念來(lái)量化，就可以在穩(wěn)定性和泛化之間建立精確的關(guān)系，借此關(guān)系可以消除一定的堆疊算法的不穩(wěn)定性。

本文針對(duì)上述堆疊的研究少有體現(xiàn)在時(shí)間復(fù)雜度、“數(shù)據(jù)泄露”以及算法穩(wěn)定性方面的問(wèn)題，提出一種介于BAG和DAG方法之間的基于LSH的Stacking算法，這里簡(jiǎn)稱為L(zhǎng)BDS(LSH-BAG-DAG-stacking)。LBDS摒棄了繁瑣復(fù)雜的k折交叉驗(yàn)證，而是利用LSH算法獲得“主流”數(shù)據(jù)并通過(guò)其完成整體的訓(xùn)練。LBDS首先將訓(xùn)練集和測(cè)試集映射到哈希桶，當(dāng)其中某個(gè)桶滿時(shí)作為開(kāi)始訓(xùn)練條件，訓(xùn)練出的模型對(duì)下一次桶滿時(shí)的訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)及其鄰域進(jìn)行預(yù)測(cè)。接著利用穩(wěn)定性和信息熵條件對(duì)基分類器篩選，生成高層數(shù)據(jù)，最后將高層訓(xùn)練預(yù)測(cè)得到的結(jié)果通過(guò)混合投票和平均的方法求得最終分類結(jié)果。

1 理論分析與設(shè)想

Stacking的設(shè)計(jì)之初就伴隨著很高的時(shí)間復(fù)雜度，并且存在著一定的“數(shù)據(jù)泄露”，這些問(wèn)題限制了Stacking的發(fā)展，本章主要從這2個(gè)方面出發(fā)并附加算法穩(wěn)定性進(jìn)行問(wèn)題闡述。

1.1 Stacking

(1)

(2)

簡(jiǎn)化為

(3)

式中g(shù)為組合器的模型方程。其中常見(jiàn)的2種不同的Stacking如圖1所示。

圖1 2種不同的Stacking構(gòu)造算法

傳統(tǒng)的Stacking算法采用k折交叉驗(yàn)證來(lái)生成元數(shù)據(jù)，但交叉驗(yàn)證具有高復(fù)雜性，同時(shí)也存在著“數(shù)據(jù)泄露”的現(xiàn)象。交替訓(xùn)練和驗(yàn)證k折數(shù)據(jù)，其時(shí)間復(fù)雜度變?yōu)樵瓉?lái)的k倍。將模型S擬合到數(shù)據(jù)d0，對(duì)數(shù)據(jù)d1進(jìn)行預(yù)測(cè)并評(píng)估性能。但是d0中的元函數(shù)取決于d1中的標(biāo)簽值。因此，這種泄漏就是我們?cè)噲D預(yù)測(cè)的目標(biāo)值本身就已嵌入到我們用來(lái)適應(yīng)模型的特性中。理論上S可以從元特征中推斷出有關(guān)標(biāo)簽值的信息，從而使其過(guò)度擬合訓(xùn)練數(shù)據(jù)，而不能很好地預(yù)測(cè)測(cè)試樣本。實(shí)際上，研究人員很容易忽略這個(gè)理論上的漏洞。文獻(xiàn)[7]中選擇用Bootstrap或Disjoint采樣代替交叉驗(yàn)證，假設(shè)有N′個(gè)樣本的隨機(jī)樣本，L Boostrap可表示為當(dāng)N≤N′時(shí)，隨機(jī)樣本L替換為大小為N的k個(gè)子集合，Disjoint則可表示為當(dāng)N≤N′時(shí)，隨機(jī)樣本L替換為k個(gè)大小為N的不相交子集，Bootstrap和Disjoint差別在于子集是否存在局部重復(fù)性。

1.2 局部敏感哈希

以往算法采用歐氏方法計(jì)算樣本之間距離極為耗時(shí)[11]，LBDS采用 LSH[12-13](局部敏感哈希)的方式來(lái)保證訓(xùn)練數(shù)據(jù)差異性和查找待測(cè)樣本的近鄰。LSH 是一種高維空間最近鄰搜索算法，其基本思想是：通過(guò)選取的哈希函數(shù)的映射變換能夠?qū)⒃嫉臄?shù)據(jù)集劃分為若干較小的子集，且每個(gè)子集中的元素個(gè)數(shù)較小且相鄰。其形式化定義如下：

定義1(局部敏感哈希函數(shù)簇) 對(duì)于Hash函數(shù)簇H中每個(gè)函數(shù)h，如果任意2點(diǎn)p、q滿足以下條件，則認(rèn)為H是(ddist1,ddist2,P1,P2)敏感的：

1)若d(p,q)≤ddist1,則

PH[h(p)=h(q)]≥P1;

(4)

2)若d(p,q)≥ddist2，則

PH[h(p)=h(q)]≥P2。

(5)

式中：ddist1

局部敏感哈希常用的距離度量有漢明距離、歐氏距離和余弦距離，對(duì)于LBDS處理數(shù)據(jù)向量則選取余弦距離來(lái)表示最為合適，對(duì)于存在于k維的2個(gè)點(diǎn)m和n(m、n為向量)，兩者的相似性為

(6)

式(6)表示向量m、n之間的夾角余弦值，值越大，則m、n越相似。

以二分類(A、B兩類)數(shù)據(jù)為例，用包含3個(gè)哈希桶的LSH對(duì)2類數(shù)據(jù)進(jìn)行處理。假設(shè)A類數(shù)據(jù)經(jīng)哈希映射落入桶1、桶2中，該類數(shù)據(jù)相對(duì)于B類數(shù)據(jù)多且分布廣，所以桶1和桶2中的A類數(shù)據(jù)更新非常快，這樣可以快速適應(yīng)數(shù)據(jù)動(dòng)態(tài)的變化，桶3則完整保留B類數(shù)據(jù)，如圖2所示。同理，多分類亦然。

圖2 LSH數(shù)據(jù)保存梗概

在算法訓(xùn)練之初建立一張空的哈希表，針對(duì)獲得的數(shù)據(jù)，將數(shù)據(jù)分別映射到表中多個(gè)固定容量的哈希桶中，若一個(gè)桶中的數(shù)據(jù)超過(guò)其容量，則對(duì)所有桶進(jìn)行訓(xùn)練，并將滿桶置空，用新數(shù)據(jù)繼續(xù)填充該空桶。對(duì)于當(dāng)前桶滿輪次獲得的模型，將對(duì)下一個(gè)桶滿輪次映射到哈希桶的訓(xùn)練集和測(cè)試集的鄰域進(jìn)行預(yù)測(cè)，通過(guò)對(duì)多個(gè)數(shù)據(jù)塊的處理，建立一張保存了數(shù)據(jù)分布梗概的哈希表。從直觀上說(shuō)，放棄交叉驗(yàn)證能避免一定的“數(shù)據(jù)泄露”現(xiàn)象。LBDS算法(基模型m對(duì)第一次桶滿數(shù)據(jù)預(yù)測(cè))如圖3。

圖3 LBDS算法

1.3 算法穩(wěn)定性

數(shù)據(jù)的采樣策略可能導(dǎo)致高偏差與高方差，造成模型不穩(wěn)定。文獻(xiàn)[14]利用疊加過(guò)程中各組成模型間假設(shè)穩(wěn)定性的相互作用分析相對(duì)于z=(x,y)的預(yù)期絕對(duì)損失誤差。

定義2(隨機(jī)假設(shè)穩(wěn)定性) 假設(shè)訓(xùn)練集D={zi=(xi,yi),i=1,…,m}∈Zm從屬于分布P中提取的，給出一個(gè)算法A，A(D)表示算法A對(duì)數(shù)據(jù)集D訓(xùn)練的模型，這里令A(yù)(D)=fD，l為損失函數(shù)，Ez表示z的期望，Di表示D{zi}，即數(shù)據(jù)集D移除了點(diǎn)zi=(xi,yi)。如果以下條件成立，隨機(jī)算法A具有隨機(jī)假設(shè)穩(wěn)定性βm，即

ED,z[|l(fD,z)-l(fDi,z)|]≤βm,?i∈{1,…,m}。

(7)

文獻(xiàn)[10]為了分析疊加的假設(shè)穩(wěn)定性，有以下2個(gè)假設(shè)：1)基學(xué)習(xí)算法彼此獨(dú)立；2)元學(xué)習(xí)算法獨(dú)立于基學(xué)習(xí)算法。因此，每個(gè)基算法的穩(wěn)定性獨(dú)立于其他算法，合并器算法的穩(wěn)定性也獨(dú)立于基算法的穩(wěn)定性[15-16]。上述穩(wěn)定性的疊加性是基于基分類器和元分類器的相互獨(dú)立的假設(shè)，在實(shí)際中，并不能保證分類器之間具有完全的獨(dú)立性?？梢岳貌町愋詠?lái)衡量分類器之間的獨(dú)立性，計(jì)算個(gè)體分類器間差異度的方式有：K度量[17]、難度度量θ[18]、廣義多樣性GD[19]、熵度量E[20]等。文獻(xiàn)[21]提出一種利用多個(gè)分類器的分類結(jié)果的熵值來(lái)表征分類器間的差異程度的熵度量，它沒(méi)有使用對(duì)數(shù)函數(shù)，更易處理且能快速運(yùn)算，其計(jì)算公式為

(8)

式中：N代表樣本數(shù)；L代表基分類器數(shù)目；zj表示第j個(gè)樣例；l(zj)表示對(duì)樣例分類正確的分類器的數(shù)量。如果所有的基分類器對(duì)于樣例zj輸出結(jié)果一致，即沒(méi)有差異，則此時(shí)熵度量值為0；如果僅僅有[L/2]的分類器分類正確，則熵度量值為1，此時(shí)集成系統(tǒng)的差異性最大。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

訓(xùn)練階段，當(dāng)下一輪次桶滿的時(shí)候，我們用本輪次的模型對(duì)訓(xùn)練集進(jìn)行預(yù)測(cè)，得到相應(yīng)的分類準(zhǔn)確度，利用式(8)得分類器群差異度最大，并且分類準(zhǔn)確率較高的Num個(gè)分類器，篩選出對(duì)應(yīng)的訓(xùn)練集元特征，最后用Num個(gè)分類器對(duì)測(cè)試集進(jìn)行預(yù)測(cè)，得到測(cè)試集元特征。

算法預(yù)測(cè)階段，針對(duì)每一個(gè)樣本的n+1個(gè)預(yù)測(cè)結(jié)果，使用混合投票和平均的方法來(lái)確定最終結(jié)果，經(jīng)過(guò)大量實(shí)驗(yàn)，決策公式定義為

(9)

2.1 算法描述與流程

輸入：訓(xùn)練數(shù)據(jù)DT，樣本類標(biāo)簽數(shù)量n，k種基分類算法{A1,A2,…,Ak}，桶滿次數(shù)m，元分類器B，測(cè)試樣本DS，哈希桶數(shù)量C以及容量S。

(Ⅰ)生成level 1訓(xùn)練集：

1)創(chuàng)建一張包含了C個(gè)桶且每個(gè)桶容量為S的空哈希表HT；

(Ⅱ)生成level 1測(cè)試集：

(Ⅲ)元學(xué)習(xí)器對(duì)level 1層數(shù)據(jù)進(jìn)行訓(xùn)練測(cè)試：

算法流程如圖4。

圖4 算法流程

2.2 算法分析

LBDS從數(shù)據(jù)采樣策略以及算法穩(wěn)定性2個(gè)方面對(duì)Stacking進(jìn)行優(yōu)化，其中的LSH方法采樣對(duì)時(shí)間復(fù)雜度和“數(shù)據(jù)泄露”有一定的降低和緩和。

2.2.1 LBDS時(shí)間復(fù)雜度

設(shè)x和y分別為訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)大小，有m種基分類算法(假設(shè)篩選了1/2)，n為類別數(shù)量，s為桶的數(shù)量，那么對(duì)于LBDS來(lái)說(shuō)，數(shù)據(jù)映射到哈希表所需時(shí)間為O(x+y)?？紤]到極端情況，假設(shè)每一次滿桶都是由一個(gè)僅差一個(gè)數(shù)據(jù)的桶所致(每個(gè)桶數(shù)據(jù)均分)，每次數(shù)據(jù)用m種分類算法訓(xùn)練分類器所需時(shí)間最長(zhǎng)為O(mxs)，最少為O(mx), 那么生成level 1訓(xùn)練集數(shù)據(jù)所用時(shí)間最長(zhǎng)為O(msx), 最短為O(mx)；生成level 1測(cè)試集數(shù)據(jù)所用時(shí)間是固定的O(my(n+1)/2)。在level 1層訓(xùn)練和測(cè)試的復(fù)雜度與生成時(shí)相同，則其花費(fèi)的時(shí)間復(fù)雜度最長(zhǎng)為O(m(2sx+y(n+1)+x+y)),最少為當(dāng)n=1時(shí)，也就是二分類時(shí)，O(2m(x+y)+x+y)。由此可見(jiàn)，桶容量的設(shè)置(即桶的設(shè)置個(gè)數(shù))和類別數(shù)量以及測(cè)試數(shù)據(jù)的選定對(duì)本算法十分關(guān)鍵。假設(shè)數(shù)據(jù)服從高斯分布，那么桶滿速度較快表示數(shù)據(jù)更迭快，其所代表的數(shù)據(jù)就是隨機(jī)變量取值的集中趨勢(shì)點(diǎn)，即LBDS時(shí)間復(fù)雜度與集中趨勢(shì)點(diǎn)有正相關(guān)聯(lián)系。

2.2.2 數(shù)據(jù)生成

LBDS使用LSH算法將數(shù)據(jù)映射到哈希桶里，在某個(gè)桶滿之后利用k個(gè)算法進(jìn)行訓(xùn)練，訓(xùn)練結(jié)束后將桶清空。這樣做的目的是代替交叉驗(yàn)證，從理論上說(shuō)訓(xùn)練結(jié)束是以訓(xùn)練數(shù)據(jù)中樣本數(shù)量最多的類別結(jié)束為終止條件，其存在的重復(fù)情況大大減少。最后利用LSH算法得到待測(cè)樣本的近鄰樣本，將對(duì)新的近鄰樣本的預(yù)測(cè)與交叉驗(yàn)證中對(duì)測(cè)試集的預(yù)測(cè)進(jìn)行合并，這從某種程度上緩和了“數(shù)據(jù)泄露”的情況。

2.2.3 LBDS的穩(wěn)定性

對(duì)于LBDS，根據(jù)式(2)以及2個(gè)假設(shè)有以下證明。假設(shè)在每次桶滿去除訓(xùn)練的數(shù)據(jù)為i，這里寫(xiě)成Di，表示D{i}，即數(shù)據(jù)集D移除了某個(gè)桶i，則有：

1)對(duì)于每對(duì)基礎(chǔ)模型的結(jié)果βs和βt，有：

(10)

(11)

從而有

(12)

(13)

結(jié)合式(10)、(11)有

(14)

由式(14)可以看出，疊加的假設(shè)穩(wěn)定性是所有基本模型和合并器假設(shè)穩(wěn)定性的乘積?；A(chǔ)算法和合并算法之間的獨(dú)立性使計(jì)算變得容易。另外，增加基礎(chǔ)模型的數(shù)量可以提高堆疊的穩(wěn)定性。

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

本次實(shí)驗(yàn)在具有6個(gè)Intel Xeon Silver 4116@2.10 GHz CPU的計(jì)算機(jī)上實(shí)現(xiàn)，操作系統(tǒng)為CentOS, Python版本為3.5.2。本次實(shí)驗(yàn)主要從3個(gè)問(wèn)題出發(fā)進(jìn)行驗(yàn)證：1)與現(xiàn)有的方法(如基于類標(biāo)簽和概率的Stacking、bag-stacking和dag-stacking)相比，LBDS的性能;2)時(shí)間復(fù)雜度，即訓(xùn)練模型所花費(fèi)時(shí)間；3)算法的穩(wěn)定性。

在實(shí)驗(yàn)中采用了經(jīng)典的支持向量機(jī)(support vector machine，SVM)、貝葉斯(navie Bayes)、決策樹(shù)(decision tree)、BP神經(jīng)網(wǎng)絡(luò)(backpropagation neural network),K近鄰算法(KNN)、邏輯回歸算法。其中SVM使用的核是Gaussian，決策樹(shù)中采用CART決策樹(shù)，貝葉斯方法中采用Gaussian，將邏輯回歸作為元分類器，其余作為基分類器，并設(shè)置4種方案作為對(duì)比：LS——標(biāo)簽分類(label stacking)為基礎(chǔ)的Stacking算法,如圖1(a)所示；SS——分類器預(yù)測(cè)分?jǐn)?shù)(score stacking)為基礎(chǔ)的Stacking算法,如圖1(b)所示；BS——bag-stacking算法，即其數(shù)據(jù)采樣采用Boostrap方法；DS——dag-stacking算法，即其數(shù)據(jù)采樣采用Disjoint方法。

為了驗(yàn)證算法設(shè)想，從UCI和Statlog 這2個(gè)公開(kāi)數(shù)據(jù)集中選取具有數(shù)量級(jí)梯度的數(shù)據(jù)集，數(shù)據(jù)集匯總見(jiàn)表1。

表1 公開(kāi)數(shù)據(jù)集一覽

在本實(shí)驗(yàn)中，LBDS的桶數(shù)量設(shè)置成樣本數(shù)量最多的類別的1/4，除LBDS外其他算法一律使用5折交叉驗(yàn)證。算法對(duì)數(shù)據(jù)集的訓(xùn)練和驗(yàn)證性能表現(xiàn)選用準(zhǔn)確率(Acc)和ROC曲線下與坐標(biāo)軸圍成的面積(AUC值)作為評(píng)價(jià)標(biāo)準(zhǔn)，在選取訓(xùn)練集和測(cè)試集的時(shí)候，引入了隨機(jī)性，為此，進(jìn)行了多次實(shí)驗(yàn)(5次實(shí)驗(yàn))，并記錄各個(gè)算法在各數(shù)據(jù)集上表現(xiàn)情況(平均Acc和AUC值，結(jié)果保留3位小數(shù))，結(jié)果見(jiàn)表2(其中多分類的AUC為宏平均和微平均，如0.98/0.98)

表2 數(shù)據(jù)集上各算法的Acc和AUC對(duì)比

通過(guò)5次實(shí)驗(yàn)，統(tǒng)計(jì)出各算法在各個(gè)數(shù)據(jù)集上的表現(xiàn)情況見(jiàn)表3。由表3的數(shù)據(jù)可以看出，LBDS算法與其他算法相比有著更好的性能表現(xiàn)。LBDS、BS、DS與LS和SS公共的不同就是采取了非交叉驗(yàn)證的策略。交叉驗(yàn)證有著一定的“暴力美學(xué)”，它檢驗(yàn)所有的數(shù)據(jù)集，理論上會(huì)產(chǎn)生更優(yōu)的結(jié)果，但“數(shù)據(jù)泄露”問(wèn)題容易使交叉驗(yàn)證出現(xiàn)過(guò)擬合，在測(cè)試集上的泛化能力會(huì)適得其反。而bag-stacking、dag-stacking有著不同的數(shù)據(jù)采樣策略，bag-stacking重復(fù)隨機(jī)采樣在大概率上獲得數(shù)據(jù)的整體結(jié)構(gòu)，操作簡(jiǎn)單，但采樣的次數(shù)和數(shù)量對(duì)結(jié)果的影響很大；dag-stacking對(duì)不重復(fù)的子集進(jìn)行訓(xùn)練，其優(yōu)點(diǎn)是速度較快，但很有可能不能完全掌握數(shù)據(jù)的整體結(jié)構(gòu)。

表3 算法在數(shù)據(jù)集上預(yù)測(cè)平均準(zhǔn)確率

通過(guò)表2可以看出，DS和BS的Acc和AUC值比LS和SS更佳，DS和BS平均表現(xiàn)在6個(gè)數(shù)據(jù)集上優(yōu)于LS和SS，平均性能高了2%。而LBDS在8個(gè)數(shù)據(jù)集上優(yōu)于其他算法，表現(xiàn)在數(shù)量級(jí)較高的數(shù)據(jù)集上，表明LBDS對(duì)高維數(shù)量級(jí)有著一定的優(yōu)越性。分析表3可以得到LBDS在小樣本數(shù)據(jù)集上表現(xiàn)較差，而在大樣本數(shù)據(jù)集上一直表現(xiàn)良好，可見(jiàn)其在較大數(shù)據(jù)集上具有良好的分類效果。經(jīng)過(guò)多次訓(xùn)練可看出LBDS表現(xiàn)出的優(yōu)越穩(wěn)定性，這在解決大數(shù)據(jù)問(wèn)題上有很大的潛力。經(jīng)LBDS算法的部分?jǐn)?shù)據(jù)集ROC曲線如圖5。

圖5 LBDS在部分?jǐn)?shù)據(jù)集上的ROC曲線和AUC值

衡量算法的性能還需考慮算法的時(shí)間復(fù)雜度，本文對(duì)算法訓(xùn)練和測(cè)試的平均時(shí)間進(jìn)行統(tǒng)計(jì)，其結(jié)果見(jiàn)表4。

由表4可以看出堆疊算法的高時(shí)間復(fù)雜性，其本身策略就是犧牲時(shí)間復(fù)雜性來(lái)?yè)Q取更好的分類性能。LBDS在低數(shù)量級(jí)上的時(shí)間復(fù)雜度接近于甚至高于其他算法，而在高維數(shù)據(jù)上有著平均約10%的時(shí)間節(jié)省，可見(jiàn)LBDS的樣本采取策略在大數(shù)據(jù)上有著一定的優(yōu)越性。

表4 算法平均時(shí)間復(fù)雜度統(tǒng)計(jì)

綜上所述，本文提出的LBDS算法在處理大量數(shù)據(jù)時(shí)有著明顯的優(yōu)勢(shì)。在10個(gè)實(shí)驗(yàn)數(shù)據(jù)集上顯示：LBDS算法Acc和AUC值通常高于常用的4 種堆疊算法而且性能更加穩(wěn)定，說(shuō)明本文提出的LBDS 算法是有效可取的。

4 結(jié)語(yǔ)

針對(duì)Stacking方法在數(shù)據(jù)挖掘、圖像處理、自然語(yǔ)言處理等機(jī)器學(xué)習(xí)領(lǐng)域上的應(yīng)用越來(lái)越廣泛，而時(shí)間復(fù)雜度和分類效果是其最重要的2個(gè)技術(shù)指標(biāo)。本文提出一種基于LSH的Stacking方法(LBDS)，首先利用LSH算法生成0層數(shù)據(jù)，再利用穩(wěn)定性和信息熵條件對(duì)基分類器篩選，生成高層數(shù)據(jù)，最后通過(guò)投票法和平均法得到最終分類結(jié)果。通過(guò)在UCI和Statlog公開(kāi)數(shù)據(jù)集上篩選的數(shù)據(jù)集驗(yàn)證表明，LBDS確實(shí)對(duì)Stacking方法本身存在的高復(fù)雜性、“數(shù)據(jù)泄露”問(wèn)題進(jìn)行了一定的改進(jìn)以及對(duì)算法穩(wěn)定性進(jìn)行了加強(qiáng)，這對(duì)于Stacking在相關(guān)應(yīng)用領(lǐng)域內(nèi)的時(shí)間復(fù)雜度以及穩(wěn)定性方面具有一定的實(shí)踐價(jià)值。另外，LBDS對(duì)圖像和自然語(yǔ)言等問(wèn)題的大數(shù)據(jù)處理的高復(fù)雜性問(wèn)題的研究提供了一定的理論指導(dǎo)意義，同時(shí)也為聚類、回歸等問(wèn)題的穩(wěn)定性研究提供了理論參考。