丁義 楊建

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

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

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

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

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

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

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

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

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

2? KNN算法

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

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

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

（3）設(shè)置參數(shù)k。因?yàn)檫M(jìn)行分類的策略是按照多數(shù)類來劃分，所以一般k選擇奇數(shù)。

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

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

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

3? 實(shí)驗(yàn)結(jié)果

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

4? 結(jié)論

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

參考文獻(xià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）.