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

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

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

2.1 KNN算法概念

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

2.2 樣本差異性算法

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

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

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

2.3 KNN算法流程

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

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

（3）選取距離最小的K個(gè)點(diǎn)；

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

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

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

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

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

3 計(jì)算機(jī)仿真實(shí)現(xiàn)KNN算法

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

通訊作者簡介：

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