歐式距離與標準化歐式距離在k近鄰算法中的比較

丁義 楊建

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

關鍵詞： 歐式距離;標準化歐式距離;K近鄰算法

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

本文著錄格式：丁義，楊建. 歐式距離與標準化歐式距離在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]，是一種理論上比較成熟的方法，也是最簡單的機器學習算法之一，獲得了廣泛的實際應用[2-5]。KNN算法的基本思想是，在特征空間中，如果一個樣本附近的k個最鄰近樣本的大多數屬于某一個類別，則該樣本也屬于這個類別。即給定一個訓練數據集，對新的輸入樣本，在訓練數據集中找到與該樣本最鄰近的k個樣本如果這k個樣本中大多數屬于某一個類別，就把該輸入樣本分類到這個類別中。目前，KNN在分類算法中獲得了廣泛的應用。KNN是一種基于實例的學習算法，它不同于決策樹、貝葉斯網絡等算法。決策樹算法是一種逼近離散函數值的方法，它首先對待分類的數據進行預處理，之后用歸納算法生成規則和決策樹。貝葉斯網絡又稱為置信網絡或信念網絡，它是基于有向無環圖來刻畫屬性之間的依賴關系的一種網絡結構，使用條件概率表來描述變量的聯合概率分布。在KNN中，當有新的實例出現時，直接在訓練數據集中找k個最近的實例，并把這個新的實例分配給這k個訓練實例中實例數最多的類，它不需要訓練過程，在類的邊界比較清晰的情況下分類的準確率較好。KNN算法需要人為決定k的取值，即找幾個最近的實例，k值不同，分類結果的結果也會不同。

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

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

1? 歐式距離與標準化歐式距離

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

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

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

2? KNN算法

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

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

（2）導入數據集。

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

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

（5）判定屬于哪一類別，應用計算出的分類執行后續處理。算法流程如圖1所示。

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

3? 實驗結果

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

4? 結論

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

參考文獻

[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）.