機器學習

k Nearest Neighbor classifier (kNN) 的 tensorflow 實作

Posted by Cyrus Chiu on 2017-12-01

k Nearest Neighbor classifier (kNN) 的 tensorflow 實作

這篇文章會提到：

  • 使用 tensorflow 實作 kNN 演算法
  • numpy 與 tensorflow 在常見 distance metric 的實作方法比較
  • 基於 tensorflow v1.4.0 撰寫

最近有個專案使用了 scikit-learn 的 kNN 演算法，但由於要預測的資料量有上億筆，並且需要週期性的不斷更新結果，就興起了拿 GPU 加速運算的念頭，於是便用 tensorflow 寫了一套操作方式與 scikit-learn 雷同的 kNN 演算法模組。

在網路上 google 一下其實不難找到一些使用 tensorflow 實作 kNN 的範例，但大多都是簡單的實現，我認為缺乏以下兩個功能：

  1. 一次只能計算一筆資料：GPU memory 明明就裝的下更多資料，一次只計算一筆實在太浪費了！
  2. 用的 distance metric 是寫死的：scikit-learn 的 kNN 允許使用不同的 metric 來做為 kNN 中距離的度量，常見的 L2 distance 有時不見得是最適合的。

這次就針對以上兩點來做些改善。

kNN 演算法的概念基本上就是尋找與目標資料點最接近的 k 個鄰居，並統計這 k 個鄰居中大部分屬於哪一類型，就把目標資料點歸類為該類型的人。有了這個概念，很快就可以實作出來。

Distance Function

上面談到最接近，如何定義最接近，便要先定義距離。下面就先把常見的三種 distance metric 實現出來。

Manhattan distances（L1 distances）

$$\sum_{i=1}^{n}\left | \vec{x_i} - \vec{y_i} \right |$$

最基本的實現就是向量 $\vec{x_1}$ 與 $\vec{x_2}$ 的直接運算：

>>> x1 = np.array([1, 2, 3])
>>> x2 = np.array([1, 0, 1])
>>> sum(abs(x1-x2))
4

如果今天希望是矩陣對矩陣的運算，例如 training set 中有 ${ \vec{x_1}, \vec{x_2}, \vec{x_3} }$ 三筆資料，test set 中有 $ { \vec{x_4}, \vec{x_5} }$ 兩筆資料，我們希望一次回傳 $\vec{x_4}, \vec{x_5}$ 對於 training set 中三筆資料的所有距離，可以透過操作 numpy array 的維度來實現：

>>> X_train = np.array([[1,2,3], [2,3,4], [3,4,5]]) #x1, x2, x_3
>>> x_test = np.array([[1,0,1], [3,0,2]]) #x4, x5
>>> abs(X_train - x_test[:, None]).sum(axis=2)
array([[ 4,  7, 10],  # x4 對於 x1, x2, x3 的距離
       [ 5,  6,  7]])

tensorflow 也支援維度的操作，我們可以改寫如下，可以看出來基本上是和 numpy 一模一樣的操作：

>>> l1 = tf.reduce_sum(
	       tf.abs(tf.subtract(
		  X_train, tf.expand_dims(x_test, 1))), axis=2) 
>>> tf.Session().run(l1)
array([[ 4,  7, 10],
       [ 5,  6,  7]])

Euclidean distances (L2 distances)

$$\sqrt{\sum_{i=1}^{n}\left ( \vec{x_i} - \vec{y_i} \right )^2}$$

這便是最常見的歐式距離 – 平方開根號。這部份在 numpy 已經有很完善的資源。

向量對向量的版本：

>>> from numpy.linalg import norm
>>> x1 = np.array([1, 2, 3])
>>> x2 = np.array([1, 0, 1])
>>> norm(x1 - x2)
2.8284271247461903

矩陣版本（同樣我們需要先擴充維度）：

>>> X_train = np.array([[1,2,3], [2,3,4], [3,4,5]], dtype='f')
>>> x_test = np.array([[1,0,1], [3,0,2]], dtype='f')
>>> XX = X_train - x_test[:, None]
>>> norm(XX , axis=2)
array([[ 2.82842708,  4.35889912,  6.        ],
       [ 3.        ,  3.7416575 ,  5.        ]], dtype=float32)

tensorflow 中也已經有 api 可以使用，不過在這邊可以看到有一些浮點數精度的問題：

>>> tf.norm(tf.subtract(X_train, tf.expand_dims(x_test, 1)), axis=2) 
array([[ 2.82842684,  4.35889864,  5.99999952],
       [ 2.99999976,  3.7416575 ,  5.        ]], dtype=float32)

Cosine distances

$$similarity=\frac{\vec{x}\cdot \vec{y}}{\left | \vec{x} \right |\left | \vec{y} \right |}$$
$$distacne=1-similarity$$

向量對向量的版本，很容易可以寫出來，並且 sklearn 裡面也有直接計算 cosine similarity 的函數可以呼叫，下面我們都只計算到 similarity，改為 distance 只要拿 1 去減就可以 ：

>>> from numpy.linalg import norm
>>> from numpy import dot
>>> x1 = np.array([1, 2, 3])
>>> x2 = np.array([1, 0, 1])
>>> dot(a, b) / norm(x1) * norm(x2)
0.7559289460184544
>>> from sklearn.metrics.pairwise import cosine_similarity
>>> cosine_similarity(x1, x2)
array([[ 0.75592895]])

矩陣版本：

>>> X_train = np.array([[1,2,3], [2,3,4], [3,4,5]], dtype='f')
>>> x_test = np.array([[1,0,1], [3,0,2]], dtype='f')
>>> cosine_similarity(X_train, x_test)
array([[ 0.75592887,  0.66712439],
       [ 0.78783858,  0.72103667],
       [ 0.80000001,  0.74524128]], dtype=float32)

tensorflow 其實也是相對應的操作：

>>> X_norm = tf.sqrt(tf.reduce_sum(tf.square(X_train), axis=1)) # 平方, 相加, 開根號
>>> Y_norm = tf.sqrt(tf.reduce_sum(tf.square(x_test), axis=1))
>>> XY_norm = tf.multiply(X_norm, tf.expand_dims(Y_norm, 1))
>>> XY = tf.reduce_sum(tf.multiply(X_train, x_test[:,None]), 2) # 內積
>>> similarity = XY / XY_norm
>>> tf.Session().run(similarity)
array([[ 0.75592899,  0.78783864,  0.80000001],
       [ 0.66712439,  0.72103673,  0.74524128]], dtype=float32)

kNN 實作

kNN 的演算法本體其實很簡單，這邊先給出比較直觀的程式碼：

def kNN(x_train, y_train, x_test, k):
    # 這邊就是上面定義的 l2 distance
    distance= tf.norm(tf.subtract(x_train, tf.expand_dims(x_test, 1)), axis=2) 
	# 在算出來的 distance 裡面，找出 k 個最近的，回傳 index 與 value
    # tf.nn.top_k 預設回傳排序為大到小，加上 negative 可以逆序排列 
    top_k_xvals, top_k_indices = tf.nn.top_k(tf.negative(distance), k=k)
    
    # 根據回傳的 index，到 y_train 找出對應的 target value
    prediction_indices = tf.gather(y_train, top_k_indices)
	# 回傳的是 1-hot 的 target vector，這邊將他改為整數
    count_of_predictions = tf.reduce_sum(prediction_indices, axis=1)
    
    # 投票結果
    prediction = tf.argmax(count_of_predictions, axis=1)
    
    # 機率
    proba = tf.div(count_of_predictions, k)
    return prediction

scikit-learn 的 kNN 提供了計算機率的 method，predict_proba()，在看了原始碼之後，發現到 scikit-learn kNN 指的機率，其實就是投票數結果的比例。例如，有一筆資料取 k=5 的預測結果如下：

array([0, 0, 1, 1, 2, 1, 0])

這代表這筆資料在上述的 7 個類別底下的投票結果為：

類別 0：0 票
類別 1：0 票
類別 2：1 票
類別 3：1 票
類別 4：2 票
類別 5：1 票
類別 6：0 票

因此，計算機率後的結果就是：

$$
\begin{equation}
\mathcal{P(x)} =
\begin{cases}
0.2 & \text{if $x=2,3,5$} \
0.4 & \text{if $x=4$} \
0 & \text{otherwise}
\end{cases}
\end{equation}
$$

模組化

最後，我們將程式碼整理成一個模組，這個模組使用 tensorflow 計算 kNN，支援 GPU 處理、自定義 distance function、支援批次計算，並且操作方式與 scikit-learn 如出一轍。

>>> from tf_knn import KNeighborsClassifier
>>> X = np.array([[0], [1], [2], [3]])
>>> y = [0, 0, 1, 1]
>>> neigh = KNeighborsClassifier(n_neighbors=3)
{'n_neighbors': 3, 'metric': 'euclidean', 'batch_size': 128}
>>> neigh.fit(X, y) 
>>> print(neigh.predict(np.array([[1.1]])))
[0]
>>> print(neigh.predict_proba(np.array([[0.9]])))
[[ 0.66666667  0.33333333]]

模組化的完整程式碼請參照我的 github repo：https://github.com/CyrusChiu/TensorFlow-kNN

FEATURED TAGS
機器學習