面向大規模類不平衡數據的變分高斯過程分類算法

馬 　 彪，　周 　 瑜，　賀 建 軍*,

( 1.大連民族大學 信息與通信工程學院， 遼寧 大連　116600；2.大連理工大學 電子信息與電氣工程學部， 遼寧 大連　116024 )

?

面向大規模類不平衡數據的變分高斯過程分類算法

馬 彪1，周 瑜2，賀 建 軍*1,2

( 1.大連民族大學 信息與通信工程學院， 遼寧 大連116600；2.大連理工大學 電子信息與電氣工程學部， 遼寧 大連116024 )

摘要：變分高斯過程分類器是最近提出的一種較有效的面向大規模數據的快速核分類算法，其在處理類不平衡問題時，對少數類樣本的預測精度通常會較低．針對此問題，通過在似然函數中引入指數權重系數和構造包含相同數目正負類樣本的誘導子集解決原始算法的分類面向少數類偏移的問題，建立了一種可以有效處理大規模類不平衡問題的改進變分高斯過程分類算法．在10個大規模UCI數據集上的實驗結果表明，改進算法在類不平衡問題上的精度較原始算法得到大幅提高．

關鍵詞：類不平衡問題；高斯過程；變分推理；大規模數據分類

0引言

高斯過程模型具有完全的貝葉斯公式化表示、可自適應地獲得模型參數、易實現等優點，是繼支持向量機之后又一種受到人們廣泛關注的核機器學習方法，被廣泛地用于回歸[1]、分類[2]、聚類[3]、關系學習[4]、強化學習[5]、多示例多標記學習[6]等各種機器學習問題中．在處理分類問題時，定義的似然函數通常是一個S形函數, 因此并不能直接得到潛變量函數的后驗概率的分析表達式．為此，人們嘗試利用各種方法來得到后驗概率的近似表達式，如Laplace(LA)方法[2]、expectation propagation(EP)方法[7]、Kullback-Leibler(KL)散度最小化方法[8]、variational bounding(VB)方法[9]、mean field方法[10]等，雖然通過不斷改進，目前已經能取得較高的預測精度，但是由于相關算法的計算復雜度通常是O(n3)(其中n為樣本數目)，只能處理數據規模比較小的問題．為了降低算法的計算復雜度，人們提出了構建稀疏模型的問題解決策略，代表性的算法有IVM[11]、FIFC[12]和KLSP[13]，它們的計算復雜度為O(nm2)，其中m為選擇的誘導變量的個數，通常m的取值達到數百時算法就可以取得較好的效果．

IVM、FIFC和KLSP等這些面向大規模數據的高斯過程分類算法，在模型構建時很少考慮數據的類不平衡性對算法性能的影響，因此當處理正負樣本比例比較懸殊的問題時，對少數類樣本的預測精度通常都很低[14]．針對以上問題，本文嘗試建立一種面向大規模類不平衡問題的高斯過程分類算法．KLSP是一種基于變分原理建立的算法，與其他兩種算法相比，它不僅具有較高的精度，而且還具有避免過擬合、可以用分布式或者隨機優化的方法對模型進行求解等優點．通過分析KLSP算法發現，造成對少數類樣本預測精度比較低的主要原因在似然函數定義和誘導集合選擇這兩個環節，因此本文將通過改進KLSP算法的這兩個環節來建立可以有效處理大規模類不平衡問題的高斯過程分類算法．

1類不平衡變分高斯過程模型的基本思想與主要模塊

設X為樣本的特征空間，S={(x1,y1),(x2,y2),…,(xn,yn)}為包含n個樣本的訓練集，其中xi∈X和yi∈{+1,-1}分別是第i個樣本的特征向量和類別標記．為便于描述，下面將用D={x1,x2,…,xn}和Y=(y1y2…yn)\%T\%分別表示S中所有訓練樣本的特征向量構成的集合和類別標記構成的向量．構建分類算法實質上就是利用訓練集在特征空間中建立一個能正確輸出待預測樣本x*的真實標記的函數f(x)．傳統高斯過程二分類模型的基本思想是在服從某個高斯過程分布的潛變量函數簇中尋找最有可能輸出待預測樣本x*的真實標記的函數，要實現該目的通常包括定義潛變量函數的先驗概率、定義似然函數、計算潛變量函數的后驗概率和計算預測概率4個核心模塊．變分高斯過程模型與傳統高斯過程模型一樣，也包括這4個模塊，二者主要的不同在后驗概率的計算上．傳統高斯過程模型是利用潛變量函數的先驗概率和似然函數推導其后驗概率的；而變分高斯過程模型是利用一組中間誘導變量來計算潛變量函數的后驗概率分布的，這樣可以有效降低算法的計算復雜度．

1.1定義先驗概率

假設潛變量函數f(x)服從如下零均值高斯過程分布：

f(x)～GP(0,k(x,x′))

(1)

其中k(x,x′)表示協方差函數，本文將采用如下的協方差函數：

(2)

假設U?D是選取的用于生成誘導變量的訓練樣本子集，x*∈X為待預測樣本，則可以根據式(1)得到f(x)在D、U和x*上的函數值FD、FU和f*的如下先驗概率分布和條件先驗概率分布：

(3)

式中：FD是f(x)在樣本集D上的函數值構成的列向量，即FD=(f1f2…fn)T，fi=f(xi)；KD是協方差函數k(x,x′)在D上的值構成的矩陣，第i行第j列上的元素是k(xi,xj)；FU是f(x) 在誘導集U上的函數值構成的列向量；KU是協方差函數k(x,x′)在U上的值構成的矩陣；KDU表示D和U中樣本之間的協方差函數值構成的矩陣；f*表示f(x)在待預測樣本x*上的值，即f*=f(x*)；K*U表示x*和U中樣本之間的協方差函數值構成的行向量；K**=k(x*,x*)．

1.2定義似然函數

與傳統高斯過程分類模型一樣，f(x)在xi上的值fi的似然函數p(yi|fi)可以定義為

(4)

對于各個類別樣本數據比較均衡的問題，聯合似然函數p(Y|FD)可以定義為所有p(yi|fi)(i=1,2,…,n)的乘積．但是對于類不平衡問題，這樣的定義意味著錯分一個少數類樣本的代價與錯分一個多數類樣本的代價一樣，從而使得算法的分類面偏向少數類一側．本文將在聯合似然函數中的正負類樣本對應的似然函數上引入不同的權重系數，使得錯分少數類樣本的代價大于錯分多數類樣本的代價，最終實現改善少數類樣本預測精度的目的．聯合似然函數的具體定義如下：

(5)

其中權重系數ri的取值為

n+和n-分別表示訓練集中正負樣本的個數．從式(5)可以看出，少數類樣本對應的權重系數要大于1，而多數類樣本對應的權重系數要小于1，兩類樣本數目越懸殊，權重的差距也越大，由于所有正(負)類樣本的權重系數之和是n/2，這在一定程度上保證了聯合似然函數中正負類樣本在整體上具有一樣的話語權，因此可以避免分類面的偏移．

1.3計算后驗概率

p(FD|D,Y)=∫p(FD|FU,D)p(FU|D,Y)dFU≈

∫p(FD|FU,D)q(FU)dFU

(6)

其中q(FU)=N(FU|μ,Σ)是p(FU|D,Y)的一個高斯逼近，參數μ、Σ可以通過最大化邊緣似然函數p(Y|D) 的如下下界得到：

logp(Y|D)≥∫logp(Y|FD)q(FD)dFD-

KL(q(FU)‖p(FU|D))?Ψ(μ,Σ)

(7)

(8)

(9)

(10)

1.4計算預測概率

在得到后驗概率p(FU|D,Y)的近似表達式以后,可以得到f*的后驗概率分布：

p(f*|D,Y,x*)=∫p(f*|FU,D,x*)×

p(FU|D,Y)dFU≈

∫p(f*|FU,D,x*)q(FU)dFU=

(11)

然后可以計算樣本x*是正樣本的概率：

p(f*|D,Y,x*)df*

(12)

1.5誘導子集U的選取

誘導子集U的選取對算法的性能會有一定的影響，但是目前還沒有統一的策略，主要的策略是選取訓練樣本的聚類中心作為誘導子集[16]．為了避免U中各個類別樣本的不均衡導致算法分類面的偏移，本文將利用K均值聚類算法分別從正負類中選取相同數目的樣本來構成U．基本流程如下：假設擬選取m個樣本構成誘導子集U，則先利用K均值聚類算法分別對正負類樣本進行聚類，各生成m/2個聚類中心，然后把這些聚類中心合并構成誘導子集U．為了降低計算復雜度，本文采用Chen[17]實現的一種快速K均值聚類算法來完成U的選取，其中算法的迭代次數設定為150．該算法有時會存在生成的聚類中心數目小于設定的數目的情況，對于這種情況，將隨機從樣本較多的聚類中選取相應數目的樣本來補齊．

2仿真實驗

本章將在10個大規模類不平衡二分類數據集上驗證本文所建算法的性能．這10個數據集全部來自于UCI數據庫[18]，其中，mnist0和mnist9數據集是在原始的mnist多類數據集基礎上分別以手寫數字0和9所在類別為正類、其他類別為負類形成的二分類數據集；covtype3、covtype4和covtype7數據集是分別以原始的covtype多類數據集中的第3、4和7類別為正類、其他類別為負類形成的二分類數據集；poker3和poker4數據集是分別以原始的poker多類數據集的第3、4類別為正類、其他類別為負類形成的二分類數據集；關于這些數據集的詳細信息見表1．本文的主要創新在于對文獻[13]提出的變分高斯過程算法(KLSP算法)進行了改進，使其可以有效處理類不平衡問題，因此下面將主要對本文所建算法(簡稱IMKLSP)和KLSP算法進行對比、分析．兩個算法都采用式(2)所示的協方差函數，并且利用有限儲存擬牛頓方法[15]進行求解，其中，協方差函數的參數α和β的取值是分別在集合{10-6,10-5,…,105}和{3-4du,3-3du,…,36du}(du為誘導子集與訓練集的樣本之間的平均距離)中通過交叉驗證法選取確定的，有限儲存擬牛頓方法的存儲長度M的取值為10，算法迭代次數L的取值為20．以下所有實驗結果都是通過隨機選取1/2 的樣本作為訓練數據，1/2的樣本作為測試數據，然后重復進行5次實驗得到的平均結果．

表1　驗證算法性能所用數據集

本文主要是通過改進KLSP算法的似然函數定義和誘導子集選擇這兩個環節來實現最終的IMKLSP算法的．為了驗證改進這兩個環節的必要性，首先在ijcnn1數據集上對KLSP、IMKLSP、IMKLSP-L和IMKLSP-I 4個算法進行了比較，其中IMKLSP-L表示通過只改變似然函數的定義環節而不改變誘導子集選擇環節所建立的算法，IMKLSP-I表示通過只改變誘導子集選擇環節而不改變似然函數的定義環節所建立的算法．圖1給出了誘導子集的樣本數目m取不同值時，上述4個算法在精度(Ac)、F-測量值(Fmeasure)和G-均值(Gmean)3個不同評價指標上的實驗結果．從圖1可以看出，雖然KLSP算法在精度這個評價指標上取得了與IMKLSP算法相當的結果，但是在另外兩個指標F-測量值和G-均值上的結果

(a) 精度

(b)F-測量值

(c)G-均值

圖1不同誘導子集樣本數目下各個算法在ijcnn1數據集上的實驗結果

Fig.1Theexperimentalresultsofeachalgorithmonijcnn1datasetwhenvaryingthesamplenumberofinducingset

卻遠遠小于IMKLSP算法，這正好說明了KLSP算法不能很好地對類不平衡問題中的少數類樣本做出預測．進一步將IMKLSP-L和IMKLSP-I算法與IMKLSP算法進行對比可以看出，這兩個算法的性能都要比IMKLSP算法差，這表明改進似然函數定義和誘導子集選擇這兩個環節都是必要的．特別的，似然函數定義環節對算法的影響要比誘導子集選擇環節的影響大．此外，從圖1可以看出，只要誘導子集的樣本個數達到100，各個算法就已經能取得較好的預測結果．

表2列出了誘導子集的樣本個數m取200時，KLSP和IMKLSP算法在10個UCI數據集上的預測結果，可以看出，除在skin和mnist0數據集上兩個算法取得了相當的實驗結果外，在其他的8個數據集上，無論是在F-測量值還是G-均值指標上，IMKLSP算法的性能都遠遠優于KLSP算法．而在skin和mnist0數據集上之所以兩個算法的性能相當是因為這兩個樣本集中的正負樣本比例不太懸殊，而且KLSP算法在這兩個數據集上的預測結果本身就比較高，改進的空間比較小．總之，以上實驗結果表明在處理大規模類不平衡問題方面，IMKLSP算法要明顯優于KLSP算法．

表2IMKLSP與KLSP算法在10個大規模類不平衡UCI數據集上的性能對比

Tab.2TheperformancecomparisonofIMKLSPandKLSPalgorithmsontenlarge-scaleclass-imbalancedUCIdatasets

數據集FmeasureGmeanKLSPIMKLSPKLSPIMKLSPmnist00.9730.9640.9810.991mnist90.8270.8460.9060.963w8a0.0710.2780.4780.826ijcnn10.4040.6300.6330.865skin0.9710.9710.9920.992covtype30.5530.5570.8070.907covtype40.0160.3820.5380.866covtype70.2610.3170.5150.902poker30.0870.1510.4020.637poker40.0420.0940.4150.719

3結語

本文基于最近提出的變分高斯過程模型建立了一種可以有效處理大規模類不平衡問題的核分類算法，在10個UCI數據集上的實驗結果表明，該算法可以取得較高的預測精度．本文算法也還有需要改進的地方，其中一個問題就是建立適合該算法的快速聚類算法，在實驗過程中發現同一個實驗重復進行兩次有時會取得不一樣的結果，甚至能相差兩個百分點，通過分析發現，這主要是由誘導子集選取環節中采用的K均值聚類算法造成的，該聚類算法雖然可以進行快速聚類，但是算法的初始聚類中心每次都是隨機給定的，這會導致得到的聚類中心有時會有一定的誤差；此外，考慮到目前基于交叉驗證法選取協方差函數參數的策略不僅效率低而且不能得到最優參數，如何利用模型的邊緣似然函數自動選擇協方差函數參數也是下一步需要考慮的問題．

參考文獻：

[1] Ranganathan A, Yang Ming-hsuan, Ho J. Online sparse Gaussian process regression and its applications [J]. IEEE Transactions on Image Processing, 2011, 20(2):391-404.

[2]Williams C, Barber D. Bayesian classification with Gaussian processes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(12):1342-1351.

[3]Kim Hyun-chul, Lee Jaewook. Clustering based on Gaussian processes [J]. Neural Computation, 2007, 19(11):3088-3107.

[4]Chu W, Sindhwani V, Ghahramani Z,etal. Relational learning with Gaussian processes [J]. Advances in Neural Information Processing Systems, 2007:289-296.

[5]Engel Y, Mannor S, Meir R. Reinforcement learning with Gaussian processes [C] // Proceedings of the 22nd International Conference on Machine Learning. New York:ACM Press, 2005:201-208.

[6]HE Jian-jun, GU Hong, WANG Zhe-long. Bayesian multi-instance multi-label learning using Gaussian process prior [J]. Machine Learning, 2012, 88(1-2):273-295.

[7]Kim Hyun-chul, Ghahramani Z. Bayesian Gaussian process classification with the EM-EP algorithm [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(12):1948-1959.

[8]Opper M, Archambeau C. The variational Gaussian approximation revisited [J]. Neural Computation, 2008, 21(3):786-792.

[9]Gibbs M N, MacKay D J C. Variational Gaussian process classifiers [J]. IEEE Transactions on Neural Networks, 2000, 11(6):1458-1464.

[10]Opper M, Winther O. Mean field methods for classification with Gaussian processes [J]. Advances in Neural Information Processing Systems, 1999:309-315.

[11]Lawrence N, Seeger M, Herbrich R. Fast sparse Gaussian process methods:The informative vector machine [J]. Advances in Neural Information Processing Systems, 2003:609-616.

[12]Naish-Guzman A, Holden S. The generalized FITC approximation [C] // Advances in Neural Information Processing Systems 20-Proceedings of the 2007 Conference. New York:Curran Associates Inc., 2009.

[13]Hensman J, Matthews A G, Ghahramani Z. Scalable variational Gaussian process classification [J]. Journal of Machine Learning Research, 2015, 38:351-360.

[14]Ganganwar V. An overview of classification algorithms for imbalanced datasets [J]. International Journal of Emerging Technology and Advanced Engineering, 2012, 2(4):42-47.

[15]Nocedal J, Wright S J. Numerical Optimization [M]. 2nd ed. New York:Springer, 2006:195-204.

[16]Hensman J, Fusi N, Lawrence N D. Gaussian processes for big data [C] // Uncertainty in Artificial Intelligence-Proceedings of the 29th Conference, UAI 2013. Arlington:AUAI Press, 2013:282-290.

[17]Chen M. Kmeans clustering [CP/OL]. [2013-01-05]. http://www.mathworks.com/matlabcentral/fileexchange/24616-kmeans-clustering.

[18]Bache K, Lichman M. UCI machine learning repository [DB/OL]. [2013-01-05]. http://archive.ics.uci.edu/ml.

Variational Gaussian process classification algorithm for large-scale class-imbalanced data

MABiao1,ZHOUYu2,HEJian-jun*1,2

( 1.College of Information and Communication Engineering, Dalian Nationalities University, Dalian 116600, China；2.Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China )

Abstract：Variational Gaussian process classifier is an effective fast kernel algorithm proposed recently for large-scale data classification. However, for the class-imbalanced problem, it usually achieves lower accuracy on the samples of minority class. By assigning different index weight coefficients to the likelihood functions and constructing an inducing set containing equal numbers of positive and negative samples to avoid hyperplane biased toward the side of minority class, an improved variational Gaussian process classification algorithm is proposed, which can deal with the large-scale class-imbalanced problem effectively. The experimental results of ten large-scale UCI datasets show that the proposed algorithm can achieve much higher accuracy than the original one for class-imbalanced problem.

Key words：class-imbalanced problem; Gaussian process; variational inference; large-scale data classification

中圖分類號：TP391

文獻標識碼：A

doi:10.7511/dllgxb201603009

作者簡介:馬 彪(1962-)，男，工程師，E-mail:mab996@sina.com；賀建軍*(1983-)，男，博士，講師，E-mail:jianjunhe@live.com.

基金項目:國家自然科學基金資助項目(61503058，61374170)；遼寧省自然科學基金資助項目(2015020084，2015020099)；遼寧省教育廳科學技術研究項目(L2014540，L2015127)；中央高校基本科研業務費專項資金資助項目(DC201501055，DC201501060201).

收稿日期：2016-01-05；修回日期: 2016-03-06．

文章編號：1000-8608(2016)03-0279-06