作者：Tavish Srivastava
翻譯：王雨桐
校對：丁楠雅
本文約2000字，建議閱讀8分鐘。
注意：本文於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：
我們將使用流行的Iris數據集來構建KNN模型。你可以從這裡下載(數據集連結：https://gist.githubusercontent.com/gurchetan1000/ec90a0a8004927e57c24b20a6f8c8d35/raw/fcd83b35021a4c1d7f1f1d5dc83c07c8ffc0d3e2/iris.csv)
#Importing libraries
importpandas as pd
importnumpy as np
importmath
importoperator
####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 twodata points
defeuclideanDistance(data1, data2, length):
distance= 0
forx in range(length):
distance+= np.square(data1[x] - data2[x])
returnnp.sqrt(distance)
#Defining our KNN model
defknn(trainingSet, testInstance, k):
distances= {}
sort= {}
length= testInstance.shape[1]
####Start of STEP 3
#Calculating euclidean distance between each row of training data andtest data
forx 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
forx 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
forx in range(len(neighbors)):
response= trainingSet.iloc[neighbors[x]][-1]
ifresponse 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]
fromsklearn.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」)和同樣的最近鄰([141139 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數據派產學研的背景為志願者帶來好的發展機遇。
其他福利：來自於名企的數據科學工作者，北大清華以及海外等名校學生他們都將成為你在翻譯小組的夥伴。
點擊文末「閱讀原文」加入數據派團隊~
點擊「閱讀原文」擁抱組織