任美麗，孟 亮

（太原理工大學 計算機科學與技術學院，山西 太原030024）

0 引 言

為了滿足行業(yè)的需求，手寫體數(shù)字的識別體系必須具有精確地識別率、可接受的分類速度和對多變字體的魯棒性。目前，在手寫體數(shù)字識別方面，有很多方法都達到了其要求的識別準確性，包括多級神經(jīng)網(wǎng)絡、支持向量機和傳統(tǒng)的鄰近算法等。然而，這些方法都沒有權衡空間和時間的差異。因此，為了避免重新訓練樣本，浪費數(shù)字的分類時間，本文采用了基于原型技術的k－NN 鄰近算法［1］進行分類識別。該技術主要包含以下幾個重要的步驟：通過自適應共振理論的無監(jiān)督性學習來選取能夠包含所有樣本特征的原型集合；利用自然演化理論的原則將原型集合進行優(yōu)化，建立一個具有最小集合的邊界，產(chǎn)生最優(yōu)的最能代表整個樣本的集合；通過k－NN 鄰近算法將原型技術應用于MNIST 手寫體數(shù)字數(shù)據(jù)庫中。依據(jù)不同階段的處理過程尋找的最優(yōu)的原型集合，減少k－NN 算法的分類時間，但不影響算法分類識別的精確度，權衡手寫體數(shù)字識別上的時間和空間的差異。話句話說，采用適當原型生成技術的k－NN 分類器可以權衡識別的準確率、分類速度和手寫體風格多變的特征。

1 工程簡介

k－NN 算法主要是針對未知的待識別的測試樣本，從訓練集中找出和其最接近的K 條記錄，然后根據(jù)它們的主要分類來決定新數(shù)據(jù)的類別。傳統(tǒng)的k－NN 分類器需要存儲所有的訓練集并依據(jù)在特征空間中最接近訓練集中的樣本作為所識別的類別［1］。因此，k－NN 算法中包含一個代表原型集［2］，使其在訓練過程中不需要花費時間，但在識別過程中需要大量的時間，這是因為在識別階段，k－NN 算法需要處理大量的數(shù)據(jù)。為了減少識別過程中的時間，提出了一種新的原型生成技術的方法，將其與k－NN 算法相結合。該方法集中收集主要的、最能代表原型的訓練集，它具有比原訓練集更小的維數(shù)，這樣不僅能夠提高測試樣本的匹配準確度，使得測試樣本在識別過程中能有效的減少訓練的時間，而且還保持其具有相對較高的識別率。實驗中，定義兩個主要策略即原型選擇和原型合成。原型選擇技術主要強調(diào)的是將訓練集中的樣本進行壓縮，從中選擇出最能代表原訓練集的特征集合，作為k－NN 算法的原型。原型合成技術強調(diào)主要是實現(xiàn)合成原型的最優(yōu)化問題，以及利用原型生成技術后的k－NN 分類器的分類能力。數(shù)字圖像的原型生成技術從原型選擇出發(fā)進而進行原型的組合，最終形成實驗所需要的原型集合，通過k－NN 算法的識別最終確定待測樣本的類別。

2 基于分類的原型

通過對數(shù)字圖像特征提取之后，在特征空間中，每個樣本都包含一個對應的特征向量v。假設一個距離矢量d（d 是一個非負的且滿足自反性條件：d（v，v）＝0），如果滿足mind（v，vi）＝d（v，v′），i＝1，2，…，n，則稱為v′∈｛v1，v2，…，vn｝為最近的鄰居。在k－NN 規(guī)則中，對于未知向量v 的預測，需要從最近的k 個訓練集中選擇出最可能的類別。

假設從原訓練集上選擇生成一個具有代表的集合RS＝｛P1，P2，…，PM｝，表示M 個樣本的原型。通過計算或是從訓練集中訓練得出相應的、并設計有效的距離矢量d，以及選擇有效的判別特征選擇出訓練樣本的原型，形成代表原型集合，降低訓練集的維數(shù)，以便k－NN 規(guī)則利用原型技術很好的完成識別。因此，不僅要注意代表原型集合的建立，而且還需要說明特征提取和距離矢量。

2.1 特征提取

特征提取對于數(shù)字圖像的識別起著關鍵性的作用，為了增加對待測樣本的辨別能力，不僅要收集訓練數(shù)字的形狀的信息還要收集形狀空間布局信息。形狀信息的獲取依據(jù)圖像區(qū)域內(nèi)發(fā)布的方向梯度，空間局部信息的描述依據(jù)不同圖像的不同網(wǎng)格的多種分辨率，這樣生成不同分辨率對應不同水平的特征提取方案，如圖1所示。

圖1 3種不同等級的特征提取方案

數(shù)字圖像利用方向梯度的二進制直方圖［3］進行描述，以保證其能夠包含關于圖像縮放、旋轉(zhuǎn)、平移和對比對等變化的差異。因為圖像的每一個像素點的梯度都含有相應的方向和數(shù)值大小，通過對圖像中每個區(qū)域的像素點在同一方向累加的幅度值來構建相應的梯度直方圖。而梯度幅值和方向的計算通過以下步驟：首先，預處理階段的執(zhí)行是生成相應的輸入數(shù)字圖像，包括運用Otsu算法進行的二值化處理，傾斜校正和歸一化成36×36的圖像。然后，根據(jù)Sobel的梯度算子在強度和方向上計算相應的梯度分量，如圖2所示。最后，將每個梯度方向分解在成標準的形式［4］。

圖2 每個方向的梯度分解

為了生成相應的二進制向量集，我們將所給定區(qū)域內(nèi)的直方圖區(qū)域的平均值作為閾值，高于閾值的部分設置為1，低于閾值的部分設置為0，例如圖3所示。

圖3 方向梯度的二進制直方圖

我們構建的直方圖［3］采用3種不同等級的形式，6×6，4×4，2×2，為了避免局部重疊的現(xiàn)象，我們采用了方向梯度的二進制直方圖為每一個等級提供二進制向量集。0等級 （6×6網(wǎng)格）由288位的向量所表示，1等級 （4×4網(wǎng)格）由一個128 位的向量所表示，2 等級 （2×2 網(wǎng)格）由一個32位的向量所表示。將這些向量鏈接起來構造一個具有448位向量的集合

因此，特征向量v可分解成3個子向量vLevel0，vLevel1，vLevel2。

2.2 距離矢量

距離矢量在識別代表原型集RS和識別未知數(shù)字圖像有著關鍵的作用。正是因為這個原因，在很多文獻中都描述了關于提高k－NN 距離測量的方法。本文，為了提取有用的空間信息，距離矢量應該能夠量化在不同等級 （如圖1所示）中的梯度方向的二進制直方圖的多樣性，我們介紹一種距離矢量的方法——在直方圖差異上的加權求和方法，設計目的是比較待測樣本與訓練集中的數(shù)字的、形狀和結構。它依據(jù)Sokal－Michener的相異度量理論［5，6］，其定義

式中：v1、v2——一個具有固定長度f的向量，——內(nèi)積。最終將Sokal－Michener的相異度量dSM的值被歸一化到0和1之間 （0≤dSM（v1，v2）≤1）。本文所采用的測試度量［7］的定義為

式中：v1、v2——兩個比較向量

wi（i＝0，1，2）是子向量相異的權重。

3 原型選擇算法——ART1

經(jīng)過對圖像的特征提取和距離矢量的定義之后，我們要從訓練集中選擇出所能代表數(shù)字類型的特征最為系統(tǒng)識別數(shù)字的原型，本文中，原型選擇的算法采用的是自適應共振理論［8］（adaptive resonance theory，ART）。ART 的發(fā)展主要是為了避免在競爭性的網(wǎng)絡學習中穩(wěn)定性－可塑性兩難的局面。穩(wěn)定性－可塑性兩難的局面主要解決的是既能夠?qū)π螺斎氲臄?shù)字進行學習又能夠保持先前學習的信息。ART 包含了一系列不同的神經(jīng)架構，其中最重要的基礎架構就是ART1。它是一種無監(jiān)督式學習的模型，尤其對于二進制輸入模式的工作。ART1系統(tǒng)不僅具有相對穩(wěn)定性，而且還包含一個可調(diào)節(jié)的警惕參數(shù)。另外，對于從給定的模型中選擇出訓練樣本的代表原型方面上，ART1 的算法具有快速學習和適應不穩(wěn)定環(huán)境的能力，能夠從輸入的數(shù)據(jù)中進行無監(jiān)督式學習且能準確自動的確定數(shù)字的原型。

為了能夠獲得更加準確的數(shù)字原型集合，本文采用的ART1的算法的主要思想：對于每個二進制輸入的向量模型v，算法都試圖從以存儲的數(shù)字圖像原型中尋找相匹配的模型作為該數(shù)字的類別，將相似度最強的原型作為最終的數(shù)字類別。首先，引入選擇函數(shù)fc用來計算二進制輸入向量v 和表示原型向量的相異值。然后，通過匹配函數(shù)fm與相異值進行計算［8］，如果滿足匹配條件，則先前所選的類別就是輸入數(shù)據(jù)的類別，而在其學習過程依據(jù)學習函數(shù)fl不斷地修改原型向量［9］以便尋找出最為相似的數(shù)字類別，但最終存儲的該類別的原型不發(fā)生變化；如果條件不匹配，例如匹配條件不滿足或是選擇出的原型復位等。將新輸入的向量v假設成為新類別的代表，將其存儲在原型集中作為新的原型特征，之后，在假設測試周期結束時，算法要么找到一個存儲的類別，其原型與輸入的向量不完全匹配，要么創(chuàng)建一個新的原型。這種情況下，存儲的原型集需要根據(jù)學習函數(shù)fl進行更新，并將學習的結果存儲在原型集RS中。如圖4所示，顯示了無監(jiān)督式學習過程。

圖4 無監(jiān)督式學習過程

作為穩(wěn)定性－可塑性的結果，該算法能夠通過輸入模式流自動在線調(diào)節(jié)學習原型，而不是訓練整個訓練集。通過警惕值δ對定義原型的數(shù)據(jù)進行控制，警惕值越高，則產(chǎn)生較大數(shù)量的原型。顯然，引入的ART1算法是一個區(qū)別定義和實現(xiàn)的基本框架，其中關鍵的要素是匹配函數(shù)fm，選擇函數(shù)fc以及學習函數(shù)fl。為了實現(xiàn)ART1算法，我們指定測試距離矢量dM作為選擇函數(shù)fc，其與匹配函數(shù)fm存在小于等于關系，與學習函數(shù)fl進行邏輯按位與運算。事實上，如果距離矢量dM在實際輸入和選中原型之間存在小于等于警惕值δ，則認為匹配條件滿足。

通過該算法的描述，我們需要選擇一組能夠具有很好代表性的原型集合作為演化策略的起點，通過代表集合的基數(shù)，自定義警惕值δ，從原訓練集中選擇出所能代表數(shù)字類型的原型集合RS，作為k－NN 分類器的參考。

4 原型合成

原型合成是指從給定的數(shù)據(jù)集合中選擇出最優(yōu)數(shù)據(jù)的原型并進行組合，形成最終所需的原型集合。在尋找代表性的數(shù)據(jù)過程中被一些學者稱為NP 問題。文獻中提出很多原型生成的方法和將它們應用于不同的地方。本文，我們主要是通過原型生成技術來提高k－NN 分類的效率。在識別未知樣本時，我們尋找一個具有較小規(guī)模的二進制向量集合。因此，我們將原型合成看作成一個最優(yōu)問題，最優(yōu)的集合RS是依據(jù)相關分類的代價函數(shù)進行最小化

式中：Err（RS）——誤判率。

本文中，為了從原型集合RS中得到最優(yōu)原型集合，我們應用演化策略 （evolution strategy）［10］在一系列的候選原型問題上。如圖5所示，演化策略依據(jù)的是變異算子［11，12］。這種算子在染色體特征中引入了隨機的變化因子，通常由基因突變產(chǎn)生的新的個體與原有的差別不是很大，換句話說，變異算子提供了一種少量的變化因子在種群融合中進行隨機搜索。因此，解決最優(yōu)問題就成了必要的，為了滿足這些條件，我們使用了ART1基礎算法描述了先前的選擇。

圖5 ART1－ES策略

假設初始的種群特征Pop＝｛1，2，…，NPop｝包含了所有群體NPop的特征，每個群體的特征i 是一個二進制向量，它是對代表集合的響應。中的每個元素是T 的按位向量 （其中T 是特征向量的維數(shù)）。因此，通過式 （6）可以計算出每個類別特征i 合適的值，將其作為該種群的代價函數(shù)CF（）。我們實現(xiàn)演化策略的過程如下：

（1）設置g ＝1和評估每個種群特征i 的值在所有的種群特征集Popg－th中的適合性。

（2）根據(jù)每個種群特征的i 值的適合程度在Popg－th對進行排列，并且根據(jù)變異率將他們分成不同的種群。

（3）生成一下代群體的過程［10］：依據(jù)每個個體所屬的種群，以及相應的和進行變異，產(chǎn)生新的種群，之后，將產(chǎn)生的新的群體作為下一代種群集合Ug－th。

（4）根據(jù)目標函數(shù)計算i 的值，并為其分配合適的值，進行評估，∈Ug－th。

（5）從Ug－th選擇出合適的個體srNPop，從Pop（g＋1）－th中為其分配。（sr是選擇的概率）。

（6）如果停止條件滿足，則終止搜索并且返回當前的種群Pop（g＋1）－th，否則，設置g ＝g＋1，繼續(xù)循環(huán)步驟（2）～步驟 （6）。直到所產(chǎn)生個體的種群滿足或者代價函數(shù)滿足：，終止在種群中搜索。

5 實驗結果

5.1 距離矢量的最優(yōu)

表1 k－NN 識別率

為了提高識別率，應該將更多的權重應用于等級1，這是因為等級0，它具有的區(qū)域比較小可能丟失一些重要的信息，等級2，具有的區(qū)域比較大，可能包含一些沒有必要的信息，而且，相異度量的線性加權組合對于提高識別率非常重要。如果我們僅僅應用等級0、等級1、等級2，則只能獲得97.91%、96.87%、89.92%的識別率。這表明將這3個等級區(qū)分單獨考慮，則識別率最高的為等級0，但是，等級0的識別率仍然要低于3個等級擁有相同加權組合的識別率98.77%。

5.2 原型生成技術的進化

通過大量的實驗生成和比較最優(yōu)原型代表集的生成。首先我們應用了ART1算法在MNIST 訓練集上和根據(jù)不同的警惕函數(shù)建立不同的代表集合，通過一些測試之后，我們選擇警惕參數(shù)δ ＝0.35。對于MNSIT 的測試樣本，通過這個代表集最終的識別率為97.32%。

在演化策略 （ES）中，選擇的參數(shù)為NPop＝10，＝100，ε＝0.01，α＝2，μr1＝0.001，μr2＝0.002，Sr＝0.5，通過測試一些數(shù)值確定k ＝3。實驗運行在Matlab7.8版本上［13］，其最終的識別率最好的可達到98.73%。例外，通過演化策略生成的原型技術的識別率要比單一的依靠ART1算法生成的好，這是因為，演化策略僅僅是對ART1階段提供的原始問題進行微調(diào)，避免使用復雜的演化算法。圖6表示了每種類別的識別率和總的識別率，結果顯示一些數(shù)字頻繁的被誤判。這是因為他們在形狀上幾乎是相似的，導致從代表原型集中計算距離度量過程出現(xiàn)無效的判決。

圖6 每種類別的識別率和總的識別率

這種所提出的原型生成技術已經(jīng)確定了721 種原型，它比MNIST 訓練集的維數(shù)要小的很多，見表2。訓練集具有的60000種樣本，但是最終我們只需要確定其中的721種樣本作為具有代表性的原型。

表2 原型集合的維數(shù)和MNIST 訓練集的維數(shù)

它表明了每一個數(shù)字類別都是依靠不同的原型表示，主要的依據(jù)的是類別內(nèi)部之間的不同變化，因此，需要對每個類別的不同形式進行表示是重要的。而且，傳統(tǒng)的k－NN （k＝3）的分類算法在MNIST 上的識別率為98.85%。因此，這種技術有效的減少了分類的時間，但其識別率保持相對較高。表3 分別顯示了傳統(tǒng)k－NN 算法和原型生成技術的識別率和相應的分類時間。

表3 傳統(tǒng)k－NN 算法和原型生成技術的比較

6 結束語

本文提出一種采用原型生成技術的k－NN 算法來實現(xiàn)手寫體數(shù)字的識別，該技術包含兩個階段的內(nèi)容，第一階段采用ART1理論實現(xiàn)決定熟悉原型和選擇有效的初始解決方案，之后應用演化理論生成最終的解決方案。依據(jù)所建立的代表原型集，k－NN 分類器的識別率達到了98.73%，同時分類的時間減少。因此，該解決方案能夠很好地權衡識別率和分類速度，但是，仍存在一些問題需要繼續(xù)研究，例如，在演化策略中的參數(shù)的選定，本文中的參數(shù)選擇主要依據(jù)的是傳統(tǒng)數(shù)值。另外，在學習過程的更新階段需要進一步的提升，需要選擇更好的學習函數(shù)應用在ART1算法中。

［1］Angiulli F.Fast nearest neighbor condensation for large datasets classification ［J］.IEEE Transactions on Knowledge and Data Engineering，2007，19 （11）：1450－1464.

［2］Chang R，Pei Z，Zhang C.A modified editing k－nearest neighbor rule ［J］.Journal of Computers，2011，6 （7）：1493－1500.

［3］Beiping H，Wen Z.Fast human detection using motion detection and histogram of oriented gradients［J］.Journal of Computers，2011，6 （8）：1597－1604.

［4］Déniz O，Bueno G，Salido J，et al.Face recognition using histograms of oriented gradients ［J］.Pattern Recognition Letters，2011，32 （12）：1598－1603.

［5］Pekalska E，Duin RP.Beyond traditional kernels：Classification in two dissimilarity－based representation spaces［J］.IEEE Transactions on Systems，Man，and Cybernetics，PartC：Applications and Reviews，2008，38 （6）：729－744.

［6］Cunningham P.A taxonomy of similarity mechanisms for casebased reasoning ［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21 （11）：1532－1543.

［7］Ciresan DC，Meier U，Gambardella LM，et al.Deep big simple neural nets excel on handwritten digit recognition ［N］.CoRR，abs／1003.0358，2010.

［8］Gil－Pita R，Yao X.Evolving edited K－nearest neighbor classifiers［J］.International Journal of Neural Systems，2008，18（6）：459－467.

［9］García S，Derrac J，Cano JR，et al.Prototype selection for nearest neighbor classification：taxonomy and empirical study［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （3）：417－435.

［10］Back T.Evolutionary algorithms in theory and practice：Evolution strategies，evolution programming，genetic algorithms［M］.New York：Oxford University Press，2011.

［11］Beyer H－G，Schwefel H－P.Evolution strategies：A comprehensive introduction ［J］.Journal： Natural Computing，2008，1 （1）：3－52.

［12］Danesh M，Naghibzadeh M，Totonchi MRA，et al.Data clustering based on an efficient hybrid of K－h(huán)armonic means，PSO and GA ［J］.Transactions on Computational Collective Intelligence，2011，4：125－140.

［13］QIN Xiangpei.MATLAB image processing and interface programming ［M］.Beijing：Electronics Industry Publishing，2009：454－455 （in Chinese）.［秦襄培.MATLAB圖像處理與界面編程寶典 ［M］.北京：電子工業(yè)出版社，2009：454－455］.