任美麗，孟 亮

（太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原030024）

0 引 言

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

1 工程簡介

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

2 基于分類的原型

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

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

2.1 特征提取

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

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

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

圖2 每個(gè)方向的梯度分解

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

圖3 方向梯度的二進(jìn)制直方圖

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

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

2.2 距離矢量

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

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

式中：v1、v2——兩個(gè)比較向量

wi（i＝0，1，2）是子向量相異的權(quán)重。

3 原型選擇算法——ART1

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

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

圖4 無監(jiān)督式學(xué)習(xí)過程

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

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

4 原型合成

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

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

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

圖5 ART1－ES策略

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

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

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

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

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

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

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

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

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

表1 k－NN 識別率

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

5.2 原型生成技術(shù)的進(jìn)化

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

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

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

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

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

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

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

6 結(jié)束語

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