數據挖掘入門系列教程（二點五）之K-近鄰算法和距離度量介紹

簡介

K-近鄰算法，又名最近鄰居算法，其英文縮寫是KNN（k-nearest neighbors）。是一種用於分類和回歸的非參數統計方法。其可能是標準數據挖掘算法中最為直觀的一種。在這篇博客中，主要討論knn用於分類的情況。

在分類中，為了確定新的個體屬於哪一個類，就尋找訓練集，查找與新個體最為相似的個體，然後根據查找到的大多數個體屬於哪一個類別，就將這個個體分類到這個類別中。

一下面這張圖為例子，我們如何判斷綠色的個體屬於哪一個類別？首先我們尋找與綠色點距離（歐式距離）最近的三個（$K = 3$）個體——2個三角形，1個正方形。三角形多於正方形，此時我們就認為該個體屬於三角形。

近鄰算法幾乎可以對任何數據集進行分類。原理也很簡單，實現也簡單，但是計算量卻比較大，因為他需要對所有的點計算距離。

在上面的舉例中，有兩個關鍵點需要我們注意：

• K的取值
• 距離的計算

K的取值很簡單理解，因為他決定着我們需要考慮多少個」鄰居「，而這個就會影響我們的模型的準確度！

那麼距離的計算是什麼呢？在前面的例子中，我們的距離指的是兩個點連成直線的距離（亦稱歐氏距離），距離越短則代表兩者之間越親密，但是歐式距離越短一定就越近嗎？想一想重慶的山城。

OK，接下來讓我們來講一講距離度量。

距離度量

距離是數據挖掘的核心概念之一。因為我們可以通過距離來判斷一對個體相對另一對個體是否更加的相近。距離的計算有很多種方式，接下來，將介紹幾種常見的計算方式。

歐式距離

歐式距離是我們接觸過最多的一種度量方式，即真實距離。

以下圖為例，我們如何計算A，B之間的歐式距離？

emm，這個很簡單，初中的時候就學過了。

$$
d_{AB} = sqrt{(x_2-x_1)^2+(y_2 – y_1)^2}
$$

上面的公式是二維坐標系情況下的計算的公式，如果是$n$維坐標系呢？
$$
d(x,y)=sqrt{Sigma_{k=1}^n (A_k-B_k)^2}
A_k 代表A點在k軸的位置
$$

我們可以將歐式距離進行標準化：

$$
d(x,y)=sqrt{Sigma_{k=1}^n (dfrac{A_k-B_k}{s_k})^2}
A_k 代表A點在k軸的位置
$$
其中，$s_k$為數據每一維的標準差，之所以這樣做，是因為考慮到了坐標軸中維度的不同。比如說$x$軸的範圍是0~1，但是$y$軸的範圍是0~100，這樣就會造成$x$,$y$軸的權重不同，而是用標準化就可以解決這個問題。

曼哈頓距離

曼哈頓距離也稱為街區距離，如果形象的來說，A到B的距離就是A作為車，A到B需要走多少距離。

如下圖所示，白色的圈圈到黑色的圈圈需要的距離用紅色的線進行表示。

計算距離的公式如下所示。
$$
d(x,y)=Sigma_{k=1}^n left|A_k-B_kright|
k代表的是k維坐標系，A_k 代表A點在k軸的位置
$$

餘弦距離

餘弦距離指的是特徵向量之間的夾角的餘弦值，如下圖紅色部分所示：

至於怎麼計算，感覺又回到了高中～.～

$$
because overrightarrow {a} cdot overrightarrow{b} = |a|times|b|times costheta
therefore costheta = frac{overrightarrow {a} cdot overrightarrow{b}}{|a|times |b|}= dfrac{Sigma_{k=1}^n a_k b_k}{sqrt{Sigma_{k=1}^n a_k^2} sqrt{Sigma_{k=1}^n b_k^2}}
$$

這篇博客主要是講一下近鄰算法以及距離的計算方式。在下一篇博客中，將使用scikit-learn，以KNN為例進行數據挖掘。

距離的度量暫時先說到這裡，以後會繼續進行添加修正。

創建時間：2020.3.09 version 1.0