從零開始用 Python 實現 k 近鄰演算法

引言

進入數據分析領域的四年來，我構建的模型的80%多都是分類模型，而回歸模型僅佔15-20%。這個數字會有浮動，但是整個行業的普遍經驗值。分類模型佔主流的原因是大多數分析問題都涉及到做出決定。例如一個客戶是否會流失,我們是否應該針對一個客戶進行數字營銷，以及客戶是否有很大的潛力等等。這些分析有很強的洞察力，並且直接關係到實現路徑。在本文中，我們將討論另一種被廣泛使用的分類技術，稱為k近鄰(KNN)。本文的重點主要集中在演算法的工作原理以及輸入參數如何影響輸出/預測。

目錄

什麼情況下使用KNN演算法？

KNN演算法如何工作？

如何選擇因子K？

分解--KNN的偽代碼

從零開始的Python實現

和Scikit-learn比較

什麼情況使用 KNN 演算法？

KNN 演算法既可以用於分類也可以用於回歸預測。然而，業內主要用於分類問題。在評估一個演算法時，我們通常從以下三個角度出發：

模型解釋性

運算時間

預測能力

讓我們通過幾個例子來評估 KNN：

KNN 演算法在這幾項上的表現都比較均衡。由於便於解釋和計算時間較短，這種演算法使用很普遍。

KNN 演算法的原理是什麼？

讓我們通過一個簡單的案例來理解這個演算法。下圖是紅圓圈和綠方塊的分布圖：

現在我們要預測藍星星屬於哪個類別。藍星星可能屬於紅圓圈，或屬於綠方塊，也可能不屬於任何類別。KNN 中的「K」是我們要找到的最近鄰的數量。假設 K = 3。因此，我們現在以藍星星為圓心來作一個圓，使其恰巧只能包含平面內的 3 個數據點。參閱下圖:

離藍星星最近的三個點都是紅圓圈。因此，我們可以以較高的置信水平判定藍星星應屬於紅圓圈這個類別。在 KNN 演算法中，參數K的選擇是非常關鍵的。接下來，我們將探索哪些因素可以得到K的最佳值。

如何選擇因子 K？

首先要了解 K 在演算法中到底有什麼影響。在前文的案例中，假定總共只有 6 個訓練數據，給定 K 值，我們可以劃分兩個類的邊界。現在讓我們看看不同 K 值下兩個類別的邊界的差異。

仔細觀察，我們會發現隨著 K 值的增加，邊界變得更平滑。當K值趨於無窮大時，分類區域最終會全部變成藍色或紅色，這取決於佔主導地位的是藍點還是紅點。我們需要基於不同K值獲取訓練錯誤率和驗證錯誤率這兩個參數。以下為訓練錯誤率隨K值變化的曲線：

如圖所示，對於訓練樣本而言，K=1 時的錯誤率總是為零。這是因為對任何訓練數據點來說，最接近它的點就是其本身。因此，K=1 時的預測總是準確的。如果驗證錯誤曲線也是這樣的形狀，我們只要設定 K 為 1 就可以了。以下是隨K值變化的驗證錯誤曲線:

顯然，在 K=1 的時候，我們過度擬合了邊界。因此，錯誤率最初是下降的，達到最小值後又隨著 K 的增加而增加。為了得到K的最優值，我們將初始數據集分割為訓練集和驗證集，然後通過繪製驗證錯誤曲線得到K的最優值，應用於所有預測。

分解 -- KNN 的偽代碼

我們可以通過以下步驟實現 KNN 模型:

載入數據。

預設K值。

對訓練集中數據點進行迭代，進行預測。

STEPS：

計算測試數據與每一個訓練數據的距離。我們選用最常用的歐式距離作為度量。其他度量標準還有切比雪夫距離、餘弦相似度等

根據計算得到的距離值，按升序排序

從已排序的數組中獲取靠前的k個點

獲取這些點中的出現最頻繁的類別

得到預測類別

從零開始的 Python 實現

我們將使用流行的 Iris 數據集來構建 KNN 模型。你可以從這裡下載(數據集鏈接：

https://gist.githubusercontent.com/gurchetan1000/ec90a0a8004927e57c24b20a6f8c8d35/raw/fcd83b35021a4c1d7f1f1d5dc83c07c8ffc0d3e2/iris.csv)

# Importing libraries

importpandasaspd

importnumpyasnp

importmath

importoperator

#### Start of STEP 1

# Importing data

data = pd.read_csv("iris.csv")

#### End of STEP 1

data.head()

#Defining afunctionwhichcalculates euclidean distance between two data points

def euclideanDistance(data1, data2, length):

distance = 0

for x in range(length):

distance += np.square(data1[x] - data2[x])

return np.sqrt(distance)

#Defining our KNN model

def knn(trainingSet, testInstance, k):

distances = {}

sort = {}

length = testInstance.shape[1]

#### Start of STEP 3

#Calculating euclidean distance between each row of training data andtestdata

for x in range(len(trainingSet)):

#### Start of STEP 3.1

dist = euclideanDistance(testInstance, trainingSet.iloc[x], length)

distances[x] = dist[0]

#### End of STEP 3.1

#### Start of STEP 3.2

#Sorting them on the basis of distance

sorted_d = sorted(distances.items(), key=operator.itemgetter(1))

#### End of STEP 3.2

neighbors = []

#### Start of STEP 3.3

#Extracting top k neighbors

for x in range(k):

neighbors.append(sorted_d[x][0])

#### End of STEP 3.3

classVotes = {}

#### Start of STEP 3.4

#Calculating the most freq classinthe neighbors

for x in range(len(neighbors)):

response = trainingSet.iloc[neighbors[x]][-1]

if response in classVotes:

classVotes[response] += 1

else:

classVotes[response] = 1

#### End of STEP 3.4

#### Start of STEP 3.5

sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)

return(sortedVotes[0][0], neighbors)

#### End of STEP 3.5

#Creating a dummy testset

testSet = [[7.2, 3.6, 5.1, 2.5]]

test = pd.DataFrame(testSet)

#### Start of STEP 2

#Setting number of neighbors = 1

k = 1

#### End of STEP 2

#Running KNN model

result,neigh = knn(data, test, k)

#Predicted class

print(result)

->Iris-virginica

#Nearest neighbor

print(neigh)

->[141]

現在我們改變k的值並觀察預測結果的變化：

#Setting number of neighbors = 3

k = 3

#Running KNN model

result,neigh = knn(data, test, k)

#Predicted class

print(result) -> Iris-virginica

#3 nearest neighbors

print(neigh)

->[141, 139, 120]

#Setting number of neighbors = 5

k = 5

#Running KNN model

result,neigh = knn(data, test, k)

#Predicted class

print(result) -> Iris-virginica

#5 nearest neighbors

print(neigh)

->[141, 139, 120, 145, 144]

和scikit-learn比較

from sklearn.neighbors import KNeighborsClassifier

neigh = KNeighborsClassifier(n_neighbors=3)

neigh.fit(data.iloc[:,0:4], data["Name"])

#Predicted class

print(neigh.predict(test))

->["Iris-virginica"]

#3 nearest neighbors

print(neigh.kneighbors(test)[1])

->[[141 139 120]]

可以看到，兩個模型都預測了同樣的類別(「irisi –virginica」)和同樣的最近鄰([141 139 120])。因此我們可以得出結論：模型是按照預期運行的。

章節附註

KNN 演算法是最簡單的分類演算法之一。即使如此簡單，它也能得到很理想的結果。KNN 演算法也可用於回歸問題，這時它使用最近點的均值而不是最近鄰的類別。R 中 KNN 可以通過單行代碼實現，但我還沒有探索如何在SAS中使用KNN演算法。

原文標題：

Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/

NLP 工程師入門實踐班

三大模塊，五大應用，知識點全覆蓋；

海外博士講師，豐富項目分享經驗；

理論+實踐，帶你實戰典型行業應用；

專業答疑社群，討論得出新知。

新人福利

關注 AI 研習社（okweiwu），回復1領取

【超過 1000G 神經網路 / AI / 大數據資料】

從零開始學習 CNN 架構 | 2017 CS231n

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！