基于自然紋理識(shí)別的分類器算法設(shè)計(jì)研究

廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 孟可然

廣州中智融通金融科技有限公司 吳衛(wèi)增 張 偉

廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 周延周

0 引言

自然紋理識(shí)別是機(jī)器學(xué)習(xí)的一種，讓計(jì)算機(jī)具有像人類一樣的學(xué)習(xí)和理解能力，可以對(duì)新的對(duì)象樣本做出它自己的判斷，并要求有一定的準(zhǔn)確率。它是一個(gè)多種學(xué)科綜合的一種科學(xué)學(xué)科，包括了機(jī)器視覺、數(shù)字圖像處理、機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)學(xué)、凸理論分析等多個(gè)領(lǐng)域的知識(shí)。機(jī)器學(xué)習(xí)其實(shí)就是一種對(duì)未知的模型的逼近，由于真實(shí)模型是未知的，所以要讓計(jì)算機(jī)學(xué)會(huì)如何去選擇一個(gè)最優(yōu)的模型。而分類器正是一個(gè)選擇最優(yōu)解的手段，并且一個(gè)好的分類器對(duì)其泛化能力和推廣能力有較高的要求。

自然紋理識(shí)別的系統(tǒng)包含兩個(gè)部分：圖像特征信息提取和圖像識(shí)別。通過將圖像提取主成分并降維成低維表示，然后讓計(jì)算機(jī)使用分類器對(duì)它們進(jìn)行分類并學(xué)習(xí)，當(dāng)下次遇到新的樣本時(shí)通過先前分類后的情況對(duì)新的樣本進(jìn)行判斷，這是圖像識(shí)別的常用流程，而且一般來說，分類器的推廣能力和準(zhǔn)確度是隨著訓(xùn)練樣本的增加而增強(qiáng)的。

1 機(jī)器學(xué)習(xí)中的常用分類器

上一章已經(jīng)對(duì)圖像特征信息提取方面進(jìn)行了介紹，本章將對(duì)機(jī)器學(xué)習(xí)中的常用分類器做簡(jiǎn)單的介紹，包括貝葉斯分類器，最近鄰分類器，人工神經(jīng)網(wǎng)絡(luò)分類器，并對(duì)本文使用到的支持向量機(jī)做原理剖析和步驟解釋。

1.1 貝葉斯分類器

貝葉斯分類器是統(tǒng)計(jì)學(xué)的一種表現(xiàn)，它的主要思想是：根據(jù)經(jīng)驗(yàn)和歷史數(shù)據(jù)分析計(jì)算出某對(duì)象的概率，然后通過貝葉斯分類器和先驗(yàn)概率得到其后驗(yàn)概率，再選擇后驗(yàn)概率最大的類別作為對(duì)象的類別。其中，先驗(yàn)概率的計(jì)算是根據(jù)目前僅有的資源而非全部相關(guān)資源進(jìn)行計(jì)算的，后驗(yàn)概率的計(jì)算則包含了更多的資源作為參考，包括計(jì)歷史和經(jīng)驗(yàn)的資源，還有后來添加的資源。

貝葉斯分類器的計(jì)算使用的是貝葉斯公式：

描述為在A時(shí)間發(fā)生的條件下Bi事件發(fā)生的概率。

貝葉斯分類的使用一般包含兩個(gè)步驟，第一個(gè)步驟是進(jìn)行分類器的構(gòu)造，依據(jù)的是輸入的訓(xùn)練樣本，并還將對(duì)分類器的結(jié)構(gòu)進(jìn)行學(xué)習(xí)，類比于機(jī)器學(xué)習(xí)中的第一步。第二個(gè)步驟是分類器的運(yùn)用（即使用其進(jìn)行分類），依據(jù)是通過計(jì)算得來類結(jié)點(diǎn)的條件概率來決定被分入哪個(gè)類別。在現(xiàn)實(shí)中應(yīng)用中，這兩個(gè)步驟通常都具有非常高的復(fù)雜度，因?yàn)樗鼈兣c特征值的關(guān)系非常密切，所以在使用時(shí)一般給予簡(jiǎn)化。

1.2 最近鄰分類器

最鄰近算法是機(jī)器學(xué)習(xí)中最為簡(jiǎn)單且成熟的算法。它的基本思想是用最鄰近的一個(gè)或者多個(gè)樣本來分類一個(gè)新的樣本，而新的樣本一般具有臨近樣本的特征。最鄰近算法分類主要是根據(jù)相關(guān)的鄰近樣本，而非類別域，故它在重復(fù)性比較高的類域情況下也有著較好的分類質(zhì)量。

度量距離的公式為：

1.3 人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)從上世紀(jì)80年代開始就一直成為人工智能領(lǐng)域發(fā)展和研究的熱點(diǎn)。它使用將大量的簡(jiǎn)單的處理單元聯(lián)系起來構(gòu)成復(fù)雜的數(shù)據(jù)處理網(wǎng)絡(luò)，由此計(jì)算計(jì)算量巨大的問題。人工神經(jīng)網(wǎng)絡(luò)的最終輸出值取決于該網(wǎng)絡(luò)的連接方式，連接方式不同則將會(huì)影響處理單元的順序，最終導(dǎo)致計(jì)算值的不同。

人工神經(jīng)網(wǎng)絡(luò)一般可以分為兩大類，分別是前向網(wǎng)絡(luò)和反饋網(wǎng)絡(luò)。前向網(wǎng)絡(luò)即是一種不包含反饋的網(wǎng)絡(luò)，每個(gè)結(jié)點(diǎn)都接收前一個(gè)單元的輸入并經(jīng)過本單元運(yùn)算輸出給下一級(jí)，前向網(wǎng)絡(luò)的特點(diǎn)是比較簡(jiǎn)單，容易實(shí)現(xiàn)。反饋網(wǎng)絡(luò)即是神經(jīng)網(wǎng)絡(luò)中包含反饋且具有聯(lián)想儲(chǔ)存的功能，特點(diǎn)是實(shí)現(xiàn)較為復(fù)雜人工神經(jīng)網(wǎng)絡(luò)在具有多種模型，其中的BP神經(jīng)網(wǎng)絡(luò)模型應(yīng)用最為廣泛且效果較好。

2 支持向量機(jī)簡(jiǎn)介

支持向量機(jī)(Support Vector Machine)在1995年首次被Cortes和Vapnik[1]所提出，它的優(yōu)勢(shì)體現(xiàn)在很多方面、包括具有高維特性、小樣本特性和非線性問題上，它還可以被推廣到其他很多的機(jī)器學(xué)習(xí)應(yīng)用中。支持向量機(jī)的理論基礎(chǔ)是建立在統(tǒng)計(jì)學(xué)的知識(shí)體系上的，其中作為主要原理的是VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小理論。其主要思想是：通過對(duì)樣本的分析和學(xué)習(xí)，尋找一個(gè)最優(yōu)的超平面，將兩類樣本的分類間隔最大化。

支持向量機(jī)有三大優(yōu)勢(shì)，第一是在其處理問題只關(guān)注VC維且與樣本的維數(shù)無關(guān)，它只尋找它所需的少數(shù)支持向量，所以它在高維數(shù)的分類中依舊可以有較好的表現(xiàn)。第二，由于支持向量機(jī)引進(jìn)了核函數(shù)和松弛變量[2]，使得它在樣本非線性情況下具有優(yōu)越性。第三，支持向量機(jī)的算法需要的樣本數(shù)相比于其他算法所需要的樣本數(shù)是相對(duì)比較小的。由于支持向量機(jī)三個(gè)顯著的優(yōu)勢(shì)，其被廣泛的應(yīng)用于各種識(shí)別應(yīng)用中。下面將對(duì)支持向量機(jī)的原理進(jìn)行剖析，其中將介紹線性SVM分類器、非線性SVM分類中的核函數(shù)和松弛變量以及應(yīng)用于SVM在多類分類中的方法。

3 支持向量機(jī)原理

3.1 線性SVM分類器

支持向量機(jī)與線性分類器的關(guān)系密不可分，支持向量機(jī)在處理低維非線性以致高維非線性的問題時(shí)，都是將其從非線性轉(zhuǎn)化為類線性的進(jìn)行處理的。線性分類器是最簡(jiǎn)單有效的分類器[3]，它的思想是尋找一個(gè)線性函數(shù)（即分類函數(shù)）將樣本分成兩類。如果樣本能夠被此線性函數(shù)完全分開，那么樣本就是線性可分的，反之則線性不可分。如圖1所示：

圖1 線性分類

圖中圈代表一類樣本，叉代表一類樣本，中間的直線便是分類函數(shù)，此樣本集便是線性可分的。

由此可以定義線性函數(shù)為：

w為權(quán)向量，x為輸入，b為閾值。在二維情況下，線性函數(shù)如上圖是一條直線，但在三維情況下，線性函數(shù)就變成了一個(gè)平面，在更高維的情況下時(shí)，線性函數(shù)就是一個(gè)超平面。當(dāng)取判斷閾值為0來判別樣本屬于哪個(gè)類時(shí)，就只需要將樣本帶入g(x)中去計(jì)算，若g(x)大于0則表明其屬于一個(gè)類，當(dāng)g(x)小于0則屬于另一個(gè)類?？梢钥吹骄€性函數(shù)并不是唯一的，若直線旋轉(zhuǎn)一點(diǎn)角度，依舊可以將兩個(gè)樣本分開，找到一個(gè)最優(yōu)的線性函數(shù)能夠最大程度的將兩類樣本分開成為了最重要的問題。因此SVM分類器的思想就在此體現(xiàn)：找到一個(gè)線性函數(shù)能使樣本之間的分類間隔最大化，分類間隔越大，說明該線性函數(shù)的分類效果越好，反之，則越差。

當(dāng)我們將樣本輸入給計(jì)算機(jī)進(jìn)行訓(xùn)練時(shí)，每個(gè)樣本的表示形式是這樣的：

其中y是標(biāo)簽值（設(shè)為1或者-1），即用來表示該樣本屬于哪個(gè)類別的標(biāo)記，x是表示樣本的向量。則一個(gè)樣本點(diǎn)到某超平面的距離可以表示為：

再使用歸一化對(duì)其進(jìn)行變換（使用w的范數(shù)||w||），則距離可以表示成：

用歸一化的方式來表示的距離被稱為幾何間隔，是點(diǎn)到超平面的歐式距離。則上述兩個(gè)公式又可以表示為：

由于SVM的目標(biāo)是找到一個(gè)分類平面使得分類間隔最大，等同于數(shù)學(xué)上的一個(gè)求最優(yōu)解的問題。如圖2所示，設(shè)H是分類超平面，其中H1和H2與H平行，且H1和H2是過離分類超平面最近的樣本做的平面。H1和H2到H的距離就是幾何距離。

圖2 幾何間隔示意圖

在數(shù)學(xué)的求解上，通常將L設(shè)為1，使得幾何間隔和||w||成反比，求幾何間隔最大，即求||w||的最小值。根據(jù)上述條件，又因?yàn)槊總€(gè)樣本都要滿足在最大分隔距離之外（即），所以目標(biāo)函數(shù)變?yōu)橐粋€(gè)帶約束的最優(yōu)解問題：

在求解這類帶多個(gè)約束的最優(yōu)問題時(shí)，一般將約束的不等情況取極端情況，也就是等于的情況。即向問題中添加拉格朗日乘子并構(gòu)造出拉格朗日函數(shù)得以將問題轉(zhuǎn)化為一個(gè)求無約束的求最優(yōu)解問題：

最后求得的分類平面函數(shù)為：

以上就是線性SVM分類器的原理。

3.2 非線性SVM分類器

在現(xiàn)實(shí)中，絕大部分分類問題都是非線性的，樣本正好呈現(xiàn)線性分類的情況少之又少。在紋理識(shí)別中也是如此，樣本被降維后仍然是一堆非線性的集合，但如果不進(jìn)行分類，計(jì)算機(jī)將無法進(jìn)行學(xué)習(xí)，識(shí)別也就無從而談。而為了解決非線性的分類問題SVM引入了核函數(shù)，和松弛變量進(jìn)行處理。當(dāng)?shù)途S的形式下的樣本不呈線性時(shí)，將其轉(zhuǎn)化為高維則可以線性表達(dá)。

圖3 非線性分類示意圖

如圖3所示，當(dāng)樣本分布為一條直線時(shí)，A和B點(diǎn)之間是一個(gè)類別，其余是另一個(gè)類別。此時(shí)要找一條直線將其分成兩個(gè)類別是不可行。設(shè)可以找到一條曲線，將兩個(gè)類別分開。其中曲線以上是一個(gè)類別，曲線以下是另一個(gè)類別。則該曲線的函數(shù)為：

可以看到此分類函數(shù)并不是一個(gè)線性函數(shù)，但可以新建向量y和a來表示g(x)，即：

4 SVM在多類分類的方法

對(duì)訓(xùn)練樣本訓(xùn)練完后，就要進(jìn)行分類的動(dòng)作。在自然紋理識(shí)別中，通常會(huì)有多個(gè)樣本，那么分類就是對(duì)多類而言的。SVM在多類分類的情況下有一對(duì)多和一對(duì)一兩種策略。

4.1 一對(duì)多的分類

一對(duì)多分類的思想就是：對(duì)樣本依次進(jìn)行屬于單個(gè)類與其他類的判斷并投票，將分類器對(duì)單個(gè)類做出相應(yīng)并間隔為最大的類別作為分類類別。現(xiàn)有五個(gè)類型A,B,C,D,E，一個(gè)新輸入的樣本O。依次對(duì)樣本進(jìn)行A與BCDE類，B與ACDE類，C與ABDE類，D與ABCE類，E與ABCD類的判斷，若分類器做出的判斷為屬于A類，又屬于C類，但在A類情況時(shí)樣本距離分類線的間隔比C類的大，那么給類別則被判定為A類。該方法的優(yōu)點(diǎn)是當(dāng)條件理想時(shí)，只需要進(jìn)行N（N為類別數(shù)目）次的分類器判斷就可以得到結(jié)果。但上述方法有個(gè)缺點(diǎn)就是，若每次分類器都判定給其他類時(shí)，將得不到結(jié)果。

4.2 一對(duì)一的分類

一對(duì)一分類的就是依次對(duì)任意兩個(gè)類別進(jìn)行判斷，每次都讓分類器做出判斷并給其中一個(gè)類別投票，最終投票最多的那個(gè)類別就確定為分類類別。這種分類方法共需要N(N-1)/2個(gè)分類器，判斷的次數(shù)比一對(duì)多的分類方法要多。這種分類方法的缺點(diǎn)，其一的泛化誤差不存在上界。其二，由于分類器數(shù)量隨著N的數(shù)量增加而增加，當(dāng)數(shù)量很大時(shí)，判斷速度會(huì)很慢。其三，這種判斷方法會(huì)使測(cè)試樣本受到非所屬類別的影響，因?yàn)榧幢阍诓粚儆谂袆e類型的分類器中也需要給出投票。

[1]VAPNIK V.Statistical learning theory[M].New York：Wiley,1998.

[2]趙文嵩.SVM在多類問題中的應(yīng)用及推廣[D].聊城大學(xué),2014.

[3]李艷芳.線性判別式的比較與優(yōu)化方法研究[D].華東理工大學(xué),2015.

[4]張婧婧.復(fù)雜網(wǎng)絡(luò)中心化的研究[D].西安理工大學(xué),2007.