基于樸素貝葉斯與半樸素貝葉斯圖像識別比較

劉 闖

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

0 引言

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

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

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

1 樸素貝葉斯分類器NBC

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

設輸入空間x∈Rn是n維向量的一個集合，輸出空間是類標記集合y={c1,c2，…，ck}。輸入是特征向量x∈x，輸出為類標記y∈y。X是定義在輸入空間x中的隨機變量，Y是定義在輸出空間y中的隨機變量，其中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)

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

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

(5)

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

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

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

(11)

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

(12)

為了最小化期望風險，只需要對X=x的值逐個極小化，由此得到：

(13)

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

(14)

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

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

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

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

(15)

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

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

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

(1)計算任意兩個屬性節(jié)點之間的條件互信息[8]：

I(xi，xj|y)=

(16)

(2)把屬性作為節(jié)點構建完全圖，任意兩個節(jié)點間的權重設為I(xi,xj|y)；

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

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

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

3 圖像識別方法流程

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

圖2 基于NBC與SEMI-NBC的圖像識別

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

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

4 圖像預處理與特征提取

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

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

5 實驗結(jié)果和分析

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

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

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

6 結(jié)束語

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

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