面向大數(shù)據(jù)流的半監(jiān)督在線多核學(xué)習(xí)算法

張鋼，謝曉珊，黃英，王春茹

(廣東工業(yè)大學(xué)自動化學(xué)院，廣東廣州510006)

隨著信息技術(shù)的快速發(fā)展和大規(guī)模應(yīng)用，數(shù)據(jù)的生成速度及存儲規(guī)模也在快速增長，特別是Web頁面、社交網(wǎng)絡(luò)及物聯(lián)網(wǎng)的普及和應(yīng)用，使人們所要存儲、處理和分析的數(shù)據(jù)規(guī)模以指數(shù)方式遞增。如谷歌搜索引擎在2008年索引的網(wǎng)頁個數(shù)突破1萬億個，沃爾瑪最近構(gòu)建的一個數(shù)據(jù)倉庫的數(shù)據(jù)規(guī)模達(dá)到4 PB。在此背景下對大數(shù)據(jù)的分析和挖掘成為當(dāng)前的熱點(diǎn)研究主題[1]。從算法的層面來看，大數(shù)據(jù)的機(jī)器學(xué)習(xí)和分析挖掘問題，主要存在以下的問題:

1)數(shù)據(jù)規(guī)模巨大，體現(xiàn)在數(shù)據(jù)記錄個數(shù)及維度上，對于很多大數(shù)據(jù)分析問題，即使是多項(xiàng)式時間復(fù)雜度的機(jī)器學(xué)習(xí)算法也不能在人們可接受的時間內(nèi)得到結(jié)果。

2)由于數(shù)據(jù)集比計算機(jī)內(nèi)存大，導(dǎo)致無法在訓(xùn)練學(xué)習(xí)器時加載整個訓(xùn)練集，或是出于應(yīng)用環(huán)境的限制，在訓(xùn)練學(xué)習(xí)器時不能獲取整個數(shù)據(jù)集，數(shù)據(jù)記錄可能按某種速率到來，而且數(shù)據(jù)產(chǎn)生的規(guī)律性會隨著時間變化而有所改變。

要解決問題1)，主要從2個途徑去考慮，其一是降低現(xiàn)有分析算法的時間復(fù)雜度，采取一些近似算法，在復(fù)雜度和精度方面取得折衷，如Yang等[2]提出了一種決策樹快速增量學(xué)習(xí)方法，通過對決策樹的屬性選擇指標(biāo)進(jìn)行近似，使算法能適用于數(shù)據(jù)流和超大型數(shù)據(jù)集，其性能和普通版本的決策樹相比并沒有明顯的下降;Jordan[3]對大數(shù)據(jù)統(tǒng)計推斷進(jìn)行了回顧，并針對大數(shù)據(jù)分而治之的算法提出了2種設(shè)計方法，其中重采樣策略是對完整訓(xùn)練集的近似，而分治策略把大數(shù)據(jù)集數(shù)據(jù)間的相互關(guān)系限制在較小的范圍內(nèi)，最終目的是降低算法的復(fù)雜度;其二是對現(xiàn)有算法進(jìn)行修改，轉(zhuǎn)化為可以并發(fā)/并行計算的版本，并利用云計算開發(fā)工具，如MapReduce編寫可以在云計算平臺上運(yùn)行的程序，通過計算云的強(qiáng)大運(yùn)算能力，使算法能在可接受的時間內(nèi)解決大數(shù)據(jù)分析問題，如Acar等[4]在MapReduce框架中實(shí)現(xiàn)了自適應(yīng)計算的數(shù)據(jù)流分析算法，通過維護(hù)一個數(shù)據(jù)表跟蹤數(shù)據(jù)集不同部分計算之間的依賴關(guān)系，當(dāng)需要更新時僅需考慮有關(guān)聯(lián)的部分?jǐn)?shù)據(jù)，算法有相對較佳的運(yùn)行效率;Ari等[5]設(shè)計了面向數(shù)據(jù)流的相關(guān)分析和關(guān)聯(lián)規(guī)則挖掘的云計算算法，能夠以批處理和在線的方式把相關(guān)分析和關(guān)聯(lián)規(guī)則挖掘的任務(wù)透明分配到計算云的不同部分，同時計算然后再進(jìn)行整合。

對于問題2)，目前主要解決思路是設(shè)計出以往機(jī)器學(xué)習(xí)和挖掘算法的在線學(xué)習(xí)版本。在線學(xué)習(xí)原是機(jī)器學(xué)習(xí)的一個研究分支，其目標(biāo)數(shù)據(jù)樣本以順序的方式輸入學(xué)習(xí)器，且不對歷史數(shù)據(jù)樣本進(jìn)行保存，算法通過對當(dāng)前輸入的樣本進(jìn)行分析，同步更新學(xué)習(xí)器，其中神經(jīng)網(wǎng)絡(luò)中的感知器模型就是在線學(xué)習(xí)的經(jīng)典例子[6]。由于在線學(xué)習(xí)不用保存以往的數(shù)據(jù)樣本，或僅需保存以往數(shù)據(jù)樣本的某種充分統(tǒng)計量，十分適合大數(shù)據(jù)分析的應(yīng)用場景。對于超大型數(shù)據(jù)集，以順序方式輸入模型，并同步更新學(xué)習(xí)器;對高速數(shù)據(jù)流，在線學(xué)習(xí)可以實(shí)現(xiàn)數(shù)據(jù)的邊輸入邊學(xué)習(xí)，使學(xué)習(xí)器模型能夠反映出最近一段時間的輸入數(shù)據(jù)規(guī)律并進(jìn)行有效預(yù)測。

本文研究大數(shù)據(jù)環(huán)境下的在線核學(xué)習(xí)(online kernel learning)算法。與傳統(tǒng)在線學(xué)習(xí)不同，本文的工作主要針對大數(shù)據(jù)流中的核函數(shù)學(xué)習(xí)問題，算法并不直接通過數(shù)據(jù)樣本的分析對學(xué)習(xí)器進(jìn)行更新，而是通過在線學(xué)習(xí)以迭代的方式確定一個最適用于當(dāng)前數(shù)據(jù)產(chǎn)生規(guī)律的核函數(shù)。本文認(rèn)為，核函數(shù)的學(xué)習(xí)比直接訓(xùn)練學(xué)習(xí)器有更廣泛的適用性，一個合適的核函數(shù)可以被嵌入到各種不同核學(xué)習(xí)器的訓(xùn)練過程，也可以直接用于核主成份分析(kernel PCA)、相關(guān)性分析(kernel CCA)或聚類分析等領(lǐng)域。因此，一個有效適用于大數(shù)據(jù)環(huán)境下的核學(xué)習(xí)算法有重要應(yīng)用價值。

目前被公開報道的在線核學(xué)習(xí)研究工作并不多，雖然核學(xué)習(xí)被廣泛用于機(jī)器學(xué)習(xí)的不同應(yīng)用領(lǐng)域，但核函數(shù)的學(xué)習(xí)問題由于其對分析目標(biāo)的間接性影響，在大數(shù)據(jù)分析和挖掘領(lǐng)域中并沒有被充分研究，因此研究大數(shù)據(jù)環(huán)境下的核函數(shù)學(xué)習(xí)問題對其他大數(shù)據(jù)機(jī)器學(xué)習(xí)任務(wù)有重要的基礎(chǔ)性意義。

本文提出一種適用于大數(shù)據(jù)流的在線核學(xué)習(xí)算法，在現(xiàn)有多核學(xué)習(xí)框架中結(jié)合數(shù)據(jù)依賴核的構(gòu)建方法，同時進(jìn)行有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)，對于高速數(shù)據(jù)流中的有標(biāo)記數(shù)據(jù)使用一種類似感知器訓(xùn)練的學(xué)習(xí)策略進(jìn)行有監(jiān)督核函數(shù)學(xué)習(xí)，對于所有數(shù)據(jù)(包括有標(biāo)記和無標(biāo)記數(shù)據(jù))進(jìn)行基于數(shù)據(jù)依賴核的核函數(shù)更新策略，實(shí)質(zhì)上進(jìn)行一種無監(jiān)督學(xué)習(xí)，不需要存儲和重新掃描歷史數(shù)據(jù)，僅需通過選擇的方式維持一個樣本工作集，在讀取新的數(shù)據(jù)樣本時能以較低的時間復(fù)雜度直接更新當(dāng)前的核函數(shù)，適用于大數(shù)據(jù)環(huán)境下的核學(xué)習(xí)問題，特別是高速大數(shù)據(jù)流中標(biāo)記缺失的情形。

1 在線核學(xué)習(xí)的相關(guān)工作

核函數(shù)學(xué)習(xí)問題是機(jī)器學(xué)習(xí)研究中的一個分支方向，通過機(jī)器學(xué)習(xí)的方法學(xué)習(xí)一個針對特定應(yīng)用背景的核函數(shù)，能夠大幅提高訓(xùn)練學(xué)習(xí)器的效果。G?nen等[7]回顧了目前的主要多核學(xué)習(xí)算法，指出大多數(shù)算法所得到核函數(shù)組合對學(xué)習(xí)器的影響差別不大，但是在學(xué)習(xí)算法的時間復(fù)雜度及核函數(shù)組合的稀疏性方面卻有很大差異，這種差異性在處理大數(shù)據(jù)的多核學(xué)習(xí)問題時必須考慮。他們的工作表明通過非線性和數(shù)據(jù)依賴的方式進(jìn)行核函數(shù)的組合具有更好的性能，數(shù)據(jù)依賴的核函數(shù)修正方式適合于高速無標(biāo)記的數(shù)據(jù)流，這是本文在線核學(xué)習(xí)方法的一個出發(fā)點(diǎn)。Orabona等[8]提出了一種多核學(xué)習(xí)的快速算法，能夠通過參數(shù)控制所生成核的稀疏程度，算法即使在待組合的核數(shù)量很大的情況下仍然能夠快速收斂，且模型訓(xùn)練的時間復(fù)雜度僅是訓(xùn)練樣本的線性函數(shù)。該工作大大減輕了核學(xué)習(xí)的算法復(fù)雜度，并能控制核的稀疏和與數(shù)據(jù)擬合的程度，有很重要的理論和應(yīng)用價值。但該工作并不完全適用于大數(shù)據(jù)，特別是高速數(shù)據(jù)流，其原因是它并非一種增量更新算法，而是一種批處理的優(yōu)化方法。此外，該方法是一種有監(jiān)督的核學(xué)習(xí)方法，并不能處理無標(biāo)記的數(shù)據(jù)樣本，而在大數(shù)據(jù)流中數(shù)據(jù)樣本的標(biāo)記缺失十分常見，因此核學(xué)習(xí)器的無監(jiān)督學(xué)習(xí)能力非常重要。

針對數(shù)據(jù)流學(xué)習(xí)和模型的增量更新問題，研究者們對在線學(xué)習(xí)進(jìn)行了深入研究，其中值得關(guān)注的研究工作是Jin等[9]提出的在線核學(xué)習(xí)框架，他們系統(tǒng)地提出了在線多核學(xué)習(xí)問題理論及其算法。針對核函數(shù)和核學(xué)習(xí)器的增量更新問題，他們提出了使用確定和隨機(jī)2種方法進(jìn)行更新，其中隨機(jī)更新需要結(jié)合一定的采樣策略進(jìn)行。他們的工作對于基本核函數(shù)較多的情況下是有效的，但僅在有監(jiān)督學(xué)習(xí)中進(jìn)行研究，即遇到一個新的樣本，若當(dāng)前模型分類正確，則不進(jìn)行更新動作，否則按照一定的策略更新模型。該方法并不直接適用于大數(shù)據(jù)流環(huán)境下的多核學(xué)習(xí)問題，其主要問題是它不能適應(yīng)數(shù)據(jù)流產(chǎn)生規(guī)律變化的情況，且當(dāng)某些數(shù)據(jù)缺少標(biāo)簽時模型無法有效處理。

本文認(rèn)為要解決此問題需要同時考慮數(shù)據(jù)標(biāo)簽和數(shù)據(jù)的空間分布，使用增量學(xué)習(xí)的方法同步更新模型，這也是在當(dāng)前很多大數(shù)據(jù)學(xué)習(xí)算法中所采用的策略。如Qin等[10]提出了一種適用于云計算增量梯度下降算法，解決大數(shù)據(jù)環(huán)境下帶線性約束的凸優(yōu)化問題。Yang等[2]提出了決策樹的增量學(xué)習(xí)近似算法，可以在沒有歷史訓(xùn)練數(shù)據(jù)的情況下通過在線學(xué)習(xí)的方式直接更新決策樹模型。但這些工作均是直接針對學(xué)習(xí)器進(jìn)行增量更新，其方法并不直接適用于本文的核函數(shù)學(xué)習(xí)問題。

2 面向大數(shù)據(jù)的多核學(xué)習(xí)算法

首先形式化描述多核學(xué)習(xí)問題，然后再給出帶有數(shù)據(jù)依賴的多核學(xué)習(xí)問題，并給出在線學(xué)習(xí)版本的算法。核學(xué)習(xí)所解決的問題是直接從訓(xùn)練數(shù)據(jù)集(有標(biāo)記或無標(biāo)記)中學(xué)習(xí)參數(shù)化或半?yún)?shù)化的核函數(shù)，使其能充分反映數(shù)據(jù)所蘊(yùn)含的分布規(guī)律。給定一系列的訓(xùn)練樣本 DL={(xi，yi)|i=1，2，…，n}，其中xi為屬性集，yi∈{－1，+1}為分類標(biāo)記，給定一個包含m個基本核函數(shù)的集合Km={kj(·，·):X × X → R，j=1，2，…，m}，學(xué)習(xí)一組非負(fù)權(quán)值使核學(xué)習(xí)器在測試集上的分類錯誤最小化。由于權(quán)值非負(fù)，根據(jù)核函數(shù)的性質(zhì)可知，核函數(shù)的凸組合仍為一個有效的核函數(shù)。該問題可以形式化描述為

式中:l為 Hinge Loss損失函數(shù)，定義為 l(a，b)=max(0，1－ab)，HK為核函數(shù)K所張成的希爾伯特空間，C控制模型復(fù)雜度與損失懲罰比重的參數(shù)。求解該優(yōu)化問題的時間復(fù)雜度比較高，這是由于其中包含2步優(yōu)化，第1步選擇一個u，確定一個核函，從而確定了HK;第2步在HK中尋找最簡單的且在當(dāng)前訓(xùn)練集中正確率最高(由C控制)的學(xué)習(xí)器f，這2個目標(biāo)分別對應(yīng)式(1)中的2項(xiàng)。若核函數(shù)確定，則尋找滿足2個條件的f的問題可以直接求解，如SVM模型則屬于此種情況。但若核函數(shù)是通過參數(shù)u來對若干基核函數(shù)進(jìn)行加權(quán)組合，要求最優(yōu)的u和f，則問題變得很有挑戰(zhàn)性，特別是在大數(shù)據(jù)學(xué)習(xí)環(huán)境中，此類問題基本上不可能在可接受的時間內(nèi)求得最優(yōu)解。

若通過限制基本核函數(shù)的個數(shù)或u中各分量的取值范圍，則會犧牲多核學(xué)習(xí)的優(yōu)勢，且沒有從根本上解決多核學(xué)習(xí)的問題。可以認(rèn)為，在沒有更好的求解算法的情況下，在線學(xué)習(xí)對上述問題是一種較好的求解策略。

2.1 在線多核學(xué)習(xí)

為了進(jìn)行在線學(xué)習(xí)，需要重新考慮式(1)。Jin等[9]的工作表明，當(dāng)所學(xué)習(xí)的核函數(shù)為某個基本核函數(shù)集合的線性組合時，式(1)的最優(yōu)化問題可以轉(zhuǎn)化為如下問題:先求出每個核函數(shù)ki在各自張成的希爾伯特空間Hki上最優(yōu)的fi，然后尋找一組權(quán)值u，使這些fi的組合最優(yōu)，在尋找最優(yōu)的過程中同步更新權(quán)值和fi。換句話說，若核函數(shù)的組合為線性時，在線多核學(xué)習(xí)問題可以兩步求解，先使用基礎(chǔ)的訓(xùn)練集為每一個核函數(shù)訓(xùn)練一個學(xué)習(xí)器，之后使用這些學(xué)習(xí)器進(jìn)行在線學(xué)習(xí)，每讀入一個訓(xùn)練樣本時，根據(jù)當(dāng)前的加權(quán)組合學(xué)習(xí)器對當(dāng)前訓(xùn)練樣本的輸出結(jié)果，使用一種策略更新該核函數(shù)的權(quán)值和所對應(yīng)的單個學(xué)習(xí)器，則最優(yōu)的核函數(shù)為各個核函數(shù)使用該最優(yōu)權(quán)值的加權(quán)組合體。即式(1)可以轉(zhuǎn)化為以下問題:

圖1描述了上述求解過程的主要步驟。

圖1 多核在線學(xué)習(xí)算法的主要框架Fig.1 The main framework of online multiple kernel learning

對式(2)進(jìn)行分析可知，由于各個fi之間沒有關(guān)聯(lián)，因此fi的最優(yōu)值可以單獨(dú)求出，再用類似感知器的權(quán)值更新算法求解最優(yōu)的組合權(quán)值u。由Representer定理可知，使式(2)最優(yōu)的fi必定滿足

式(3)給出了一種在線學(xué)習(xí)fi的方法，當(dāng)讀入一個訓(xùn)練樣本時，先判斷fi能否給出正確的標(biāo)簽，然后采用fi=fi+φyxki(x，·)更新，其中φ為指示函數(shù)，當(dāng)fi對x正確分類時其值為1，反之為0。Jin等在文獻(xiàn)[9]中實(shí)現(xiàn)了上述思想。算法1描述了整個過程。

算法1 在線多核學(xué)習(xí)

輸入:

核函數(shù)集合:Km={k1，k2，…，km}

初始化學(xué)習(xí)器:F={f1，f2，…，fm}

更新因子:β∈(0，1)

最大分類錯誤的容忍水平:e

當(dāng)前的權(quán)重向量:u

有標(biāo)記數(shù)據(jù)樣本:(x，y)

輸出:更新后的權(quán)重u

1)y*=sign(wT·F(x))

2)if y*=y then

3)φ=0

4)else

5)φ=1

6)end if

7)for i=1，2，…，m do

8)p= φ(min(e，－yfTi(x)+0.5))

9)ui=uiβp//更新 u

10)fi=fi+ φyki(x，·)

11)end for

12)return u

算法1在輸入有標(biāo)記數(shù)據(jù)樣本時，同時更新核權(quán)重和每個核所對應(yīng)的學(xué)習(xí)器。當(dāng)樣本被當(dāng)前學(xué)習(xí)器分類正確時，φ為0，此時不執(zhí)行更新動作;若分類錯誤，則減少該學(xué)習(xí)器的權(quán)重，見算法1的第8)和第9)行。第10)行根據(jù)Representer定理對每個核所對應(yīng)的最優(yōu)學(xué)習(xí)器進(jìn)行調(diào)整。最大錯誤容忍水平e控制以多大的力度去懲罰被學(xué)習(xí)器錯分的樣本。

由于僅對訓(xùn)練數(shù)據(jù)集進(jìn)行一次掃描，算法1并不能達(dá)到離線批處理學(xué)習(xí)器的性能。但可依據(jù)感知器訓(xùn)練過程對算法1的收斂性分析如下。算法第10)行對各個fi進(jìn)行更新，且各個fi相互獨(dú)立，相當(dāng)于m個獨(dú)立的感知器訓(xùn)練過程，當(dāng)輸入樣本線性可分時，各個fi可以收斂于當(dāng)前訓(xùn)練集下的最優(yōu)學(xué)習(xí)器，進(jìn)而確定其最優(yōu)組合;當(dāng)輸入樣本線性不可分時，其收斂性依賴于各個學(xué)習(xí)器的核函數(shù)，一般情況下并不收斂于最優(yōu)解，但實(shí)驗(yàn)部分的第4組實(shí)驗(yàn)說明經(jīng)過一段時間后學(xué)習(xí)器的性能會趨于穩(wěn)定，逼近一個可接受的較優(yōu)解。

2.2 基于數(shù)據(jù)依賴的核函數(shù)修改

數(shù)據(jù)依賴核[11]是一種無監(jiān)督的核函數(shù)學(xué)習(xí)方法，實(shí)質(zhì)是對核函數(shù)在訓(xùn)練樣本集上的值進(jìn)行修改，使其所反映的在可見數(shù)據(jù)樣本上的距離更加符合數(shù)據(jù)樣本點(diǎn)的空間分布，而不考慮樣本標(biāo)簽。它可以對任意現(xiàn)有核函數(shù)根據(jù)可見的數(shù)據(jù)樣本進(jìn)行修改，實(shí)質(zhì)是對由核函數(shù)所誘導(dǎo)的希爾伯特空間的內(nèi)積進(jìn)行修改[12]。首先給出數(shù)據(jù)依賴核的主要結(jié)論，然后再提出針對大數(shù)據(jù)和高速數(shù)據(jù)流的數(shù)據(jù)依賴核在線核學(xué)習(xí)算法。

給定一個核函數(shù)k和一個數(shù)據(jù)集D={x1，x2，…，xn}，記 kxi=(k(xi，x1)，…，k(xi，xn))，M=(∑iWij－W)p，k關(guān)于 D的 Gram矩陣記為 kD，Wij=RBF(xi，xj)，xi，xj∈ D 。則可以通過式(4)的方式對核函數(shù)k進(jìn)行修改，使其等距線沿D進(jìn)行分布:

kD(a，b)=k(a，b)－ kTa(I+MKD)－1Mkb(4)其中a和b為任意2個訓(xùn)練樣本，Μ是一個在原點(diǎn)對稱的距離矩陣，按文獻(xiàn)[12]的方法用圖拉普拉斯矩陣計算得到。整個過程中并沒有考慮數(shù)據(jù)的標(biāo)簽，僅是通過考慮數(shù)據(jù)的密度分布，對原有核函數(shù)的值進(jìn)行修改。

式(4)的計算需要離線批量進(jìn)行，且計算的時間復(fù)雜度較高，具體而言，式(4)在修改數(shù)據(jù)樣本a和b的核函數(shù)值時要計算ka和kb，即a和b與當(dāng)前可見數(shù)據(jù)集的核函數(shù)k值。當(dāng)可見數(shù)據(jù)不變時，M和kD這兩項(xiàng)只需計算一次，但對數(shù)據(jù)流而言，M和kD是在不斷變化的。但可以肯定的一點(diǎn)是，對于大規(guī)模數(shù)據(jù)集和數(shù)據(jù)流，直接計算整個數(shù)據(jù)集的M和kD在計算資源上并不現(xiàn)實(shí)。

因此考慮M和kD的在線更新策略，采用限制M和kD的規(guī)模為N×N，則必須有D中的數(shù)據(jù)樣本替換策略。借鑒操作系統(tǒng)中內(nèi)存頁面的調(diào)度算法，對靜態(tài)的大數(shù)據(jù)集應(yīng)用類似近期最少使用(least recently used，LRU)的樣本更新策略[13]，而對于高速數(shù)據(jù)流應(yīng)用先進(jìn)先出(first in first out，F(xiàn)IFO)更新策略[13]，其中LRU是替換最近一段時間沒有被使用過的樣本，由于樣本各不相同，本文采用聚類意義下的樣本使用統(tǒng)計。這兩種策略的合理性基于以下分析。對于靜態(tài)大數(shù)據(jù)集，雖然數(shù)據(jù)是順序地輸入到學(xué)習(xí)器中，但其數(shù)據(jù)到達(dá)順序和時序不相關(guān)，因此不能使用與時間密切相關(guān)的FIFO策略，而采用LRU策略較為合理;對于數(shù)據(jù)流，其數(shù)據(jù)生成規(guī)律有可能隨時間變化而變化，因此替換存在時間最長樣本的FIFO策略是合理的。同時，數(shù)據(jù)依賴核是通過對數(shù)據(jù)的分布估計對核函數(shù)進(jìn)行修改，計算這種分布需要對一定規(guī)模的數(shù)據(jù)點(diǎn)進(jìn)行分析，因此維持一個工作集M是必須的，它可被看作一個緩存，反映近一段時間的數(shù)據(jù)分布規(guī)律。這種限制工作集大小的更新策略有一定的局部性，但在有限的計算和存儲資源下是折衷的策略。

算法維持一個不考慮標(biāo)簽的樣本集D并進(jìn)行在線更新。ka和kb的計算步聚是先查表kD，若不命中再計算，時間復(fù)雜度為O(N)。對于M和kD，替換樣本之后需要重新計算一行，然后更新一行和一列，因此其時間復(fù)雜度也為O(N)。算法初始時計算M和kD的時間復(fù)雜度為O(N2)。

一個重要問題是LRU和FIFO中對輸入樣本的時間屬性記錄，對LRU還有聚類意義下最近被使用樣本的判斷。本文首先用聚類的方式產(chǎn)生數(shù)據(jù)集D的r個簇，應(yīng)用在線聚類的方式更新這r個簇，替換樣本時每次從最久沒有被更新過的簇中隨機(jī)選取一個樣本進(jìn)行替換，使用一個長度為r優(yōu)先隊列記錄每個簇最近被訪問的情況。對于FIFO策略，不需要優(yōu)先隊列，每次把新加入的樣本放在最下行和最右列，然后去掉第1行第1列即可。算法2和算法3分別描述了靜態(tài)大數(shù)據(jù)集和流數(shù)據(jù)集2種情況下的數(shù)據(jù)依賴核的在線學(xué)習(xí)過程。

算法2使用一個優(yōu)先隊列記錄樣本簇最近被訪問的情況，認(rèn)為一個簇中的樣本被訪問過一次，則該簇最近被訪問過，核矩陣的更新從第7至10行，需要對所有樣本掃描一次，時間復(fù)雜度是O(N2)，優(yōu)先隊列的操作需要O(r)，其中r為簇的個數(shù)，判斷x0屬于哪個簇的粗糙算法需要O(r)時間，整體的時間復(fù)雜度為O(N2)。

算法2 大數(shù)據(jù)集的數(shù)據(jù)依賴核在線學(xué)習(xí)

輸入:

數(shù)據(jù)樣本集:D={x1，x2，…，xN}

當(dāng)前輸入樣本:x0

核函數(shù)Gram矩陣和距離矩陣:K、Μ

樣本空間聚類分布:LC

記錄簇最近訪問的優(yōu)先隊列:Q

輸出:更新后的核矩陣:K

1)r=clus(LC，x0)//查找樣本 x0的簇號

2)根據(jù)r更新優(yōu)先隊列Q

3)把x0加到簇r中

4)在優(yōu)先隊列Q的隊尾所示的簇中隨機(jī)去掉一個樣本

5)初始化kx0

6)令 k1=(k(x0，x1)，…，k(x0，xN))

7)for j=1，…，N do

8)k2=K(j，·)

9)kk0=k1－ kT1(I+ ΜK)－1Μk2

10)end for

11)用kx0更新矩陣K中關(guān)于x0的一行和一列

12)return K

算法3 流數(shù)據(jù)集的數(shù)據(jù)依賴核在線學(xué)習(xí)

輸入:

數(shù)據(jù)樣本集D={x1，…xN}

當(dāng)前輸入樣本:x0

核函數(shù)Gram矩陣和距離矩陣:K、Μ

輸出:更新后的核矩陣K

1)初始化kx0

2)k1=(k(x0，x1)，…，k(x0，xN))

3)for j=1，…，N do

4)k2=K(j，·)

5)kx0=k1－ kT1(I+MK)－1Mk2

6)end for

7)用kx0更新矩陣K中的最后一行和最后一列

8)return K

對于數(shù)據(jù)流在線核學(xué)習(xí)問題，采用FIFO策略，即每次把當(dāng)前的數(shù)據(jù)樣本替換時間最長的數(shù)據(jù)樣本，因此算法3中不需要優(yōu)先隊列。

算法4 半監(jiān)督在線多核學(xué)習(xí)SSL－MKL

輸入:

初始訓(xùn)練數(shù)據(jù)集D0輸入數(shù)據(jù)樣本集，D={xi，yi}，xi是樣本，yi是其標(biāo)簽

輸出:更新后的核矩陣K

1)初始化K

2)使用批處理算法由D0學(xué)習(xí)K

3)for each(xi，yi)in D

4)if Liis not NULL then

5)Call算法 1(xi，yi)

6)更新K

7)end if

8)if靜態(tài)大數(shù)據(jù)集then

9)Call算法 2(K，D0，M，xi，LC，Q)

10)else if數(shù)據(jù)流 then

11)Call算法 3(K，D0，M，xi)

12)end if

13)更新K

14)end for

15)return K

為了把在線多核學(xué)習(xí)和數(shù)據(jù)依賴進(jìn)行結(jié)合，算法每讀入一個數(shù)據(jù)樣本x，判斷是否有標(biāo)簽，若有標(biāo)簽，則先執(zhí)行多核學(xué)習(xí)的權(quán)重值更新，再執(zhí)行基于數(shù)據(jù)依賴的核修改;若沒有標(biāo)簽，則僅執(zhí)行核修改(算法2和算法3)。核修改是針對加權(quán)之后的核函數(shù)進(jìn)行。算法4描述了2部分核學(xué)習(xí)的結(jié)合過程。

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

在人工數(shù)據(jù)集和大數(shù)據(jù)學(xué)習(xí)的基準(zhǔn)數(shù)據(jù)集上對本文算法進(jìn)行有效性評估，并與現(xiàn)有的算法進(jìn)行比較。人工數(shù)據(jù)集使用MOA[14]的序列生成器自動生成，在實(shí)驗(yàn)中共生成了3個規(guī)模不同的人工數(shù)據(jù)集，由MOA所生成的人工數(shù)據(jù)集被廣泛用于大數(shù)據(jù)算法有效性的評估工作中[15－16]?；鶞?zhǔn)數(shù)據(jù)集采用UCI數(shù)據(jù)集[19]中的數(shù)據(jù)集。實(shí)驗(yàn)中選取MOA提供的其中3個生成器生成不同的人工數(shù)據(jù)集，蘊(yùn)含不同的數(shù)據(jù)生成規(guī)律。表1和2分別展示了人工數(shù)據(jù)集和UCI基準(zhǔn)數(shù)據(jù)集的主要信息。MOA序列生成器生成的3個人工數(shù)據(jù)集，以數(shù)據(jù)記錄生成時間順序保存在3個單獨(dú)的數(shù)據(jù)文件中，在線多核學(xué)習(xí)時順序讀取文件中的數(shù)據(jù)進(jìn)行訓(xùn)練和測試。2個UCI數(shù)據(jù)集中的數(shù)據(jù)隨機(jī)重排之后按順序讀入。其中數(shù)據(jù)集M1生成20份，規(guī)模從106～2×107，用于評估數(shù)據(jù)集規(guī)模與CPU處理時間的增長關(guān)系。

表1 MOA實(shí)驗(yàn)數(shù)據(jù)集的主要信息Table 1 Details of MOA data sets

表2 UCI實(shí)驗(yàn)數(shù)據(jù)集的主要信息Table 2 Details of UCI data sets

在上述5個數(shù)據(jù)集上進(jìn)行3組實(shí)驗(yàn)。第1組實(shí)驗(yàn)評估本文的半監(jiān)督在線多核學(xué)習(xí)算法(semi－supervised learning － multiple kernel learning，SSLMKL)的有效性，并與文獻(xiàn)[17]中的批處理多核學(xué)習(xí)算法及文獻(xiàn)[9]、[18]中的有監(jiān)督在線多核學(xué)習(xí)算法進(jìn)行比較。第2組實(shí)驗(yàn)分析本文算法對不同規(guī)模數(shù)據(jù)集處理的CPU運(yùn)算時間增長與數(shù)據(jù)集大小之間的關(guān)系。第3組實(shí)驗(yàn)評估本文算法的迭代次數(shù)與學(xué)習(xí)器性能的變化關(guān)系，從而說明其收斂性能。

在3組實(shí)驗(yàn)中均采用參數(shù)隨機(jī)的RBF核、多項(xiàng)式核和三角函數(shù)核函數(shù)各100個，即m=300。第1組實(shí)驗(yàn)采用如下設(shè)置:對比的一般核函數(shù)采用參數(shù)隨機(jī)的RBF核和多項(xiàng)式核，核學(xué)習(xí)器使用標(biāo)準(zhǔn)的SVM，只進(jìn)行二類分類，并采用0－1損失函數(shù)評估分類錯誤率。其中數(shù)據(jù)集M1的規(guī)模為106。在Μ和kD的更新算法中，限制其規(guī)模N為1000個樣本。

第1組實(shí)驗(yàn)評估SSL－MKL算法有效性并與有監(jiān)督的在線核學(xué)習(xí)算法進(jìn)行比較，同時引入一個非在線學(xué)習(xí)的多核學(xué)習(xí)算法作為算法有效性的基線。表3給出了對比算法的基本信息。

表3 實(shí)驗(yàn)對比算法的基本信息Table 3 Details of evaluation methods for comparison

F1與F2可以在5個實(shí)驗(yàn)數(shù)據(jù)集上運(yùn)行，F(xiàn)3不能運(yùn)行在數(shù)據(jù)流集上，即只能在M4和M5上運(yùn)行，因此可以把M1、M2、M3與M4、M5分別進(jìn)行比較。

由于算法F3無法直接處理M4和M5這樣大規(guī)模的數(shù)據(jù)集，只能采用隨機(jī)抽樣的方法，限制訓(xùn)練集的大小才可以使用批處理算法。本組實(shí)驗(yàn)對訓(xùn)練數(shù)據(jù)集進(jìn)行無回放抽樣，抽樣規(guī)模為10000。其余2個算法也在此抽樣數(shù)據(jù)集上進(jìn)行性能測試，對本文的SSL－MKL算法，從測試數(shù)據(jù)集中抽取同樣規(guī)模的數(shù)據(jù)集作為算法的無標(biāo)記數(shù)據(jù)?？紤]到抽樣的隨機(jī)性，對批處理核學(xué)習(xí)進(jìn)行10次抽樣訓(xùn)練并記錄10次的分類正確率的平均值。圖2展示了在M4和M5上的實(shí)驗(yàn)結(jié)果。

圖2 M4和M5的實(shí)驗(yàn)結(jié)果(限制數(shù)據(jù)集規(guī)模)Fig.2 The main framework of online multiple kernel learning

從圖2中可以看到，SSL－MKL不比F3差太多，但比F1和F2好，表明SSL－MKL對于規(guī)模受限制的數(shù)據(jù)集的性能較有監(jiān)督的在線核學(xué)習(xí)算法(F1和F2)好，歸功于SSL－MKL算法中的無監(jiān)督學(xué)習(xí)對最終學(xué)習(xí)器性能提升的貢獻(xiàn)，說明整個半監(jiān)督學(xué)習(xí)框架的有效性。另一方面，注意到3個在線算法的性能均不如批處理算法F3，這是可以理解的，因?yàn)樵诰€學(xué)習(xí)算法每次僅能“看到”當(dāng)前的訓(xùn)練樣本，且基本上不存儲(SSL－MKL算法中的工作集僅是有限度存儲)，批處理方法在整個訓(xùn)練期間能訪問所有的訓(xùn)練數(shù)據(jù)。因此可以接受在線學(xué)習(xí)方法性能稍差于批處理方法。但批處理方法難以處理大規(guī)模的數(shù)據(jù)集，正如本組實(shí)驗(yàn)的第2部分即將展示的(圖3)，這正是在線學(xué)習(xí)方法的優(yōu)勢[20－21]。下面給出 F1、F2與SSL－MKL在M4和M5整個數(shù)據(jù)集上的結(jié)果。訓(xùn)練集與測試集的規(guī)模按原數(shù)據(jù)集大小的3:7，對于SSL－MKL 采用轉(zhuǎn)導(dǎo)學(xué)習(xí)的方式[22－23]，即把整個測試集作為無標(biāo)記集。同樣對數(shù)據(jù)集進(jìn)行10次隨機(jī)劃分，記錄每次分類正確率并計算方差，圖3給出了在數(shù)據(jù)集M4和M5上算法正確率的比較結(jié)果。

圖3 M4和M5的實(shí)驗(yàn)結(jié)果(完整數(shù)據(jù)集)Fig.3 Evaluation results of M4 and M5(full data set size)

從圖3中可看出，由于有完整的訓(xùn)練集，各個算法的正確率相比圖2有所提升。SSL－MKL算法相比F1和F2的提升幅度比限制規(guī)模數(shù)據(jù)集時更大，表明數(shù)據(jù)依賴核對于數(shù)據(jù)分布的估計能夠提升核函數(shù)的性能。

最后給出數(shù)據(jù)流集(M1、M2、M3)的測試結(jié)果。測試過程是把訓(xùn)練樣本按其順序號依次輸入學(xué)習(xí)模型進(jìn)行訓(xùn)練;在接受測試樣本時，SSL－MKL同時進(jìn)行無監(jiān)督學(xué)習(xí)，而F1和F2，則僅輸出測試結(jié)果。由于數(shù)據(jù)集有順序，截取前面的30%作為訓(xùn)練集，后面70%作為測試集。表4給出了實(shí)驗(yàn)中各算法在數(shù)據(jù)集上正確率的比較。

表4 各算法在流數(shù)據(jù)集上正確率的比較Table 4 Accuracy comparison on stream data sets

從表4中可知SSL－MKL算法在3個數(shù)據(jù)集上都有最好的表現(xiàn)。第2組實(shí)驗(yàn)分析本文算法對不同規(guī)模數(shù)據(jù)集處理的CPU運(yùn)算時間增長與數(shù)據(jù)集大小之間的關(guān)系。為了精確控制實(shí)驗(yàn)數(shù)據(jù)集的規(guī)模，本組實(shí)驗(yàn)使用了20種規(guī)模依次等距遞增的M1數(shù)據(jù)集(以106為遞增單位)，記錄了 F2和 SSL－MKL算法的核學(xué)習(xí)時間，圖4給出了運(yùn)行時間對比。

圖4 不同數(shù)據(jù)集規(guī)模下的算法運(yùn)行時間比較Fig.4 CPU Time comparison for different data set sizes

從圖4中可以看出，SSL－MKL算法的運(yùn)算時間與數(shù)據(jù)集的規(guī)模成線性關(guān)系，并且SSL－MKL算法的有監(jiān)督學(xué)習(xí)部分的復(fù)雜性與算法F2同階，從圖4中可以看出其運(yùn)算時間的增長率與數(shù)據(jù)集規(guī)模有較好的線性關(guān)系，具有較好的可擴(kuò)展性，能適用于更大規(guī)模的數(shù)據(jù)集的分析和應(yīng)用問題。

第3組實(shí)驗(yàn)評估算法SSL－MKL的迭代次數(shù)與學(xué)習(xí)器性能的變化關(guān)系，從而說明其收斂性。設(shè)置測試集為整個數(shù)據(jù)集的5%，通過隨機(jī)有回放抽取的方式生成。訓(xùn)練集為整個數(shù)據(jù)集的30%，與第1組實(shí)驗(yàn)相同。每輸入5%的訓(xùn)練數(shù)據(jù)，運(yùn)行一次測試并記錄結(jié)果。上述過程重復(fù)10次取平均正確率。并以F3在限制數(shù)據(jù)集規(guī)模的實(shí)驗(yàn)(第1組)中的正確率作為基線進(jìn)行對比。圖5給出了在M4數(shù)據(jù)集上算法正確率迭代收斂性的實(shí)驗(yàn)結(jié)果。

圖5 算法正確率的收斂性Fig.5 The convergence of accuracy of the proposed algorithm

在圖5中，F(xiàn)3表示離線批處理核學(xué)習(xí)方法得到的核函數(shù)在SVM上的測試正確率曲線，SSL－MKL代表本文方法。每輸入一個樣本算法1就會運(yùn)行一次，核函數(shù)同時更新一次。從圖5中可以看出，在開始階段，僅需讀入少量樣本(5%)，SSL－MKL的正確率會大幅上升，隨后會比較穩(wěn)定收斂于一個較優(yōu)的值。當(dāng)輸入數(shù)據(jù)的內(nèi)在生成規(guī)律相對穩(wěn)定時，SSLMKL對核函數(shù)的更新會在一段時間內(nèi)(如圖5中輸入15%數(shù)據(jù)之后)穩(wěn)定下來，從而產(chǎn)生較穩(wěn)定的測試結(jié)果。

4 結(jié)束語

大數(shù)據(jù)環(huán)境下的多核學(xué)習(xí)問題是大數(shù)據(jù)機(jī)器學(xué)習(xí)的一個基礎(chǔ)性問題，比單純通過改進(jìn)訓(xùn)練算法效率構(gòu)建學(xué)習(xí)器有更重要的意義。本文提出了一種適用于大數(shù)據(jù)環(huán)境下的在線多核學(xué)習(xí)算法，考慮了數(shù)據(jù)的有監(jiān)督信息以及數(shù)據(jù)的空間分布，并應(yīng)用數(shù)據(jù)依賴核的構(gòu)建方法，對所學(xué)習(xí)得到的核函數(shù)進(jìn)行無監(jiān)督修正，使其具有更好的泛化能力。算法基于在線學(xué)習(xí)的框架進(jìn)行增量學(xué)習(xí)，僅需對訓(xùn)練數(shù)據(jù)進(jìn)行一次掃描，就可以更新核函數(shù)，并不需要對歷史數(shù)據(jù)進(jìn)行保存。算法適用于高速數(shù)據(jù)流，以及訓(xùn)練數(shù)據(jù)規(guī)模很大以致不能全部加載到內(nèi)存中的情形。在由著名的大數(shù)據(jù)流分析工具M(jìn)OA生成的人工數(shù)據(jù)集和UCI的大數(shù)據(jù)集上進(jìn)行算法有效性評估，表明了本文方法能學(xué)習(xí)得到與數(shù)據(jù)集規(guī)律相一致的核函數(shù)，在分類器上有較好的效果，且本文算法是一種在線學(xué)習(xí)算法，支持?jǐn)?shù)據(jù)增量更新。此外，本文的算法能同時處理有標(biāo)記和無標(biāo)記數(shù)據(jù)，對于數(shù)據(jù)概念標(biāo)記稀疏的高速數(shù)據(jù)流可以進(jìn)行半監(jiān)督學(xué)習(xí)，有很好的擴(kuò)展性。

[1]GOPALKRISHNAN V，STEIER D，LEWIS H，et al.Big data，big business:bridging the gap[C]//Proceedings of the 1st International Workshop on Big Data，Streams and Heterogeneous Source Mining:Algorithms，Systems，Programming Models and Applications.Beijing，China，2012:7－11.

[2]YANG H，F(xiàn)ONG S.Incrementally optimized decision tree for noisy big data[C]//Proceedings of the 1st International Workshop on Big Data，Streams and Heterogeneous Source Mining:Algorithms，Systems，Programming Models and Applications.Beijing，China，2012:36－44.

[3]JORDAN M I.Divide－and－conquer and statistical inference for big data[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining.Beijing，China，2012:4－4.

[4]ACAR U A，CHEN Y.Streaming big data with self－adjusting computation[C]//Proceedings of the 2013 Proceedings of the 2013 Workshop on Data driven Functional Programming.Rome，Italy，2013:15－18.

[5]ARI I，CELEBI O F，OLMEZOGULLARI E.Data stream analytics and mining in the cloud[C]//Proceedings of the 2012 IEEE 4th International Conference on Cloud Computing Technology and Science.Washington，DC，USA，2012:857－862.

[6]AGMON S.The relaxation method for linear inequalities[J].Canadian Journal of Mathematics，1954，6(3):393－404.

[7]GONEN M，ALPAYD E.Multiple kernel learning algorithms[J].Journal of Machine Learning Research，2011(12):2211－2268.

[8]ORABONA F，JIE L，CAPUTO B.Multi kernel learning with online－batch optimization[J].Journal of Machine Learning Research，2012(13):227－253.

[9]JIN R，HOI S C H，YANG T，et al.Online multiple kernel learning:algorithms and mistake bounds[J].Algorithmic Learning Theory，2010(6331):390－404.

[10]QIN C，RUSU F.Scalable I/O－bound parallel incremental gradient descent for big data analytics in GLADE[C]//Proceedings of the Second Workshop on Data Analytics in the Cloud.New York，USA，2013:16－20.

[11]SINDHWANI V，NIYOGI P，BELKIN M.Beyond the point cloud:from transductive to semi－supervised learning[C]//Proceedings of the 22nd International Conference on Machine Learning.Bonn，Germany，2005:824－831.

[12]李宏偉，劉揚(yáng)，盧漢清，等.結(jié)合半監(jiān)督核的高斯過程分[J].自動化學(xué)報，2009，35(7):888－895.LI Hongwei，LIU Yang，LU Hanqing，et al.Gaussian processes classification combined with semi－supervised kernels[J].Acta Automatica Sinica，2009，35(7):888－895.

[13]鄒恒明.計算機(jī)的心智:操作系統(tǒng)之哲學(xué)原理[M].北京:機(jī)械工業(yè)出版社，2012:100－102.

[14]BIFET A，HOLMES G，KIRKBY R，et al.MOA:massive online analysis[J].Journal of Machine Learning Research，2010(11):1601－1604.

[15]KREMER H，KRANEN P，JANSEN T，et al.An effective evaluation measure for clustering on evolving data streams[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego，California，USA，2011:868－876.

[16]BIFET A，HOLMES G，PFAHRINGER B，et al.Mining frequent closed graphs on evolving data streams[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego，USA，2011:591－599.

[17]FRANCESCO O，LUO Jie，BARBARA C.Multi kernel learning with online－batch optimization[J].Journal of Machine Learning Research，2012(13):227－253.

[18]STEVEN C H，RONG Jin，ZHAO Peilin，et al.Online multiple kernel classification[J].Machine Learning，2013，90(2):289－316.

[19]UCI數(shù)據(jù)集:http://archive.ics.uci.edu/ml/[EB/OL].[2014－03－18].

[20]YANG Haiqin，MICHAEL R L，IRWIN K.Efficient online learning for multitask feature selection[J].ACM Transactions on Knowledge Discovery from Data，2013，7(2):6－27.

[21]CHEN Jianhui，LIU Ji，YE Jieping.Learning incoherent sparse and low－rank patterns from multiple tasks[J].ACM Transactions on Knowledge Discovery from Data，2012，5(4):22－31.

[22]HONG Chaoqun，ZHU Jianke.Hypergraph－based multiexample ranking with sparse representation for transductive learning image retrieval[J].Neurocomputing，2013(101):94－103.

[23]YU Jun，BIAN Wei，SONG Mingli，et al.Graph based transductive learning for cartoon correspondence construction[J].Neurocomputing，2012(79):105－114.