文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.170174
中文引用格式： 武海燕，李衛(wèi)平. 結(jié)合本征分解和抽樣學(xué)習(xí)的快速SVM分類器[J].電子技術(shù)應(yīng)用，2017，43(9)：141-145.
英文引用格式： Wu Haiyan，Li Weiping. A fast SVM classifier combined with Eigen decomposition and sample-learning[J].Application of Electronic Technique，2017，43(9)：141-145.
0 引言
在數(shù)據(jù)挖掘、圖像分類、目標(biāo)識別等領(lǐng)域，經(jīng)常需要對不同的數(shù)據(jù)進(jìn)行分類。常用的策略是，先對已有的數(shù)據(jù)和先驗(yàn)知識進(jìn)行學(xué)習(xí)并構(gòu)造一個(gè)分類器，然后再采用分類器對待分類數(shù)據(jù)進(jìn)行分類。分類器也可以看作是一個(gè)數(shù)據(jù)映射函數(shù)，可以將待分類數(shù)據(jù)映射到數(shù)據(jù)庫中的某一個(gè)給定的類別[1-3]。通常，數(shù)據(jù)分類方法統(tǒng)稱為分類器。目前，常用的分類器有五類：(1)樸素貝葉斯分類器，該分類器具有收斂速度快的優(yōu)點(diǎn)，對樣本數(shù)量要求不高，可以適用于小樣本的學(xué)習(xí)。但是，該分類假設(shè)數(shù)據(jù)條件獨(dú)立，難以有效學(xué)習(xí)數(shù)據(jù)之間的關(guān)聯(lián)信息[4]；(2)邏輯回歸分類器，該分類器的最大優(yōu)點(diǎn)是支持增量學(xué)習(xí)，當(dāng)分類器構(gòu)建完畢之后，后續(xù)如果又有了新樣本需要學(xué)習(xí)，可以采用在線梯度下降方法在原有分類器的基礎(chǔ)上快速學(xué)習(xí)新的數(shù)據(jù)，而且，該分類器的正則化模型較多，不要求數(shù)據(jù)之間相互獨(dú)立，但是該分類器的分類性能目前表現(xiàn)還不是很突出[5]；(3)決策樹分類器，該分類器首先需要構(gòu)建一個(gè)屬性集合，決策樹基于屬性集合來做出一系列的決策，實(shí)現(xiàn)數(shù)據(jù)的分類。該分類器易于處理數(shù)據(jù)間的關(guān)聯(lián)信息，不限制數(shù)據(jù)是否異常或者線性可分。缺點(diǎn)是容易發(fā)生過擬合現(xiàn)象[6]；(4)神經(jīng)網(wǎng)絡(luò)分類器，該分類器也對輸入數(shù)據(jù)沒有嚴(yán)格的要求，網(wǎng)絡(luò)的構(gòu)建比較靈活，但涉及參數(shù)較多，運(yùn)算效率偏低[7]；(5)支持向量機(jī)（Support Vector Machine，SVM）分類器，該分類器為過擬合提供了好的理論保證，泛化能力較強(qiáng)，對于小樣本的學(xué)習(xí)尤其有效，分類效果較好。該分類器在學(xué)習(xí)非線性可分?jǐn)?shù)據(jù)時(shí)，需要先將數(shù)據(jù)映射到高維空間，使得高維空間的數(shù)據(jù)線性可分。常采用核函數(shù)來完成數(shù)據(jù)由低維到高維的映射[8]。然而，當(dāng)數(shù)據(jù)維數(shù)較高時(shí)，核變換的復(fù)雜度較高，導(dǎo)致SVM的運(yùn)算效率偏低。
為了提高SVM分類器的運(yùn)算效率，本文提出一種結(jié)合本征分解和抽樣學(xué)習(xí)改進(jìn)的快速SVM分類器，通過本征分解方法來降低低維空間向高維空間變換時(shí)核矩陣的維數(shù)，通過對訓(xùn)練樣本進(jìn)行抽樣學(xué)習(xí)來降低數(shù)據(jù)處理量，提高SVM分類器的運(yùn)算效率。
1 SVM概述
SVM是一種應(yīng)用廣泛的分類器，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小原理進(jìn)行學(xué)習(xí)，具有泛化能力強(qiáng)的優(yōu)點(diǎn)，可以有效解決小樣本的學(xué)習(xí)難題，在高維特征分類領(lǐng)域也有優(yōu)勢。
依據(jù)訓(xùn)練數(shù)據(jù)的不同，可以將SVM分為線性SVM和非線性SVM兩類，下面進(jìn)行簡要介紹。
1.1 線性SVM
當(dāng)訓(xùn)練數(shù)據(jù)線性可分時(shí)，可以采用線性SVM學(xué)習(xí)一個(gè)最優(yōu)的分類面來進(jìn)行分類。SVM的基本原理是：最優(yōu)分類面既要能將兩類樣本正確分開，又要使得分類間隔最大。
SVM的學(xué)習(xí)可以看作一個(gè)最優(yōu)化問題，可以表示為：
1.2 非線性SVM
當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時(shí)，可以采用非線性SVM學(xué)習(xí)一個(gè)最優(yōu)分類面。通常的解決方法是：采用一個(gè)非線性的映射函數(shù)將低維空間上線性不可分的數(shù)據(jù)映射到高維空間上，變成線性可分的數(shù)據(jù)。依據(jù)Hilbert-Schmidt原理，滿足Mercer條件的核函數(shù)可以代替高維空間上的點(diǎn)積運(yùn)算。因此，這里的關(guān)鍵是選擇一個(gè)合適的核函數(shù)來進(jìn)行數(shù)據(jù)映射。核函數(shù)可以表示為：
其中，f(·)表示映射函數(shù)，用于表示將低維空間上的數(shù)據(jù)映射到高維的核空間F上。可見，核函數(shù)k(xi，xj)可以用高維空間上數(shù)據(jù)的乘積運(yùn)算來代替低維空間上數(shù)據(jù)的點(diǎn)積運(yùn)算。
常用的核函數(shù)主要有3個(gè)，包括：
(1)徑向基函數(shù)(Radial Basis Function，RBF)，可以表示為：
2 改進(jìn)的非線性SVM
數(shù)據(jù)的核變換可以構(gòu)建一個(gè)核矩陣K∈RN×N，表示為：
其中，F(xiàn)是指數(shù)據(jù)x映射到核空間F上的數(shù)據(jù)集，可以表示為：
當(dāng)數(shù)據(jù)維數(shù)較高時(shí)，核變換的運(yùn)算效率偏低。為了提高核運(yùn)算效率，本文考慮對核矩陣進(jìn)行降維處理。考慮到核矩陣K為正半定矩陣，通常可以通過本征分解來進(jìn)行降維。因此，對于核空間F上的數(shù)據(jù)集F，可以分解為：
其中，L是由矩陣F的特征值構(gòu)建的對角矩陣。這里，特征值按照從大到小的順序降序排列。U為對應(yīng)的特征向量矩陣。
這樣，低維空間上的數(shù)據(jù)x映射到高維空間之后對應(yīng)的n維向量可以表示為：
計(jì)算整個(gè)核矩陣仍然非常耗時(shí)，為了進(jìn)一步提高運(yùn)算效率，本文對訓(xùn)練子集進(jìn)行劃分，隨機(jī)挑選包含n個(gè)訓(xùn)練樣本的子集來計(jì)算K的子矩陣，表示為：
3 實(shí)驗(yàn)與分析
分類器在圖像分類領(lǐng)域應(yīng)用非常普遍，因此，本節(jié)通過圖像分類實(shí)驗(yàn)來測試和評價(jià)本文所述的改進(jìn)SVM分類器的性能。
3.1 圖像分類實(shí)驗(yàn)流程
圖像分類的基本流程如圖1所示。主要包括兩個(gè)階段：(1)分類器訓(xùn)練階段，主要是對訓(xùn)練數(shù)據(jù)集進(jìn)行特征提取，依據(jù)先驗(yàn)的圖像類別標(biāo)簽來進(jìn)行分類器的訓(xùn)練；(2)圖像分類階段，對于待分類的圖像，先要提取圖像特征，然后結(jié)合訓(xùn)練階段得到的分類器估計(jì)特征所屬的類別，得到圖像分類結(jié)果。
其中，特征提取和特征分類是圖像分類的關(guān)鍵環(huán)節(jié)。特征提取是對圖像的抽象描述，常用的特征有Haar[9]、方向梯度直方圖（Histogram of Oriented Gradient，HOG）[10]、局部二元模式（Local Binary Pattern，LBP）[11]和尺度不變特征轉(zhuǎn)換(Scale-Invariant Feature Transform，SIFT)[12]等，本文將在后續(xù)實(shí)驗(yàn)中對不同的特征進(jìn)行定量評測，進(jìn)而選擇最有效的特征進(jìn)行圖像分類。特征分類是本文的研究重點(diǎn)，本文所述方法是一種改進(jìn)的SVM分類器，因此后續(xù)實(shí)驗(yàn)著重是將本文改進(jìn)的SVM分類器與經(jīng)典SVM分類器以及目前常用的一些分類器進(jìn)行性能對比，具體將在后續(xù)實(shí)驗(yàn)部分詳述。
3.2 實(shí)驗(yàn)數(shù)據(jù)集
圖像分類領(lǐng)域的公開測試的數(shù)據(jù)集比較多，本文選用目前常用的兩個(gè)測試數(shù)據(jù)集，分別是PASCAL VOC-2007和COIL-100數(shù)據(jù)集，簡要介紹如下。
(1)PASCAL VOC-2007數(shù)據(jù)集
該數(shù)據(jù)集包含20個(gè)類別的目標(biāo)圖像，這些目標(biāo)存在尺度、視角和光照方面的變化，數(shù)據(jù)集包含的圖像總數(shù)為9 963幅，其中訓(xùn)練子集中包含圖像5 011幅，測試子集中包含圖像4 592幅。
(2)COIL-100數(shù)據(jù)集
該數(shù)據(jù)集包含100個(gè)類別的目標(biāo)圖像，目標(biāo)也存在尺度、視角及光照方面的變化，圖像數(shù)量為7 200幅，其中訓(xùn)練子集中包含圖像800幅，測試子集中包含圖像6 400幅。
后續(xù)對比不同的特征提取和分類方法時(shí)，分別在上述兩個(gè)數(shù)據(jù)集上進(jìn)行訓(xùn)練和測試，在相同的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集上統(tǒng)計(jì)各種方法的性能指標(biāo)，以便于驗(yàn)證本文方法的性能。
3.3 性能評價(jià)指標(biāo)
本文實(shí)驗(yàn)的目的主要用于評價(jià)改進(jìn)SVM分類器的分類正確率和運(yùn)算效率。因此，這里的圖像分類實(shí)驗(yàn)選用3個(gè)性能評價(jià)指標(biāo)，分別是分類正確率、訓(xùn)練耗時(shí)和平均分類耗時(shí)。其中，分類正確率可以用分類正確的圖像總數(shù)與測試數(shù)據(jù)集中的圖像總數(shù)的比值來表示，記為AR。訓(xùn)練耗時(shí)指兩個(gè)數(shù)據(jù)集的整個(gè)訓(xùn)練過程所耗費(fèi)的總時(shí)間，記為TT。平均分類耗時(shí)可以用所有測試圖像的分類耗時(shí)與圖像數(shù)量的比值來表示，記為TC。需要說明的是：分類耗時(shí)與計(jì)算機(jī)平臺性能有關(guān)。實(shí)驗(yàn)時(shí)不同方法使用相同的計(jì)算機(jī)平臺進(jìn)行測試。所有計(jì)算機(jī)平臺的性能參數(shù)為：3.2 GHz四核 Intel I5 CPU、16G DDR3內(nèi)存、Windows 7 32位操作系統(tǒng)、Visual Studio 2010開發(fā)環(huán)境。
3.4 實(shí)驗(yàn)結(jié)果與對比分析
3.4.1 特征選擇對比
下面首先對比采用不同特征時(shí)兩個(gè)數(shù)據(jù)集的圖像征分類性能指標(biāo)，其中，圖2展示了分別采用Haar、HOG、LBP和SIFT 4種特征時(shí)的圖像分類結(jié)果，分類器采用的是本文改進(jìn)的SVM分類器。其中，改進(jìn)SVM分類器所用的核函數(shù)為徑向基函數(shù)，參數(shù)σ取值為0.5。
由圖2可見，在分類器相同的條件下，采用SIFT特征在兩個(gè)數(shù)據(jù)集上測試所得的圖像分類正確率指標(biāo)都高于其他3種特征。這說明SIFT特征優(yōu)于其他3種特征，因此，后續(xù)的實(shí)驗(yàn)中在特征提取階段都采用SIFT特征對圖像進(jìn)行描述。
3.4.2 核函數(shù)選擇對比
本文1.2節(jié)列出了3種常用的核函數(shù)，分別是徑向基函數(shù)（RBF）、二層神經(jīng)網(wǎng)絡(luò)函數(shù)（Sigmoid）和多項(xiàng)式函數(shù)（Polynomial）。采用的核函數(shù)不同，所得到的圖像分類結(jié)果也不同。圖3展示了分別采用3種不同的核函數(shù)時(shí)得到的圖像分類正確率指標(biāo)，其中，圖3(a)采用的是經(jīng)典的SVM分類器，詳見文獻(xiàn)[8]；圖3(b)采用的是本文改進(jìn)的SVM分類器。
由圖3(a)和圖3(b)可見，對于兩個(gè)不同的數(shù)據(jù)集，不論是采用經(jīng)典的SVM分類器還是采用本文改進(jìn)的SVM分類器，都可以看出采用徑向基函數(shù)作為核函數(shù)得到的圖像分類正確率指標(biāo)高于其他兩種核函數(shù)，因此，后續(xù)實(shí)驗(yàn)中經(jīng)典SVM分類器和本文改進(jìn)的SVM分類器都選擇徑向基函數(shù)作為核函數(shù)。
3.4.3 分類器對比
為了驗(yàn)證本文改進(jìn)的SVM分類器的性能，下面采用不同的分類器進(jìn)行對比實(shí)驗(yàn)。圖4展示了分別采用經(jīng)典SVM分類器、隨機(jī)森林分類器、神經(jīng)網(wǎng)絡(luò)分類器和本文改進(jìn)的SVM分類器得到的圖像分類正確率指標(biāo)。表1展示了對應(yīng)的平均分類耗時(shí)指標(biāo)。
由圖4可見，本文改進(jìn)的SVM分類器得到的圖像分類正確率指標(biāo)略高于經(jīng)典的SVM分類器，明顯高于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類器。這說明，相對于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類器，SVM分類器的泛化能力更強(qiáng)，更適用于圖像分類。同時(shí)，改進(jìn)的SVM采用本征分解降低了噪聲干擾，相對于經(jīng)典SVM分類器其圖像分類正確率指標(biāo)略有提升。由表1可見，本文改進(jìn)的SVM分類器的訓(xùn)練耗時(shí)明顯低于其他3種分類器，平均分類耗時(shí)也明顯低于經(jīng)典SVM分類器和神經(jīng)網(wǎng)絡(luò)分類器，略高于隨機(jī)森林分類器。這說明，通過降維和抽樣處理，可以明顯提高SVM分類器的分類耗時(shí)。因此，綜合評價(jià)，本文改進(jìn)的SVM分類器不僅提高了運(yùn)算效率，而且提高了分類正確率。
4 結(jié)束語
為了提高經(jīng)典支持向量機(jī)分類器的運(yùn)算效率，本文提出了一種結(jié)合本征分解和抽樣學(xué)習(xí)改進(jìn)的快速SVM分類器。主要是針對低維空間向高維空間變換時(shí)核矩陣運(yùn)算效率低的問題進(jìn)行改進(jìn)：對核矩陣進(jìn)行降維處理，采用本征分解方法得到核矩陣的近似表示，提高核矩陣的運(yùn)算效率；在表示低維的核矩陣時(shí)，采用抽樣學(xué)習(xí)的思想，先對訓(xùn)練數(shù)據(jù)進(jìn)行劃分，隨機(jī)抽樣一個(gè)數(shù)量很小的訓(xùn)練樣本子集進(jìn)行學(xué)習(xí)，進(jìn)一步降低了數(shù)據(jù)量，進(jìn)而提高了SVM分類器的運(yùn)算效率。
經(jīng)過優(yōu)化，不僅提高了SVM分類器的運(yùn)算效率，也進(jìn)一步強(qiáng)化了SVM分類器的泛化能力。通過將改進(jìn)的SVM分類器與經(jīng)典的SVM分類器以及常用的隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)分類器進(jìn)行圖像分類對比實(shí)驗(yàn)，證明了改進(jìn)的SVM分類器不僅分類正確率高于經(jīng)典SVM、隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類器，而且訓(xùn)練耗時(shí)最少，平均分類耗時(shí)也優(yōu)于經(jīng)典SVM分類器，是一種快速可靠的分類器。
參考文獻(xiàn)
[1] LIU Q.Kernel local sparse representation based classifier[J].Neural Processing Letters，2016，43(1)：123-137.
[2] 楊春，殷緒成，郝紅衛(wèi)，等.基于差異性的分類器集成：有效性分析及優(yōu)化集成[J].自動(dòng)化學(xué)報(bào)，2014，40(4)：660-674.
[3] LIAN C，SU R，DEN?覹UX T.An evidential classifier based on feature selection and two-step classification strategy[J].Pattern Recognition，2015，48(7)：2318-2327.
[4] 王雙成，高瑞，杜瑞杰.基于高斯核函數(shù)的樸素貝葉斯分類器依賴擴(kuò)展[J].控制與決策，2015，30(12)：2280-2284.
[5] 郭華平，董亞東，鄔長安，等.面向類不平衡的邏輯回歸方法[J].模式識別與人工智能，2015，28(8)：686-693.
[6] PUISSANT A，ROUGIER S，STUMPF A.Object-oriented mapping of urban trees using Random Forest classifiers[J].International Journal of Applied Earth Observation & Geoinformation，2014，26(1)：235-245.
[7] SUJAY R N，DEKA P C.Support vector machine applications in the field of hydrology：A review[J].Applied Soft Computing，2014，19(6)：372-386.
[8] CHAI R，LING S H，HUNTER G P，et al.Brain-computer interface classifier for wheelchair commands using neural network with fuzzy particle swarm optimization[J].IEEE Journal of Biomedical & Health Informatics，2014，18(5)：1614-1624.
[9] Chang Zheng，Ban Xiaojuan，Wang Yu.Fatigue driving detection based on Haar feature and extreme learning machine[J].Journal of China Universities of Posts & Telecommunications，2016，23(4)：91-100.
[10] YANG X, DI T.Research on mean-shift target tracking based on image HOG feature[J].Open Automation & Control Systems Journal，2015，7(1)：1022-1028.
[11] CIOCCA G，CUSANO C，SCHETTINI R.Image orientation detection using LBP-based features and logistic regression[J].Multimedia Tools and Applications，2015，74(9)：3013-3034.
[12] GHOUALMI L，CHIKHI S，DRAA A.A SIFT-based feature level fusion of iris and ear biometrics[C].Multimodal Pattern Recognition of Social Signals in Human-Computer-Interaction(MPRSS 2014)，2014：102-112.
作者信息：
武海燕1，李衛(wèi)平1，2
（1.鐵道警察學(xué)院 公安技術(shù)系，河南 鄭州450000；2.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢430070）