基于加權(quán)K—最近鄰分類的手寫數(shù)字識別

摘要：機器學(xué)習(xí)算法是人工智能應(yīng)用領(lǐng)域的熱點研究問題。將改進加權(quán)距離的K-最近鄰分類算法應(yīng)用到手寫數(shù)字智能識別中，通過計算機仿真實驗驗證了該算法預(yù)測準確率為85%。為了減少算法計算量，Kd-Tree等高效的檢索技術(shù)是今后的研究方向。

關(guān)鍵詞：K-最近鄰；智能識別；加權(quán)距離

the Handwritten Digit Recognition Based on Weighted K-Nearest Neighbor Algorithm

YU Yu-lian

（College of Communication Engineering，Shanghai Technical Institute of Electronics&Information，Shanghai 201411，China）

Abstract：Machine learning algorithms are hot research problems in the field of artificial intelligence applications. The improved weighted distance to K - nearest neighbor classification algorithm is applied to intelligent handwritten numerals recognition，the algorithm is verified through the code experiment forecast accuracy of 85%. In order to reduce the algorithm computation，the efficient retrieval technology such as Kd-Tree is the research direction in the future.

Key words：K-Nearest Neighbor；intelligent identification；the weighted distance

1 引言

近年來隨著人工智能應(yīng)用的發(fā)展，機器學(xué)習(xí)算法成了熱點研究問題[1]。在眾多機器學(xué)習(xí)算法中[2]，K-最近鄰（K-Nearest Neighbor，KNN）算法是理論上比較成熟的分類算法[3-4]，有較高的分類準確率。該文首先闡述了KNN算法原理，提出了改進的加權(quán)距離，用以降低算法對K的選擇的敏感度；其次通過計算機仿真實驗論證了KNN算法在手寫數(shù)字智能識別中的應(yīng)用；最后展望了KNN算法改進的研究方向。

2 K-最近鄰（KNN）算法原理

2.1 KNN算法概念

K-最近鄰（KNN）算法是一種典型的非參模型，與生成方法（generalizing method）不同的是，在KNN算法中，通過以實例的形式存儲所有的訓(xùn)練樣本。對于一個待預(yù)測的樣本，通過計算它與訓(xùn)練樣本之間的差異性，并將差異按照由小到大排序，選出前面K個差異最小的類別，并統(tǒng)計在K個中類別出現(xiàn)次數(shù)最多的類別為最相似的類，最終將待預(yù)測樣本分到最相似的訓(xùn)練樣本的類中。

2.2 樣本差異性算法

常用的差異性計算方法為歐式距離、曼哈頓距離等。該文實驗中使用歐式距離：假設(shè)測

試樣本，訓(xùn)練樣本，兩者之間的歐式距離為D，D

值越小，兩者相似度越大。

2.3 KNN算法流程

（1）計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離；

（2）按照距離的遞增關(guān)系進行排序；

（3）選取距離最小的K個點；

（4）確定前K個點所在類別的出現(xiàn)頻率；

（5）返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。

2.4 改進的加權(quán)距離

在多數(shù)表決方法中，每個近鄰對分類的影響都一樣，這使得算法對K的選擇很敏感。降低K的影響的一種途徑是根據(jù)每個最近鄰Xi距離的不同對其作用加權(quán)，取距離的倒數(shù)作為權(quán)重：

從而降低遠離待分類樣本的那些訓(xùn)練實例的影響，加權(quán)后的表決公式為：

3 計算機仿真實現(xiàn)KNN算法

以手寫字體MNIST數(shù)據(jù)庫識別為例，該數(shù)據(jù)庫共包含7000幅圖像：6000幅訓(xùn)練圖像（用于創(chuàng)建模），1000幅測試圖像（用于評估模型的精度）。每個 MNIST 圖像是一個單一的手寫的數(shù)字字符的數(shù)字化的圖片，每個圖像是 28 x 28 像素大小。每個像素值是范圍是[0 255]，0表示白色，255表示黑色，中間像素值表示各灰度級。圖1所示為MNIST庫手寫數(shù)字測試樣本。通過計算機仿真實驗實現(xiàn)KNN算法在在手寫數(shù)字識別中的應(yīng)用。

4 結(jié)束語

文中用加權(quán)距離的KNN算法進行了手寫數(shù)字智能識別，最終的預(yù)測準確率為85%。由于每一個預(yù)測樣本需要與所有的訓(xùn)練樣本計算相似度，計算量比較大。為了降低為測試樣本尋找最近鄰的時間和計算量，今后將研究高效的索引技術(shù)，如Kd-Tree，Ball-tree、Cover-Tree等。

參考文獻：

[1]曹承志. 人工智能技術(shù). 北京：清華大學(xué)出版社，2010.

[2]陳凱，朱鈺. 機器學(xué)習(xí)及其相關(guān)算法綜述. 統(tǒng)計與信息論壇，2007，22（5）：105-112.

[3]石欣等. 基于K最近鄰分類的無線傳感器網(wǎng)絡(luò)定位算法. 儀器儀表學(xué)報，2014，35（10）：2238-2247.

[4]蘇毅娟等. 大數(shù)據(jù)下的快速KNN分類算法. 計算機應(yīng)用研究，2016，33（4）：1003-1006.

通訊作者簡介：

俞玉蓮（1979-），女，副教授，碩士研究生，主要研究方向：信號與信息處理。