基于KNN算法的特征過濾預(yù)處理研究

張玉輝 常澤楠

摘? 要：K最近鄰算法是機器學(xué)習(xí)中一種經(jīng)典的監(jiān)督算法。但該算法處理數(shù)據(jù)時需要遍歷所有特征，在處理高維數(shù)據(jù)時，運行效率低。針對該問題，文章采用方差過濾對數(shù)據(jù)特征進行預(yù)處理，該方法可有效降低數(shù)據(jù)特征數(shù)，提高算法運行效率。實驗測試表明，經(jīng)過特征預(yù)處理后的數(shù)據(jù)集，特征數(shù)有效減少，在不降低準確率的情形下，可減少30%的運行時間。

關(guān)鍵詞：KNN;方差過濾;卡方過濾;F檢驗;互信息法

中圖分類號：TP18 ? ? ?文獻標識碼：A文章編號：2096-4706（2022）04-0126-03

Research on Feature Filtering Preprocessing Based on KNN Algorithm

ZHANG Yuhui， CHANG Zenan

（Hunan Petrochemical Vocational Technology College， Yueyang? 414021， China）

Abstract： K-Nearest Neighbors （KNN） algorithm is a classical supervision algorithm in machine learning. However， the algorithm needs to traverse all the features when processing data， and when processing high-dimensional data， the algorithm runs inefficiently. In view of this problem， variance filtering is used in this paper to preprocess data features， which can effectively reduce the number of data features and improve the efficiency of the algorithm. Experimental results show that the number of of data set can be effectively reduced after feature preprocessing， and the running time can be reduced by 30% without reducing the accuracy.

Keywords： KNN; variance filtering; chi-square filtering; F test; mutual information method

0? 引? 言

隨著信息化建設(shè)的蓬勃發(fā)展，數(shù)據(jù)已經(jīng)成為社會發(fā)展、人民生活越來越重要的一部分，對數(shù)據(jù)的分析也已成為計算機發(fā)展的一個重要方向，以數(shù)據(jù)為核心的機器學(xué)習(xí)也已成為一門重要學(xué)科，分類算法是機器學(xué)習(xí)中重點研究對象之一，包括了KNN算法、決策樹算法、隨機森林、邏輯回歸等。其中，KNN算法具有的思想簡潔、易于運用、且在分類問題的處理上有較高的準確率，已被廣泛的運用于分類問題的處理上。為了能提升KNN算法效果，有大量學(xué)者對此進行了優(yōu)化研究，如嚴曉明提出了基于類別平均距離的加權(quán)KNN分類算法，石鑫鑫等提出了融合互近鄰和可信度的KNN算法，李昂提出了基于高斯函數(shù)加權(quán)的自適應(yīng)KNN算法，這些學(xué)者主要的研究工作是針對KNN算法進行優(yōu)化。本文從數(shù)據(jù)處理的整體出發(fā)，針對數(shù)據(jù)集中的特征進行過濾處理，采用優(yōu)化數(shù)據(jù)集的方式，提升KNN算法的運行效率。本文的設(shè)計思想是采用過濾法對數(shù)據(jù)集中的特征進行優(yōu)化，為此，分別對方差過濾、卡方過濾、F檢驗和互信息法的原理進行了研究，編寫了相關(guān)的程序，并設(shè)計了一個采用卡方過濾的KNN算法的對比實驗，通過對比使用卡方過濾前后的KNN算法實現(xiàn)效果，驗證了采用過濾法后的KNN算法應(yīng)用效率有了明顯的提升。

1? KNN算法原理

K最近鄰算法（K-Nearest Neighbors， KNN）由Cover和Hart提出，是機器學(xué)習(xí)中一種較為經(jīng)典的監(jiān)督算法[1]，即可用于處理分類問題，也可用于處理回歸問題，其思路也比較直接，在處理分類問題時，采用少數(shù)服從多數(shù)的原則，在處理回歸問題時，根據(jù)樣本周圍K個鄰近樣本的平均值或進行加權(quán)運算得到的平均值進行預(yù)測。KNN一般多用于處理分類問題，K值和距離度量是對樣本進行計算時影響較大的因子。

K值是指獲取特征空間中離該樣本距離最近的K個值，統(tǒng)計這K個值中各種類別所占的個數(shù)，選出個數(shù)最多的類別作為該樣式的所屬類別[2]，如圖1所示。此種計算方式，K值大小的設(shè)置對異常點的處理和分類的確定影響較大，當(dāng)設(shè)置較大的K值時，雖然較容易排除異常點，但因包含的樣本較多，模型將更簡單，容易產(chǎn)生欠擬合的問題。當(dāng)設(shè)置的K值較小時，雖然解決了欠擬合的問題，但模型將變得復(fù)雜，對異常點的排除變得困難，會帶來過擬合的問題。因此在使用KNN算法中，可通過設(shè)置不同的K值，進行交叉驗證并畫出曲線，最終選取合適的K值。

距離度量是獲取特征空間中距離最近的K個值的關(guān)鍵因素，關(guān)于距離的度量方法主要有：歐氏距離、馬氏距離、曼哈頓距離、閔可夫斯基距離、漢明距離和切比雪夫距離等，在使用KNN算法時可根據(jù)特征空間的不同選擇合適的距離度量方法。歐幾里得度量是最常見的兩點之間或多點之間的距離表示法[3]。在二維空間下，歐氏距離計算公式為：

ρ為點（x2，y2）與點（x1，y1）之間的歐氏距離;| X |為點（x2，y2）到原點的歐氏距離。

三維空間下，歐氏距離計算公式為：

n維空間下，歐氏距離計算公式為：

KNN算法計算時會遍歷數(shù)據(jù)集中的所有特征，當(dāng)數(shù)據(jù)集中的特征越多，計算所需要的時間也越長。為了縮短KNN算法的計算時長，可對特征進行預(yù)處理，過濾具有干擾性的特征和影響力為零的特征，甚至有時為了提高計算效率，在將準確率降低到可接受的前提下，過濾部分影響力較小的特征。因此，為了達到優(yōu)化KNN算法，可對數(shù)據(jù)集特征進行預(yù)處理。

2? 過濾法

2.1? 方差過濾

方差過濾的中心思想是將特征中方差值較小的特征過濾掉，保留方差值較大的特征。因為在數(shù)據(jù)集中，某特征方差的大小決定了此特征在樣本中的區(qū)別度，方差越小，區(qū)別度越小，則對樣本分類計算或回歸計算的影響力越小;方差越大的特征，區(qū)別度越大，對分類計算或回歸計算的影響力也大。在使用方差過濾時，可設(shè)置方差過濾的閾值，當(dāng)某特征的方差小于該閾值時，該特征將被過濾掉。閾值大小的設(shè)置必須與特征的取值范圍相聯(lián)系，當(dāng)某特征的取值范圍較大時，可設(shè)置較大的閾值，當(dāng)某特征的取值范圍較小時，則需降低閾值的大小，默認情況下，閾值設(shè)置為0，即過濾掉影響力幾乎為0的特征。當(dāng)數(shù)據(jù)集中某個特征為伯努利分布時，即二分類時，可采用伯努利方差過濾公式進行計算，伯努利方差計算公式為：σ=p（1-p）。在使用方差過濾預(yù)處理特征時，需根據(jù)模型計算的實際需求，在性能與精度之間找到平衡，設(shè)置合適閾值。

以下為使用方差過濾的代碼：

from sklearn.feature_selection import VarianceThreshold

vt? = VarianceThreshold（threshold=val）

vt.fit（X[，Y]）? //從特征集X中學(xué)習(xí)經(jīng)驗方差

X_vt = vt.transform（X）? ?//對數(shù)據(jù)集進行過濾

如上實現(xiàn)過濾所有閾值小于val的特征，即過濾掉方差值小于val的特征，當(dāng)不設(shè)置threshold參數(shù)時，將默認過濾閾值為0的特征。

2.2? 卡方過濾

卡方過濾主要用于處理分類問題數(shù)據(jù)集中的特征，通過使用卡方方程計算每個特征與類別之間的卡方值[4]，卡方方程為：

Ai為實際頻數(shù)，Ti為理論頻數(shù)。

卡方值越大的特征對分類結(jié)果的影響越大，因此可通過卡方值對特征進行排序，保留卡方值較大的特征，過濾掉卡方值較小的特征，即對分類計算影響較小的特征，實現(xiàn)代碼為：

from sklearn.feature_selection import SelectKBest

from sklearn.feature_selection import chi2

X_chi2= SelectKBest（chi2， k=100）.fit_transform（X， Y）

chi2為卡方檢驗類，用于計算每個非負特征與類標簽之間的卡統(tǒng)計量，該分數(shù)可用于從特征集中選擇測試卡方統(tǒng)計量值最高的特征，相對于類標簽，該特征必須僅包含非負特征。

k=100表示獲取卡方值較大的前100個特征。

2.3? F檢驗

F檢驗是由英國統(tǒng)計學(xué)家Ronald Aylmer Fisher提出，也稱方差齊性檢驗、單因子方差分析或方差檢驗（ANOVA），F(xiàn)檢驗通過求出每個特征與標簽的F統(tǒng)計量[5]，再根據(jù)統(tǒng)計量查F表，如果大于某閾值（一般選取0.05或0.01），表示此特征與標簽具有較強相關(guān)性，保留該特征。如果小于某閾值，則表示此特性與標簽的相關(guān)性較弱，可過濾掉此特征。F檢驗即可用于處理分類問題數(shù)據(jù)集中的特征，也可用于處理回歸問題數(shù)據(jù)集中的特征。

使用F檢驗過濾分類問題特征的代碼：

from sklearn.feature_selection import SelectKBest

from sklearn.feature_selection import f_classif

X_f_classif = SelectKBest（f_classif， k=100）.fit_transform（X，Y）

f_classif用于計算樣本的ANOVA F值，它將返回F值和p值。如要過濾p值小于某閾值（如0.01）的特征，其實現(xiàn)代碼：

f_value， p_value = f_classif（X，Y）

k_value = f_value.shape[0] – （p_value>0.01）.sum（）

X_fcf = SelectKBest（f_classif， k=k_value）.fit_transform（X，Y）

2.4? 互信息法

互信息法通過計算每個特征與標簽的互信息量值，確定每個特征與標簽的相關(guān)性（線性關(guān)系或非線性關(guān)系）[6]，并且回歸問題和分類問題數(shù)據(jù)集中的特征都可以使用互信息法過濾?；バ畔⒘恐档挠嬎愎綖椋?/p>

其中：X表示某個特性數(shù)據(jù)，Y表示標簽，MI為互信息值。

Px（xi）為X的概率密度。

Py（yi）為Y的概率密度。

Px，y（x，y）為X與Y的聯(lián)合分布密度。

當(dāng)X與Y相關(guān)性較弱時，互信息值趨近于0，當(dāng)X與Y相關(guān)性較強時，互信息值趨近于1，互信息化通過將信息值為0的特征過濾掉，達到刪除無效特征的目的。

使用互信息法過濾分類問題特征的代碼為：

from sklearn.feature_selection import SelectKBest

from sklearn.feature_selection import mutual_info_classif as MIC

r = MIC（X，Y）? ?//獲取每個特征與目標之間的互信息量值，值在[0，1]之間

k_value = result.shape[0] – sum（result<=0）//獲取互信息量值大于0的特征數(shù)

X_mic = SelectKBest（MIC， k=k_value）.fit_transform（X，Y）//基于信息量實現(xiàn)過濾

3? 實驗

實驗選用一組分類數(shù)據(jù)集作為實驗數(shù)據(jù)，數(shù)據(jù)集包含了784個特征，42 000個樣本。實驗選用方差過濾對特征進行預(yù)處理，采用KNN算法結(jié)合交叉驗證進行處理，通過對比過濾前后準確率與運行時間，驗證特征預(yù)處理對性能的優(yōu)化。

方差過濾前，運行時間與準確率如圖2所示。

方差過濾后，特征數(shù)為392個，在預(yù)處理后的特征下，運行時間與準確率如圖3所示。

采用方差過濾進行對比實驗的過程中，在不同的數(shù)據(jù)集下，設(shè)置不同的閾值，對KNN算法的影響也會不同。當(dāng)閾值設(shè)置較小時，對于方差值范圍較小的數(shù)據(jù)集，過濾掉的特征將會比較多，模型的準確率會有所變化，KNN算法的運行時間會有明顯地減少，算法優(yōu)化效果明顯;對于方差值范圍較大的數(shù)據(jù)集，過濾掉的特征會比較小，模型的準確率變化不大，KNN算法的運行時間會減少，但不明顯，算法優(yōu)化效果一般。當(dāng)閾值設(shè)置的較大時，對于方差值范圍較小的數(shù)據(jù)集，過濾掉的特征會更多，模型的準確率會有明顯的降低，KNN算法的運行時間會更少，此時，算法在時間上的優(yōu)化是以準確率的大幅度降低為代價;對于方法值范圍較大的數(shù)據(jù)集，過濾掉了無效的特征，模式準確率會有提升，KNN算法的運行時間也會減少，算法的優(yōu)化效果明顯。

4? 結(jié)? 論

本文采用方差過濾進行特征預(yù)處理，將特征數(shù)由784個減少至392個，針對KNN算法與交叉驗證的運行，運行時間減少了1/3，準確率。使用此數(shù)據(jù)集在之后采用卡方過濾、F檢驗和互信息法，進行預(yù)處理實驗的結(jié)果中，特征數(shù)都有一定程度的減少，準確率卻不低于未進行特征預(yù)處理的運行結(jié)果，甚至出現(xiàn)了準確率被提高的結(jié)果。利用特征預(yù)處理可有效提高運算的效率，如果對于數(shù)據(jù)集所對應(yīng)的業(yè)務(wù)有所了解，將更有利于特征的預(yù)處理，為運算效率的提升提供更優(yōu)化的數(shù)據(jù)集。

參考文獻：

[1] 吳星辰.基于KNN算法的城市軌道車輛時序數(shù)據(jù)異常檢測 [J].智能城市，2021，7（22）：20-21.

[2] 張燕寧，陳海燕，常瑩，等.基于KNN算法的手寫數(shù)字識別技術(shù)研究 [J].電腦編程技巧與維護，2021（11）：123-124+132.

[3] 王巨灝，蔡嘉輝，王琨等.基于KNN與LOF算法的臺區(qū)線損異常檢測 [J].電工技術(shù)，2021（24）：175-177.

[4] 劉云，鄭文鳳，張軼.卡方校正算法對入侵檢測特征選擇的優(yōu)化 [J].武漢大學(xué)學(xué)報（理學(xué)版），2022，68（1）：65-72.

[5] 郭鴻飛.F檢驗法和T檢驗法在方法驗證過程中的應(yīng)用探究 [J].山西冶金，2019，42（4）：114-116.

[6] 周育琳，穆振俠，彭亮，等.基于互信息與神經(jīng)網(wǎng)絡(luò)的天山西部山區(qū)融雪徑流中長期水文預(yù)報 [J].長江科學(xué)院院報，2018，35（8）：17-21.

作者簡介：張玉輝（1983.10—），男，漢族，湖南岳陽人，講師，碩士，研究方向：機器學(xué)習(xí)。