基于加權KNN與隨機森林的表情識別方法

馮開平，賴思淵

(廣東工業大學 計算機學院，廣東 廣州 510006)

0 引言

人臉表情識別主要涉及圖像處理與模式識別兩個方面，在教育、游戲[1]、醫學[2]、動畫[3-4]等領域都有著廣泛應用。表情識別過程分為特征提取與分類識別兩部分，常用的特征提取算法有PCA[5]、LBP[6]以及Gabor小波變換[7]。好的分類模型能夠提高表情識別準確性，降低計算復雜度。常用于表情識別的分類方法有K最近鄰(KNN)、支持向量機(SVM)[8]、神經網絡(NN)[9-10]、分類樹(CT)[11]與稀疏表示(SP)[12-13]等。Qite Wang等[14]提出一種基于PCA與KNN的表情識別方法，并用于在車聯網中識別路怒癥、疲勞駕駛與酒后駕駛狀態。卷積神經網絡[15]雖然分類準確率高，但需要大量參數，而且當數據出現部分缺失時容易發生錯誤。分類樹計算復雜度不高，能夠處理一定的數據缺失，但對于噪聲數據比較敏感，容易導致過擬合。針對SVM計算量大以及KNN分類精度不高問題，王小虎等[16]提出一種組合FSVM與KNN的方法，通過區分度函數判斷輸入樣本的區分程度，然后自適應地選擇分類器；Zineb等[17]提出一種基于一維隱馬爾可夫模型的方法，首先通過小波變換提取特征，然后通過線性判別分析法降低數據冗余度，從而減少計算量。

本文在分析上述方法后，提出一種結合加權KNN和RF[18]的分類器。首先通過人臉對齊方法SDM[19]將訓練樣本的人臉特征點提取出來，生成一張平均特征點分布圖，然后計算測試樣本與平均人臉特征點之間的距離，最后根據距離選擇分類器，利用加權KNN算法對表現程度弱的樣本進行分類，其余樣本交由RF處理。實驗結果證明，該方法具有一定可行性，在改善分類效果的同時，能夠減少KNN算法的計算量。

1 相關算法描述

1.1 加權KNN算法基本原理

KNN算法是一種簡單、容易實現的分類方法，尤其適用于多分類問題。其基本原理是給定訓練集T，其中的每個樣本都有一個類別，輸入一個沒有分類的測試數據，遍歷所有樣本，計算測試數據與樣本之間的距離，然后選取距離最近的k個樣本，將k個樣本中出現最多的類別作為測試數據類別。雖然KNN算法易于理解，但當訓練集中的樣本類別不均勻時，如一個類的樣本較多，而其它類別樣本過少，則容易使分類結果受到影響。另外當訓練集過大時，計算量也會比較大，從而降低了分類效率，不適合直接用于表情識別。針對上述情況，可以采取加權方式改善表情識別的分類效果。

在特征提取階段，將人臉的68個特征點提取出來，如圖1所示。從圖中可以看出，不同特征點對于表情的貢獻度不同，如果同等對待每個特征點，則可能會對最后的分類結果造成影響，從而降低識別率。例如每個人的輪廓不同，因此可以認為輪廓對表情的貢獻度較低，計算距離時可以刪除該部分特征點，降低數據維度，以達到減少計算量的目的。

圖1 不同表情特征點分布

用歐式距離計算兩個樣本之間的距離D：

(1)

其中，I為特征點集合，x、y、w、v分別為測試樣本與訓練樣本的特征點坐標。

最常見的加權方式是用距離D的倒數作為權重，權重W計算方式如下：

(2)

其中，C為一個常數，因為測試樣本有可能與訓練樣本完全一樣或相當接近，將導致權重趨于無窮大，因此在求距離倒數時需要額外加上一個常數。

距離倒數加權方法的優點在于計算簡單，但其對于較近的樣本會分配很大的權重，對稍遠的樣本分配權重時則衰減很快。該加權方法在表情識別中效果一般，對噪聲數據變得較為敏感。

還有一種常用的加權方式是使用高斯函數加權，其公式如下：

(3)

其中，a為曲線高度，b為曲線中心線在橫軸的偏移，c為半峰寬度。當a=1，b=0，c=0.5時，高斯函數的函數圖像如圖2所示。

圖2 高斯函數圖像

從圖2中可以看出，當距離等于0時，權重獲得最大值1，隨著距離增加，權重逐漸減少，但是永遠不等于0，因而能夠滿足實際應用需要。實驗結果證明，在本文中使用高斯函數加權時的分類效果優于距離倒數加權。

首先對求得的樣本距離從小到大進行排序，選擇距離最近的k個訓練樣本進行加權。設與第n個訓練樣本屬于同類的概率為Pn，通過以下公式計算Pn：

(4)

其中，Wn為第n個樣本權重，分母為距離最近的k個樣本權重之和。

1.2 隨機森林基本原理

隨機森林是通過隨機構建多棵決策樹對樣本進行訓練與預測的一種分類器，其中的每棵決策樹都按照如下規則生成：①設樣本集大小為N，對于隨機森林中的每棵決策樹，隨機有放回地從訓練集中抽取N個樣本，作為決策樹的訓練集；②設訓練集中的每個樣本特征維度為M，隨機從M個特征中選擇m個特征子集，其中m<

2 加權KNN結合隨機森林算法

2.1 算法描述

加權KNN算法能夠有效識別表現力較弱的表情，但是如果樣本過多，則會導致KNN算法計算量增大，而隨機森林訓練速度較快，能在不作特征選擇的前提下有效處理高維數據，并且對特征的重要性進行排序。為了充分結合兩者的優越性，提高人臉表情識別率與識別速度，同時降低計算復雜度，本文提出一種加權KNN與隨機森林相結合的分類器。該分類器將JAFEE表情數據庫中的語義程度評分作為樣本的一部分特征，通過判斷測試樣本是否屬于表現程度較弱的表情進行分類器選擇，以充分發揮改進KNN算法的優勢，識別表現程度較弱的表情，同時利用魯棒性較好的隨機森林對其它表情進行分類，算法基本流程如下：

(1)根據語義程度評分r對樣本從低到高進行排序，為了防止樣本不均勻導致的分類缺陷，需要保證加權KNN算法中樣本的平衡性，按比例從排序結果中抽取樣本，根據樣本的特征點分布，計算坐標平均值，然后生成一張平均特征點分布圖，如圖3所示。

圖3 生成平均特征點分布

(2)按下列步驟隨機抽取樣本，訓練d棵決策樹作為弱分類器：

計算每個特征點的基尼不純度(Gini impurity)，Gini值越大，則意味著分裂后的總體內包含的類別越雜亂。對于樣本集S，Gini值計算公式如下：

(5)

其中，pk表示樣本集分類結果中第k個類別出現的概率。

為了選擇最好的特征進行分裂，加強隨機森林中每棵決策樹的分類能力，從而使隨機森林獲得最佳分類效果，本文選擇最小基尼增益值GiniGain作為決策樹分裂方案。GiniGain計算公式如下：

(6)

其中，S1、S2為樣本集S的兩個樣本子集，n1、n2為兩個樣本子集的數量，N為樣本容量。

對于樣本S中的特征，計算任意可能的特征值組合的GiniGain，最后選擇GiniGain最小的特征值組合作為決策樹當前節點的最優分裂方案，并聯合訓練出多棵決策樹作為隨機森林分類器。

(3)計算測試樣本與新生成特征分布圖的距離，當距離小于閾值t時，認為該測試樣本屬于表現程度較弱的一類，選擇加權KNN算法對其進行分類；當距離大于t時，選擇隨機森林進行分類。當選擇加權KNN算法進行分類時，輸出分類結果。算法流程如圖4所示。

圖4 算法流程

2.2 分類器有效性驗證

將分類器用于測試樣本之前需要驗證其有效性，以避免測試時出現過擬合現象。在KNN算法中，k的取值對分類效果有很大影響，若k值太小會造成過擬合現象，導致分類器分類錯誤。因此，Ghosh[20]提出一種基于貝葉斯的方法選擇較優的k值，但是計算比較復雜。本文采用十折交叉驗證方法確定k值。

十折交叉驗證是驗證分類器泛化性能的一種方法，其基本思想是通過對訓練集進行分組，將其平均分為K個子集，每個子集分別作為一次測試集，其它K-1個子集作為訓練集，從而得到K個分類模型，然后用K個模型分類準確率的平均數評估分類器性能。通過十折交叉驗證能夠為算法選擇一個較優的參數k，以避免出現過擬合現象。

3 實驗結果與分析

實驗中采用JAFFE表情數據庫，表情庫中包含10個日本女性的7種不同表情，包括生氣、恐懼、厭惡、高興、驚訝、悲傷和中性，每人同種表情的圖像有3～4幅。實驗中，從每種表情中隨機選取22～23幅共160幅圖像作為訓練集，然后將160幅圖像平均分為10組進行交叉驗證，評估分類模型效果并且確定加權KNN算法中的參數k，每次測試時從剩下圖像中隨機選取20幅圖像作為測試集。為了對比分類效果，分別采用KNN、RF、SVM與本文方法對數據集進行實驗。4種分類器表情識別率如表1所示。

表1 4種分類器表情識別率 單位/%

圖5為進行十折交叉驗證時不同加權方法的錯誤率。從圖中可以看出，高斯函數加權的識別錯誤率都低于倒數加權，因此認為高斯函數加權的方式優于倒數加權。同時隨著k值增加，錯誤率趨于穩定，當k為6時錯誤率最低，但是隨著k值繼續增加，噪聲越來越大，導致分類模型效果變差。

圖5 十折交叉驗證錯誤率

4 結語

本文提出的加權KNN結合隨機森林的分類器在表情識別領域優于普通的KNN和SVM方法，其具有以下特點：①減少了訓練模型參數，通過加權方法改善了KNN算法分類效果；②與隨機森林相結合，減少了KNN算法的計算量并且提高了隨機森林的可調控性，充分發揮了隨機森林魯棒性強、訓練速度快的優點，降低了計算復雜度。盡管通過在JAFFE表情庫中的實驗證明了該算法的可行性與穩定性，但若只考慮人臉特征點分布仍然不太嚴謹，因為每個人的臉型存在一定差異，因此下一步研究中需要考慮融合其它特征信息。