0 引言

    在數(shù)據(jù)挖掘、圖像分類(lèi)、目標(biāo)識(shí)別等領(lǐng)域，經(jīng)常需要對(duì)不同的數(shù)據(jù)進(jìn)行分類(lèi)。常用的策略是，先對(duì)已有的數(shù)據(jù)和先驗(yàn)知識(shí)進(jìn)行學(xué)習(xí)并構(gòu)造一個(gè)分類(lèi)器，然后再采用分類(lèi)器對(duì)待分類(lèi)數(shù)據(jù)進(jìn)行分類(lèi)。分類(lèi)器也可以看作是一個(gè)數(shù)據(jù)映射函數(shù)，可以將待分類(lèi)數(shù)據(jù)映射到數(shù)據(jù)庫(kù)中的某一個(gè)給定的類(lèi)別^[1-3]。通常，數(shù)據(jù)分類(lèi)方法統(tǒng)稱(chēng)為分類(lèi)器。目前，常用的分類(lèi)器有五類(lèi)：(1)樸素貝葉斯分類(lèi)器，該分類(lèi)器具有收斂速度快的優(yōu)點(diǎn)，對(duì)樣本數(shù)量要求不高，可以適用于小樣本的學(xué)習(xí)。但是，該分類(lèi)假設(shè)數(shù)據(jù)條件獨(dú)立，難以有效學(xué)習(xí)數(shù)據(jù)之間的關(guān)聯(lián)信息^[4]；(2)邏輯回歸分類(lèi)器，該分類(lèi)器的最大優(yōu)點(diǎn)是支持增量學(xué)習(xí)，當(dāng)分類(lèi)器構(gòu)建完畢之后，后續(xù)如果又有了新樣本需要學(xué)習(xí)，可以采用在線梯度下降方法在原有分類(lèi)器的基礎(chǔ)上快速學(xué)習(xí)新的數(shù)據(jù)，而且，該分類(lèi)器的正則化模型較多，不要求數(shù)據(jù)之間相互獨(dú)立，但是該分類(lèi)器的分類(lèi)性能目前表現(xiàn)還不是很突出^[5]；(3)決策樹(shù)分類(lèi)器，該分類(lèi)器首先需要構(gòu)建一個(gè)屬性集合，決策樹(shù)基于屬性集合來(lái)做出一系列的決策，實(shí)現(xiàn)數(shù)據(jù)的分類(lèi)。該分類(lèi)器易于處理數(shù)據(jù)間的關(guān)聯(lián)信息，不限制數(shù)據(jù)是否異?；蛘呔€性可分。缺點(diǎn)是容易發(fā)生過(guò)擬合現(xiàn)象^[6]；(4)神經(jīng)網(wǎng)絡(luò)分類(lèi)器，該分類(lèi)器也對(duì)輸入數(shù)據(jù)沒(méi)有嚴(yán)格的要求，網(wǎng)絡(luò)的構(gòu)建比較靈活，但涉及參數(shù)較多，運(yùn)算效率偏低^[7]；(5)支持向量機(jī)（Support Vector Machine，SVM）分類(lèi)器，該分類(lèi)器為過(guò)擬合提供了好的理論保證，泛化能力較強(qiáng)，對(duì)于小樣本的學(xué)習(xí)尤其有效，分類(lèi)效果較好。該分類(lèi)器在學(xué)習(xí)非線性可分?jǐn)?shù)據(jù)時(shí)，需要先將數(shù)據(jù)映射到高維空間，使得高維空間的數(shù)據(jù)線性可分。常采用核函數(shù)來(lái)完成數(shù)據(jù)由低維到高維的映射^[8]。然而，當(dāng)數(shù)據(jù)維數(shù)較高時(shí)，核變換的復(fù)雜度較高，導(dǎo)致SVM的運(yùn)算效率偏低。

    為了提高SVM分類(lèi)器的運(yùn)算效率，本文提出一種結(jié)合本征分解和抽樣學(xué)習(xí)改進(jìn)的快速SVM分類(lèi)器，通過(guò)本征分解方法來(lái)降低低維空間向高維空間變換時(shí)核矩陣的維數(shù)，通過(guò)對(duì)訓(xùn)練樣本進(jìn)行抽樣學(xué)習(xí)來(lái)降低數(shù)據(jù)處理量，提高SVM分類(lèi)器的運(yùn)算效率。

1 SVM概述

    SVM是一種應(yīng)用廣泛的分類(lèi)器，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小原理進(jìn)行學(xué)習(xí)，具有泛化能力強(qiáng)的優(yōu)點(diǎn)，可以有效解決小樣本的學(xué)習(xí)難題，在高維特征分類(lèi)領(lǐng)域也有優(yōu)勢(shì)。

    依據(jù)訓(xùn)練數(shù)據(jù)的不同，可以將SVM分為線性SVM和非線性SVM兩類(lèi)，下面進(jìn)行簡(jiǎn)要介紹。

1.1 線性SVM

    當(dāng)訓(xùn)練數(shù)據(jù)線性可分時(shí)，可以采用線性SVM學(xué)習(xí)一個(gè)最優(yōu)的分類(lèi)面來(lái)進(jìn)行分類(lèi)。SVM的基本原理是：最優(yōu)分類(lèi)面既要能將兩類(lèi)樣本正確分開(kāi)，又要使得分類(lèi)間隔最大。

    SVM的學(xué)習(xí)可以看作一個(gè)最優(yōu)化問(wèn)題，可以表示為：

1.2 非線性SVM

    當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時(shí)，可以采用非線性SVM學(xué)習(xí)一個(gè)最優(yōu)分類(lèi)面。通常的解決方法是：采用一個(gè)非線性的映射函數(shù)將低維空間上線性不可分的數(shù)據(jù)映射到高維空間上，變成線性可分的數(shù)據(jù)。依據(jù)Hilbert-Schmidt原理，滿(mǎn)足Mercer條件的核函數(shù)可以代替高維空間上的點(diǎn)積運(yùn)算。因此，這里的關(guān)鍵是選擇一個(gè)合適的核函數(shù)來(lái)進(jìn)行數(shù)據(jù)映射。核函數(shù)可以表示為：

其中，f(·)表示映射函數(shù)，用于表示將低維空間上的數(shù)據(jù)映射到高維的核空間F上?？梢?jiàn)，核函數(shù)k(x_i，x_j)可以用高維空間上數(shù)據(jù)的乘積運(yùn)算來(lái)代替低維空間上數(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為正半定矩陣，通常可以通過(guò)本征分解來(lái)進(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)練樣本的子集來(lái)計(jì)算K的子矩陣，表示為：

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

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

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

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

    其中，特征提取和特征分類(lèi)是圖像分類(lèi)的關(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)行圖像分類(lèi)。特征分類(lèi)是本文的研究重點(diǎn)，本文所述方法是一種改進(jìn)的SVM分類(lèi)器，因此后續(xù)實(shí)驗(yàn)著重是將本文改進(jìn)的SVM分類(lèi)器與經(jīng)典SVM分類(lèi)器以及目前常用的一些分類(lèi)器進(jìn)行性能對(duì)比，具體將在后續(xù)實(shí)驗(yàn)部分詳述。

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

    圖像分類(lèi)領(lǐng)域的公開(kāi)測(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è)類(lèi)別的目標(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è)類(lèi)別的目標(biāo)圖像，目標(biāo)也存在尺度、視角及光照方面的變化，圖像數(shù)量為7 200幅，其中訓(xùn)練子集中包含圖像800幅，測(cè)試子集中包含圖像6 400幅。

    后續(xù)對(duì)比不同的特征提取和分類(lèi)方法時(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分類(lèi)器的分類(lèi)正確率和運(yùn)算效率。因此，這里的圖像分類(lèi)實(shí)驗(yàn)選用3個(gè)性能評(píng)價(jià)指標(biāo)，分別是分類(lèi)正確率、訓(xùn)練耗時(shí)和平均分類(lèi)耗時(shí)。其中，分類(lèi)正確率可以用分類(lèi)正確的圖像總數(shù)與測(cè)試數(shù)據(jù)集中的圖像總數(shù)的比值來(lái)表示，記為A_R。訓(xùn)練耗時(shí)指兩個(gè)數(shù)據(jù)集的整個(gè)訓(xùn)練過(guò)程所耗費(fèi)的總時(shí)間，記為T(mén)_T。平均分類(lèi)耗時(shí)可以用所有測(cè)試圖像的分類(lèi)耗時(shí)與圖像數(shù)量的比值來(lái)表示，記為T(mén)_C。需要說(shuō)明的是：分類(lèi)耗時(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開(kāi)發(fā)環(huán)境。

3.4 實(shí)驗(yàn)結(jié)果與對(duì)比分析

3.4.1 特征選擇對(duì)比

    下面首先對(duì)比采用不同特征時(shí)兩個(gè)數(shù)據(jù)集的圖像征分類(lèi)性能指標(biāo)，其中，圖2展示了分別采用Haar、HOG、LBP和SIFT 4種特征時(shí)的圖像分類(lèi)結(jié)果，分類(lèi)器采用的是本文改進(jìn)的SVM分類(lèi)器。其中，改進(jìn)SVM分類(lèi)器所用的核函數(shù)為徑向基函數(shù)，參數(shù)σ取值為0.5。

    由圖2可見(jiàn)，在分類(lèi)器相同的條件下，采用SIFT特征在兩個(gè)數(shù)據(jù)集上測(cè)試所得的圖像分類(lèi)正確率指標(biāo)都高于其他3種特征。這說(shuō)明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ù)不同，所得到的圖像分類(lèi)結(jié)果也不同。圖3展示了分別采用3種不同的核函數(shù)時(shí)得到的圖像分類(lèi)正確率指標(biāo)，其中，圖3(a)采用的是經(jīng)典的SVM分類(lèi)器，詳見(jiàn)文獻(xiàn)[8]；圖3(b)采用的是本文改進(jìn)的SVM分類(lèi)器。

    由圖3(a)和圖3(b)可見(jiàn)，對(duì)于兩個(gè)不同的數(shù)據(jù)集，不論是采用經(jīng)典的SVM分類(lèi)器還是采用本文改進(jìn)的SVM分類(lèi)器，都可以看出采用徑向基函數(shù)作為核函數(shù)得到的圖像分類(lèi)正確率指標(biāo)高于其他兩種核函數(shù)，因此，后續(xù)實(shí)驗(yàn)中經(jīng)典SVM分類(lèi)器和本文改進(jìn)的SVM分類(lèi)器都選擇徑向基函數(shù)作為核函數(shù)。

3.4.3 分類(lèi)器對(duì)比

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

    由圖4可見(jiàn)，本文改進(jìn)的SVM分類(lèi)器得到的圖像分類(lèi)正確率指標(biāo)略高于經(jīng)典的SVM分類(lèi)器，明顯高于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類(lèi)器。這說(shuō)明，相對(duì)于隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類(lèi)器，SVM分類(lèi)器的泛化能力更強(qiáng)，更適用于圖像分類(lèi)。同時(shí)，改進(jìn)的SVM采用本征分解降低了噪聲干擾，相對(duì)于經(jīng)典SVM分類(lèi)器其圖像分類(lèi)正確率指標(biāo)略有提升。由表1可見(jiàn)，本文改進(jìn)的SVM分類(lèi)器的訓(xùn)練耗時(shí)明顯低于其他3種分類(lèi)器，平均分類(lèi)耗時(shí)也明顯低于經(jīng)典SVM分類(lèi)器和神經(jīng)網(wǎng)絡(luò)分類(lèi)器，略高于隨機(jī)森林分類(lèi)器。這說(shuō)明，通過(guò)降維和抽樣處理，可以明顯提高SVM分類(lèi)器的分類(lèi)耗時(shí)。因此，綜合評(píng)價(jià)，本文改進(jìn)的SVM分類(lèi)器不僅提高了運(yùn)算效率，而且提高了分類(lèi)正確率。

4 結(jié)束語(yǔ)

    為了提高經(jīng)典支持向量機(jī)分類(lèi)器的運(yùn)算效率，本文提出了一種結(jié)合本征分解和抽樣學(xué)習(xí)改進(jìn)的快速SVM分類(lèi)器。主要是針對(duì)低維空間向高維空間變換時(shí)核矩陣運(yùn)算效率低的問(wè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分類(lèi)器的運(yùn)算效率。

    經(jīng)過(guò)優(yōu)化，不僅提高了SVM分類(lèi)器的運(yùn)算效率，也進(jìn)一步強(qiáng)化了SVM分類(lèi)器的泛化能力。通過(guò)將改進(jìn)的SVM分類(lèi)器與經(jīng)典的SVM分類(lèi)器以及常用的隨機(jī)森林、神經(jīng)網(wǎng)絡(luò)分類(lèi)器進(jìn)行圖像分類(lèi)對(duì)比實(shí)驗(yàn)，證明了改進(jìn)的SVM分類(lèi)器不僅分類(lèi)正確率高于經(jīng)典SVM、隨機(jī)森林和神經(jīng)網(wǎng)絡(luò)分類(lèi)器，而且訓(xùn)練耗時(shí)最少，平均分類(lèi)耗時(shí)也優(yōu)于經(jīng)典SVM分類(lèi)器，是一種快速可靠的分類(lèi)器。

參考文獻(xiàn)

[1] LIU Q.Kernel local sparse representation based classifier[J].Neural Processing Letters，2016，43(1)：123-137.

[2] 楊春，殷緒成，郝紅衛(wèi)，等.基于差異性的分類(lè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ù)的樸素貝葉斯分類(lèi)器依賴(lài)擴(kuò)展[J].控制與決策，2015，30(12)：2280-2284.

[5] 郭華平，董亞?wèn)|，鄔長(zhǎng)安，等.面向類(lèi)不平衡的邏輯回歸方法[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）