《電子技術應用》
您所在的位置：首頁 > 嵌入式技術 > 設計應用 > 結合本征分解和抽樣學習的快速SVM分類器
結合本征分解和抽樣學習的快速SVM分類器
2017年電子技術應用第9期
武海燕1，李衛(wèi)平1，2
1.鐵道警察學院 公安技術系，河南 鄭州450000；2.武漢理工大學 信息工程學院，湖北 武漢430070
摘要： 為了提高經(jīng)典支持向量機（SVM）分類器的運算效率，提出一種改進的快速SVM分類器。針對低維空間向高維空間變換時核矩陣運算效率低的問題，采用本征分解方法對核矩陣進行降維處理，得到核矩陣的近似表示；同時，對訓練子集進行劃分，隨機抽樣訓練樣本進行學習，進一步提高SVM分類器的運算效率。圖像分類實驗結果表明，改進的SVM分類器不僅分類正確率高于經(jīng)典SVM、隨機森林和神經(jīng)網(wǎng)絡分類器，而且訓練耗時最少，平均分類耗時也低于經(jīng)典SVM分類器。
中圖分類號： TP391
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.170174
中文引用格式： 武海燕，李衛(wèi)平. 結合本征分解和抽樣學習的快速SVM分類器[J].電子技術應用，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.
A fast SVM classifier combined with Eigen decomposition and sample-learning
Wu Haiyan1，Li Weiping1，2
1.Department of Public Security Technology，Railway Police College，Zhengzhou 450000，China； 2.School of Information Engineering，Wuhan University of Technology，Wuhan 430070，China
Abstract： In order to improve the efficiency of classic support vector machine(SVM) classifier, an improved fast SVM classifier is proposed. For solving the low efficiency problem of kernel matrix operations in the process of transforming low-dimensional space to high-dimensional one, it uses Eigen decomposition method to reduce the dimension of kernel matrix and obtains the approximate representation of the kernel matrix. Meanwhile, it divides the training subset and random sample the subset for learning, further improves the efficiency of SVM classifier. Experimental results of image classification show that, the improved SVM classifier has not only higher accuracy classification rate than classic SVM, random forests and neural network classifiers, but also least time-consuming on training, and less mean classification time-consuming than classical SVM classifier.
Key words : support vector machine；Eigen decomposition；kernel matrix；radial basis function；image classification

0 引言

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

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

1 SVM概述

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

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

1.1 線性SVM

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

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

jsj5-gs1-4.gif

1.2 非線性SVM

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

    jsj5-gs5.gif

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

    常用的核函數(shù)主要有3個，包括：

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

jsj5-gs6-10.gif

2 改進的非線性SVM

    數(shù)據(jù)的核變換可以構建一個核矩陣K∈RN×N，表示為：

    jsj5-gs11.gif

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

    jsj5-gs12.gif

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

    jsj5-gs13.gif

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

jsj5-gs14.gif

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

jsj5-gs15-16.gif

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

jsj5-gs17-29.gif

3 實驗與分析

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

3.1 圖像分類實驗流程

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

jsj5-t1.gif

    其中，特征提取和特征分類是圖像分類的關鍵環(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ù)實驗中對不同的特征進行定量評測，進而選擇最有效的特征進行圖像分類。特征分類是本文的研究重點，本文所述方法是一種改進的SVM分類器，因此后續(xù)實驗著重是將本文改進的SVM分類器與經(jīng)典SVM分類器以及目前常用的一些分類器進行性能對比，具體將在后續(xù)實驗部分詳述。

3.2 實驗數(shù)據(jù)集

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

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

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

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

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

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

3.3 性能評價指標

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

3.4 實驗結果與對比分析

3.4.1 特征選擇對比

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

jsj5-t2.gif

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

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

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

jsj5-t3.gif

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

3.4.3 分類器對比

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

jsj5-t4.gif

jsj5-b1.gif

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

4 結束語

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

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

參考文獻

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

[2] 楊春，殷緒成，郝紅衛(wèi)，等.基于差異性的分類器集成：有效性分析及優(yōu)化集成[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] 王雙成，高瑞，杜瑞杰.基于高斯核函數(shù)的樸素貝葉斯分類器依賴擴展[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.鐵道警察學院 公安技術系，河南 鄭州450000；2.武漢理工大學 信息工程學院，湖北 武漢430070）

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉(zhuǎn)載。