面向概念漂移問題的漸進(jìn)多核學(xué)習(xí)方法

白東穎 易亞星 王慶超 余志勇

摘 要：針對概念漂移問題，構(gòu)建數(shù)據(jù)特性隨時間發(fā)生漸進(jìn)變化特點的分類學(xué)習(xí)模型，提出一種基于漸進(jìn)支持向量機(jī)（G-SVM）的漸進(jìn)多核學(xué)習(xí)方法（G-MKL）。該方法采用支持向量機(jī)（SVM）為基本分類器，進(jìn)行多區(qū)間上的子分類器耦合訓(xùn)練，并通過約束子分類器增量方式使模型適應(yīng)數(shù)據(jù)漸進(jìn)變化特性，最終將多個核函數(shù)以線性組合方式融入SVM求解框架。該方法綜合發(fā)揮了各個核函數(shù)的優(yōu)勢，大大提高了模型適應(yīng)性和有效性。最后在具有漸變特性的模擬數(shù)據(jù)集和真實數(shù)據(jù)集上將所提算法與多種經(jīng)典算法進(jìn)行了對比，驗證了所提算法在處理非靜態(tài)數(shù)據(jù)問題的有效性。

關(guān)鍵詞：概念漂移;支持向量機(jī);多核學(xué)習(xí);子分類器;KKT條件

中圖分類號：TP311

文獻(xiàn)標(biāo)志碼：A

Gradual multi-kernel learning method for concept drift

BAI Dongying1，2， YI Yaxing1*， WANG Qingchao1， YU Zhiyong1

1.Institute of Combat and Support. Xian Institute of High-Tech， Xian Shaanxi 710025， China;

2.Institute of Air and Missile Defense， Air Force Engineering University， Xian Shaanxi 710051， China

Abstract：

Aiming at the concept drift problem， a classification learning model with the characteristics of data changing progressively over time was constructed， and a Gradual Multiple Kenerl Learning method （G-MKL） based on Gradual Support Vector Machine （G-SVM） was proposed. In this method， with Support Vector Machine （SVM） used as the basic classifier， multi-interval sub-classifier coupling training was carried out and the incremental method of constraining sub-classifier was used to adapt the model to the gradual change of data. Finally， multiple kernels were integrated into SVM solution framework in a linear combination manner. This method integrated the advantages of different kernel functions and greatly improved the adaptability and validity of the model. Finally， the comparison experiments between the proposed algorithm and several classical algorithms were carried out on the simulated and real datasets with gradual characteristics， verifying the effectiveness of the proposed algorithm in dealing with non-stationary data problems.

Key words：

concept drift; Support Vector Machine （SVM）; multi-kernel learning; sub-classifier; Karush-Kuhn-Tucher （KKT） condition

0 引言

概念漂移問題[1-3]大致可以分為兩類：一種是數(shù)據(jù)的某種特征或分布方式發(fā)生突然變化從而導(dǎo)致數(shù)據(jù)分類模型的突然變化問題;另一種則是數(shù)據(jù)分布發(fā)生著逐漸而又緩慢的變化[4]，本文的研究內(nèi)容為漸變性的概念漂移問題。

對漸變數(shù)據(jù)進(jìn)行分類的重點在于分類模型不僅要在每一特定時間內(nèi)對現(xiàn)有數(shù)據(jù)達(dá)到最優(yōu)，而且要使得分類模型能夠平穩(wěn)遞進(jìn)地變化。這是由于數(shù)據(jù)分布的稀疏性決定的，在較短的時間片段內(nèi)獲取的少量數(shù)據(jù)通常不足以建立可靠的模型，反而非常容易使得模型過擬合，因此需要合理利用時間相近的數(shù)據(jù)為當(dāng)前時刻構(gòu)建分類模型[5-6]。

Grinblat等[7]提出時間自適應(yīng)支持向量機(jī)（Time Adaptive Support Vector Machine， TA-SVM），將數(shù)據(jù)按照時間順序劃分為若干區(qū)間，并在不同區(qū)間上求解子分類器;其最大的特點在于子分類器間的耦合，即不僅要使子分類器在相應(yīng)區(qū)間內(nèi)盡量達(dá)到最優(yōu)，而且將相鄰子分類器間的變化在目標(biāo)函數(shù)中進(jìn)行了約束，從而使得分類器能夠較好地平衡分類模型在不同時間區(qū)間的全局優(yōu)化和局部優(yōu)化。

雖然TA-SVM方法可以通過子分類器耦合的方式處理漸變式的概念漂移問題，然而其求解過程并不簡單，并且其中涉及到求矩陣的逆和偽逆等問題。Shi等[8]在TA-SVM的基礎(chǔ)上提出改進(jìn)的時間自適應(yīng)支持向量機(jī)（Improved TA-SVM， ITA-SVM），使用增量的概念表示相鄰分類器間的變化，將基礎(chǔ)分類器與增量序列結(jié)合構(gòu)成各個子分類器。雖然ITA-SVM解決了TA-SVM難以求解的問題，但是ITA-SVM本質(zhì)是一種核心向量機(jī)模型，雖然易于優(yōu)化，但是在有效性上與支持向量機(jī)有一定差距。

為此本文提出了基于漸進(jìn)支持向量機(jī)（Gradual Support Vector Machine，G-SVM）的漸進(jìn)多核學(xué)習(xí)方法（Gradual Multiple Kernel Learning， G-MKL），以支持向量機(jī)為基本分類器，通過子分類器耦合的方式處理漸變式的概念漂移問題，通過分類器增量的方式使得模型適應(yīng)數(shù)據(jù)特性的漸進(jìn)變化，通過將分類器學(xué)習(xí)和多核自適應(yīng)優(yōu)化置于統(tǒng)一的優(yōu)化框架，在一組基核上充分發(fā)揮各個核的優(yōu)勢，得出最優(yōu)的組合方式，進(jìn)一步提高模型的適應(yīng)性和有效性。

根據(jù)上述推導(dǎo)過程，多核漸進(jìn)支持向量機(jī)模型（G-MKL）訓(xùn)練階段的計算流程可描述為：

步驟1 將按照時間排序的樣本序列{x1，x2，…，xN}劃分為L個子區(qū)間。

步驟2 計算核矩陣K和樣本間關(guān)系矩陣G。

步驟3 初始化核權(quán)值θm=1/m，m。

步驟4 使用序列最小化（Sequential Minimal Optimization， SMO）算法解式（13）所示的QP問題。

步驟5 使用式（24）更新核權(quán)重。

步驟6 判斷是否滿足迭代停止條件，若滿足，則訓(xùn)練結(jié)束;若不滿足，重復(fù)步驟4～6，直到滿足停止條件。

2 實驗與結(jié)果分析

為評估本文所提多核漸進(jìn)支持向量機(jī)模型的有效性和可行性，通過實驗的方式進(jìn)行比較分析。實驗選擇ITA-SVM[8]，TA-SVM[10]和G-SVM算法作為基準(zhǔn)算法進(jìn)行對比。實驗使用Matlab 2012a作為編程環(huán)境，使用SMO算法解SVM。本章的實驗內(nèi)容安排如下：首先在使用人工數(shù)據(jù)集模擬數(shù)據(jù)分布模型隨時間逐漸變化的情況，在模擬數(shù)據(jù)集上分析算法跟隨數(shù)據(jù)變化的能力，然后在真實數(shù)據(jù)集上進(jìn)行對比分析。

2.1 模擬數(shù)據(jù)集實驗與結(jié)果分析

為驗證本文所提出漸進(jìn)支持向量機(jī)和漸進(jìn)多核學(xué)習(xí)方法在概念漂移問題處理上的有效性，按照和文獻(xiàn)[8，10]相同的方法構(gòu)造了兩個人工數(shù)據(jù)集，以模擬現(xiàn)實世界中數(shù)據(jù)分布模型隨時間變化的情形。兩個數(shù)據(jù)集分別命名為Sliding和Rotating。

數(shù)據(jù)集Sliding是一個兩分類數(shù)據(jù)集，數(shù)據(jù)包含兩個維度。兩個類別的樣本都服從高斯分布，并沿著一個二維空間上的正弦函數(shù)緩慢漂移，樣本點根據(jù)式（28）生成：

xi=2πin-π+0.2yi+ε1，sin2πin-π+0.2yi+ε2（28）

其中i=1，2，…，N（N為樣本數(shù)量）;ε1和ε2都取自于均值為0，方差為0.1的正態(tài)分布;yi∈{-1，+1}為樣本xi的標(biāo)簽。圖1所示為數(shù)據(jù)集Sliding在時刻t（i∈[1，t]）分別為25，175，325，475時樣本分布情況。其中t時刻最近產(chǎn)生的25個樣本使用實心點標(biāo)記。

Sliding的兩類樣本在每一較短的時間段內(nèi)基本上是可分的。但是隨著時間的變化，兩類樣本沿著正弦曲線不斷漂移，從整體上看兩類樣本混淆在一起難以分辨。由于這個數(shù)據(jù)集具有如此特點，因此也常用來模擬概念漂移問題驗證算法對于非靜態(tài)數(shù)據(jù)處理的能力。

數(shù)據(jù)集Rotating是一個旋轉(zhuǎn)數(shù)據(jù)集，模擬的是正負(fù)兩類樣本的分界面以原點為中心，沿逆時針旋轉(zhuǎn)的情況下的數(shù)據(jù)分布。兩類樣本的分界面法向量定義為v，v的變化情況可以用式（29）表示：

v1（t）=cos（2πt/n）10

v2（t）=sin（2πt/n）

v3，4，…，d（t）=0（29）

樣本xi的每一維度均服從[-1，1]上的均勻分布，其所屬類別為yi=sign（xiv（ti））。在實際實驗中每一時刻只生成一個樣本點，與文獻(xiàn)[8]相同。

按照上面描述的數(shù)據(jù)產(chǎn)生方式，分別為兩個數(shù)據(jù)集生成數(shù)據(jù)。按照相同的方式分別產(chǎn)生三組數(shù)據(jù)，其中第一組為訓(xùn)練集，用于模型訓(xùn)練;第二組為校驗集，用于參數(shù)選擇;第三組為測試集，用于評估算法。為了能更加深入地評估漸進(jìn)支持

向量機(jī)和漸進(jìn)多核學(xué)習(xí)算法的優(yōu)劣，實驗共分兩步。首先在

校驗集上訓(xùn)練模型以檢驗?zāi)Ｐ椭行略鰠?shù)對算法的性能的影響，然后使用優(yōu)化后的參數(shù)訓(xùn)練分類模型，使用訓(xùn)練好的決策函數(shù)在測試集上對算法的性能進(jìn)行對比分析。

懲罰因子C∈{0.1，1，10，100，1000}，通過交叉驗證的方式選擇最優(yōu)參數(shù)C。單核支持向量機(jī)模型分別使用線性核和高斯核，高斯核寬度通過交叉驗證的方式從{0.01，0.1，1，5，10，20，50，100}選擇最優(yōu)值，多核方法G-MKL同時使用線性核，一階多項式核以及高斯核進(jìn)行訓(xùn)練，高斯核的寬度σ∈{0.01，0.1，1，5，10，20，50，100}，因此共計10個核。

在本節(jié)實驗中將本文算法與TA-SVM、ITA-SVM、G-SVM在兩個數(shù)據(jù)集上進(jìn)行對比以評估本文G-MKL的分類效果。因數(shù)據(jù)生成得較為稀疏，故具有較大的隨機(jī)性，需要多次實驗取平均值。實驗過程參照文獻(xiàn)[15]的方式進(jìn)行，首先按照式（24）和式（25）的模型分別生成訓(xùn)練集、校驗集以及測試集各100組。將訓(xùn)練集分為L個數(shù)據(jù)子集，使用訓(xùn)練集和校驗集選擇該數(shù)據(jù)集上最優(yōu)的C，λ和σ。在訓(xùn)練集上訓(xùn)練模型，在測試集上驗證模型，重復(fù)100次實驗取平均值。表1分別記錄了不同算法在Sliding數(shù)據(jù)集和Rotating數(shù)據(jù)集上的平均分類準(zhǔn)確率和標(biāo)準(zhǔn)差。

根據(jù)表1可以看出無論使用線性核還是使用高斯核，G-SVM算法的分類準(zhǔn)確率均高于TA-SVM和ITA-SVM算法，體現(xiàn)了它在數(shù)據(jù)分布模型發(fā)生變化時可以更好地擬合數(shù)據(jù)，通過全局優(yōu)化和局部優(yōu)化方式學(xué)習(xí)到良好的分類分界線;而其多核方式G-MKL則在分類準(zhǔn)確率上有進(jìn)一步的提高，體現(xiàn)了本文多核學(xué)習(xí)方法在優(yōu)化多核上的優(yōu)勢。

2.2 真實數(shù)據(jù)集實驗與結(jié)果分析

1）Spam_corpus數(shù)據(jù)集

Spam_corpus數(shù)據(jù)集為垃圾郵件數(shù)據(jù)集，記錄了大約為期18個月發(fā)送給指定地址的郵件語料，包含9324個樣本。在Spam_corpus數(shù)據(jù)集中，隨著時間推移垃圾郵件的語料特征也隨之逐漸變化，因此該數(shù)據(jù)集是一個常用于檢驗概念漂移問題的數(shù)據(jù)集。實驗方式與文獻(xiàn)[8]相同，按照時間關(guān)系將數(shù)據(jù)等分為36組，每組包含259個樣本。每組樣本中隨機(jī)選取一半作為訓(xùn)練集，另外一半作為測試集，在訓(xùn)練集上通過交叉驗證的選擇各方法的模型參數(shù)。使用訓(xùn)練好的模型在測試集上進(jìn)行測試，實驗結(jié)果如表2和表3所示。

從表3可以看出ITA-SVM算法在所有月份中共有5次達(dá)到最佳，G-SVM和本文所提的G-MKL則分別有5次和8次達(dá)到最佳，總體來看四種算法的預(yù)測準(zhǔn)確率相差不是特別大。

表3記錄了在所有月份的平均預(yù)測錯誤率。從表中可以看出，TA-SVM算法錯誤率略高于其他三種算法，ITA-SVM在預(yù)測錯誤率上較之略有降低，本文的多核學(xué)習(xí)方法G-MKL表現(xiàn)最優(yōu)，通常情況下錯誤率低于其他三種算法，體現(xiàn)了多核組合學(xué)習(xí)的優(yōu)勢。

3 結(jié)語

本文研究了非靜態(tài)數(shù)據(jù)的分類問題，提出了漸進(jìn)多核學(xué)習(xí)方法。通過將數(shù)據(jù)劃分為若干子數(shù)據(jù)集，在約束子分類器間的變化的同時優(yōu)化各子分類器，實現(xiàn)分類模型隨數(shù)據(jù)分布逐漸變化，使用多個核函數(shù)進(jìn)行數(shù)據(jù)度量，并將多核線性組合的方式求解融入支持向量機(jī)求解框架，充分發(fā)揮各個核函數(shù)的優(yōu)勢。在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗結(jié)果驗證了本文提出的算法在處理概念漂移問題時的有效性。

參考文獻(xiàn)

[1]LIOBAITE I， PECHENIZKIY M， GAMA J. An overview of concept drift applications[M]// JAPKOWICZ N， STEFANOWSKI J. Big Data Analysis： New Algorithms for a New Society， SBD 16. Berlin： Springer， 2016： 91-114.

[2]孫宇.針對含有概念漂移問題的增量學(xué)習(xí)算法研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2017：12-18.（SUN Y. Research on incremental learning algorithms for conceptual drift problem [D]. Hefei： University of Science and Technology of China， 2017： 12-18）.

[3]HEWAHI N M， KOHAIL S N. Learning concept drift using adaptive training set formation strategy [J]. International Journal of Technology Diffusion， 2013， 4（1）：33-55.

[4]ALIPPI C， BORACCHI G， ROVERI M. An effective just-in-time adaptive classifier for gradual concept drifts[C] // Proceedings of the 2011 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2011： 1675-1682.

[5]史熒中.耦合的支持向量學(xué)習(xí)方法及應(yīng)用研究[D].無錫：江南大學(xué)，2016：89-106.（SHI Y Z. Study on coupled supported vector method and its application [D]. Wuxi： Jiangnan University， 2016： 89-106.）

[6]PALIVELA H， KUBAL D， NIRMALA C R. Multiple kernel learning techniques for ligand based virtual screening [C]// Proceedings of the 2017 International Conference on Computer Communication and Informatics. Piscataway， NJ： IEEE， 2017： 1-6.

[7]GRINBLAT G L， UZAL L C， CECCATTO H A， et al. Solving nonstationary classification problems with coupled support vector machines [J]. IEEE Transactions on Neural Networks， 2011， 22（1）： 37-51.

[8]SHI Y， CHUNG F， WANG S. An improved TA-SVM method without matrix inversion and its fast implementation for nonstationary datasets [J]. IEEE Transactions on Neural Networks and Learning Systems， 2015， 26（9）： 2005-2018.

[9]汪洪橋，孫富春，蔡艷寧，等.多核學(xué)習(xí)方法[J].自動化學(xué)報，2010，36（8）：1037-1050.（WANG H Q， SUN F C， CAI Y N， et al. On multiple kernel learning methods [J]. Acta Automatica Sinica， 2010， 36（8）： 1037-1050.）

[10]GNEN M， ALPAYDIN E. Multiple kernel learning algorithms [J]. Journal of Machine Learning Research， 2011， 12： 2211-2268.

GNEN M， ALPAYDIN E. Multiple kernel learning algorithms [EB/OL]. [2018-12-21]. http：//delivery.acm.org/10.1145/2030000/2021071/p2211-gonen.pdf？ip=171.221.175.194&id=2021071&acc=OPEN&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&__acm__=1562746429_892bd32fdc36440e5615efc0f82c56b2.

[11]MANOGARAN G， VARATHARAJAN R， PRIYAN M K. Hybrid recommendation system for heart disease diagnosis based on multiple kernel learning with adaptive neuro-fuzzy inference system [J]. Multimedia Tools and Applications， 2018， 77（4）： 4379-4399.

[12]MARCINIAK M， AREVALO H， TFELT-HANSEN J， et al. A multiple kernel learning framework to investigate the relationship between ventricular fibrillation and first myocardial infarction [C]// Proceedings of the 2017 International Conference on Functional Imaging and Modeling of the Heart， LNCS 10263. Berlin： Springer， 2017： 161-171.

[13]LIU T， JIN X， GU Y. Sparse multiple kernel learning for hyperspectral image classification using spatial-spectral features [C]// Proceedings of the 6th International Conference on Instrumentation and Measurement， Computer， Communication and Control. Piscataway， NJ： IEEE， 2016： 614-618.

[14]VAPNIK V N. The Nature of Statistical Learning Theory[M]. New York： Springer， 1995： 24-30.

[15]HAN Y， YANG K， YANG Y， et al. Localized multiple kernel learning with dynamical clustering and matrix regularization [J]. IEEE Transactions on Neural Networks and Learning Systems， 2018， 29（6）： 486-499.

This work is partially supported by the National Natural Science Foundation of China for Young Scholars （61806219）.

BAI Dongying， born in 1982， M. S.， lecturer. Her research interests include intelligent information processing， integrated command and control.

YI Yaxing， born in 1966， Ph. D.， professor. His research interests include system modeling and simulation.

WANG Qingchao， born in 1988， Ph. D.， lecturer. His research interests include remote sensing image analysis.

YU Zhiyong， born in 1972， Ph. D.， professor. His research interests include electromagnetic compatibility.