面向概念漂移問題的漸進多核學習方法

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

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

關鍵詞：概念漂移;支持向量機;多核學習;子分類器;KKT條件

中圖分類號：TP311

文獻標志碼：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]大致可以分為兩類：一種是數據的某種特征或分布方式發生突然變化從而導致數據分類模型的突然變化問題;另一種則是數據分布發生著逐漸而又緩慢的變化[4]，本文的研究內容為漸變性的概念漂移問題。

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

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

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

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

根據上述推導過程，多核漸進支持向量機模型（G-MKL）訓練階段的計算流程可描述為：

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

步驟2 計算核矩陣K和樣本間關系矩陣G。

步驟3 初始化核權值θm=1/m，m。

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

步驟5 使用式（24）更新核權重。

步驟6 判斷是否滿足迭代停止條件，若滿足，則訓練結束;若不滿足，重復步驟4～6，直到滿足停止條件。

2 實驗與結果分析

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

2.1 模擬數據集實驗與結果分析

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

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

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

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

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

數據集Rotating是一個旋轉數據集，模擬的是正負兩類樣本的分界面以原點為中心，沿逆時針旋轉的情況下的數據分布。兩類樣本的分界面法向量定義為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））。在實際實驗中每一時刻只生成一個樣本點，與文獻[8]相同。

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

向量機和漸進多核學習算法的優劣，實驗共分兩步。首先在

校驗集上訓練模型以檢驗模型中新增參數對算法的性能的影響，然后使用優化后的參數訓練分類模型，使用訓練好的決策函數在測試集上對算法的性能進行對比分析。

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

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

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

2.2 真實數據集實驗與結果分析

1）Spam_corpus數據集

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

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

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

3 結語

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

參考文獻

[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]孫宇.針對含有概念漂移問題的增量學習算法研究[D].合肥：中國科學技術大學，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]史熒中.耦合的支持向量學習方法及應用研究[D].無錫：江南大學，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]汪洪橋，孫富春，蔡艷寧，等.多核學習方法[J].自動化學報，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.