基于流形判別分析的全局保序學習機

張 靜，劉忠寶

基于流形判別分析的全局保序學習機

張 靜1，劉忠寶2

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

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

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

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

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

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

1 流形判別分析

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

式中，μ和λ為常數并通過網格搜索策略進行選擇；SW和SB分別表示類內離散度和類間離散度，其定義同LDA；SS和SD分別表征同類樣本和異類樣本的局部結構，兩者定義如下：

式中，S′為對角陣且S′=∑jSij，Sij為同類權重函數：

MDA的最優化問題定義如下：

2 GRPLM

2.1 最優化問題

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

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

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

上述最優化問題的對偶形式如下：

證明：由Lagrangian定理可得：

將式(16)和式(17)帶入到式(15)，并去掉與研究無關的常數項可得上述對偶式。

2.2 決策函數

GRPLM的決策函數為：

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

2.3 核化形式

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

式中，

原最優化問題的核化對偶形式為：

2.4 時間復雜度分析

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

2.5 大規模分類

2.5.1 核心向量機

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

2.5.2 最小包含球

最優化問題定義線性形式為：

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

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

由Lagrangian定理可得如下對偶形式：

2.5.3 GRPLM與MEB關系

令/βα ν=，GRPLM的QP形式可轉化為：

GRPLM-CVM算法描述如下：

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

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

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

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

5) t=t+1并轉到步驟2)；

6) GRPLM對核心集進行訓練并得到決策函數。

3 實驗分析

3.1 人工數據集

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

圖1 人工數據集及實驗結果

由圖1b可以看出，GRPLM找到的方向向量能較好地保持原始數據的相對關系不變，且具有良好的可分性。

3.2 中小規模數據集

實驗數據集見表1所示，分別選取實驗數據集中各類樣本的60%作為訓練樣本，剩余樣本用作測試。

表1 中小規模數據集

3.2.1. 核函數對分類結果的影響

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

圖2 核函數對分類結果的影響

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

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

3.2.2 比較實驗

本節通過與多類支持向量機[22]、K近鄰算法比較實驗驗證GRPLM的有效性。本文實驗K取5。Multi-class SVM的最優化表達式如下：

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

表2 實驗參數表

表3 中小規模數據集實驗結果

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

3.3 大規模數據集

3.3.1 終止參數ε對分類結果的影響

實驗采用Bank數據集，實驗選取60%的數據集用作訓練，剩余的用于測試。CVM中的參數ε在網格{10?2, 10?3, 10?4, 10?5, 10?6, 10?7}中選取。GRPLMCVM的效率受到參數ε取值的影響。具體情況參如圖3所示。

圖3 終止參數ε對GRPLM-CVM的影響

圖3 反映的結論是參數ε影響到算法的訓練時間以及分類精度。不失一般性，實驗選取ε=10?6。

3.3.2 GRPLM-CVM分類性能分析

實驗采用文獻[23]提供的數據集。實驗訓練樣本分別取數據集的20%、40%、60%、80%，從剩下樣本中任取500個作為測試樣本。實驗結果如表4所示。

表4 GRPLM-CVM分類結果

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

4 結 論

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

[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] 鄧乃揚, 田英杰. 支持向量機——理論、算法與拓展[M].北京: 科學出版社, 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]. 電子與信息學報, 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

國家自然科學基金(61202311)；山西省高等學校科技創新項目(2014142)作者簡介：張靜(1980 ? )，女，博士生，主要從事智能信息處理方面的研究.