楊晨 林國宇

摘要：KNN算法在數(shù)據(jù)分析領(lǐng)域有著重要的應(yīng)用。文章針對KNN算法中參數(shù)k選擇不合理將導(dǎo)致分類結(jié)果準(zhǔn)確率低的問題，將K折交叉驗(yàn)證法應(yīng)用于KNN算法中k值的選取，通過k值分析圖選取最佳k值，利用Python語言并基于Sklearn庫實(shí)現(xiàn)KNN算法。在鳶尾花數(shù)據(jù)集上的實(shí)驗(yàn)表明，該模型是進(jìn)行花卉分類的有效方法。

關(guān)鍵詞：KNN算法；聚類；花卉分類

中圖分類號：TP399? 文獻(xiàn)標(biāo)志碼：A

0 引言

分類算法是人工智能領(lǐng)域研究的重要分支，通過對比樣本間的相似度進(jìn)行分類。分類算法已被廣泛應(yīng)用于智慧園林［1］，用于對城市中的各類花卉進(jìn)行識別和檢測，從而有針對性地預(yù)防各類花卉病蟲害，保護(hù)植物的健康生長，有利于加快我國城市的綠色低碳發(fā)展。根據(jù)植物的生長特性和形態(tài)屬性來對花朵進(jìn)行描述是識別植物的高效、簡便的方法。

KNN作為分類算法中最簡潔清晰而邏輯明了、快速簡單且最高效的分類算法之一［2］ ，在不同領(lǐng)域都得到了廣泛應(yīng)用。本文旨在利用KNN算法對植物的花朵進(jìn)行識別，并在鳶尾花數(shù)據(jù)集上進(jìn)行驗(yàn)證。

1 KNN算法介紹

KNN算法通常被人們泛稱為最近鄰居算法或被稱為K最近鄰（K-Nearest Neighbor）分類算法，KNN算法的一個(gè)指導(dǎo)性思想是“近紅赤，近墨黑”，根據(jù)當(dāng)前已知的最近鄰居來推斷出所屬類別。KNN算法有計(jì)算簡單與便捷、精準(zhǔn)度比較高、對異常和數(shù)值誤差不特別敏感等突出特點(diǎn)。其首次是在1968年由Cover和Hart發(fā)表出來，發(fā)展到當(dāng)代在理論上已經(jīng)相對完善，是一種舉足輕重的非參數(shù)類的分類算法。非參數(shù)類的特性使得該算法僅僅只通過對花卉特征數(shù)據(jù)進(jìn)行擬合來分析，而不對特征數(shù)據(jù)進(jìn)行參數(shù)修正后再進(jìn)行分類，使得最終的分類結(jié)果能更加貼合實(shí)際情況。

首先，計(jì)算每個(gè)待排序訓(xùn)練樣本數(shù)據(jù)與已知訓(xùn)練類別數(shù)據(jù)之間的最小距離，并盡可能多地找到下一個(gè)可能最接近待排序結(jié)果的訓(xùn)練樣本數(shù)據(jù)中的前k個(gè)相鄰點(diǎn)。其次，在進(jìn)行分類或檢驗(yàn)后的訓(xùn)練樣本數(shù)據(jù)中包含的訓(xùn)練要素類別數(shù)可以僅根據(jù)該樣本的相鄰的各訓(xùn)練要素?cái)?shù)據(jù)或所屬訓(xùn)練要素?cái)?shù)據(jù)的類別確定［3］。具體實(shí)現(xiàn)算法步驟如下：

（1）創(chuàng)建用來訓(xùn)練的樣本集合D。

（2）設(shè)定k值。確定一個(gè)初始值，根據(jù)多次重復(fù)試驗(yàn)得出最優(yōu)的結(jié)果。

（3）計(jì)算得出各個(gè)測試樣本與每個(gè)訓(xùn)練樣本間的歐氏距離。從訓(xùn)練樣本集合中選出和測試樣本的歐式距離最近的樣本為作為測試樣本的k個(gè)鄰近值。構(gòu)建一個(gè)n維空間向量，將樣本放置于其對應(yīng)的n維空間Rn中，根據(jù)歐式距離定義，把任意的樣本x表示為特征向量x=（x1，x2…，xm），則xm為第m個(gè)特征的值，設(shè)任意兩個(gè)樣本xi和xj之間的距離定義為d（xi，xj），其中，d（xi，xj）=∑ni=1（xi-yi）2。

（4）選擇k個(gè)近鄰樣本。將根據(jù)公式計(jì)算出來的歐式距離從小到大排序，選擇歐式距離相對接近的k個(gè)樣本作為測試樣本中的k個(gè)鄰近樣本。

（5）尋找主導(dǎo)類型。假設(shè)k個(gè)近鄰樣本為x1，x2，…，xk，其類型標(biāo)簽設(shè)為c1，c2，…，ct，將這些類型標(biāo)簽統(tǒng)一歸類于標(biāo)簽集C。根據(jù)k個(gè)近鄰的類型采用最大概率法對鄰近樣本進(jìn)行分類。該方法中的概率是每一類型的k個(gè)鄰近樣本占所有鄰近樣本的比例，用每種類型在k個(gè)鄰近中的樣本數(shù)量除以總數(shù)k來進(jìn)行計(jì)算。將其中具有最大概率的類型作為主導(dǎo)類型。設(shè)S={s1，s2，…st}為k個(gè)近鄰中每類別樣本數(shù)量的集合。設(shè)Ω=SMax為主導(dǎo)類型。

（6）將待測樣本歸為Ω類。重復(fù)執(zhí)行3，4，5直到Ω趨于穩(wěn)定。

1.1 KNN算法的優(yōu)點(diǎn)

KNN算法操作簡便、易于理解，易于處理多模分類和多標(biāo)簽分類問題（Multi-modal，即研究對象具有多種類型），尤其是對于鳶尾花這類有具體明顯特征的植物。同時(shí)，當(dāng)類別體系的變化和訓(xùn)練集的變化時(shí)重新訓(xùn)練很便捷（例如：對鳶尾花添加新的訓(xùn)練樣本）。不需要應(yīng)用訓(xùn)練，只需要輸入樣本集計(jì)算機(jī)完成分類后，當(dāng)再輸入新的樣本時(shí)就會識別并自動(dòng)分類出來。

1.2 KNN算法的不足

KNN算法中的參數(shù)k表示著k個(gè)距離最近的樣本，結(jié)果的正確與否與k的取值有著很大的關(guān)系，如圖1所示。當(dāng)k=3時(shí)，圖中方塊應(yīng)該為三角形，而k=5時(shí)圖中的方塊應(yīng)該為圓形，所以參數(shù)k不同的取值有著不同的結(jié)果。選取過小的k值，使得訓(xùn)練對象數(shù)量太少，導(dǎo)致分類結(jié)果受到噪聲影響大大增加，同時(shí)模型會變得復(fù)雜化，容易出現(xiàn)擬合結(jié)果過擬合的現(xiàn)象，但k值如果過大，則會引入過多的噪聲樣本，導(dǎo)致分類結(jié)果的準(zhǔn)確度降低，同時(shí)模型又變得單一化，使得結(jié)果出現(xiàn)欠擬合的現(xiàn)象?？傊琸值選擇太小導(dǎo)致鄰居數(shù)量太少，會降低分類精度，還會進(jìn)一步放大噪聲數(shù)據(jù)和干擾信號數(shù)據(jù)。如果k的值太大，那么在樣本分類中真正屬于該類的數(shù)據(jù)樣本較少，會導(dǎo)致實(shí)際上不相似的數(shù)據(jù)也會包含在內(nèi)，導(dǎo)致噪聲增加，分類效果降低［2］。由于傳統(tǒng)上的KNN算法往往需通過反復(fù)實(shí)驗(yàn)和計(jì)算來準(zhǔn)確選擇合適的k值，本文主要采用交叉驗(yàn)證法選取最優(yōu)值的k值。

2 利用 KNN算法實(shí)現(xiàn)植物分類

本文通過交叉驗(yàn)證的方法尋找最優(yōu)k值，利用植物花朵的特征來判斷類別。使用Python語言實(shí)現(xiàn)該實(shí)驗(yàn)，數(shù)據(jù)集采用Sklearn官方提供的鳶尾花相關(guān)數(shù)據(jù)集。

2.1 K折交叉驗(yàn)證的優(yōu)點(diǎn)

K折交叉驗(yàn)證［4］可以解決植物花朵數(shù)據(jù)集的數(shù)據(jù)量不夠大的問題和KNN算法中k值參數(shù)尋優(yōu)的問題，該方法能夠有效提高模型評估的準(zhǔn)確性，對于樣本外數(shù)據(jù)有更高的準(zhǔn)確率，從而最大程度地發(fā)揮原始的所有樣本數(shù)據(jù)的作用。

2.2 k值尋優(yōu)

KNN算法中參數(shù)k的取值對結(jié)果有顯著的影響，本文考慮通過K折交叉驗(yàn)證的一種方法來準(zhǔn)確選取k的值，該驗(yàn)證方法將原始的所有樣本數(shù)據(jù)分成n份相同容量的樣本子集（“折”），隨機(jī)選取其中一份作為測試集，接著拿其他的n-1份樣本數(shù)據(jù)組成訓(xùn)練集訓(xùn)練模型，為樣本進(jìn)行訓(xùn)練，接著計(jì)算各個(gè)模型在測試集上的均方誤差MSEi，將n次MSEi取算術(shù)平均后得到CVn。

CVn=1n∑ni=1MSEi

根據(jù)上式計(jì)算出錯(cuò)誤率。筆者先取較小的k值，接著逐漸增加k值的大小，再通過計(jì)算驗(yàn)證集合的方差，根據(jù)方差數(shù)值和錯(cuò)誤率繪制分析圖，錯(cuò)誤率最低處對應(yīng)的k值即為最優(yōu)解，選取對應(yīng)k值為KNN算法中的k個(gè)距離最近的樣本。

2.3 算法實(shí)現(xiàn)

本文使用經(jīng)典的鳶尾花數(shù)據(jù)集，數(shù)據(jù)集包含了鳶尾花、變色鳶尾花、弗吉尼亞鳶尾花3種不同的花型品種中鳶尾花的花瓣長度、花萼長度和花萼寬度還有花瓣寬度這4項(xiàng)特征屬性值，鳶尾花形態(tài)如圖2所示。

使用Python語言中的Sklearn庫對KNN算法進(jìn)行模型搭建，本文使用KNN算法進(jìn)行花卉分類的算法步驟如下。

（1）計(jì)算錯(cuò)誤率：讀取Sklearn 官方提供的鳶尾花相關(guān)數(shù)據(jù)集并循環(huán)設(shè)置k值，其中k∈［1，31］，根據(jù)K折交叉驗(yàn)證的方法計(jì)算出錯(cuò)誤率。

（2）繪圖：利用錯(cuò)誤率與k值繪制分析圖，如圖3所示。

（3）選取k值：通過分析圖可以看出當(dāng)k接近11時(shí)，錯(cuò)誤率達(dá)到最低值。對比實(shí)驗(yàn)采用不同的k值對結(jié)果進(jìn)行分析。

（4）擬合數(shù)據(jù)：在KNN算法中存在一個(gè)重要的權(quán)

重參數(shù)weights。算法模型本身對應(yīng)是uniform與distance。uniform參數(shù)主要表示距離的大小而與權(quán)重參數(shù)無關(guān)。distance參數(shù)表示出來的數(shù)據(jù)是權(quán)重大小和距離的大小成反比，權(quán)重越小，距離預(yù)測目標(biāo)越遠(yuǎn)。本文分別采用這兩種方式來構(gòu)建KNN分類器。

（5）結(jié)果如圖4所示。圖4為不同k值不同權(quán)重下的分類結(jié)果。

2.4 結(jié)果分析

通過表1看出，本文實(shí)現(xiàn)的KNN算法在k=11時(shí)，無論在權(quán)重為distance的情況下還是uniform的情況下，其準(zhǔn)確率都明顯高于其他的取值。當(dāng)k=11時(shí)，色彩范圍邊界整體上要比其他取值時(shí)更平滑，并在兩種權(quán)重下都能夠取得較好的效果，說明本文算法具有有效性和魯棒性，如圖4所示。

3 結(jié)語

在KNN算法中，結(jié)果的準(zhǔn)確性與參數(shù)k的取值密切相關(guān)。為了選取最優(yōu)的k值，本文采用了K折交叉驗(yàn)證方法。通過根據(jù)鳶尾花的特征描述對花卉進(jìn)行品類劃分，本文在KNN算法的不同權(quán)重策略下進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，使用K折交叉驗(yàn)證方法選擇參數(shù)k時(shí)，準(zhǔn)確率更高。然而，本文的研究還存在一些不足。盡管準(zhǔn)確率有所提高，但最高僅達(dá)到76%，仍有較大的改進(jìn)空間。另外，K折交叉驗(yàn)證方法在選取k值時(shí)仍需要通過觀察來確定，缺乏自適應(yīng)選擇的能力。因此，有效解決上述問題將成為下一步研究的主要方向。未來的研究可以致力于進(jìn)一步提高分類準(zhǔn)確率，并探索自適應(yīng)選擇參數(shù)k的方法，以改進(jìn)KNN算法在花卉分類中的應(yīng)用。

參考文獻(xiàn)

［1］謝建梅.基于圖像處理的農(nóng)作物病蟲害分類算法的研究［J］.吉林農(nóng)業(yè)科技學(xué)院學(xué)報(bào)，2021（6）：9-13.

［2］竇小凡.KNN算法綜述［J］.通訊世界，2018（10）：273-274.

［3］SUN J， DU W， SHI N. A survey of KNN algorithm［J］. Information Engineering and Applied Computing， 2018（1）：10.

［4］BENGIO Y， GRANDVALET Y. No unbiased estimator of the variance of K-Fold cross-validation［J］. The Journal of Machine Learning Research，2004 （5） ： 1089-1105.

（編輯 王永超）

Research on flower classification technology based on KNN

Yang? Chen， Lin? Guoyu

（Guangzhou College of Technology and Business， Foshan 528131， China）

Abstract：? The KNN algorithm plays a crucial role in data analysis. This paper addresses the issue of low classification accuracy resulting from the improper selection of parameter k in the KNN algorithm. To tackle this problem， the K-fold cross-validation method is employed for selecting the optimal value of k in the KNN algorithm. The best k value is determined through an analysis of the k value diagram. The KNN algorithm is implemented using the Python language and Sklearn library. Experimental results on the iris dataset demonstrate that this model is an effective approach for flower classification.

Key words： KNN algorithm; clustering; flowers classification