基于核心向量機(jī)的多任務(wù)概念漂移數(shù)據(jù)快速分類

史熒中，王士同，鄧趙紅,3，侯立功，錢冬杰

隨著計算機(jī)信息技術(shù)的發(fā)展，每天都會產(chǎn)生大量電信服務(wù)、電子商務(wù)、金融市場、交通流量、網(wǎng)絡(luò)監(jiān)控、超市零售等方面的數(shù)據(jù)，這些數(shù)據(jù)是持續(xù)增加且不斷變化的。由于數(shù)據(jù)特征會隨著時間逐漸變化，針對這些非靜態(tài)數(shù)據(jù)的分類、回歸、聚類模型也在隨著時間而緩慢漂移，稱為概念漂移[1-2]。對概念漂移的研究已在理論上[1-4]及交通流量預(yù)測[5]、超市客戶行為分析[6]、氣體傳感器陣列漂移[7]、垃圾郵件過濾[8]等應(yīng)用場合取得了良好的效果。概念漂移建模過程中每個時刻的數(shù)據(jù)量都很少，因而需要借助相鄰時刻的一些數(shù)據(jù)來構(gòu)建合適的當(dāng)前時刻模型。以往針對概念漂移分類所作的工作大多是基于滑動窗算法[9-11]的思路，即采用一定時間窗口(區(qū)間)內(nèi)的數(shù)據(jù)進(jìn)行建模。2011 年，Grinblat等[12]借鑒 Crammer等在多任務(wù)學(xué)習(xí)中兼顧局部優(yōu)化與全局優(yōu)化的策略，提出了時間自適應(yīng)支持向量機(jī)[13]方法來求解漸變的子分類器。Shi等[14]提出了增強(qiáng)型時間自適應(yīng)支持向量機(jī)方法，在提高分類性能的同時，從理論上保證了其對偶為凸二次規(guī)劃問題。

由于生活中的概念漂移問題并不是孤立出現(xiàn)的，如某個氣體傳感器陣列上對多種氣體的測定數(shù)據(jù)可能會同時漂移；相鄰城市的天氣情況具有一定的關(guān)聯(lián)；相近街區(qū)的交通流量會相互影響等。對多個相關(guān)概念漂移問題同時建模，挖掘其他問題中的有效信息，能對建模起到有益的補(bǔ)充。共享矢量鏈支持向量機(jī)[15](shared vector chain supported vector machines, SVC-SVM)方法通過對相關(guān)概念漂移問題協(xié)同建模，有效地提升了所得模型的泛化性能。但由于具有較高的算法時間復(fù)雜度，限制了其在數(shù)據(jù)量急劇增長的社會現(xiàn)狀下的應(yīng)用能力。

現(xiàn)在已進(jìn)入大數(shù)據(jù)時代，各種社交和電子商務(wù)等信息量都越來越大，多任務(wù)概念漂移算法的時間復(fù)雜度也變得越來越重要。SVC-SVM方法可轉(zhuǎn)化為核空間中的另一SVM問題，算法時間復(fù)雜度一般為，其中為樣本容量。如采用SMO(sequential minimal optimization)[16]方法來求解，其復(fù)雜度可降為，但SVC-SVM方法仍然無法從容面對大規(guī)模概念漂移數(shù)據(jù)集。本文旨在尋找出一種新的概念漂移學(xué)習(xí)方法，除了能保持SVC-SVM方法良好的分類特性外，又能在面對多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集時具有較好的算法時間性能。

結(jié)合前期在概念漂移領(lǐng)域的研究基礎(chǔ)[14-16]，本文提出了共享矢量鏈核心向量機(jī)(shared vector chain core vector machines, SVC-CVM)方法，并基于核心向量機(jī)[17-19](core vector machine, CVM)理論給出了SVC-CVM方法的快速算法。所提SVCCVM方法具有以下特點：

1)面對多任務(wù)概念漂移問題時，SVC-CVM方法優(yōu)于獨立求解單個概念漂移問題的TA-SVM及ITA-SVM方法；

2)SVC-CVM方法采用了與SVC-SVM方法相同的技巧，即假設(shè)多個概念漂移問題共享漸變的矢量鏈序列，因而在分類性能上，SVC-CVM方法與SVC-SVM方法相當(dāng)；

3)SVC-CVM方法可以借鑒CVM理論[17]設(shè)計出快速求解算法，以處理多任務(wù)概念漂移中數(shù)據(jù)量較大的問題，算法時間復(fù)雜度接近。

1 概念漂移問題相關(guān)研究

在概念漂移研究方面，傳統(tǒng)的研究是基本滑動窗算法，這是一類局部優(yōu)化模式。TA-SVM和ITA-SVM方法對局部優(yōu)化和全局優(yōu)化進(jìn)行了權(quán)衡，取得了良好的效果。

1.1 單任務(wù)概念漂移分類方法

TA-SVM[13]方法及ITA-SVM[14]方法針對的是傳統(tǒng)的單任務(wù)概念漂移分類。假設(shè)有T個按時間順序采集的子數(shù)據(jù)集，TA-SVM方法在優(yōu)化各子分類器的同時，還假設(shè)子分類器應(yīng)該能夠光滑地變化，因此約束相鄰子分類器之間的差異，其基本思想可由(1)式來表示。

1.2 SVC-SVM方法及其對偶

為了能進(jìn)一步挖掘出相關(guān)概念漂移數(shù)據(jù)集中蘊(yùn)含的有效信息，需要協(xié)同求解多個分類模型。假定現(xiàn)有K個相關(guān)概念漂移數(shù)據(jù)集，每個概念漂移數(shù)據(jù)集中的數(shù)據(jù)由T個按時間順序采集的子數(shù)據(jù)集組成,每個子數(shù)據(jù)集中的數(shù)據(jù)量為m個。將所有數(shù)據(jù)合并記為數(shù)據(jù)集，。記為 第個任務(wù)在第T)時刻的分類模型，為第t 時刻的共享矢量，表示在第t 時刻共享矢量與第個任務(wù)之間的差異。面向多任務(wù)概念漂移分類的共享矢量鏈支持向量機(jī)方法SVC-SVM的原理可通過式(2)來表示：

式中：H為擴(kuò)展核空間上的某個核函數(shù)，具體表達(dá)形式可以參見相關(guān)文獻(xiàn)[15]。從式(3)可知，SVCSVM方法對多個概念漂移問題同時建模，其對偶問題為核空間中的另一個支持向量機(jī)問題，當(dāng)采用普通方法來求解此二次規(guī)劃問題時，其算法時間復(fù)雜度為，即便采用SMO[16]方法來求解SVC-SVM的對偶問題，使其復(fù)雜度降為，仍然是無法承受計算的代價，難以從容面對現(xiàn)實生活中數(shù)據(jù)規(guī)模較大的應(yīng)用場景。

2 共享矢量鏈核心向量機(jī)及快速算法

2.1 共享矢量鏈核心向量機(jī)

鑒于SVC-SVM方法在針對多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集時算法時間復(fù)雜度偏高，本文借鑒CVM[17-19]的思路，提出了與SVC-SVM方法在分類性能相似，但在數(shù)據(jù)量較大的場景時又能進(jìn)行快速處理的SVC-CVM方法。SVC-CVM方法借鑒了SVC-SVM方法的思想，為了能進(jìn)一步用快速算法求解，本文按文獻(xiàn)[17-18]的方法對SVC-SVM[15]的目標(biāo)函數(shù)稍作變化，采用平方損失函數(shù)，通過推導(dǎo)得到可以用CVM方法快速求解的對偶形式。

SVC-CVM方法的目標(biāo)函數(shù)為

由KKT條件，J取得極值時，有

因此有：

式中：

原始問題的對偶問題如下：

由此，SVC-CVM方法中雖然包含了多個數(shù)據(jù)流，但其對偶問題仍相當(dāng)于核空間中的另一個SVM問題，可以用常規(guī)方法來求解，其算法時間復(fù)雜度為，在算法效率上并不具有優(yōu)勢。因此下文將介紹SVC-CVM的快速求解方法。

2.2 核心向量機(jī)

求解最小包含球(minimum enclosing ball,MEB)是一個數(shù)學(xué)問題，等價于求解一個二次規(guī)劃問題[17-19]，如式(20)所示：

Tsang等在文獻(xiàn)[17-18]中指出，形如式（20）的二次規(guī)劃問題，如果核矩陣對角線元素為常量，則均等價于求解MEB問題。他們借助求解MEB問題時的近似包含球方法[19]，提出了核心向量機(jī)(core vector machines, CVM),在處理大規(guī)模數(shù)據(jù)集時有接近線性的時間復(fù)雜度。對形如式(20)的二次規(guī)劃問題，即使核矩陣對角線元素不為常量，也可以使用核心集方法進(jìn)行求解，這時就需要給核空間中每個樣本點都添加一個新的維度,樣本在新特征空間中表示為，然后求解在新特征空間中的最小包含球。該問題的形式如下：

2.3 SVC-CVM的快速算法

當(dāng)使用普通方法來求解SVC-CVM時，其求解時間復(fù)雜度為，對于多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集來說，是相當(dāng)大的計算開銷。對比式(18)和式(22)，它們具有相似的形式，因此，SVCCVM方法可以利用核心向量機(jī)技巧來求解。可以將式(18)等價地改寫為

SVC-CVM算法的輸入為多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集S, 核心集逼近精度、、等參數(shù)；輸出為核心集和權(quán)重系數(shù)。下面給出實現(xiàn)步驟：

由于SVC-CVM算法是基于核心集理論的，因而在描述算法的時間與空間復(fù)雜度時，可以參考文獻(xiàn)[17-18]，得到相關(guān)結(jié)論：

輸入 數(shù)據(jù)集S, 最小包含球近似精度；

5) 計算新的中心到其他各點的距離 ;

3 實驗研究和分析

本節(jié)將對SVC-CVM方法進(jìn)行實驗驗證，實驗將從SVC-CVM方法的分類準(zhǔn)確率、SVCCVM算法的時間性能兩個方面展開。這里有必要首先驗證其分類準(zhǔn)確率。1)需要考察引入分類間隔及采用平方損失函數(shù)以后，SVC-CVM算法是否保持了良好的分類能力；2)因為SVC-CVM方法的有效性是其快速算法有效的必要條件。本文另外選取了在單任務(wù)概念漂移建模中取得良好效果的兩個方法作為對比算法,作為對比算法的共有：1)TA-SVM 方法[13]；2)ITA-SVM 方法[14]；3)SVM-SVM方法[15]。為了對比的客觀性，本節(jié)實驗中所使用的數(shù)據(jù)集及實驗的設(shè)置都參照對比算法TA-SVM[13]。實驗環(huán)境為MATLAB R2013a，操作系統(tǒng)為Windows7， 8 GB內(nèi)存及3.30 GHz奔騰處理器。

3.1 實驗設(shè)置

實驗中涉及的各方法與相應(yīng)參數(shù)在表1中列出。

表 1 實驗所用的對比方法及相應(yīng)參數(shù)Table 1 Methods and parameters used in experiments

本文獨立生成相同分布的訓(xùn)練集、驗證集和測試集各10組，共進(jìn)行10次重復(fù)實驗，以獲得比較客觀的實驗結(jié)果。實驗分為參數(shù)優(yōu)化和建模測試兩個階段，首先需要基于訓(xùn)練集，利用驗證集獲得各方法的最優(yōu)參數(shù)；其次基于得到的優(yōu)化參數(shù)對訓(xùn)練集建模，并利用測試集來獲得各方法的性能。本文采用網(wǎng)格遍歷法來尋找最優(yōu)參數(shù)。

將旋轉(zhuǎn)超平面數(shù)據(jù)集記為數(shù)據(jù)集DS1中的第1個任務(wù)Task1，Task1數(shù)據(jù)集的樣本量為500，采樣于獨立分布的2維立方體，兩類之間的邊界是一個超平面，并繞原點緩慢旋轉(zhuǎn)。設(shè)超平面的法向量為，Task1的訓(xùn)練、驗證、測試數(shù)據(jù)由式(24)生成：

數(shù)據(jù)集DS1中的第2個任務(wù)Task2數(shù)據(jù)則由Task1模型順時針旋轉(zhuǎn)一定的角度后隨機(jī)生成，以體現(xiàn)出Task2與Task1模型的相關(guān)性。

將TA-SVM方法中所使用的高斯漂移數(shù)據(jù)集記為數(shù)據(jù)集DS2中的第1個任務(wù)Task1，數(shù)據(jù)集中包含兩個類別，共含有個數(shù)據(jù)點，每個類別中數(shù)據(jù)的特征都在緩慢變化。Task1的訓(xùn)練、驗證、測試數(shù)據(jù)由式(25)取時獨立生成，DS2中還包含另一個概念漂移數(shù)據(jù)集Task2，其數(shù)據(jù)同樣由(25)式生成，這時，以體現(xiàn)任務(wù)之間的差異性。

將DS1、DS2中的類別標(biāo)簽按一定比例隨機(jī)替換以模擬噪音數(shù)據(jù)，得到數(shù)據(jù)集DS3、DS4，用于測試SVC-SVM方法在噪音條件下的分類能力。

數(shù)據(jù)集DS5、DS6由DS1, DS2逐步加大采樣量分別得到，它們用于測試SVC-CVM方法的算法時間復(fù)雜度。實驗所用數(shù)據(jù)集如表2所示。

3.2 SVC-SVM的分類性能

本子節(jié)基于數(shù)據(jù)集DS1和DS2來觀察SVCCVM方法的分類能力，并將在噪音數(shù)據(jù)集DS3、DS4上觀察SVC-CVM方法在噪音條件下的性能。

針對數(shù)據(jù)集DS1，依據(jù)文獻(xiàn)[13]的策略，我們獨立生成10組訓(xùn)練集、測試集及用于選擇最優(yōu)參數(shù)的驗證集。根據(jù)前述的實驗設(shè)置，實驗分為優(yōu)化參數(shù)和建模測試兩個階段。核函數(shù)選用最常用的線性核及高斯核。當(dāng)兩個概念漂移數(shù)據(jù)Task1、 Task2呈現(xiàn)出不同的偏離程度時，求得各方法在兩個概念漂移數(shù)據(jù)Task1、Task2上的分類精度及平均值A(chǔ)verage。每個方法對各訓(xùn)練集共計10次運(yùn)行后的平均分類精度及標(biāo)準(zhǔn)差記錄在圖1中。

表 2 實驗所用的數(shù)據(jù)集Table 2 Description of artificial dataset

由圖1可以得到如下觀察：

1)在數(shù)據(jù)集DS1上，不管采用高斯核還是線性核，當(dāng)多個任務(wù)呈不同偏移程度時，協(xié)同求解多個概念漂移問題的SVC-SVM、SVC-CVM方法在任務(wù)Task1和Task2上總是優(yōu)于獨立求解單個概念漂移問題的TA-SVM和ITA-SVM方法，顯示了協(xié)同求解多任務(wù)概念漂移問題是有效的。

2)隨著多個任務(wù)之間偏離程度的增加，相對于獨立求解單個任務(wù)，協(xié)同求解方法的優(yōu)勢逐漸減弱。

3)不管是采用高期核還是線性核，也不管任務(wù)間的偏移程度，用普通方法求解的SVC-SVM與核心集技術(shù)求解的SVC-CVM的分類性能都非常接近。

對高斯漂移數(shù)據(jù)集DS2，按照同樣的實驗流程，求得當(dāng)兩個任務(wù)Task1、 Task2呈現(xiàn)出不同的偏離程度時，各方法的分類性能。每個方法對各訓(xùn)練集共計10次運(yùn)行后的平均分類精度及標(biāo)準(zhǔn)差記錄在表3及表4中。

由表3及表4可以得到如下觀察：

1)在高斯漂移數(shù)據(jù)集DS2上，不管是采用高斯核還是線性核，協(xié)同求解多個概念漂移問題的SVC-SVM、SVC-CVM方法總是優(yōu)于獨立求解單個概念漂移問題的TA-SVM方法及ITA-SVM方法，與數(shù)據(jù)集DS1上的實驗結(jié)果相似。

2)采用高期核或線性核時，不管任務(wù)間的偏移程度，SVC-CVM與SVC-SVM方法的分類性能是相當(dāng)?shù)摹?/p>

圖1 旋轉(zhuǎn)超平面數(shù)據(jù)集DS1上各概念漂移數(shù)據(jù)之間偏移角度變化時的分類性能Fig. 1 Classification accuracies on DS1 with different diversities of data stream

表 3 數(shù)據(jù)集DS2上采用高斯核時各方法的平均分類精度Table 3 Classification accuracies on dataset DS2 with Gaussian kernel

表 4 數(shù)據(jù)集DS2上采用線性核時各方法的平均分類精度Table 4 Classification accuracies on dataset DS2 with Linear kernel

下面繼續(xù)評估SVC-CVM方法在噪音數(shù)據(jù)集DS3和DS4上的表現(xiàn)，以觀察本文方法的抗噪能力。與文獻(xiàn)[13]的實驗設(shè)置相同，通過將DS1和DS2上的類別標(biāo)簽隨機(jī)變換來模擬噪音數(shù)據(jù)，噪音比例分別為2%～10%。在數(shù)據(jù)集DS3和DS4上，當(dāng)含有不同噪音時各方法的實驗結(jié)果記錄在表5到表6中。

由表5及表6可知：

1) 在噪音數(shù)據(jù)集DS3及DS4上，不管采用高斯核或是線性核時，SVC-SVM和SVC-CVM方法相對于獨立求解的TA-SVM方法及ITA-SVM方法，都有較大的優(yōu)勢。

表 5 數(shù)據(jù)集DS3上各方法在不同噪音下的平均分類精度Table 5 Classification accuracies on dataset DS3 with Different kernel

表 6 數(shù)據(jù)集DS4上各方法在不同噪音下的平均分類精度Table 6 Classification accuracies on dataset DS4 with Different kernel

2) SVC-CVM與SVC-SVM方法在噪音情況下的分類性能是相當(dāng)?shù)摹?/p>

3.3 SVC-CVM方法的時間性能

本子節(jié)將以數(shù)據(jù)集DS5、DS6為基礎(chǔ)來評估各方法的算法時間效率。各數(shù)據(jù)集的樣本量從500緩慢增加到30 000個。對于數(shù)據(jù)集DS5，獨立生成10組訓(xùn)練集及測試集，并將各方法在取不同容量樣本時的平均準(zhǔn)確率及平均訓(xùn)練時間顯示在圖2中。隨著數(shù)據(jù)量增加時，為了能更準(zhǔn)確地觀察各方法時間性能的量級，本文分別以(為樣本量)為橫坐標(biāo)，以(S為運(yùn)行時間，單位為s)為縱坐標(biāo)描述各方法的時間性能圖，將始的指數(shù)曲線轉(zhuǎn)化為線性曲線，斜率代表運(yùn)行時間的指數(shù)量級，如圖2(b)所示。

由圖2可以得到如下觀察：

圖2(a)可知，在數(shù)據(jù)集合DS5上，隨著訓(xùn)練數(shù)據(jù)量的加大，各方法的泛化性能穩(wěn)定增加。同時SVC-SVM和SVC-CVM方法優(yōu)于獨立求解單個概念漂移問題的TA-SVM和ITA-SVM方法。由于用普通SVM方法求解時需要先求解相應(yīng)方法的核矩陣，因此受硬件約束較大，當(dāng)數(shù)據(jù)量較大時，相應(yīng)方法無法繼續(xù)求解。而SVC-CVM方法采用核心集技術(shù)求解，相應(yīng)的支持向量逐個添加到核心集中，不需要預(yù)先計算核矩陣，因而能處理更大容量的數(shù)據(jù)，得到泛化能力更強(qiáng)的模型。

圖2(b)可知，在數(shù)據(jù)集DS5上，求解各方法所需時間與數(shù)據(jù)量之間呈現(xiàn)穩(wěn)定的指數(shù)級關(guān)系，其中SVC-CVM方法所表示的準(zhǔn)直線的斜率明顯小于其他方法，顯示了SVC-CVM方法在時間效率上遠(yuǎn)優(yōu)于TA-SVM、ITA-SVM與SVC-SVM方法。

圖2 各方法在數(shù)據(jù)集DS5上的性能Fig. 2 Performance on DS5

在數(shù)據(jù)集DS6上，按相同的流程進(jìn)行訓(xùn)練及測試，并將各方法在不同容量樣本上的平均準(zhǔn)確率和標(biāo)準(zhǔn)差、平均訓(xùn)練時間和標(biāo)準(zhǔn)差分別記錄在表7及表8中(其中—表示在本文實驗環(huán)境中無法得到相應(yīng)結(jié)果)。

由表7及表8可以得到如下觀察：

表 7 在數(shù)據(jù)集DS6上當(dāng)不同數(shù)據(jù)量情況下各方法的平均分類準(zhǔn)確率及標(biāo)準(zhǔn)差Table 7 Classification accuracies with different dataset size of DS6 %

表 8 在數(shù)據(jù)集DS6上當(dāng)不同數(shù)據(jù)量情況下各方法的平均訓(xùn)練時間及標(biāo)準(zhǔn)差Table 8 Training time with different dataset size of DS6 s

1) 從表7中可以看出，在數(shù)據(jù)集DS6上，隨著訓(xùn)練數(shù)據(jù)量的增加，各方法的分類性能逐漸增高，其中SVC-SVM和SVC-CVM的分類性能相當(dāng)，都優(yōu)于獨立求解單個概念漂移問題的TA-SVM與ITA-SVM方法。

2) 從表8可以看出，在數(shù)據(jù)集DS6上，當(dāng)數(shù)據(jù)量較小時，SVC-CVM方法的求解時間上并不具有優(yōu)勢。當(dāng)數(shù)據(jù)量的逐漸增加時，SVC-CVM方法求解時間的變化很緩慢，明顯優(yōu)于用普通二次規(guī)劃方式進(jìn)行求解。

在數(shù)據(jù)集DS5和DS6上的實驗可知，當(dāng)數(shù)據(jù)量不大時，SVC-SVM方法和SVC-CVM方法都優(yōu)于獨立求解的方法，且兩者的分類性能相當(dāng)。當(dāng)數(shù)據(jù)量很大時，只有SVC-CVM方法能處理較大規(guī)模數(shù)據(jù)集，且在算法時間性能上保持近線性時間復(fù)雜度，因而具有較強(qiáng)的實用性。

4 結(jié)束語

本文提出了適用于對概念漂移大規(guī)模數(shù)據(jù)集快速求解的多任務(wù)核心向量機(jī)方法SVC-CVM。由于采用共享矢量鏈技術(shù)協(xié)同求解多個概念漂移問題，SVC-CVM方法在分類精度上等價于SVCSVM方法，明顯優(yōu)于獨立求解單個概念漂移問題的TA-SVM及ITA-SVM方法，且SVC-CVM算法在面對多個概念漂移大數(shù)集時仍然能夠進(jìn)行快速建模決策。當(dāng)然SVC-CVM方法仍需要進(jìn)一步研究，特別是多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集的回歸問題；多任務(wù)概念漂移大規(guī)模數(shù)據(jù)集的單類問題，將是更有意義的挑戰(zhàn)。