基于樸素貝葉斯與半樸素貝葉斯圖像識(shí)別比較

劉 闖

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023)

0 引言

圖像識(shí)別技術(shù)[1]指的是使用計(jì)算機(jī)對(duì)圖像進(jìn)行相應(yīng)處理、分析以及理解，以此來識(shí)別出不同模式的目標(biāo)和對(duì)象的一種技術(shù)。根據(jù)對(duì)圖像的觀測，對(duì)圖像中的事物分辨其所屬類別，做出清晰的判斷。通過利用現(xiàn)代信息處理以及計(jì)算技術(shù)的方式，來模擬和完成人腦對(duì)于外物的認(rèn)識(shí)以及理解的過程。一般來說，常見的圖像識(shí)別系統(tǒng)主要由三個(gè)模塊組成，分別是：圖像切割、提取圖像特征以及選擇分類器。

貝葉斯分類算法[2]是統(tǒng)計(jì)學(xué)中一種常用的分類方法，其主要是利用概率論統(tǒng)計(jì)里的知識(shí)進(jìn)行分類的算法。而基于條件獨(dú)立性假設(shè)情況下的樸素貝葉斯分類器(Naive Bayes Classifier,NBC)有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)以及相對(duì)穩(wěn)定的對(duì)事物的分類效率。樸素貝葉斯分類算法在某些場景下可以與決策樹算法以及神經(jīng)網(wǎng)絡(luò)分類算法相媲美，該算法也能夠運(yùn)用到大型數(shù)據(jù)庫中，并且其擁有方法簡單、分類準(zhǔn)確率相對(duì)較高、執(zhí)行速度快等優(yōu)點(diǎn)。同時(shí)，NBC模型所需估計(jì)的參數(shù)相對(duì)較少，對(duì)某些缺失的數(shù)據(jù)不太敏感，從理論上來說，NBC模型與其他一些分類方法相比較而言，其具有最小的誤差率。

本質(zhì)上來說，圖像識(shí)別同樣是一個(gè)分類問題，通過使用樸素貝葉斯分類器將包含人體行為的圖像進(jìn)行識(shí)別分類,從而能夠有效地識(shí)別出所測圖像中的個(gè)體行為。而半樸素貝葉斯分類器(SEMI-NBC)[3]是在樸素貝葉斯分類器的基礎(chǔ)之上對(duì)其的一種改進(jìn)，由于樸素貝葉斯分類器對(duì)于屬性條件獨(dú)立性[4]進(jìn)行了前提假設(shè)，但是在現(xiàn)實(shí)生活中，這類前提假設(shè)往往是難以成立的，因此人們嘗試對(duì)這種前提假設(shè)進(jìn)行一定程度上的放松，由此產(chǎn)生了半樸素貝葉斯分類器。半樸素貝葉斯分類器的基本設(shè)想是適當(dāng)?shù)乜紤]部分屬性之間的相互依賴信息，從而既不需要計(jì)算其完全聯(lián)合概率，又不至于完全忽略相對(duì)較強(qiáng)的屬性之間的依賴關(guān)系，其中半樸素貝葉斯分類器最常用的一種思路是獨(dú)依賴估計(jì)(One-Dependent Estimator)[5]。本文討論了NBC和SEMI-NBC分類技術(shù),將NBC和SEMI-NBC應(yīng)用到圖像識(shí)別上,對(duì)兩種算法的準(zhǔn)確率判定和執(zhí)行時(shí)間進(jìn)行比較。

1 樸素貝葉斯分類器NBC

樸素貝葉斯分類器是一類以貝葉斯定理與條件獨(dú)立性假設(shè)為前提的分類方法，對(duì)于所給定的訓(xùn)練集，首先基于特征條件獨(dú)立性的假設(shè)計(jì)算出輸入/輸出的聯(lián)合概率分布，然后基于所得到的數(shù)據(jù)，對(duì)于所給定的輸入數(shù)據(jù)x，再利用貝葉斯定理計(jì)算出后驗(yàn)概率為最大的輸出y。樸素貝葉斯分類器實(shí)現(xiàn)起來相對(duì)簡單，學(xué)習(xí)與預(yù)測出正確的結(jié)果的概率都很高。

設(shè)輸入空間x∈Rn是n維向量的一個(gè)集合，輸出空間是類標(biāo)記集合y={c1,c2，…，ck}。輸入是特征向量x∈x，輸出為類標(biāo)記y∈y。X是定義在輸入空間x中的隨機(jī)變量，Y是定義在輸出空間y中的隨機(jī)變量，其中P(X,Y)是X與Y的聯(lián)合概率分布。

(1)

j=1,2,…,n;l=1,2,…,Sj;k=1,2,…,K

(2)

k=1,2,…，K

(3)

然后再根據(jù)公式確定輸入x的類別：

(4)

但是當(dāng)使用極大似然估計(jì)法時(shí)，可能會(huì)出現(xiàn)所需估計(jì)的概率值為0的情況，這時(shí)會(huì)影響到接下來后驗(yàn)概率的計(jì)算結(jié)果，從而使分類結(jié)果產(chǎn)生偏差，而解決這種情況的方法是采用貝葉斯估計(jì)，具體操作為：先計(jì)算條件概率的貝葉斯估計(jì)：

P(X(j)=ajl|Y=ck)=

(5)

其中，λ≥0，等價(jià)于在隨機(jī)變量各個(gè)取值的頻數(shù)上賦一個(gè)正數(shù)值λ≥0。當(dāng)λ=0時(shí)就被稱為極大似然估計(jì)。常取λ=1,這時(shí)這個(gè)等式稱為拉普拉斯平滑，從而，對(duì)任何l=1,2,…,Sj;k=1,2,…,K,有:

Pλ(X(j)=ajl|Y=ck)>0

(6)

(7)

表明上式所計(jì)算的條件概率貝葉斯估計(jì)確實(shí)為一種概率分布。同樣地，先驗(yàn)概率的貝葉斯估計(jì)調(diào)整為：

(8)

從而得到分類函數(shù)為：

(9)

最終將輸入x分到后驗(yàn)概率最大的類y中，后驗(yàn)概率最大與0-1損失函數(shù)的期望風(fēng)險(xiǎn)最小化是相等價(jià)的。假設(shè)選擇0-1損失函數(shù)：

(10)

式中f(X)是分類決策函數(shù)，此時(shí)，得到的期望風(fēng)險(xiǎn)函數(shù)為：

Rexp(f)=E[L(Y,f(x))]

(11)

其中期望是對(duì)聯(lián)合分布函數(shù)P(X,Y)所取的，由此可以得出條件期望為：

(12)

為了最小化期望風(fēng)險(xiǎn)，只需要對(duì)X=x的值逐個(gè)極小化，由此得到：

(13)

因此，通過期望風(fēng)險(xiǎn)最小化準(zhǔn)則轉(zhuǎn)化也就得到了后驗(yàn)概率最大化的準(zhǔn)則：

(14)

這就是樸素貝葉斯分類器所采用的基本原理[6]。

2 半樸素貝葉斯分類器SEMI-NBC

由于樸素貝葉斯分類器是基于屬性條件獨(dú)立性為前提的假設(shè)，然而，在現(xiàn)實(shí)生活中，這種假設(shè)往往是很難成立的，所以，人們試著對(duì)屬性條件獨(dú)立性這一假設(shè)進(jìn)行某種程度上的放松，因此產(chǎn)生了半樸素貝葉斯分類器這一類型。

半樸素貝葉斯分類器的基本思路是，首先適當(dāng)考慮部分屬性之間的相互依賴關(guān)系，從而既不需要先計(jì)算完全的聯(lián)合概率，也不會(huì)徹底忽視了較強(qiáng)的相關(guān)屬性之間的依賴關(guān)系[7]。而獨(dú)依賴估計(jì)是在半樸素貝葉斯分類器中的一種比較常用的策略，即首先假設(shè)在類別之外，每個(gè)屬性最多僅依賴于另外一個(gè)其他屬性，即：

(15)

其中，px(j)表示為屬性x(j)所依賴的屬性，為x(j)的父屬性。接下來，對(duì)于每個(gè)屬性x(j)，假如其父屬性px(j)都是已知的，即可以求出相對(duì)應(yīng)的概率值，那么，接下來的問題就是如何確定每一個(gè)屬性的父屬性，而采用不同的策略會(huì)產(chǎn)生不同的獨(dú)依賴分類器，如圖1所示。

圖1 樸素貝葉斯與兩種半樸素貝葉斯分類器屬性依賴關(guān)系

其中，最直觀的做法是首先假設(shè)所有的屬性都通通依賴于同一個(gè)屬性，這種做法稱之為超父(Super-Parent)，接下來使用交叉驗(yàn)證等模型方法來確定其超父屬性，這就是所謂的SPODE(Super-parent ODE)方法。而TAN(Tree Augments Naive Bayes)則是在最大帶權(quán)生成樹(Maximum Weighted Spanning Tree)算法的基礎(chǔ)之上，通過下述步驟將不同屬性之間的相互依賴關(guān)系構(gòu)建成如圖1所示的樹形結(jié)構(gòu)。

(1)計(jì)算任意兩個(gè)屬性節(jié)點(diǎn)之間的條件互信息[8]：

I(xi，xj|y)=

(16)

(2)把屬性作為節(jié)點(diǎn)構(gòu)建完全圖，任意兩個(gè)節(jié)點(diǎn)間的權(quán)重設(shè)為I(xi,xj|y)；

(3)以所構(gòu)建的完全圖構(gòu)建最大帶權(quán)生成樹，然后挑選根變量，將邊置為有向；

(4)加入分類節(jié)點(diǎn)y，增加從y節(jié)點(diǎn)到每個(gè)屬性節(jié)點(diǎn)間的有向邊。

由上述表明，條件互信息I(xi,xj|y)這一定義刻畫了在已知類別情況下的屬性xi和xj間的相關(guān)性，所以，通過最大生成樹這一算法，TAN產(chǎn)生的結(jié)果是留下了強(qiáng)相關(guān)性屬性間的相互依賴性。本文采用SPODE方法作為此半樸素貝葉斯分類器核心思想[9]。

3 圖像識(shí)別方法流程

使用NBC的圖像識(shí)別方法與使用其他機(jī)器學(xué)習(xí)方法流程基本上是一樣的，它們都是利用對(duì)訓(xùn)練數(shù)據(jù)先進(jìn)行學(xué)習(xí)得到其分類模型,再利用所得到的分類模型來對(duì)待分類的數(shù)據(jù)進(jìn)行判斷。不同的是,某些分類器所輸出的結(jié)果是一個(gè)數(shù)值,比如決策樹、SVM等。而有些分類算法輸出的結(jié)果是一個(gè)概率值,比如樸素貝葉斯(NBC)、神經(jīng)網(wǎng)絡(luò)(NN)等。不管是哪種分類器都可以將數(shù)據(jù)進(jìn)行分類。本文將利用樸素貝葉斯對(duì)圖像中的人體行為進(jìn)行四分類識(shí)別,即輸出值是{0，1，2，3}。基于NBC與SEMI-NBC的圖像識(shí)別方法如圖2所示。

圖2 基于NBC與SEMI-NBC的圖像識(shí)別

在此方法中，首先對(duì)獲取的圖像進(jìn)行預(yù)處理，包括將圖像數(shù)值化、特征選擇提取等。數(shù)據(jù)特征選擇的目的是為了降低維數(shù),有利于提高計(jì)算效率。

常見的模式識(shí)別[10]流程主要包含樣本采集、數(shù)據(jù)預(yù)處理、特征選擇與提取、特征變換與分類器。而實(shí)驗(yàn)樣本采用了KTH activity數(shù)據(jù)庫的圖像，該數(shù)據(jù)庫包含6個(gè)動(dòng)作，分別為走、慢跑、揮手、打拳、拍手、快跑，每個(gè)動(dòng)作有25個(gè)樣本。本文選取其中四組動(dòng)作，對(duì)每種動(dòng)作視頻中截取25張圖片關(guān)鍵幀，共100張圖像作為樣本訓(xùn)練集，另外再截取50張圖像作為樣本測試集。

4 圖像預(yù)處理與特征提取

首先截取每個(gè)視頻樣本中的一些關(guān)鍵幀圖像，然后對(duì)圖像做高斯模糊、灰度化、二值化、閉操作等處理后，再使用直方統(tǒng)計(jì)函數(shù)對(duì)圖像進(jìn)行特征提取。最后再使用樸素貝葉斯算法與半樸素貝葉斯算法作為分類器進(jìn)行分類比較。對(duì)圖片進(jìn)行高斯模糊處理后，會(huì)使得圖片變得模糊，目的是去除與圖像識(shí)別不相關(guān)的干擾噪聲，為接下來的Sobel算子圖像處理步驟做準(zhǔn)備。接著再對(duì)圖像進(jìn)行灰度化處理、二值化處理，以及對(duì)圖像進(jìn)行閉操作，取其最小外接矩形，最后獲取僅包含人體動(dòng)作行為的最小矩形塊圖像。

特征提取的目的是為了提取出對(duì)分類預(yù)測有幫助的信息，并且忽略不重要的信息與噪聲。而數(shù)據(jù)特征選擇能夠有效提高數(shù)據(jù)的測試效率,若直接采用圖像所有的像素點(diǎn)作為輸入特征值，則會(huì)導(dǎo)致特征屬性過大，從而不利于對(duì)信息的篩選與模型的預(yù)測。直方統(tǒng)計(jì)函數(shù)是圖像特征提取的一種重要統(tǒng)計(jì)方式，其可以近似被認(rèn)為是圖像灰度密度函數(shù)。當(dāng)圖片的對(duì)比度較小時(shí)，其灰度直方圖特征只在灰度軸上較小的一小段區(qū)域上為非零值，而相對(duì)較暗的圖片因?yàn)槠湎袼鼗叶戎档偷膮^(qū)域較大，所以它的直方圖的主體特征出現(xiàn)在低值的灰度區(qū)間上，在高值灰度區(qū)間上，其幅度較小或者為零，這反映出圖片像素矩陣中行與列之間的相關(guān)性和圖像之間的特點(diǎn)。通過上述所做的預(yù)處理獲取30×20像素的人體圖像，將圖像二值化后，統(tǒng)計(jì)每一行以及每一列中元素為1的數(shù)目，構(gòu)成屬性維度為50的特征向量，即為所需要的特征數(shù)據(jù)。

5 實(shí)驗(yàn)結(jié)果和分析

本實(shí)驗(yàn)采用Spyder作為編程環(huán)境，實(shí)驗(yàn)數(shù)據(jù)來自KTH數(shù)據(jù)庫，通過隨機(jī)選取的四組動(dòng)作(走、跑、拳擊、揮手)視頻樣本，從各視頻中進(jìn)行每隔5幀圖片提取取樣。每個(gè)視頻樣本選取25張圖像，共獲取100張圖片作為訓(xùn)練數(shù)據(jù)。再另取四組動(dòng)作圖像共50張圖像作為測試數(shù)據(jù)。

本實(shí)驗(yàn)對(duì)于四種動(dòng)作進(jìn)行了預(yù)測判斷識(shí)別，實(shí)驗(yàn)中先通過對(duì)圖像作高斯模糊、灰度化、二值化、閉操作等前期處理，從而將圖像數(shù)據(jù)轉(zhuǎn)化為一組向量數(shù)據(jù)，再分別利用樸素貝葉斯分類器與半樸素貝葉斯分類器對(duì)這包含四組動(dòng)作的圖片進(jìn)行預(yù)測，計(jì)算其分類識(shí)別率。實(shí)驗(yàn)結(jié)果如表1所示。通過對(duì)比發(fā)現(xiàn)，采用半樸素貝葉斯分類器的準(zhǔn)確率更高，而相對(duì)地其花費(fèi)的時(shí)間也更多。究其原因，主要緣由是樸素貝葉斯分類器是以屬性條件獨(dú)立性假設(shè)作為前提條件，而這個(gè)假設(shè)在現(xiàn)實(shí)生活中很難成立，因條件過于苛刻，從而導(dǎo)致識(shí)別率較低，而半樸素貝葉斯分類器在一定程度上對(duì)這一條件進(jìn)行松動(dòng)，增加屬性之間的依賴性，雖然增加了計(jì)算的復(fù)雜度，但也使得識(shí)別率有所提高。

表1 兩種分類器的性能比較

6 結(jié)束語

樸素貝葉斯分類器是以屬性條件獨(dú)立性假設(shè)作為前提條件，而這個(gè)假設(shè)在現(xiàn)實(shí)生活中其實(shí)往往難以成立，但奇妙的是，在很多情況下樸素貝葉斯分類器都能夠獲取相當(dāng)好的性能。而半樸素貝葉斯分類器是以對(duì)屬性之間的部分依賴關(guān)系作出各種假設(shè)和約束來進(jìn)行建模的。利用弱化條件獨(dú)立性這一假設(shè)來提高樸素貝葉斯分類器預(yù)測的準(zhǔn)確性。如果訓(xùn)練數(shù)據(jù)足夠充分，且選擇合適的父屬性，其算法的泛化性能則會(huì)提升，但其缺點(diǎn)同樣很明顯，在有限的樣本條件下，往往會(huì)導(dǎo)致其計(jì)算時(shí)間的開銷過大。如何挑選能夠使分類器產(chǎn)生較好的泛化性的屬性作為父屬性，是目前研究的重點(diǎn)。

雖然樸素貝葉斯分類器在很多情況下都能獲得相當(dāng)好的性能，但其應(yīng)用的場景更多的是在信息檢索領(lǐng)域以及文本分類領(lǐng)域。在圖像識(shí)別方面受限于數(shù)據(jù)的特征維度以及特征值間的復(fù)雜依賴關(guān)系，而得不到很準(zhǔn)確的識(shí)別效果。目前圖像識(shí)別主流更多采用深度學(xué)習(xí)方法，并且能獲得很好的識(shí)別率。