0 引言

    在數(shù)據(jù)挖掘,、圖像分類、目標(biāo)識(shí)別等領(lǐng)域,，經(jīng)常需要對(duì)不同的數(shù)據(jù)進(jìn)行分類,。常用的策略是，先對(duì)已有的數(shù)據(jù)和先驗(yàn)知識(shí)進(jìn)行學(xué)習(xí)并構(gòu)造一個(gè)分類器,，然后再采用分類器對(duì)待分類數(shù)據(jù)進(jìn)行分類,。分類器也可以看作是一個(gè)數(shù)據(jù)映射函數(shù)，可以將待分類數(shù)據(jù)映射到數(shù)據(jù)庫(kù)中的某一個(gè)給定的類別^[1-3],。通常,，數(shù)據(jù)分類方法統(tǒng)稱為分類器。目前,，常用的分類器有五類：(1)樸素貝葉斯分類器,，該分類器具有收斂速度快的優(yōu)點(diǎn)，對(duì)樣本數(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ò)分類器,，該分類器也對(duì)輸入數(shù)據(jù)沒有嚴(yán)格的要求,，網(wǎng)絡(luò)的構(gòu)建比較靈活，但涉及參數(shù)較多,，運(yùn)算效率偏低^[7],；(5)支持向量機(jī)（Support Vector Machine，SVM）分類器,，該分類器為過擬合提供了好的理論保證,，泛化能力較強(qiáng),，對(duì)于小樣本的學(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ù),，通過對(duì)訓(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)勢(shì),。

    依據(jù)訓(xùn)練數(shù)據(jù)的不同，可以將SVM分為線性SVM和非線性SVM兩類,，下面進(jìn)行簡(jiǎ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(x_i，x_j)可以用高維空間上數(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∈R^N×N,，表示為：

其中，F(xiàn)是指數(shù)據(jù)x映射到核空間F上的數(shù)據(jù)集,，可以表示為：

    當(dāng)數(shù)據(jù)維數(shù)較高時(shí),，核變換的運(yùn)算效率偏低,。為了提高核運(yùn)算效率，本文考慮對(duì)核矩陣進(jìn)行降維處理,?？紤]到核矩陣K為正半定矩陣，通?？梢酝ㄟ^本征分解來進(jìn)行降維,。因此，對(duì)于核空間F上的數(shù)據(jù)集F,，可以分解為：

其中,，L是由矩陣F的特征值構(gòu)建的對(duì)角矩陣。這里,，特征值按照從大到小的順序降序排列,。U為對(duì)應(yīng)的特征向量矩陣。

    這樣,，低維空間上的數(shù)據(jù)x映射到高維空間之后對(duì)應(yīng)的n維向量可以表示為：

    計(jì)算整個(gè)核矩陣仍然非常耗時(shí),，為了進(jìn)一步提高運(yùn)算效率，本文對(duì)訓(xùn)練子集進(jìn)行劃分,，隨機(jī)挑選包含n個(gè)訓(xùn)練樣本的子集來計(jì)算K的子矩陣,，表示為：

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

    分類器在圖像分類領(lǐng)域應(yīng)用非常普遍，因此,，本節(jié)通過圖像分類實(shí)驗(yàn)來測(cè)試和評(píng)價(jià)本文所述的改進(jìn)SVM分類器的性能,。

3.1 圖像分類實(shí)驗(yàn)流程

    圖像分類的基本流程如圖1所示。主要包括兩個(gè)階段：(1)分類器訓(xùn)練階段,，主要是對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行特征提取,，依據(jù)先驗(yàn)的圖像類別標(biāo)簽來進(jìn)行分類器的訓(xùn)練；(2)圖像分類階段,，對(duì)于待分類的圖像,，先要提取圖像特征，然后結(jié)合訓(xùn)練階段得到的分類器估計(jì)特征所屬的類別,，得到圖像分類結(jié)果,。

    其中，特征提取和特征分類是圖像分類的關(guān)鍵環(huán)節(jié),。特征提取是對(duì)圖像的抽象描述,，常用的特征有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)中對(duì)不同的特征進(jìn)行定量評(píng)測(cè)，進(jìn)而選擇最有效的特征進(jìn)行圖像分類,。特征分類是本文的研究重點(diǎn),，本文所述方法是一種改進(jìn)的SVM分類器，因此后續(xù)實(shí)驗(yàn)著重是將本文改進(jìn)的SVM分類器與經(jīng)典SVM分類器以及目前常用的一些分類器進(jìn)行性能對(duì)比,，具體將在后續(xù)實(shí)驗(yàn)部分詳述,。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

    圖像分類領(lǐng)域的公開測(cè)試的數(shù)據(jù)集比較多，本文選用目前常用的兩個(gè)測(cè)試數(shù)據(jù)集,，分別是PASCAL VOC-2007和COIL-100數(shù)據(jù)集,，簡(jiǎn)要介紹如下。

    (1)PASCAL VOC-2007數(shù)據(jù)集

    該數(shù)據(jù)集包含20個(gè)類別的目標(biāo)圖像,，這些目標(biāo)存在尺度,、視角和光照方面的變化，數(shù)據(jù)集包含的圖像總數(shù)為9 963幅,，其中訓(xùn)練子集中包含圖像5 011幅,，測(cè)試子集中包含圖像4 592幅。

    (2)COIL-100數(shù)據(jù)集

    該數(shù)據(jù)集包含100個(gè)類別的目標(biāo)圖像,，目標(biāo)也存在尺度,、視角及光照方面的變化，圖像數(shù)量為7 200幅,，其中訓(xùn)練子集中包含圖像800幅,，測(cè)試子集中包含圖像6 400幅。

    后續(xù)對(duì)比不同的特征提取和分類方法時(shí),，分別在上述兩個(gè)數(shù)據(jù)集上進(jìn)行訓(xùn)練和測(cè)試,，在相同的訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集上統(tǒng)計(jì)各種方法的性能指標(biāo)，以便于驗(yàn)證本文方法的性能,。

3.3 性能評(píng)價(jià)指標(biāo)

    本文實(shí)驗(yàn)的目的主要用于評(píng)價(jià)改進(jìn)SVM分類器的分類正確率和運(yùn)算效率,。因此，這里的圖像分類實(shí)驗(yàn)選用3個(gè)性能評(píng)價(jià)指標(biāo),，分別是分類正確率,、訓(xùn)練耗時(shí)和平均分類耗時(shí)。其中,，分類正確率可以用分類正確的圖像總數(shù)與測(cè)試數(shù)據(jù)集中的圖像總數(shù)的比值來表示,，記為A_R。訓(xùn)練耗時(shí)指兩個(gè)數(shù)據(jù)集的整個(gè)訓(xùn)練過程所耗費(fèi)的總時(shí)間,，記為T_T,。平均分類耗時(shí)可以用所有測(cè)試圖像的分類耗時(shí)與圖像數(shù)量的比值來表示，記為T_C,。需要說明的是：分類耗時(shí)與計(jì)算機(jī)平臺(tái)性能有關(guān),。實(shí)驗(yàn)時(shí)不同方法使用相同的計(jì)算機(jī)平臺(tái)進(jìn)行測(cè)試,。所有計(jì)算機(jī)平臺(tái)的性能參數(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é)果與對(duì)比分析

3.4.1 特征選擇對(duì)比

    下面首先對(duì)比采用不同特征時(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ù)集上測(cè)試所得的圖像分類正確率指標(biāo)都高于其他3種特征。這說明SIFT特征優(yōu)于其他3種特征,，因此,，后續(xù)的實(shí)驗(yàn)中在特征提取階段都采用SIFT特征對(duì)圖像進(jìn)行描述。

3.4.2 核函數(shù)選擇對(duì)比

    本文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)可見,，對(duì)于兩個(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 分類器對(duì)比

    為了驗(yàn)證本文改進(jìn)的SVM分類器的性能,，下面采用不同的分類器進(jìn)行對(duì)比實(shí)驗(yàn)。圖4展示了分別采用經(jīng)典SVM分類器、隨機(jī)森林分類器,、神經(jīng)網(wǎng)絡(luò)分類器和本文改進(jìn)的SVM分類器得到的圖像分類正確率指標(biāo),。表1展示了對(duì)應(yīng)的平均分類耗時(shí)指標(biāo),。

    由圖4可見,，本文改進(jìn)的SVM分類器得到的圖像分類正確率指標(biāo)略高于經(jīng)典的SVM分類器，明顯高于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類器,。這說明,，相對(duì)于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類器，SVM分類器的泛化能力更強(qiáng),，更適用于圖像分類,。同時(shí)，改進(jìn)的SVM采用本征分解降低了噪聲干擾,，相對(duì)于經(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í)。因此,，綜合評(píng)價(jià),，本文改進(jìn)的SVM分類器不僅提高了運(yùn)算效率，而且提高了分類正確率,。

4 結(jié)束語

    為了提高經(jīng)典支持向量機(jī)分類器的運(yùn)算效率,，本文提出了一種結(jié)合本征分解和抽樣學(xué)習(xí)改進(jìn)的快速SVM分類器。主要是針對(duì)低維空間向高維空間變換時(shí)核矩陣運(yùn)算效率低的問題進(jìn)行改進(jìn)：對(duì)核矩陣進(jìn)行降維處理,，采用本征分解方法得到核矩陣的近似表示,，提高核矩陣的運(yùn)算效率；在表示低維的核矩陣時(shí),，采用抽樣學(xué)習(xí)的思想,，先對(duì)訓(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)行圖像分類對(duì)比實(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] 郭華平,，董亞東,，鄔長(zhǎng)安，等.面向類不平衡的邏輯回歸方法[J].模式識(shí)別與人工智能,，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）