0 引言

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

    為了提高SVM分類器的運算效率，本文提出一種結合本征分解和抽樣學習改進的快速SVM分類器，通過本征分解方法來降低低維空間向高維空間變換時核矩陣的維數，通過對訓練樣本進行抽樣學習來降低數據處理量，提高SVM分類器的運算效率。

1 SVM概述

    SVM是一種應用廣泛的分類器，基于結構風險最小原理進行學習，具有泛化能力強的優點，可以有效解決小樣本的學習難題，在高維特征分類領域也有優勢。

    依據訓練數據的不同，可以將SVM分為線性SVM和非線性SVM兩類，下面進行簡要介紹。

1.1 線性SVM

    當訓練數據線性可分時，可以采用線性SVM學習一個最優的分類面來進行分類。SVM的基本原理是：最優分類面既要能將兩類樣本正確分開，又要使得分類間隔最大。

    SVM的學習可以看作一個最優化問題，可以表示為：

1.2 非線性SVM

    當訓練數據線性不可分時，可以采用非線性SVM學習一個最優分類面。通常的解決方法是：采用一個非線性的映射函數將低維空間上線性不可分的數據映射到高維空間上，變成線性可分的數據。依據Hilbert-Schmidt原理，滿足Mercer條件的核函數可以代替高維空間上的點積運算。因此，這里的關鍵是選擇一個合適的核函數來進行數據映射。核函數可以表示為：

其中，f(·)表示映射函數，用于表示將低維空間上的數據映射到高維的核空間F上。可見，核函數k(x_i，x_j)可以用高維空間上數據的乘積運算來代替低維空間上數據的點積運算。

    常用的核函數主要有3個，包括：

    (1)徑向基函數(Radial Basis Function，RBF)，可以表示為：

2 改進的非線性SVM

    數據的核變換可以構建一個核矩陣K∈R^N×N，表示為：

其中，F是指數據x映射到核空間F上的數據集，可以表示為：

    當數據維數較高時，核變換的運算效率偏低。為了提高核運算效率，本文考慮對核矩陣進行降維處理。考慮到核矩陣K為正半定矩陣，通?？梢酝ㄟ^本征分解來進行降維。因此，對于核空間F上的數據集F，可以分解為：

其中，L是由矩陣F的特征值構建的對角矩陣。這里，特征值按照從大到小的順序降序排列。U為對應的特征向量矩陣。

    這樣，低維空間上的數據x映射到高維空間之后對應的n維向量可以表示為：

    計算整個核矩陣仍然非常耗時，為了進一步提高運算效率，本文對訓練子集進行劃分，隨機挑選包含n個訓練樣本的子集來計算K的子矩陣，表示為：

3 實驗與分析

    分類器在圖像分類領域應用非常普遍，因此，本節通過圖像分類實驗來測試和評價本文所述的改進SVM分類器的性能。

3.1 圖像分類實驗流程

    圖像分類的基本流程如圖1所示。主要包括兩個階段：(1)分類器訓練階段，主要是對訓練數據集進行特征提取，依據先驗的圖像類別標簽來進行分類器的訓練；(2)圖像分類階段，對于待分類的圖像，先要提取圖像特征，然后結合訓練階段得到的分類器估計特征所屬的類別，得到圖像分類結果。

    其中，特征提取和特征分類是圖像分類的關鍵環節。特征提取是對圖像的抽象描述，常用的特征有Haar^[9]、方向梯度直方圖（Histogram of Oriented Gradient，HOG）^[10]、局部二元模式（Local Binary Pattern，LBP）^[11]和尺度不變特征轉換(Scale-Invariant Feature Transform，SIFT)^[12]等，本文將在后續實驗中對不同的特征進行定量評測，進而選擇最有效的特征進行圖像分類。特征分類是本文的研究重點，本文所述方法是一種改進的SVM分類器，因此后續實驗著重是將本文改進的SVM分類器與經典SVM分類器以及目前常用的一些分類器進行性能對比，具體將在后續實驗部分詳述。

3.2 實驗數據集

    圖像分類領域的公開測試的數據集比較多，本文選用目前常用的兩個測試數據集，分別是PASCAL VOC-2007和COIL-100數據集，簡要介紹如下。

    (1)PASCAL VOC-2007數據集

    該數據集包含20個類別的目標圖像，這些目標存在尺度、視角和光照方面的變化，數據集包含的圖像總數為9 963幅，其中訓練子集中包含圖像5 011幅，測試子集中包含圖像4 592幅。

    (2)COIL-100數據集

    該數據集包含100個類別的目標圖像，目標也存在尺度、視角及光照方面的變化，圖像數量為7 200幅，其中訓練子集中包含圖像800幅，測試子集中包含圖像6 400幅。

    后續對比不同的特征提取和分類方法時，分別在上述兩個數據集上進行訓練和測試，在相同的訓練數據集和測試數據集上統計各種方法的性能指標，以便于驗證本文方法的性能。

3.3 性能評價指標

    本文實驗的目的主要用于評價改進SVM分類器的分類正確率和運算效率。因此，這里的圖像分類實驗選用3個性能評價指標，分別是分類正確率、訓練耗時和平均分類耗時。其中，分類正確率可以用分類正確的圖像總數與測試數據集中的圖像總數的比值來表示，記為A_R。訓練耗時指兩個數據集的整個訓練過程所耗費的總時間，記為T_T。平均分類耗時可以用所有測試圖像的分類耗時與圖像數量的比值來表示，記為T_C。需要說明的是：分類耗時與計算機平臺性能有關。實驗時不同方法使用相同的計算機平臺進行測試。所有計算機平臺的性能參數為：3.2 GHz四核 Intel I5 CPU、16G DDR3內存、Windows 7 32位操作系統、Visual Studio 2010開發環境。

3.4 實驗結果與對比分析

3.4.1 特征選擇對比

    下面首先對比采用不同特征時兩個數據集的圖像征分類性能指標，其中，圖2展示了分別采用Haar、HOG、LBP和SIFT 4種特征時的圖像分類結果，分類器采用的是本文改進的SVM分類器。其中，改進SVM分類器所用的核函數為徑向基函數，參數σ取值為0.5。

    由圖2可見，在分類器相同的條件下，采用SIFT特征在兩個數據集上測試所得的圖像分類正確率指標都高于其他3種特征。這說明SIFT特征優于其他3種特征，因此，后續的實驗中在特征提取階段都采用SIFT特征對圖像進行描述。

3.4.2 核函數選擇對比

    本文1.2節列出了3種常用的核函數，分別是徑向基函數（RBF）、二層神經網絡函數（Sigmoid）和多項式函數（Polynomial）。采用的核函數不同，所得到的圖像分類結果也不同。圖3展示了分別采用3種不同的核函數時得到的圖像分類正確率指標，其中，圖3(a)采用的是經典的SVM分類器，詳見文獻[8]；圖3(b)采用的是本文改進的SVM分類器。

    由圖3(a)和圖3(b)可見，對于兩個不同的數據集，不論是采用經典的SVM分類器還是采用本文改進的SVM分類器，都可以看出采用徑向基函數作為核函數得到的圖像分類正確率指標高于其他兩種核函數，因此，后續實驗中經典SVM分類器和本文改進的SVM分類器都選擇徑向基函數作為核函數。

3.4.3 分類器對比

    為了驗證本文改進的SVM分類器的性能，下面采用不同的分類器進行對比實驗。圖4展示了分別采用經典SVM分類器、隨機森林分類器、神經網絡分類器和本文改進的SVM分類器得到的圖像分類正確率指標。表1展示了對應的平均分類耗時指標。

    由圖4可見，本文改進的SVM分類器得到的圖像分類正確率指標略高于經典的SVM分類器，明顯高于隨機森林和神經網絡分類器。這說明，相對于隨機森林和神經網絡分類器，SVM分類器的泛化能力更強，更適用于圖像分類。同時，改進的SVM采用本征分解降低了噪聲干擾，相對于經典SVM分類器其圖像分類正確率指標略有提升。由表1可見，本文改進的SVM分類器的訓練耗時明顯低于其他3種分類器，平均分類耗時也明顯低于經典SVM分類器和神經網絡分類器，略高于隨機森林分類器。這說明，通過降維和抽樣處理，可以明顯提高SVM分類器的分類耗時。因此，綜合評價，本文改進的SVM分類器不僅提高了運算效率，而且提高了分類正確率。

4 結束語

    為了提高經典支持向量機分類器的運算效率，本文提出了一種結合本征分解和抽樣學習改進的快速SVM分類器。主要是針對低維空間向高維空間變換時核矩陣運算效率低的問題進行改進：對核矩陣進行降維處理，采用本征分解方法得到核矩陣的近似表示，提高核矩陣的運算效率；在表示低維的核矩陣時，采用抽樣學習的思想，先對訓練數據進行劃分，隨機抽樣一個數量很小的訓練樣本子集進行學習，進一步降低了數據量，進而提高了SVM分類器的運算效率。

    經過優化，不僅提高了SVM分類器的運算效率，也進一步強化了SVM分類器的泛化能力。通過將改進的SVM分類器與經典的SVM分類器以及常用的隨機森林、神經網絡分類器進行圖像分類對比實驗，證明了改進的SVM分類器不僅分類正確率高于經典SVM、隨機森林和神經網絡分類器，而且訓練耗時最少，平均分類耗時也優于經典SVM分類器，是一種快速可靠的分類器。

參考文獻

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

[2] 楊春，殷緒成，郝紅衛，等.基于差異性的分類器集成：有效性分析及優化集成[J].自動化學報，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] 王雙成，高瑞，杜瑞杰.基于高斯核函數的樸素貝葉斯分類器依賴擴展[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，李衛平1，2

（1.鐵道警察學院 公安技術系，河南 鄭州450000；2.武漢理工大學 信息工程學院，湖北 武漢430070）