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

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

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

中圖分類號(hào)：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 引言

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

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

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

雖然TA-SVM方法可以通過(guò)子分類器耦合的方式處理漸變式的概念漂移問(wèn)題，然而其求解過(guò)程并不簡(jiǎn)單，并且其中涉及到求矩陣的逆和偽逆等問(wèn)題。Shi等[8]在TA-SVM的基礎(chǔ)上提出改進(jìn)的時(shí)間自適應(yīng)支持向量機(jī)（Improved TA-SVM， ITA-SVM），使用增量的概念表示相鄰分類器間的變化，將基礎(chǔ)分類器與增量序列結(jié)合構(gòu)成各個(gè)子分類器。雖然ITA-SVM解決了TA-SVM難以求解的問(wèn)題，但是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ī)為基本分類器，通過(guò)子分類器耦合的方式處理漸變式的概念漂移問(wèn)題，通過(guò)分類器增量的方式使得模型適應(yīng)數(shù)據(jù)特性的漸進(jìn)變化，通過(guò)將分類器學(xué)習(xí)和多核自適應(yīng)優(yōu)化置于統(tǒng)一的優(yōu)化框架，在一組基核上充分發(fā)揮各個(gè)核的優(yōu)勢(shì)，得出最優(yōu)的組合方式，進(jìn)一步提高模型的適應(yīng)性和有效性。

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

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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)集Sliding是一個(gè)兩分類數(shù)據(jù)集，數(shù)據(jù)包含兩個(gè)維度。兩個(gè)類別的樣本都服從高斯分布，并沿著一個(gè)二維空間上的正弦函數(shù)緩慢漂移，樣本點(diǎn)根據(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在時(shí)刻t（i∈[1，t]）分別為25，175，325，475時(shí)樣本分布情況。其中t時(shí)刻最近產(chǎn)生的25個(gè)樣本使用實(shí)心點(diǎn)標(biāo)記。

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

數(shù)據(jù)集Rotating是一個(gè)旋轉(zhuǎn)數(shù)據(jù)集，模擬的是正負(fù)兩類樣本的分界面以原點(diǎn)為中心，沿逆時(shí)針旋轉(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））。在實(shí)際實(shí)驗(yàn)中每一時(shí)刻只生成一個(gè)樣本點(diǎn)，與文獻(xiàn)[8]相同。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(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]孫宇.針對(duì)含有概念漂移問(wèn)題的增量學(xué)習(xí)算法研究[D].合肥：中國(guó)科學(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].無(wú)錫：江南大學(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].自動(dòng)化學(xué)報(bào)，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.