基于核心向量機的多任務概念漂移數據快速分類

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

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

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

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

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

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

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

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

1 概念漂移問題相關研究

在概念漂移研究方面，傳統的研究是基本滑動窗算法，這是一類局部優化模式。TA-SVM和ITA-SVM方法對局部優化和全局優化進行了權衡，取得了良好的效果。

1.1 單任務概念漂移分類方法

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

1.2 SVC-SVM方法及其對偶

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

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

2 共享矢量鏈核心向量機及快速算法

2.1 共享矢量鏈核心向量機

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

SVC-CVM方法的目標函數為

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

因此有：

式中：

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

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

2.2 核心向量機

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

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

2.3 SVC-CVM的快速算法

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

SVC-CVM算法的輸入為多任務概念漂移大規模數據集S, 核心集逼近精度、、等參數；輸出為核心集和權重系數。下面給出實現步驟：

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

輸入 數據集S, 最小包含球近似精度；

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

3 實驗研究和分析

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

3.1 實驗設置

實驗中涉及的各方法與相應參數在表1中列出。

表 1 實驗所用的對比方法及相應參數Table 1 Methods and parameters used in experiments

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

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

數據集DS1中的第2個任務Task2數據則由Task1模型順時針旋轉一定的角度后隨機生成，以體現出Task2與Task1模型的相關性。

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

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

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

3.2 SVC-SVM的分類性能

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

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

表 2 實驗所用的數據集Table 2 Description of artificial dataset

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

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

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

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

對高斯漂移數據集DS2，按照同樣的實驗流程，求得當兩個任務Task1、 Task2呈現出不同的偏離程度時，各方法的分類性能。每個方法對各訓練集共計10次運行后的平均分類精度及標準差記錄在表3及表4中。

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

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

2)采用高期核或線性核時，不管任務間的偏移程度，SVC-CVM與SVC-SVM方法的分類性能是相當的。

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

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

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

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

由表5及表6可知：

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

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

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

2) SVC-CVM與SVC-SVM方法在噪音情況下的分類性能是相當的。

3.3 SVC-CVM方法的時間性能

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

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

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

圖2(b)可知，在數據集DS5上，求解各方法所需時間與數據量之間呈現穩定的指數級關系，其中SVC-CVM方法所表示的準直線的斜率明顯小于其他方法，顯示了SVC-CVM方法在時間效率上遠優于TA-SVM、ITA-SVM與SVC-SVM方法。

圖2 各方法在數據集DS5上的性能Fig. 2 Performance on DS5

在數據集DS6上，按相同的流程進行訓練及測試，并將各方法在不同容量樣本上的平均準確率和標準差、平均訓練時間和標準差分別記錄在表7及表8中(其中—表示在本文實驗環境中無法得到相應結果)。

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

表 7 在數據集DS6上當不同數據量情況下各方法的平均分類準確率及標準差Table 7 Classification accuracies with different dataset size of DS6 %

表 8 在數據集DS6上當不同數據量情況下各方法的平均訓練時間及標準差Table 8 Training time with different dataset size of DS6 s

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

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

在數據集DS5和DS6上的實驗可知，當數據量不大時，SVC-SVM方法和SVC-CVM方法都優于獨立求解的方法，且兩者的分類性能相當。當數據量很大時，只有SVC-CVM方法能處理較大規模數據集，且在算法時間性能上保持近線性時間復雜度，因而具有較強的實用性。

4 結束語

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