王紫薇 徐凱 侯益明

摘 要：傳統(tǒng)的KNN算法采用歐氏距離公式，文章中的KNN算法分別采用歐式距離公式、切比雪夫距離公式、曼哈頓距離公式對鳶尾花數(shù)據(jù)集進行分類，在不同距離公式下，分類結(jié)果的準確率具有一定的區(qū)別，采用切比雪夫距離公式時，分類結(jié)果的準確率達到100%，對以后KNN算法的研究及應用具有重要意義。

關鍵詞：KNN;距離公式;分類

0?引言

數(shù)據(jù)挖掘分類技術(shù)方法眾多，包括決策樹、神經(jīng)網(wǎng)絡、模糊集、粗糙集、回歸分析、差別分析等。數(shù)據(jù)挖掘分類技術(shù)應用越來越廣泛，徐彧鏵采用決策樹對鳶尾花進行分類，對比分析了ID3算法、C4.5算法以及CART算法在鳶尾花分類任務上的可行性[1]。其中，神經(jīng)網(wǎng)絡技術(shù)迅速發(fā)展，應用到很多方面。比如，豬臉識別[2]、豬只飲食行為識別[3]、無人機的小目標實時監(jiān)測[4]。

本文采用基于不同距離計算方法的KNN算法對鳶尾花進行識別，KNN分類算法分別采用歐氏距離公式、切比雪夫距離公式、曼哈頓距離公式對鳶尾花進行分類。在不同距離公式下，得出的準確率、分類時間有一定的區(qū)別。其中，當KNN算法采用切比雪夫距離公式時，分類結(jié)果的準確率可以達到100%，對以后KNN算法的研究具有重要意義。

1 數(shù)據(jù)準備與預處理

Iris鳶尾花數(shù)據(jù)集是一個經(jīng)典公開的數(shù)據(jù)集，數(shù)據(jù)集包含3類，共有150條記錄，每個類別有50條記錄。包含4個特征，分別為花萼長度、花萼寬度、花瓣長度、花瓣寬度。公開的數(shù)據(jù)中已經(jīng)標明了每個特征對應的數(shù)值。

對收集到的鳶尾花數(shù)據(jù)集進行歸一化操作，可以提升模型的精度與收斂速度。Iris鳶尾花數(shù)據(jù)集包含150條記錄，在150條記錄中隨機選擇100條記錄作為訓練集，50條記錄作為測試集。隨機選取可以保證結(jié)果的普遍性。

2?KNN算法

2.1? KNN原理

KNN又稱K鄰近分類算法，KNN算法是一種數(shù)據(jù)挖掘分類技術(shù)，屬于有監(jiān)督學習方法。將未知數(shù)據(jù)的特征與訓練集中的每一個數(shù)據(jù)相對應的特征進行計算，采用距離公式進行相應特征間的計算，計算完畢，再選擇出前K個距離最小的數(shù)據(jù)，計算出的距離代表未知數(shù)據(jù)的特征與訓練集中每一個數(shù)據(jù)的特征的相似度，距離越小，說明相似度越大，未知數(shù)據(jù)是這個數(shù)據(jù)對應的類別的概率越大。在這K個數(shù)據(jù)中，記錄每一個數(shù)據(jù)出現(xiàn)的次數(shù)，出現(xiàn)次數(shù)最多的數(shù)據(jù)對應的類別就是未知數(shù)據(jù)的類別。

2.2 距離公式

在以下公式中，d表示距離，xi表示未知數(shù)據(jù)的特征，yi表示訓練集中的每一個數(shù)據(jù)相對應的特征。

2.2.1 歐氏距離

傳統(tǒng)的KNN算法采用歐氏距離公式對未知數(shù)據(jù)的特征與訓練集中的每一個數(shù)據(jù)相對應的特征進行計算。歐式距離計算公式為：

2.2.2 切比雪夫距離

切比雪夫距離是一種定義在向量空間上的度量方法，也被稱為棋盤距離[5]。切比雪夫距離公式為：

2.2.3 曼哈頓距離

曼哈頓距離又稱為租車距離，距離公式為：

2.3? 算法流程

采用距離公式計算出未知數(shù)據(jù)的特征與訓練集中的每一個數(shù)據(jù)相對應特征的大小之后，再選取前K個數(shù)據(jù)，其中K值的選取會影響到未知數(shù)據(jù)的分類結(jié)果。經(jīng)實驗發(fā)現(xiàn)，當選取K值為14時，得到的分類結(jié)果的準確率達到最高。選擇出前K個數(shù)據(jù)，根據(jù)這K個數(shù)據(jù)中每個類別出現(xiàn)的次數(shù)來得出未知數(shù)據(jù)的類別。出現(xiàn)次數(shù)最多的類別就是未知數(shù)據(jù)的類別。算法流程如圖1所示。

3 ? 實驗過程

根據(jù)KNN算法的原理，首先，將所有的數(shù)據(jù)進行歸一化處理，可以得到一個高精度及收斂速度較快的模型。其次，打亂所有的數(shù)據(jù)，將所有的數(shù)據(jù)分為訓練集和測試集，訓練集和測試集要隨機選取，保證結(jié)果具有普遍性。KNN算法分別以3種距離公式對測試集進行測試。最后，選取前K個數(shù)據(jù)，記錄K個數(shù)據(jù)中每個類別出現(xiàn)的次數(shù)，出現(xiàn)次數(shù)最多的類別就是未知數(shù)據(jù)的類別。分類流程如圖2所示。

4結(jié)果分析

分別采用歐氏距離公式、切比雪夫距離公式、曼哈頓距離公式對隨機選取的測試集進行測試，并記錄下每種距離公式下的分類結(jié)果的準確率以及運行時間。采用歐式距離公式時，分類結(jié)果準確率為98%，運行時間為0.026 927秒;采用切比雪夫距離公式時，分類結(jié)果準確率為100%，運行時間為0.015 021秒;采用曼哈頓距離公式時，分類結(jié)果準確率為96%，運行時間為0.012 925秒。采用切比雪夫距離時準確率雖然能達到100%，但是，與采用曼哈頓距離時相比，運行時間要長。具體數(shù)據(jù)如表1所示。

5 ? 結(jié)語

本文以基于不同距離公式的KNN算法對Iris鳶尾花數(shù)據(jù)集進行分類，分別以歐式距離公式、切比雪夫距離公式、曼哈頓距離公式來計算未知數(shù)據(jù)的特征與訓練集中每一個數(shù)據(jù)相應的特征的相似度，選取出前14個數(shù)據(jù)，根據(jù)14個數(shù)據(jù)的類別對未知數(shù)據(jù)進行分類。當KNN算法采用切比雪夫距離公式時，分類結(jié)果的準確率達到100%，運行時間為? ? ? ? ? ? 0.015 021秒，對以后KNN算法的研究具有重要意義。

[參考文獻]

[1]徐彧鏵.基于決策樹的鳶尾花分類[J].電子制作，2018（20）：99-100，84.

[2]秦興，宋各方.基于雙線性卷積神經(jīng)網(wǎng)絡的豬臉識別算法[J].杭州電子科技大學學報（自然科學版），2019（2）：12-17.

[3]李菊霞，李艷文，牛帆，等.基于YOLOv4的豬只飲食行為檢測[J/OL].農(nóng)業(yè)機械學報：1-10[2021-03-03].http：//kns.cnki.net/kcms/detail/11.1964.S.20210111.0938.010.html.

[4]張偉，莊幸濤，王雪力，等.DS-YOLO：一種部署在無人機終端上的小目標實時檢測算法[J/OL].南京郵電大學學報（自然科學版），2021（01）：1-13[2021-03-03].https：//doi.org/10.14132/j.cnki.1673-5439.2021.01.011.

[5]毛鑫，蔡江輝，張素蘭.一種基于加權(quán)切比雪夫距離的圖像分割方法[J].太原科技大學學報，2020（6）：449-455.

（編輯 何 琳）