基于不同距離公式的KNN算法對鳶尾花的分類

王紫薇 徐凱 侯益明

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

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

0?引言

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

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

1 數據準備與預處理

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

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

2?KNN算法

2.1? KNN原理

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

2.2 距離公式

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

2.2.1 歐氏距離

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

2.2.2 切比雪夫距離

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

2.2.3 曼哈頓距離

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

2.3? 算法流程

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

3 ? 實驗過程

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

4結果分析

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

5 ? 結語

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

[參考文獻]

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

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

[3]李菊霞，李艷文，牛帆，等.基于YOLOv4的豬只飲食行為檢測[J/OL].農業機械學報：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]毛鑫，蔡江輝，張素蘭.一種基于加權切比雪夫距離的圖像分割方法[J].太原科技大學學報，2020（6）：449-455.

（編輯 何 琳）