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

王紫薇 徐凱 侯益明

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

關(guān)鍵詞：KNN;距離公式;分類

0?引言

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

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

1 數(shù)據(jù)準(zhǔn)備與預(yù)處理

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

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

2?KNN算法

2.1? KNN原理

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

2.2 距離公式

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

2.2.1 歐氏距離

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

2.2.2 切比雪夫距離

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

2.2.3 曼哈頓距離

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

2.3? 算法流程

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

3 ? 實(shí)驗(yàn)過(guò)程

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

4結(jié)果分析

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

5 ? 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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

（編輯 何 琳）