作者: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/
譯者簡介
王雨桐,統計學在讀,數據科學碩士預備,跑步不停,彈琴不止。夢想把數據可視化當作藝術,目前日常是摸著下巴看機器學習。
閱讀更多 數據派THU 的文章