人工智慧演算法通俗講解系列(一)：K臨近法

今天，介紹一種特別簡單的機器學習演算法，叫K－臨近法，英文k-nearest neighbors，簡稱KNN。

在介紹演算法之前，我們先舉一個案例。等案例講完後，看看我們怎麼用K－臨近法去解決這個案例中的問題。

有一個遊戲公司，他們開發了一款遊戲。這款遊戲發布了一段時間後，他們得到了一些用戶的數據。數據如面這幅圖所示：

這個圖上的每一個圖形表示一個用戶。紅色的三角形表示該用戶喜歡這款遊戲；藍色的正方形表示該用戶不喜歡這款遊戲。圖上有2個坐標。橫坐標表示用戶的年齡，縱坐標表示用戶平均每天玩手機的時長，單位是分鐘。

比如，右下角這個藍色方框。這個用戶的年齡大概50歲，TA每天平均玩手機的時間30分鐘左右。這個圖形是藍色，表示他不喜歡這款遊戲。再比如左上角的紅色三角形。這個用戶的年齡不到15歲，每天玩手機時間240分鐘，也就是4個小時。這個圖形是紅色，表示他喜歡這款遊戲。其它用戶也是一樣等邏輯。

這些都是已知用戶的數據。現在，他們從某些渠道獲得了一批新用戶。比如，有一個用戶，在圖上表示為綠色的圓點。這個用戶大概30歲，每天玩手機時長有200分鐘左右。 公司想知道，他們是否應該向這個用戶推廣這款遊戲？

需要說明一下，推廣遊戲是有成本的，需要花費一定的推廣費用。所以，只有推廣給那些喜歡這款遊戲的人，公司才能獲取收益。

於是，剛才那個問題就轉換成為：預測這個綠色的新用戶是否喜歡這款遊戲。

那如何預測呢？

這裡我們需要一個假設：屬性越接近的人，行為偏好也越相似。

比如，兩個20多歲的人，他們的行為偏好可能比較相似；而一個20多歲和一個50多歲的人，他們的行為偏好就會相差比較大。也就是說，年齡這個屬性越接近，行為偏好也就越相似。

再比如，兩個工程師，他們的行為偏好可能就比較相似。而一個工程師和一個演員，他們的行為偏好就會相差比較大。也就是說，行業這個屬性越接近，行為偏好也就越相似。

推廣一下，就是屬性越接近的人，行為偏好也越相似。這跟我們常說的「物以類聚、人以群分」是一個道理。

回到我們的案例。要想知道綠色的用戶跟那一類用戶更相似，我們可以比較他跟哪些人的屬性更接近。或者反過來說，跟他接近的人有哪些？

我們發現，「接近」是一個距離的概念。在二維平面圖上，就是指哪些圖形距離這個綠色圓點比較短。

我們要判斷新用戶(綠色圓點)喜歡不喜歡這款遊戲，就是判斷這個點應該屬於紅色還是應該屬於藍色。根據上面的假設，我們可以先找到跟他屬性接近的圖形，也就是它的鄰居。看看它的鄰居都是什麼類型的。如果鄰居都是紅色，根據物以類聚的原則，它大概率也是紅色。如果鄰居都是藍色，它大概率也就是藍色。

那選幾個鄰居比較合適呢？這個數由我們自己定，我們可以選任意K個鄰居，K是個整數。這就是K臨近法的含義。

比如，我們選4個最近鄰居。發現四個鄰居有3個是紅色，只有一個藍色。鄰居中紅色占多數，我們就可以判斷，這個新用戶也大概也是紅色。物以類聚嘛！他是紅色就表示他喜歡這款遊戲，因此這家公司應該給他推薦這款遊戲。

我們還可以擴大一下鄰居的範圍，比如找8個鄰居。這時發現5個紅色，3個藍色。還是紅色鄰居多，因此我們仍然判斷這個用戶是紅色。

不過，並不是任意選幾個鄰居都能得出相同的結論。比如我們選1個鄰居。這時就會發現，這個鄰居是藍色，因此結論應該是該用戶為藍色。與之前的結論不一樣！

理論上講，選的鄰居越多越好。不過，太多的話，計算量大，算起來也就會慢。通常我們需要根據實際情況選擇合適的K值，既使得結論比較合理，同時計算量也不會太大。

到此為止，K臨近法的主要原理就介紹完了。

不過，有心的同學可能會發現一個問題。我們的圖只有兩個屬性：「年齡」和「每天玩手機的時長」。如果有三個屬性怎麼辦？比如，我們還有一個屬性是「學歷」。該怎麼表達呢？

其實，三個屬性可以用三維的空間表示，x、y、z三個坐標。每一個坐標代表一個屬性。一個點的鄰居，就是它在三維空間中離它最近的那些點。三維空間中兩點的距離，其計算方法與二維平面兩點距離是類似的。

如果有4個屬性，那就是4維空間表示。有N個屬性，就用N維空間表示。我們可能無法想像出高維空間是什麼樣子大，不過高維空間中兩個點的距離，其計算方法與二維、三維中的距離計算方法是類似的。

因此，不管有多少個屬性，K臨近法都可以用相同的計算方法。

今天我們介紹了一個遊戲公司的案例，案例中的公司要判斷是否應該給新用戶推廣某一款遊戲，然後用K臨近法解決了這個問題。

你覺得K臨近法還可以解決哪些問題？如果你有想法，可以寫到評論里。

Tags: