歐式距離與標(biāo)準(zhǔn)化歐式距離在k近鄰算法中的比較

丁義 楊建

摘? 要： 相似性度量是綜合評定兩個數(shù)據(jù)樣本之間差異的指標(biāo)，歐式距離是較為常用的相似性度量方法之一。本文分析了歐式距離與標(biāo)準(zhǔn)化的歐式距離在KNN算法中對數(shù)據(jù)分類的影響。仿真實驗結(jié)果表明，當(dāng)向量之間的各維度的尺度差別較大時，標(biāo)準(zhǔn)化的歐式距離較好地改善了分類的性能。

關(guān)鍵詞： 歐式距離;標(biāo)準(zhǔn)化歐式距離;K近鄰算法

中圖分類號： TP311? ? 文獻標(biāo)識碼： A? ? DOI：10.3969/j.issn.1003-6970.2020.10.033

本文著錄格式：丁義，楊建. 歐式距離與標(biāo)準(zhǔn)化歐式距離在k近鄰算法中的比較[J]. 軟件，2020，41（10）：135136+140

【Abstract】： Similarity measurement is an index to evaluate the difference between two data samples. Euclidean distance is one of the most common similarity measurement methods. This paper analyzes the influence of Euclidean distance and standardized Euclidean distance on data classification in KNN algorithm. The simulation results show that the normalized Euclidean distance improves the classification performance as the scales of the dimensions between vectors differ greatly.

【Key words】： Euclidean distance; Standardized Euclidean distance; K-nearest neighbor algorithm

0? 引言

K近鄰（k-Nearest Neighbor，KNN）算法[1]，是一種理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)算法之一，獲得了廣泛的實際應(yīng)用[2-5]。KNN算法的基本思想是，在特征空間中，如果一個樣本附近的k個最鄰近樣本的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。即給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入樣本，在訓(xùn)練數(shù)據(jù)集中找到與該樣本最鄰近的k個樣本如果這k個樣本中大多數(shù)屬于某一個類別，就把該輸入樣本分類到這個類別中。目前，KNN在分類算法中獲得了廣泛的應(yīng)用。KNN是一種基于實例的學(xué)習(xí)算法，它不同于決策樹、貝葉斯網(wǎng)絡(luò)等算法。決策樹算法是一種逼近離散函數(shù)值的方法，它首先對待分類的數(shù)據(jù)進行預(yù)處理，之后用歸納算法生成規(guī)則和決策樹。貝葉斯網(wǎng)絡(luò)又稱為置信網(wǎng)絡(luò)或信念網(wǎng)絡(luò)，它是基于有向無環(huán)圖來刻畫屬性之間的依賴關(guān)系的一種網(wǎng)絡(luò)結(jié)構(gòu)，使用條件概率表來描述變量的聯(lián)合概率分布。在KNN中，當(dāng)有新的實例出現(xiàn)時，直接在訓(xùn)練數(shù)據(jù)集中找k個最近的實例，并把這個新的實例分配給這k個訓(xùn)練實例中實例數(shù)最多的類，它不需要訓(xùn)練過程，在類的邊界比較清晰的情況下分類的準(zhǔn)確率較好。KNN算法需要人為決定k的取值，即找?guī)讉€最近的實例，k值不同，分類結(jié)果的結(jié)果也會不同。

相似性度量是綜合評定兩個樣本之間相近程度的一種度量，兩個樣本越接近，它們之間的相似性度量也就越大;反之，兩個樣本差別越大，它們的相似性度量也就越小。一般情況下，采用距離度量兩個樣本的相似程度，數(shù)值越小，距離越近，而相似度越大;而距離越大，相似程度也越遠(yuǎn)。相似性度量應(yīng)用廣泛，例如測度兩幅圖像相似程度的圖像相似性度量，在圖像檢索中獲得了廣泛應(yīng)用;在購物網(wǎng)站中，確定兩個用戶或商品的向量之間的相似程度，以根據(jù)用戶喜好向用戶推薦商品。在KNN算法中，距離相似性度量的種類有多種，一般根據(jù)實際問題進行選用。

本文基于兩種常用的距離，即歐式距離和標(biāo)準(zhǔn)化歐式距離，在給定數(shù)據(jù)集各向量之間的維度尺度差別較大時，來對它們在KNN算法中得到的效果進行比較。

1? 歐式距離與標(biāo)準(zhǔn)化歐式距離

歐氏距離是最簡單和易于理解的一種距離計算方法，來源于歐幾里得幾何中兩點間的距離公式。設(shè)在二維平面上的兩個點分別為A（x1，y1）、B（x2，y2），則A、B兩點間的歐式距離為：

歐式距離盡管應(yīng)用較為普遍，但它適用于樣本向量的各個分量度量標(biāo)準(zhǔn)統(tǒng)一的情形。對絕大部分統(tǒng)計問題來說，由于樣本分量的取值對歐氏距離的貢獻是相同的，往往不能取得令人滿意的效果。特別是當(dāng)各分量的波動范圍量綱差距較大時，會引起各分量對總體的貢獻差別較大，甚至某一坐標(biāo)的貢獻幾乎可以忽略不計，當(dāng)各個分量為不同性質(zhì)的量時，歐式距離的大小與樣本分量的單位有關(guān)。例如某維向量的取值范圍為[0，1]，而另一維向量的取值范圍為[0，100]，前者變量的波動范圍對距離計算的影響很小，甚至可以忽略不計。在這種情況下，合理的方法應(yīng)該是對各個坐標(biāo)分量加權(quán)，使變化較大的坐標(biāo)比變化較小的坐標(biāo)有較小的權(quán)重系數(shù)，將樣本的不同屬性之間的差異量化到同一個區(qū)間。在某些特殊應(yīng)用時，也可以對樣本分量的不同屬性分別賦予不同的權(quán)重，從而取得更理想的計算效果。

標(biāo)準(zhǔn)化歐氏距離是針對簡單歐氏距離的缺點而提出的一種改進方案，當(dāng)向量之間的各維度的尺度差別較大時，使用簡單歐氏距離使得各向量對最終分類結(jié)果產(chǎn)生較大的影響。標(biāo)準(zhǔn)化歐氏距離的思想是，將數(shù)據(jù)各維分量的分布進行歸一化處理，將數(shù)據(jù)的各個分量均標(biāo)準(zhǔn)化到均值、方差。假設(shè)樣本集S的均值為m，標(biāo)準(zhǔn)差為sd，則將特征S標(biāo)準(zhǔn)化為均值為零方差為1的變量。因此，兩個歸一化后的n維向量A（x1， x2， …， xn）、B（y1， y2， …， yn）間的標(biāo)準(zhǔn)化歐氏距離可以表示為：

2? KNN算法

K近鄰算法是數(shù)據(jù)挖掘分類技術(shù)中最常用的方法，它的算法流程如下：

（1）分析數(shù)據(jù)，對數(shù)據(jù)預(yù)處理。刪除含有缺失值的特征，采用PCA[6，7]對數(shù)據(jù)集進行特征選擇降維處理。

（2）導(dǎo)入數(shù)據(jù)集。

（3）設(shè)置參數(shù)k。因為進行分類的策略是按照多數(shù)類來劃分，所以一般k選擇奇數(shù)。

（4）分別采用公式（3）和（5）兩種方法計算特征之間的距離。

（5）判定屬于哪一類別，應(yīng)用計算出的分類執(zhí)行后續(xù)處理。算法流程如圖1所示。

標(biāo)準(zhǔn)化的歐式距離相當(dāng)于對樣本產(chǎn)生的影響賦予不同的權(quán)重[8]。當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其它類樣本容量較小時，當(dāng)輸入一個新樣本時，可能導(dǎo)致該樣本的k個近鄰中大容量類的樣本占多數(shù)，而那些容量較小的樣本采用這種算法比較容易產(chǎn)生錯誤分類。KNN算法不僅可以用于分類，也可用于回歸，根據(jù)現(xiàn)有數(shù)據(jù)對數(shù)據(jù)分類邊界建立回歸公式，從而找到最佳擬合參數(shù)。利用邏輯回歸進行分類的主要思想是，根據(jù)已知的數(shù)據(jù)對分類邊界建立回歸公式，并以此進行分類。KNN算法的優(yōu)點是精度高，對輸入數(shù)據(jù)的異常值不敏感，無數(shù)據(jù)輸入假定，對數(shù)值型數(shù)據(jù)和標(biāo)稱型數(shù)據(jù)都能適用;不足之處是運算量較大，計算復(fù)雜度和空間復(fù)雜度相對較高，同時占用較多的存儲資源，因為對每一個待分類的樣本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。

3? 實驗結(jié)果

圖2和圖3分別給出了兩種方法在數(shù)據(jù)集上的分類效果。k值的選擇會影響算法的結(jié)果，k值較大時，可以減少訓(xùn)練中的誤差估計，但缺點是與輸入樣本距離較遠(yuǎn)的訓(xùn)練樣本也會對預(yù)測起作用，使預(yù)測差錯率提高，k值較小意味著只有與輸入樣本距離較近的訓(xùn)練樣本才會對預(yù)測結(jié)果發(fā)生作用，容易發(fā)生過擬合。實驗中選擇k的值為3。從圖中可以看出，采用標(biāo)準(zhǔn)化的歐式距離，分類邊界效果更清晰，分類效果更有效。為了測試數(shù)據(jù)的分類效果，可以使用帶標(biāo)簽的數(shù)據(jù)，檢驗分類器給出的結(jié)果是否與給定的標(biāo)簽一致，通過大量的測試數(shù)據(jù)，可以計算出分類器的錯誤率，即分類錯誤的樣本數(shù)與樣本總數(shù)之比。在分類執(zhí)行過程中，算法必須保留全部數(shù)據(jù)，如果訓(xùn)練數(shù)據(jù)集很大，則會占用較多的存儲空間。由于必須對數(shù)據(jù)集中的每個數(shù)據(jù)都需要計算距離值，對較大的數(shù)據(jù)集來說，算法需要較長的運行時間。

4? 結(jié)論

本文基于在實際數(shù)據(jù)分類中獲得廣泛應(yīng)用的k近鄰算法，分析了歐式距離和標(biāo)準(zhǔn)化歐式距離對算法的影響，對絕大部分統(tǒng)計問題來說，由于樣本分量的取值對歐氏距離的貢獻相同，往往不能取得令人滿意的效果。標(biāo)準(zhǔn)化歐氏距離是針對簡單歐氏距離的缺點而提出的一種改進方案，當(dāng)樣本的各個特征屬性的取值范圍差別較大時，使用簡單歐氏距離使得各向量對最終分類結(jié)果產(chǎn)生較大的影響，從而使得最終分類效果不理想。采用標(biāo)準(zhǔn)化的歐式距離，克服了數(shù)據(jù)特征的取值范圍波動的差異，能夠優(yōu)化數(shù)據(jù)之間的離散程度，使樣本的各個特征之間量綱統(tǒng)一，也可以根據(jù)具體實際應(yīng)用，賦予不同特征之間不同的權(quán)重，從而取得較好的分類效果。

參考文獻

[1]T. Cover， P. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory. 1967.

[2]Pal， Nikhil R.， Ghosh， Swati. Some classification algorithms integrating Dempster-Shafer theory of evidence with the rank nearest neighbor rules. IEEE Transactions on Systems， Man， and Cybernetics Part A：Systems and Humans. 2001.

[3]Yigit H. A weighting approach for KNN classifier. 2013 International Conference on （ICECCO）Electronics， Computer and Computation. 2013.

[4]Weiss S M， Indurkhya N. Rule-based regression. IJCAI Proceedings of the International Joint Conference on Artificial Intelligence. 1993.

[5]Meesad， P， Hengpraprohm， K. Combination of KNN-Based Feature Selection and KNN Based Missing-Value Imputation of Microarray Data. 3rd International Conference on Innovative Computing Information and Control. 2008.

[6]Xiaojun Chang， Feiping Nie， Yi Yang， Chengqi Zhang， Heng Huang. Convex Sparse PCA for Unsupervised Feature Learning[J]. ACM Transactions on Knowledge Discovery from Data （TKDD）. 2016（1）.

[7]Reiff P A， Niziolek M M. RN. Troubleshooting tips for PCA.[J]. 2001（4）.

[8]Mostafa A. Salama， Ghada Hassan. A Novel Feature Selection Measure Partnership-Gain[J]. International Journal of Online and Biomedical Engineering. 2019（4）.