核零空間算法在字符識別中的應用?

韓 笑 畢 波 唐錦萍 曹 莉

（1.東北石油大學數學與統計學院 大慶 163318）（2.海南醫學院公共衛生與全健康國際學院 海口 571199）（3.黑龍江大學數據科學與技術學院 哈爾濱 150080）

1 引言

在當今大數據時代，在很多領域都面臨著需要對大量數據進行整理、分類以及異常判別的問題，但是如果利用人力來解決這些問題，無疑非常耗時也耗力，因此利用數據的某些特點來進行分批分類整理以及判別異常無疑是一種更加便捷且高效的方式。

模式識別作為一門新興的學科，與人工智能和信息科學等學科的發展相輔相成［1~3］。如今，模式識別發展越來越成熟，應用也越來越廣泛，遍及機器人、遙感數據分析、生物醫學工程等多個領域［4~9］。而字符識別是模式識別中的一個應用，通過訓練模型可以教會計算機如何識別字符［10］。通過進行字符識別，不僅可以幫助我們對字符進行整理分類，而且還可以幫助我們從海量的數據中有效檢測異常字符。

常用的字符識別方法主要用于利用字符對樣本進行整理分類，常用的方法主要基于統計分析、神經網絡和聚類分析，如支持向量機（SVM）、誤差反向傳播（Back Propagation，BP）算法、Bagging 算法等［11~15］。而對字符進行異常識別的方法相對較少，考慮到每個字符的維度是特別多的，而核零空間算法作為一種異常檢測算法，并且考慮到它對于處理高維數據，以及提取數據非線性特征的優勢，因此將其用于字符異常識別是合理的。

本文充分利用核零空間算法進行異常檢測的優勢，將其應用于字符異常識別，仿真實驗結果表明，利用核零空間算法對字符進行異常識別，性能表現良好。

2 字符識別的發展

字符識別的發展是一個漫長的過程，20 世紀70 年代才由中科院自動化所的戴汝為院士牽頭進行手寫體字符識別，并在1974 年將所研究的手寫體數字識別系統應用到郵政信件的自動分揀中。70 年代末開始進行漢字識別的研究，到1986 年漢字識別的研究進入一個實質性階段，取得了較大的成果［16］。

傳統的用來進行字符識別的方法大多還是集中于對字符識別進行分類，不同的字母對應一個不同的類別，因此常用來進行大量數據的整理、分類等領域。但若要檢測字符數據集中的異常字符，核零空間算法則是一種合適的識別異常字符的方法。

3 核零空間算法的算法描述

核零空間算法是一種基于最大化Fisher 準則的一分類算法，Fisher 線性分類器由R.A.Fisher 在1936 年提出，之后在該分類器的基礎上，Foley 和Sammon 基于最大化Fisher 準則提出了Foley-sammon 變換［17］，但之后，Foley 和Sammon 發現當樣本數遠遠小于它的維數時，會出現類內散度矩陣奇異的情況，這時，會導致后續無法計算。基于該問題，許多研究者想到利用PCA 方法來進行降維來得到最終結果。之后，Chen 等［18］和Yu and Yang［19］基于最大化類間散度，最小化類內散度的原則，希望將類內散度矩陣利用某種變換將其投影為0，從而有效解決類內散度矩陣奇異的問題，因此提出了零變換，再結合FST 變換，得到NFST 變換。隨后，在2008 年，Y.Lin，G.Gu，H.Liu，and J.Shen 又從數據本身出發，考慮到數據不僅具有線性特征而且具有非線性特征，因此基于數據的非線性，提出了核零空間變換，先將數據映射到高維空間中，再進行零空間變換［20］。此方法的應用，有效提取出了數據的非線性特征，并且表現良好。

3.1 Fisher準則

假設φ為LDA算法的投影矩陣，則

Fisher準則公式為

設總樣本X={X1,X2,…,Xn}，N為總樣本個數，n為總類別數，ni為第i類樣本的個數，分別為第i類樣本Xi的平均值，xij為第i類第j個樣本，則分別可以將類內散度矩陣SW與類間散度矩陣Sb定義如下：

基于最大化Fisher準則，則上式可表示為

其中φ可表示為SbSW-1的前P 個最大特征值對應的特征向量所組成的投影矩陣，即φ={φ1,φ2,…,φp}，其中，φp為投影矩陣的第p個投影向量。

但是，在樣本數遠遠小于樣本的維數時，很容易造成Sw為奇異矩陣，這時很可能會導致投影向量無法求解的問題，即小樣本問題。

3.2 NFST變換

為了解決上述小樣本問題，我們引入了零空間變換，先提取Sw的零特征值對應的特征向量構成零空間，然后再在此基礎上提取Sb的前p個最大特征值對應的特征向量。具體過程如下：

令：

引入了總散度矩陣St，令：

若存在零投影方向矩陣φ={φ1,φ2,…,φp}，使得 公 式φT SWφ=0成 立，則 此 時，φT Sbφ>0與φT Stφ>0等價。

令Zt和Zb分別為St和Sb的零空間，分別表示為

則非零向量矩陣φ屬于Zt⊥∩Zw的子空間中，其中，Zt⊥和Zb⊥分別表示Zt和Zw的正交空間。

設θ1,θ2,…,θm為Zt⊥子空間的正交基，則在該子空間中的任一向量φ都可以表為

其中B為γ在正交基θ下的系數矩陣。

對于公式φT SWφ=0 ，其實際上與Swφ=0 等價，又由于φ?Zt⊥∩Zw，則：

且此時BT(θT Swθ)B=0 與(θT Swθ)B=0 等價，因此我們便可以求得零方向投影矩陣φ。

3.3 KNFST變換

雖然利用NFST 變換成功解決了小樣本問題，但是它卻僅僅考慮了樣本的線性特征，忽略了一些隱形的非線性特征，這很容易造成最終的結果不準確，因此就引入了后來的核零空間算法。具體描述如下：

設經過非線性映射后的特征空間為F，非線性映射后的樣本為φ(X)，其中φ(X)={φ(X1),φ(X2),…,φ(Xn)}，n為類別數。

設在F空間中，ni為第i類樣本的個數，φ(xij)為第i類第j個樣本，為第i類樣本φ(Xi)的均值，N為總的樣本個數，則此時有：

第i類的類內均值：

總均值：

類內方差矩陣為

類間方差矩陣為

總方差矩陣Sφt為

由于進行了非線性映射以后才計算零投影方向矩陣的計算，因此需要對非線性映射后的核矩陣進行零投影方向的計算，其中核矩陣是由不同類不同樣本間的內積構成的，即有：

核函數：

其中，i,k=1,2,…,n,j=1,2,…,ni,l=1,2,…,nk。

核函數矩陣為

核類內方差矩陣為

核類間方差矩陣為

核總方差矩陣為

則此時的條件為

非零向量矩陣φ位于Kt⊥∩Kw的子空間中。

設θ1,θ2,…,θm為Kt⊥子空間的正交基，則在該子空間中的任一向量φ都可以表示成：

對于公式φT KWφ=0，其實際上與Kwφ=0 等價，又由于φ?Zt⊥∩Zw，則：

且此時BT(θT Kwθ)B=0 與(θT Kwθ)B=0 等價，因此我們便可以求得零方向投影矩陣φ。

本文中首次將核零空間算法用于UCI 數據集中的字符識別數據集，首先需要將所有的訓練樣本利用某個核函數進行非線性映射得到核矩陣，之后再計算核矩陣的零投影方向矩陣，將核矩陣按照該零投影方向，將整個訓練集映射為零空間內的一個正常點，之后，將每個測試樣本都通過該零投影方向進行映射得到零空間中的一個點，最后計算零空間中每個測試樣本到正常點的距離，并且將此距離與事先設定的異常閾值進行對比，若超出該閾值則判斷為異常樣本。并且核零空間算法作為一種一分類算法，相較于其他分類算法，它僅需要使用正常類樣本作為訓練集，計算出零空間的投影即可，而其它分類算法則需要同時利用正常類與異常類樣本一起作為訓練集進行計算，這無疑會增加很多計算的工作量。并且通過與其他一分類算法的性能進行比較，可以發現，將該算法用于該字符識別數據集中，性能表現較好。

4 實驗及分析

我們選取UCI 數據集中的字符識別數據集中的合成數據集［21］，該數據集是由不同形式的A-Z26個字符組成的，原來每個字符的維度為16 維，具體特征主要包括：圖片的水平尺寸x-box、圖片的垂直尺寸y-box、像素的寬度width、像素的高度high、像素的總數cnpix、圖片水平尺寸的平均像素值x-bar、圖片垂直尺寸的平均像素值y-bar、水平尺寸均方差x2bar、垂直尺寸均方差y2bar、水平均值與垂直均值的相關性xybar、x2y的均值x2ybr、xy2的均值xy2br、從左到右邊緣計數的均值x-ege、x-ege 與y 的相關性、從底到頂的邊緣計數的均值y-ege、y-ege 與x 的相關性。為了進行異常點檢測，我們選取其中3 個字符，共有1600 個字符樣本作為總的數據集，其中正常樣本有1500 個，異常樣本有100 個，并且為了驗證算法在高維空間上的有效性，將其維度進行任意組合，例如可以將1，2 維組合，4，5，6 維組合等，這里我們將1，2 維；2，3 維；3，4 維；4，5 維；5，6 維；6，7 維；7，8 維；8，9 維；9，10維；10，11 維；11，12 維；12，13 維；13，14 維；14，15維；15，16 維；1，8 維進行組合，得到新增的16 個新特征，從而將整個數據集變成一個32維的數據集。

4.1 數據預處理

1）缺失值處理：經檢測，該數據集沒有缺失值。

2）數據歸一化處理

線性函數歸一化：將數據轉換為［0，1］之間的數。

z-score 歸一化：將數據轉換為服從于均值為0，標準差為1的標準正態分布的數據。

3）核函數確定

考慮到字符數據的非線性特征，因此在利用核零空間算法對字符數據進行計算時，必須先選擇合適的核函數，將數據進行非線性映射到高維空間中，再進行零變換，因此選擇合適的核函數是必要的。常見的核函數有：線性核函數、多項式核函數、高斯核函數、冪指數核函數、拉普拉斯核函數等。

線性核函數：

多項式核函數：

高斯核函數：

冪指數核函數：

拉普拉斯核函數：

4.2 實驗及結論

由于考慮到不同歸一化處理以及不同核函數下的測試結果是不同的，因此，我們分別嘗試對數據在不同的歸一化處理下，選擇不同的核函數進行ROC曲線測試的結果進行分析。

首先對數據進行線性函數歸一化，令所有核函數里面的相關參數c=0 與σ=1，多項式核函數分別取d=2，d=10，d=50，d=100，然后得到不同核函數下的ROC曲線如圖1~圖2。

圖1 線性歸一化后不同核函數下ROC曲線圖

圖2 線性歸一化后不同階數的多項式核函數下的ROC曲線圖

通過觀察圖像我們可以發現，高斯核函數、冪指數與拉普拉斯核函數下的ROC 曲線呈現緩慢增長的趨勢，并且在該數據集上表現良好，除此之外也可以通過調節它們的核參數得到其他不同的結果。但是線性核函數與低次多項式核函數則表現出近乎直線的增長趨勢，并且性能表現較差。

仔細觀察多項式核函數，盡管我們發現隨著次數增長，圖像越來越平滑，但是我們發現在d=50時，圖像表現較為平滑，而在d=100 時，圖像又呈現出直線的趨勢，因此可以推測，在多項式核函數下，性能表現最優的d的取值位于［10，100］之間。

為了進一步更加直觀地觀察我們將核零空間算法用于字符異常識別的有效性，選擇F1-score作為評測指標，得到不同異常閾值（均值與最佳值）下的結果，其中均值指的是所有測試樣本到正常點的距離的平均值，最佳值指的是使得F1-score分數不等于1 時的最大值所對應的距離值，具體結果如下。

線性函數歸一化不同核函數下的不同異常閾值的F1-score結果見表1。

表1 線性函數歸一化不同核函數下的不同異常閾值的F1-score結果

觀察表格我們發現，當取均值作為異常閾值檢測時并不是一個很好的選擇，因為它的F1-score普遍低于取最佳值作為異常閾值下的F1-score。但不管取均值作為異常閾值還是最佳值作為異常閾值，在高斯核函數下的F1-score分數都比其他核函數下的值要大，這說明在線性歸一化處理下的數據集，采用高斯核函數映射，性能表現最佳，而線性核函數下的值則最小，性能最差。除此之外，我們還發現，在冪指數函數與拉普拉斯函數下的性能表現差距不大，只有作為均值作為異常閾值時，才拉開差距。而對于多項式核函數來說，在d的值較小時，F1-score 是不斷增大的，但是當，d≥50 時，F1-score 變化不明顯，僅僅有很小的增加，再結合ROC 曲線，我們可以知道，雖然在d=100 與d=50時的最佳值的F1-score相同，但是，通過觀察圖像，可以發現，d=100 沒有d=50 時的性能表現好。因此，判斷一個模型的好壞要結合準確率與圖像進行綜合分析。

之后，我們又得出了在z-score 歸一化處理下的不同核函數的ROC曲線圖如圖3~圖4，同樣令所有核函數里面的γ=1 與σ=1，多項式核函數分別取d=2，d=10，d=50，d=100。

圖3 z-score歸一化后不同核函數下ROC曲線圖

圖4 z-score歸一化后不同階數的多項式核函數下的ROC曲線圖

通過觀察圖像，我們發現被z-score 歸一化處理后的數據集，在高斯核函數的映射下，在最初階段F1-score出現了迅速增長，之后緩慢趨近于1，而在冪指數核函數與拉普拉斯核函數下，從一開始就是處于緩慢增長的態勢，圖像表現較為平滑。而線性核函數則使得ROC 曲線呈現出直線趨于1 的態勢，這可能與線性函數本身的特點相關。而多項式函數在次數d為低次時，性能表現與線性核函數差不多，但是當d=10 時，圖像也表現出與前面幾種徑向基核函數差不多的性能，但是隨著次數的增加，當d=50 時，圖像又近乎于直線趨于1，而在d=100 時，則出現了很多缺失值，實際上這是沒有意義的，因為通過前面對d=2,5,10,50 下的考察我們已經發現，性能表現由壞變好之后趨于穩定，這說明，對于多項式核函數來說，在該數據集下，性能表現最好的d的取值，可能位于10左右。

z-score 函數歸一化不同核函數下的不同異常閾值的F1-score結果見表2。

表2 z-score函數歸一化不同核函數下的不同異常閾值的F1-score結果

觀察表格，我們同樣得出，經過z-score 歸一化處理后的數據，在高斯核映射下利用最佳值作為異常閾值進行判別時得到的F1-score表現最佳，但是該映射下利用均值作為異常閾值時則表現最差，因此，在一個表現良好的核函數下，不一定任何異常閾值下的性能表現都是最好的。在冪指數核與拉普拉斯核函數下無論取均值作為異常閾值還是最佳值作為異常閾值，F1-score 分數都相同，再觀察圖像發現兩者的性能表現幾乎相同。而線性核函數在取均值作為異常閾值時，F1-score 分數是除了高斯核函數以外的最低，除此之外，它取最佳值作為異常閾值時，F1-score 分數與多項式核函數下的當d=100 時相同，取值最低。綜合來看，線性核函數映射下的性能表現最差。在多項式核函數下，無論取均值作為異常閾值還是取最佳值作為異常閾值，性能表現在d≥10 后已趨于穩定，均值保持在0.9 附近，最佳值也穩定在0.9 附近，因此在實際應用中可以考慮選取d=10。

除此之外，為了更好地體現該算法的有效性，我們還將其他一分類算法用于該數據集，并與之進行性能比對，如表3。

表3 一分類算法性能比較

從表3 可以看出：對于one-class svm 算法、SVDD 算法與孤立森林算法，無論使用線性函數歸一化還是z-score 歸一化后的數據，它們三者的算法性能在兩種情況下的表現都差不多，并且縱向對比之下，在one-class svm 算法上的表現相對來說較好，但是在SVDD 算法上的表現卻極差，這可能與數據樣本的分布不是球狀有關。除此之外，這三種算法與核零空間算法相比，無論是使用線性函數歸一化還是z-score 歸一化，三種算法與之對應的最好的性能分別為one-class svm 算法的0.8636 與0.8643，但都位于0.9 以下，而核零空間算法在不同核函數下的最差的性能也分別為0.8989 與0.8989，接近0.9，因此，相比之下，核零空間算法在字符識別數據集中的表現更好。顯然，將核零空間算法用于字符識別數據集是合理的。

因此，在利用核零空間算法進行異常檢測時，對數據進行正確的歸一化處理，并且選擇一個合適的核函數以及選擇一個不同核函數下的較為準確的異常閾值作為判斷依據是值得我們仔細考量的。

5 結語

本文在當今時代對字符識別的處理大多集中在對數據集的整理與分類，很少用于異常識別的背景下，通過利用核零空間算法作為一種異常檢測算法，在處理高維數據集，以及提取數據非線性特征上的優勢，將其用于字符異常識別中，通過仿真實驗表明，將核零空間算法用于字符識別是有效的。但考慮到，合適的異常閾值的選擇往往特別依賴于數據集的選定，不同的數據集的最佳的異常閾值是不同的，因此在未來，如何在不限定數據集的情況下選擇一個通用的異常閾值或者計算異常閾值的通用公式仍然是一個值得研究的課題。