一種基于皮爾森相似度和距離權(quán)重的改進(jìn)KNN算法

尹歡一 文志誠 馬正見

摘要：KNN算法中各樣本特征被視為等值權(quán)重，特征之間的關(guān)聯(lián)因素沒有考慮在分類算法中。為了解決此問題，提出一種基于皮爾森相似度和距離權(quán)重的改進(jìn)KNN算法，根據(jù)訓(xùn)練樣本和待分類樣本計算皮爾森相似度和距離權(quán)重來判定特征和類別的相關(guān)度，且提出一種貢獻(xiàn)率類別的判定方法。仿真結(jié)果表明，與KNN算法相比，提高了算法的分類精確度。

關(guān)鍵詞：K近鄰;皮爾森相似度;距離權(quán)重;相關(guān)程度

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

文章編號：1009-3044（2019）27-0208-03

Abstract：In the KNN algorithm， each sample feature is treated as an equivalent weight， and the correlation factors between the features are not considered in the classification algorithm. In order to solve this problem， an improved KNN algorithm based on Pearson similarity and distance weight is proposed. The Pearson similarity and distance weight are calculated according to the training samples and the samples to be classified to determine the correlation between features and categories， and a contribution is proposed. The method of determining the rate category. The simulation results show that compared with the KNN algorithm， the classification accuracy of the algorithm is improved.

Key words：K nearest neighbor; Pearson similarity; Distance weight; Correlation degree

1 引 言

KNN算法模型[1]易于理解，是機(jī)器學(xué)習(xí)經(jīng)典算法中最容易實現(xiàn)的非參數(shù)的監(jiān)督學(xué)習(xí)算法之一，不僅能夠解決分類問題，且在回歸問題上也有很好的表現(xiàn)。但KNN算法也存在一定的缺陷：一是計算訓(xùn)練樣本和待分類樣本特征的距離中未考慮到特征權(quán)重對分類結(jié)果的影響，不同的特征對待分類樣本的分類結(jié)果的貢獻(xiàn)是不相同的 [2];二是KNN作為一種實例學(xué)習(xí)的基本方法[3]，采用簡單的樣本特征間距計算方法，計算待分類樣本與每一個訓(xùn)練樣本特征距離，對距離進(jìn)行排序，以投票的方式判定樣本的類別，算法的計算開銷較大[4];三是當(dāng)訓(xùn)練樣本類別嚴(yán)重切斜時，分類效果不佳，且待分類樣本的分類結(jié)果嚴(yán)重依賴于超參數(shù)K的取值[5]。

針對上述KNN算法的不足之處，在提升算法準(zhǔn)確度方面，有研究學(xué)者提出對樣本的距離賦予權(quán)重，在分類模型中引入權(quán)重值提升了分類的準(zhǔn)確度[6]。但是很少考慮訓(xùn)練樣本和待分類樣本的屬性相關(guān)因素對分類的影響程度，當(dāng)出現(xiàn)距離權(quán)重相近，不同類別的訓(xùn)練樣本近鄰個數(shù)相等時，則無法對待分類樣本進(jìn)行正確分類。

本文在上述問題的研究過程中，著重考慮了樣本之間的特征的相關(guān)程度對樣本分類結(jié)果的影響，提出一種基于皮爾森相似度和距離權(quán)重的改進(jìn)KNN算法（Pearson Similarity and Distance Weight KNN，PSDW-KNN），將皮爾森系數(shù)作為樣本特征之間的相關(guān)程度的度量方式，再結(jié)合KNN算法模型中計算的樣本特征距離，最終確定待分類樣本的類別。文中將PSDW-KNN算法與KNN算法、距離權(quán)重KNN算法進(jìn)行了比較，經(jīng)過仿真實驗發(fā)現(xiàn)，本文PSDW-KNN算法在分類準(zhǔn)確度上比KNN算法、距離權(quán)重KNN算法在近鄰K值取較小值且訓(xùn)練樣本數(shù)不同的情況下，分類準(zhǔn)確度更高。

2 KNN算法

KNN算法在解決分類問題上的主要思想是：給定已知分類的數(shù)據(jù)樣本作為訓(xùn)練樣本集，將訓(xùn)練樣本集輸入到算法模型中存儲，將待分類樣本再輸入到算法模型中計算與訓(xùn)練樣本之間的距離，對距離進(jìn)行排序，選擇距離最近的K個訓(xùn)練樣本，最后將這K個訓(xùn)練樣本中出現(xiàn)次數(shù)最多的類別作為此待分類樣本的類別[7]。距離權(quán)重KNN算法在KNN算法的基礎(chǔ)上為每一個特征添加了距離權(quán)重，算法模型與KNN算法類似。

設(shè)訓(xùn)練樣本[S={X，C} ={（X1，C1），（X2，C2），…，（Xm，Cm）}]作為訓(xùn)練樣本集的第[i]個樣本的[n]維特征向量，[p=1，2，…n]，[Ci∈TC1， C2，…，Cm]為訓(xùn)練樣本類別，[i=1，2，3…m];待分類樣本[S'= {X'，C'}={（X'1，C'1），（X'2，C'2），…，（X'm，C'm）}]，作為待分類樣本集的第[j]個樣本的[n]維特征向量，[k=1，2，…n]，[C'j∈TC'1， C'2， C'3，…，C'm]作為待分類樣本集的類別，[j=1，2，3…m]。

KNN算法的具體分類步驟如下[8]：

輸入：訓(xùn)練樣本XTrain和類別CTrain。

輸出：待分類樣本Xj的類別Cj。

1） 均值方差歸一化，將訓(xùn)練樣本和待分類樣本數(shù)據(jù)歸一到均值為0，方差為1的分布。

2） 計算訓(xùn)練樣本Xi與待分類樣本Xj之間的歐拉距離，n為樣本的特征維度，p=1，2，3…n。

3） 對距離d進(jìn)行排序，通過窮舉的方法取前k個距離d對應(yīng)的訓(xùn)練樣本，查看這k個訓(xùn)練樣本的分類，統(tǒng)計結(jié)果中最多的類別作為[X'（j）]的所屬類別。

4） 遍歷[S']待分類樣本集中的所有樣本，重復(fù)上述2，3步驟，獲得[S']待分類樣本集的類別向量。

3 PSDW-KNN算法

本文在PSDW-KNN算法中通過引入超參數(shù)的方式，動態(tài)調(diào)整皮爾森相關(guān)系數(shù)和距離權(quán)重值兩個類別的判定因素在分類問題上的比重，提出了一種新的類別判定方法：貢獻(xiàn)率判定法。貢獻(xiàn)率作為待分類樣本的判定方法，不僅考慮到縱向距離權(quán)重對分類的影響，還顧及到了特征之間的橫向的特征相關(guān)性。

3.1 皮爾森相關(guān)系數(shù)

皮爾森相關(guān)系數(shù)多數(shù)應(yīng)用場景都是用來描述兩個樣本的線性相關(guān)的度量[9]，對于兩個樣本X={x1，x2，…，xn}，Y={y1，y2，…，yn}，皮爾森相關(guān)系數(shù)定義如下：

式（3）中，n為特征維度，[xi]、[yi]分別是X，Y的均值，[rX，Y∈[-1，1]]表示相關(guān)程度，當(dāng)r取值為-1或1時，表示兩個樣本完全相關(guān)，當(dāng)r取值為0時，表示兩個樣本完全無關(guān)。

為了方便對樣本相關(guān)程度的度量，對式（3）中皮爾森系數(shù)進(jìn)行適當(dāng)變形如下：

其中ρ（X，Y）的取值為0～1，例如計算X1={3，5，1，3}，Y1={4，3，1，9}時，ρ（X1，Y1）=0.2399。X2{3，50，23，3}，Y2={4，3，1，9}時，ρ（X1，Y1）=0.5444。

3.2 貢獻(xiàn)率

對比于KNN算法和距離權(quán)重的KNN算法優(yōu)劣研究表明，當(dāng)出現(xiàn)距離權(quán)重相近，不同類別的訓(xùn)練樣本近鄰個數(shù)相等時，可能導(dǎo)致分類精確度不高或分類錯誤，因此本文將距離權(quán)重和皮爾森相關(guān)系數(shù)都作為影響分類結(jié)果的一部分，提出一種特征貢獻(xiàn)率的分類判定方法。

設(shè)XTrain=（x（1），x（2），…，x（m））為訓(xùn)練樣本集，CTrain={c1，c2，…，cm}為訓(xùn)練樣本集類別，x（j）為待分類樣本，訓(xùn)練樣本集XTrain的特征維度維n，樣本數(shù)為m，特征B的距離權(quán)重可定義如下：

其中m為樣本個數(shù)，n為樣本的特征維度，C為皮爾森相關(guān)系數(shù)的超參數(shù)，用于調(diào)整縱向距離與橫向特征相關(guān)性對分類結(jié)果的影響比重。

PSDW-KNN算法步驟如下：

輸入：待分類樣本XTrain的類別CTrain。

輸出：待分類樣本x（j）的類別Cj。

1） 均值方差歸一化，將訓(xùn)練樣本和待分類樣本數(shù)據(jù)歸一到均值為0，方差為1的分布。

2） 根據(jù)式（4）計算訓(xùn)練樣本與待分類樣本的皮爾森相關(guān)系數(shù)ρ（x（i），x（j）），根據(jù)式（5）和式（6）計算特征的距離權(quán)重向量[θ]。

3） 根據(jù)式（7）計算訓(xùn)練樣本的貢獻(xiàn)率G（x（i），x（j）），且選取最優(yōu)的超參數(shù)C。

4） 對貢獻(xiàn)率G（x（i），x（j））進(jìn)行排序，通過投票的方式，再次選擇前K個訓(xùn)練樣本，查看這K個訓(xùn)練樣本的分類，統(tǒng)計結(jié)果中最多的類別作為x（j）的所屬類別。

下面使用UCI的Optical Recognition of Handwritten Digits數(shù)據(jù)集對PSDW-KNN算法進(jìn)行驗證：

Digits 數(shù)據(jù)集有5620個樣本，64個特征，10個類別。為了測試方便，在Digits 數(shù)據(jù)集中隨機(jī)挑選15個樣本作為訓(xùn)練樣本集，選1個樣本作為待分類樣本，表1是隨機(jī)挑選的15個訓(xùn)練樣本和1個待分類樣本，由于樣本的特征為64，為了便于展示，選擇前6個特征。

（3） 取K的值為3，選取最優(yōu)的超參數(shù)C=1000，根據(jù)式（7）計算訓(xùn)練樣本的貢獻(xiàn)率G（x（i），x（j）），選取前K個樣本的類別為：{7，7，1}，因此最后判定X待分類樣本的類別Cj=7。

4 實驗結(jié)果與分析

為了方便操作和驗證算法的有效性，本文實驗選擇在Mac OS操作系統(tǒng)上完成，選用UCI數(shù)據(jù)集上的Optical Recognition of Handwritten Digits數(shù)據(jù)集，將Anaconda的Jupyter Notebook作為實驗仿真開發(fā)環(huán)境。將Digits數(shù)據(jù)集隨機(jī)切割為訓(xùn)練數(shù)據(jù)樣本和待分類數(shù)據(jù)樣本。為了驗證PSDW-KNN算法的分類準(zhǔn)確度，將KNN算法與距離權(quán)重的KNN算法進(jìn)行對比實驗。

實驗1 測試不同k 值對分類結(jié)果的影響。測試數(shù)據(jù)集占總數(shù)據(jù)集的20%，訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集經(jīng)過均值方差歸一化處理，在Anaconda的Jupyter Notebook將Nearest Neighbor k作為因變量，k值每次遞增的幅度為1，直到k的值為99，仿真得到不同k值下KNN、DW-KNN、PSDW-KNN的算法準(zhǔn)確率，仿真結(jié)果如圖1所示。

在k值為[1～60]區(qū)間范圍內(nèi)，PSDW-KNN的算法在樣本分類的準(zhǔn)確率均高于KNN算法和DW-KNN算法。在k值大于60以后，PSDW-KNN的算法準(zhǔn)確率與DW-KNN算法的準(zhǔn)確率大體一致，且趨于平穩(wěn)。從算法仿真結(jié)果的整體趨勢來看，PSDW-KNN的算法和DW-KNN算法在分類準(zhǔn)確度均高于KNN算法。

實驗2 測試樣本的大小對分類結(jié)果的影響。將k值設(shè)定為40，實驗中訓(xùn)練樣本數(shù)占總樣本集的比率從[10%～80%]， 遞增的幅度為5%。在訓(xùn)練樣本數(shù)不斷遞增的情況下，算法的分類準(zhǔn)確率如圖2所示。

從圖2可以看出，當(dāng)訓(xùn)練樣本逐步遞增的情況下，PSDW-KNN的算法分類準(zhǔn)確率不斷提高，雖然訓(xùn)練樣本數(shù)占總樣本數(shù)的[55%～60%]的區(qū)間內(nèi)，DW-KNN算法的準(zhǔn)確率略高于PSDW-KNN算法的準(zhǔn)確率，但是從這三種算法整體的準(zhǔn)確率趨勢看，PSDW-KNN算法明顯優(yōu)于KNN算法和DW-KNN算法。

5 結(jié)論

本文針對KNN算法和距離權(quán)重KNN算法未考慮訓(xùn)練樣本和待分類樣本的屬性相關(guān)因素對分類的影響程度，提出一種基于皮爾森相似度和距離權(quán)重的改進(jìn)KNN算法，該算法考慮到特征的相關(guān)性和特征的距離權(quán)重兩個方面對分類的影響因素，使用貢獻(xiàn)率的分類方法對待分類樣本進(jìn)行分類。從仿真結(jié)果來看，該算法提高了KNN算法的分類準(zhǔn)確率和分類穩(wěn)定性。由于PSDW-KNN算法主要目的是在原有KNN算法的基礎(chǔ)上，提高分類的準(zhǔn)確率，但是算法計算效率上還有待提高，下一步的研究重點會放在時間復(fù)雜度的優(yōu)化上，提高算法的計算效率。

參考文獻(xiàn)：

[1] 郝巖，白艷萍，張校非.基于KNN的合成孔徑雷達(dá)目標(biāo)識別[J].火力與指揮控制，2018，43（9）：111-113.

[2] Yong Xu，QiZhu，Zizhu Fan，Minna Qiu，Yan Chen，Hong Liu.Coarse to fine K nearest neighbor classifier[J].Pattern Recognition Letters，2013，34（9）：980-986.

[3] 陸微微，劉晶.一種提高K_近鄰算法效率的新算法[J].計算機(jī)工程與應(yīng)用，2008，44（4）：163-165.

[4] Yong Xu，QiZhu，Zizhu Fan，Minna Qiu，Yan Chen，Hong Liu.Coarse to fine K nearest neighbor classifier[J].Pattern Recognition Letters，2013，34（9）：980-986.

[5] Serpen，Gursel Aghaei，Ehsan.Host-based misuse intrusion detection using PCA feature extraction and kNN classification algorithms [J].2018，22（5）：1101-1114.

[6] 嚴(yán)曉明.基于類別平均距離的加權(quán)KNN分類算法[J].計算機(jī)系統(tǒng)應(yīng)用，2014，23（2）：128-132.

[7] 劉磊，初秀民，蔣仲廉，等.基于KNN的船舶軌跡分類算法[J].大連海事大學(xué)學(xué)報，2018，44（3）：15-21.

[8] 戴璞微，潘斌，王玉銘，等.一種基于層次分析法的改進(jìn)KNN算法[J].遼寧石油化工大學(xué)學(xué)報，2018，38（4）：87-92.

[9] 張峰，謝振華，程江濤，等.基于向量皮爾森相關(guān)系數(shù)的組合賦權(quán)法[J].火力與指揮控制，2015，40（5）：83-86.

【通聯(lián)編輯：唐一東】