張 靜，劉忠寶

基于流形判別分析的全局保序?qū)W習(xí)機(jī)

張 靜1，劉忠寶2

(1. 中北大學(xué)軟件學(xué)院 太原 030051; 2. 中北大學(xué)計(jì)算機(jī)與控制工程學(xué)院 太原 030051)

當(dāng)前主流分類方法在分類決策時(shí)無法同時(shí)考慮樣本的全局特征和局部特征，而且大多算法僅關(guān)注各類樣本的可分性，往往忽略樣本之間的相對(duì)關(guān)系。為了解決上述問題，提出了基于流形判別分析的全局保序?qū)W習(xí)機(jī)。該方法引入流形判別分析來反映樣本的全局特征和局部特征；通過保持各類樣本中心的相對(duì)關(guān)系不變進(jìn)而實(shí)現(xiàn)保持全體樣本的先后順序不變；借鑒核心向量機(jī)有關(guān)理論和方法，通過建立所提方法與核心向量機(jī)對(duì)偶形式的等價(jià)關(guān)系實(shí)現(xiàn)大規(guī)模分類。人工數(shù)據(jù)集和標(biāo)準(zhǔn)數(shù)據(jù)集上的比較實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

全局保序; 大規(guī)模分類; 流形判別分析; 支持向量機(jī)

模式分類是數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)習(xí)等領(lǐng)域的研究熱點(diǎn)。當(dāng)前主流的分類方法可歸納為以下幾類：1) 決策樹。ID3算法通過互信息理論建立樹狀分類模型，在ID3基礎(chǔ)上先后提出C4.5[1]、PUBLIC[2]、SLIQ[3]、RainForest[4]等改進(jìn)算法；2) 關(guān)聯(lián)規(guī)則算法主要包括關(guān)聯(lián)分析算法[5]、多維關(guān)聯(lián)規(guī)則算法以及預(yù)測(cè)性關(guān)聯(lián)規(guī)則算法[6]；3) 支持向量機(jī)。支持向量機(jī)(support vector achine, SVM)[7-10]起初于1995年被提出，隨著應(yīng)用的不斷深入，根據(jù)不同的應(yīng)用場(chǎng)合，研究人員先后提出眾多改進(jìn)算法：ν-SVM[11]、單類支持向量機(jī)(one class support vector machine, OCSVM)[12]、支持向量數(shù)據(jù)描述(support vector data description, SVDD)[13]、核心向量機(jī)(core vector machine, CVM)[14]、Lagrangian支持向量機(jī)(Largrangian support vector machine, LSVM)[15]、最小二乘支持向量機(jī)(least squares support vector machine, LSSVM)[16]以及光滑支持向量機(jī)(smooth support vector machine, SSVM)[17]等；4) 貝葉斯分類器包括半樸素貝葉斯分類器(semi-naive Bayesian classifier)、基于屬性刪除的選擇性貝葉斯分類器(selective Bayesian classifier based on atribute deletion)[18]、基于懶惰式貝葉斯規(guī)則的學(xué)習(xí)算法(lazy Bayesian rule learning algorithm，LBR)[19]及樹擴(kuò)張型貝葉斯分類器(tree augmented Bayesian classifier, TAN)[20]等。

上述方法在實(shí)際應(yīng)用中取得良好的分類效果，但它們面臨如下挑戰(zhàn)：1) 在分類決策時(shí)無法同時(shí)考慮樣本的全局特征和局部特征；2) 大多算法僅關(guān)注各類樣本的可分性，而忽略樣本之間的相對(duì)關(guān)系。GRPLM工作原理為，三類樣本在W1方向上的投影順序?yàn)閙1 m2 m3，而在W2方向上的投影順序是m2 m3 m1，假設(shè)原空間三類樣本的相對(duì)關(guān)系為m1 m2 m3，則W1方向優(yōu)于W2方向；3) 無法解決大規(guī)模分類問題。鑒于此，提出基于流形判別分析的全局保序?qū)W習(xí)機(jī)(global rank preservation learning machine based on manifold-based discriminant analysis, GRPLM)。該方法通過引入流形判別分析[21]來保持樣本的全局和局部特征；在最優(yōu)化問題的約束條件中增加樣本中心相對(duì)關(guān)系限制保證分類決策時(shí)考慮樣本的相對(duì)關(guān)系；通過引入核心向量機(jī)(core vector machine, CVM)[14]將所提方法適用范圍擴(kuò)展到大規(guī)模數(shù)據(jù)。

本文后續(xù)做如下假設(shè)：樣本集為T={(x1, y1), (x2,y2),…,(xN,yN)}∈(X×Y)N，其中xi∈X=RN，yi∈Y={1,2,…,c}，類別數(shù)為c，各類樣本數(shù)為Ni(1,2,…,c)，x為所有樣本均值，xi為第i類樣本均值。

1 流形判別分析

文獻(xiàn)[21]提出流形判別分析MDA，流形判別分析引入基于流形的類內(nèi)離散度(manifold-based Within-class scatter, MWCS)WM和基于流形的類間離散度(manifold-based between-class scatter, MBCS)BM兩個(gè)概念，試圖利用Fisher準(zhǔn)則，通過最大化BM和WM之比獲得最佳投影方向。其中，BM和WM的定義如下：

式中，μ和λ為常數(shù)并通過網(wǎng)格搜索策略進(jìn)行選擇；SW和SB分別表示類內(nèi)離散度和類間離散度，其定義同LDA；SS和SD分別表征同類樣本和異類樣本的局部結(jié)構(gòu)，兩者定義如下：

式中，S′為對(duì)角陣且S′=∑jSij，Sij為同類權(quán)重函數(shù)：

MDA的最優(yōu)化問題定義如下：

2 GRPLM

2.1 最優(yōu)化問題

GRPLM利用SVM和MDA分別在智能分類和特征提取方面的優(yōu)勢(shì)，在分類過程中將樣本的全局特征和局部特征以及樣本之間相對(duì)關(guān)系考慮在內(nèi)，在一定程度上提高分類效率。GRPLM找到的分類超平面具有以下優(yōu)勢(shì)：1) 通過引入流形判別分析來保持樣本的全局特征和局部特征；2) 通過最小化基于流形的類內(nèi)離散度，保證同類樣本盡可能緊密；3) 通過保持各類樣本中心的相對(duì)關(guān)系不變進(jìn)而實(shí)現(xiàn)保持全體樣本的先后順序不變。

上述思想可表示為如下最優(yōu)化問題：式中，W為分類超平面的法向量；ν為常數(shù)并通過網(wǎng)格搜索策略選擇；ρ為各類樣本間隔；mi=為各類樣本均值，c為樣本類別數(shù)；WTM W表示找到的分類超平面將樣本的全

W局特征和局部特征考慮在內(nèi)；νρ的存在保證各類樣本的間隔盡可能大，有利于提高分類精度；式(11)表明GRPLM在分類決策時(shí)保持各類樣本的相對(duì)關(guān)系不變。

上述最優(yōu)化問題的對(duì)偶形式如下：

證明：由Lagrangian定理可得：

將式(16)和式(17)帶入到式(15)，并去掉與研究無關(guān)的常數(shù)項(xiàng)可得上述對(duì)偶式。

2.2 決策函數(shù)

GRPLM的決策函數(shù)為：

式中，bk=WT(mi+1+mi)/2

2.3 核化形式

假設(shè)映射函數(shù)φ滿足φ:x→φ(x)。原最優(yōu)化問題的核化形式可表示為：

式中，

原最優(yōu)化問題的核化對(duì)偶形式為：

2.4 時(shí)間復(fù)雜度分析

GRPLM優(yōu)化問題求解主要包括大小為N×N矩陣的轉(zhuǎn)置運(yùn)算以及大小為(c?1)×(c?1)Hessian矩陣QP問題求解運(yùn)算。大小為N×N矩陣的轉(zhuǎn)置運(yùn)算的時(shí)間復(fù)雜度為O( N2log(N))，大小為(c?1)×(c?1) Hessian矩陣QP問題求解的時(shí)間復(fù)雜度為O(( c?1)3)，GRPLM的時(shí)間復(fù)雜度為O( N2log(N))+ O(( c?1)3)，由于c＜＜N，則GRPLM的時(shí)間復(fù)雜度近似表示為O( c3)。

2.5 大規(guī)模分類

2.5.1 核心向量機(jī)

核心向量機(jī)CVM的基本思路是在大規(guī)模樣本空間中利用一個(gè)逼近率為(1+ε)的近似算法找到核心集，該集合較之原始樣本具有比更小的規(guī)模。更重要的是，文獻(xiàn)[14]指出該核心集與樣本數(shù)無關(guān)，只與參數(shù)ε有關(guān)，該結(jié)論有力地支持了CVM在解決大規(guī)模分類問題方面的有效性。

2.5.2 最小包含球

最優(yōu)化問題定義線性形式為：

式中，c為超球體球心；R為超球體半徑。非線性形式為：

式中，φ(xi)表示從原始樣本空間到高維特征空間的映射。

由Lagrangian定理可得如下對(duì)偶形式：

2.5.3 GRPLM與MEB關(guān)系

令/βα ν=，GRPLM的QP形式可轉(zhuǎn)化為：

GRPLM-CVM算法描述如下：

1) 初始化參數(shù)；B(c, R)：球心為c，半徑為R的最小包含球；St：核心集；t：迭代次數(shù)；ε：終止參數(shù)。

2) 對(duì)于?z有φ(z)∈B(ct,(1+ε)R)，則轉(zhuǎn)到步驟6)，否則轉(zhuǎn)到步驟3)；

3) 如果φ(z)距離球心ct最遠(yuǎn)，則St+1=St∪{φ(z)}；

4) 尋找最新最小包含球B(St+1)，并設(shè)置：

5) t=t+1并轉(zhuǎn)到步驟2)；

6) GRPLM對(duì)核心集進(jìn)行訓(xùn)練并得到?jīng)Q策函數(shù)。

3 實(shí)驗(yàn)分析

3.1 人工數(shù)據(jù)集

人工生成4類服從Gaussian分布的數(shù)據(jù)集，各類樣本50個(gè)，其中心點(diǎn)分別為(4,4)、(?3,?3)、(?9,?9)、(?15,?15)，均方差均為2.5。人工數(shù)據(jù)集如圖1a所示。將上述數(shù)據(jù)集投影到GRPLM找到的方向向量可得圖1b，GRPLM中參數(shù)ν選取1。

圖1 人工數(shù)據(jù)集及實(shí)驗(yàn)結(jié)果

由圖1b可以看出，GRPLM找到的方向向量能較好地保持原始數(shù)據(jù)的相對(duì)關(guān)系不變，且具有良好的可分性。

3.2 中小規(guī)模數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集見表1所示，分別選取實(shí)驗(yàn)數(shù)據(jù)集中各類樣本的60%作為訓(xùn)練樣本，剩余樣本用作測(cè)試。

表1 中小規(guī)模數(shù)據(jù)集

3.2.1. 核函數(shù)對(duì)分類結(jié)果的影響

GRPLM的分類性能受核函數(shù)選擇的影響。本實(shí)驗(yàn)將Gaussian核函數(shù)、Polynomial核函數(shù)、Sigmoid核函數(shù)、Epanechnikov核函數(shù)，分別帶入GRPLM核化形式中來考察GRPLM的分類性能。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 核函數(shù)對(duì)分類結(jié)果的影響

由圖2可以看出：在Wine、Liver、Glass、Pima數(shù)據(jù)集上，選取Gaussian核函數(shù)的GRPLM分類精度最優(yōu)，選取Epanechnikov核函數(shù)的GRPLM分類精度次之，選取Sigmoid核函數(shù)和Polynomial核函數(shù)的GRPLM分類精度分別排在后兩位；選取Gaussian核函數(shù)和Epanechnikov核函數(shù)的GRPLM在Iris數(shù)據(jù)集上分類精度相同且均具有最優(yōu)的分類能力。

后續(xù)實(shí)驗(yàn)選取核函數(shù)的依據(jù)是：Sigmoid核函數(shù)在特定參數(shù)下與Gaussian核函數(shù)具有近似性能；Polynomial核函數(shù)參數(shù)較多Polynomial核函數(shù)參數(shù)較多且較難確定；Gaussian核函數(shù)和Epanechnikov核函數(shù)在實(shí)際中均廣泛被使用。但從方便計(jì)算角度考慮，后續(xù)實(shí)驗(yàn)選用Gaussian核函數(shù)。

3.2.2 比較實(shí)驗(yàn)

本節(jié)通過與多類支持向量機(jī)[22]、K近鄰算法比較實(shí)驗(yàn)驗(yàn)證GRPLM的有效性。本文實(shí)驗(yàn)K取5。Multi-class SVM的最優(yōu)化表達(dá)式如下：

GRPLM分類精度與參數(shù)選取有關(guān)。參數(shù)通過網(wǎng)格搜索策略選擇。Gaussian核函數(shù)的方差δ在網(wǎng)格中搜索選取，其中x為訓(xùn)練樣本平均范數(shù)的平方根；多類支持向量機(jī)中，懲罰因子C在網(wǎng)格{0.01, 0.05, 0.1, 0.5, 1, 5, 10}中搜索選??；GRPLM中，參數(shù)ν在網(wǎng)格{0.1, 0.5, 1, 5, 10}中搜索選取。Gaussian核函數(shù)方差δ、Multi-class SVM的懲罰因子C、GRPLM的參數(shù)ν均通過5倍交叉驗(yàn)證法獲得。實(shí)驗(yàn)參數(shù)選取如表2所示，實(shí)驗(yàn)結(jié)果如表3所示。

表2 實(shí)驗(yàn)參數(shù)表

表3 中小規(guī)模數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由表3可以看出：從平均分類性能看，與Multi-class SVM和KNN相比，GRPLM在UCI數(shù)據(jù)集上具有更優(yōu)的分類精度。具體而言，在Wine、Liver、Glass、Pima數(shù)據(jù)集上GRPLM的分類精度好于Multi-class SVM和KNN；在Iris數(shù)據(jù)集上GRPLM和Multi-class SVM分類精度相當(dāng)且略高于KNN。綜上所述，GRPLM在中小規(guī)模數(shù)據(jù)集上能較好地完成分類任務(wù)。

3.3 大規(guī)模數(shù)據(jù)集

3.3.1 終止參數(shù)ε對(duì)分類結(jié)果的影響

實(shí)驗(yàn)采用Bank數(shù)據(jù)集，實(shí)驗(yàn)選取60%的數(shù)據(jù)集用作訓(xùn)練，剩余的用于測(cè)試。CVM中的參數(shù)ε在網(wǎng)格{10?2, 10?3, 10?4, 10?5, 10?6, 10?7}中選取。GRPLMCVM的效率受到參數(shù)ε取值的影響。具體情況參如圖3所示。

圖3 終止參數(shù)ε對(duì)GRPLM-CVM的影響

圖3 反映的結(jié)論是參數(shù)ε影響到算法的訓(xùn)練時(shí)間以及分類精度。不失一般性，實(shí)驗(yàn)選取ε=10?6。

3.3.2 GRPLM-CVM分類性能分析

實(shí)驗(yàn)采用文獻(xiàn)[23]提供的數(shù)據(jù)集。實(shí)驗(yàn)訓(xùn)練樣本分別取數(shù)據(jù)集的20%、40%、60%、80%，從剩下樣本中任取500個(gè)作為測(cè)試樣本。實(shí)驗(yàn)結(jié)果如表4所示。

表4 GRPLM-CVM分類結(jié)果

由表4可以看出：隨著訓(xùn)練樣本規(guī)模的增大，GRPLM-CVM分類精度和訓(xùn)練時(shí)間呈上升趨勢(shì)，即訓(xùn)練樣本規(guī)模影響GRPLM-CVM的分類性能。從分類效果看，GRPLM-CVM基本上能在有限時(shí)間內(nèi)較好地完成分類任務(wù)。

4 結(jié) 論

針對(duì)當(dāng)前分類方法面臨的不足，提出基于流形判別分析的全局保序?qū)W習(xí)機(jī)GRPLM。該方法的主要優(yōu)勢(shì)在于：1) 進(jìn)行分類決策時(shí)同時(shí)考慮樣本的全局特征和局部特征；2) 具有保持樣本相對(duì)關(guān)系不變的特性；3) 能在一定程度上解決傳統(tǒng)分類器面臨的大規(guī)模分類問題。與傳統(tǒng)分類器的比較實(shí)驗(yàn)表明本文所提方法在分類性能方面具有一定優(yōu)勢(shì)。但GRPLM仍存在一定問題，如其分類能力對(duì)參數(shù)的選取較為依賴，如何提高參數(shù)選取效率對(duì)GRPLM分類性能的提升至關(guān)重要，這也是下一步的工作。

[1] QUINLAN J R. C4.5: Programs for Machine Learning[M]. San Francisco: Morgan Kaufmann Publishers, 1993.

[2] RASTOGI R, SHIM K. Public: a decision tree classifier that integrates building and pruning[C]//Proc of the Very Large Database Conference (VLDB). New York: [s.n.], 1998: 404-415.

[3] MEHTA M, AGRAWAL R, RISSANEN J. SLIQ: a fast scalable classifier for data mining[C]//Proc of International Conf Extending Database Technology(EDBT'96). France: [s.n.], 1996: 18-32.

[4] GEHRKE J, RAMAKRISHNAN R, GANTI V. Rainforest: a framework for fast decision tree construction of large datasets[J]. Data Mining and Knowledge Discovery, 2000, 4(2-3): 127-162.

[5] LIU B, HSU W, MA Y. Integrating classification and association rule[C]//Proc of the 4th International Conf on Knowledge Discovery and Data Mining. New York, USA: AAAI Press, 1998: 80-86.

[6] LI W M, HAN J, JIAN P. CMAR: Accurate and efficient classification based on multiple class association rules[C]//Proc of IEEE International Conf on Data Mining. Washington D C: IEEE Computer Society, 2001: 369-376.

[7] YIN X, HAN J. Classification based on predictive association rules[C]//SIAM International Conf on Data Mining. San Francisco: [s.n.], 2003: 331-335.

[8] VAPNIK V. The nature of statistical learning theory[M]. New York: Springer-Verlag, 1995.

[9] 鄧乃揚(yáng), 田英杰. 支持向量機(jī)——理論、算法與拓展[M].北京: 科學(xué)出版社, 2009. DENG Nai-yang, TIAN Ying-jie. Support vector machine: Theory, algorithm and development[M]. Beijing: Science Press, 2009.

[10] PAL M, FOODY G M. Feature selection for classification of hyper spectral data by SVM[J]. IEEE Trans on Geoscience and Remote Sensing, 2010, 48(5): 2297-2307.

[11] SCHOLKOPF B, SMOLA A, BARTLET P. New support vector algorithms[J]. Neural Computation, 2000, 12: 1207-1245.

[12] SCHOLKOPF B, PLATT J, SHAWE-TAYLOR J, et a1. Estimating the support of high-dimensional distribution[J]. Neural Computation, 2001, 13: 1443-1471.

[13] TAX D M J, DUIN R P W. Support vector data description [J]. Machine Learning, 2004(54): 45-66.

[14] TSANG I W, KWOK J T, CHEUNG P M. Core vector machines: Fast SVM training on very large data sets[J]. Journal of Machine Learning Research, 2005(6): 363-392.

[15] MANGASARIAN O, MUSICANT D. Lagrange support vector machines[J]. Journal of Machine Learning Research, 200l(1): 161-177.

[16] SUYKENS J A, VANDEWALLE J. Least squares support vector machines classifiers[J]. Neural Processing Letters, 1999, 19(3): 293-300.

[17] LEE Y J, MANGASARIAN O. SSVM: a smooth support vector machines[J]. Computational Optimization and Applications, 2001, 20(1): 5-22.

[18] LANGLEY P, SAGE S. Introduction of selective Bayesian classifier[C]//Proc of the 10th Conf on Uncertainty in Artificial Intelligence. Seattle: Morgan Kaufmann Publishers, 1994: 339-406.

[19] ZHENG Z H, WEBB G I. Lazy Bayesian rules[J]. Machine Learning, 2000, 32(1): 53-84.

[20] FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network classifiers[J]. Machine Learing, 1997, 29(2): 131-163.

[21] 劉忠寶, 潘廣貞, 趙文娟. 流形判別分析[J]. 電子與信息學(xué)報(bào), 2013, 35(9): 2047-2053. LIU Zhong-bao, PAN Guang-zhen, ZHAO Wen-juan. Manifold-based discriminant analysis[J]. Journal of Electroincs & Information Technology, 2013, 35(9): 2047-2053.

[22] WESTON J, WATKINS C. Multi-class support vector machines[R]. London: Department of Computer Science, Royal Holloway University of London Technology, 1998.

[23] LIN L, LIN H T. Ordinal regression by extended binary classification[J]. Advanced in Neural Information Processing Systems, 2007, 19: 865-872.

編 輯 蔣 曉

Global Rank Preservation Learning Machine Based on Manifold-Based Discriminant Analysis

ZHANG Jing1and LIU Zhong-bao2

(1. School of Software, North University of China Taiyuan 030051; 2. School of Computer and Control Engineering, North University of China Taiyuan 030051)

In order to solve the problems that many traditional classification methods confronted, a global rank preservation learning machine (GRPLM) based on manifold-based discriminant analysis is proposed in this paper. In GRPLM, the manifold-based discriminant analysis (MDA) is introduced to represent the samples’ global and local characteristic; the relative relationship of different class centers is taken into consideration in order to preserve the samples’ ranks; the equivalent relation between the QP form of GRPLM and core vector machine (CVM) is analyzed in order to broaden the usage of GRPLM from small- and medium-scale to large-scale. Comparative experiments on several standard datasets verify the effectiveness of the proposed methods.

global rank preservation; large-scale classification; manifold-based discriminant analysis (MDA); support vector machine (SVM)

TP181

A

10.3969/j.issn.1001-0548.2015.06.020

2015 ? 01 ? 25；

2015 ? 09 ? 25

國(guó)家自然科學(xué)基金(61202311)；山西省高等學(xué)?？萍紕?chuàng)新項(xiàng)目(2014142)作者簡(jiǎn)介：張靜(1980 ? )，女，博士生，主要從事智能信息處理方面的研究.