您的位置：首頁>正文

從零開始用Python實現k近鄰演算法（附代碼、資料集）

THU數據派 2018-04-19 2

作者：Tavish Srivastava

翻譯：王雨桐

校對：丁楠雅

本文約2000字， 建議閱讀8分鐘。

本文將帶領讀者理解KNN演算法在分類問題中的使用， 並結合案例運用Python進行實戰操作。

注意：本文於2014年10月10日首發， 並於2018年3月27日更新

引言

進入資料分析領域的四年來， 我構建的模型的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

import pandas as pd

import numpy as np

import math

import operator

#### Start of STEP 1

# Importing data

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

#### End of STEP 1

data.head()

# Defining a function which calculates 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 and test data

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 class in the 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演算法。

您覺得這篇文章有用嗎？您最近使用過其他機器學習工具嗎？您是否打算在一些業務問題中使用KNN？如果是的話，請與我們分享你打算如何去做。

原文標題：Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

原文連結：https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/

譯者簡介

王雨桐，統計學在讀，資料科學碩士預備，跑步不停，彈琴不止。夢想把資料視覺化當作藝術，目前日常是摸著下巴看機器學習。

如圖所示，對於訓練樣本而言，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

import pandas as pd

import numpy as np

import math

import operator

#### Start of STEP 1

# Importing data

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

#### End of STEP 1

data.head()

# Defining a function which calculates 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 and test data

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 class in the 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演算法。

您覺得這篇文章有用嗎？您最近使用過其他機器學習工具嗎？您是否打算在一些業務問題中使用KNN？如果是的話，請與我們分享你打算如何去做。

原文標題：Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

原文連結：https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/

譯者簡介

王雨桐，統計學在讀，資料科學碩士預備，跑步不停，彈琴不止。夢想把資料視覺化當作藝術，目前日常是摸著下巴看機器學習。

上一篇：中國造了這座橋之後，全世界網友都在瘋狂吐槽！
同類文章
精品文章
Next Article
喜欢就按个赞吧!!!
点击关闭提示