KNN演算法的機器學習基礎

本文為 AI 研習社編譯的技術博客，原標題 ：

Machine Learning Basics with the K-Nearest Neighbors Algorithm

翻譯 | 小哥哥、江舟 校對 | 呂鑫燦 整理 | 志豪

https://towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761

基於K近鄰演算法的機器學習基礎

k近鄰( KNN )演算法是一種簡單、易於實現的監督機器學習演算法，可用於解決分類和回歸問題。暫停！讓我們從這裡入手。

我們接下來將保持它超級簡單！

把問題分解

有監督的機器學習演算法(與無監督的機器學習演算法相反)是一種依靠標記的輸入數據來學習函數的演算法，當給定新的未標記數據時，該函數會產生適當的輸出。

想像一下，一台計算機當做一個孩子，我們是它的主管(例如父母、監護人或老師)，我們希望孩子(計算機)能了解豬是什麼樣子。我們向孩子展示幾幅不同的照片，其中一些是豬，其餘的可能是任何東西的照片(貓、狗等)。

當我們看到一隻豬時，我們喊「豬！」！當它不是豬時，我們喊「不，不是豬！」！和孩子一起做了幾次之後，我們給他們看了一張照片，然後問「豬？他們會正確地(大多數時候)說「豬！」！「或者」不，不是豬！「取決於照片是什麼。這就是有監督的機器學習。

「豬！」

有監督機器學習演算法用於解決分類或回歸問題。

分類問題的輸出是離散值。例如，「喜歡比薩上的菠蘿」和「不喜歡比薩上的菠蘿」是離散的。沒有中間地帶。上面教孩子識別豬的類比是分類問題的另一個例子。

顯示隨機生成數據的圖像

這張圖片展示了分類數據可能是什麼樣子的基本例子。我們有一個預測器(或一組預測器)和一個標籤。在這張圖片中，我們可能試圖根據年齡(預測因子)來預測某人是(1)否(0)喜歡比薩餅上的菠蘿。

標準做法是將分類演算法的輸出(標籤)表示為整數，例如1、-1或0。在這種情況下，這些數字純粹是代表性的。不應該對它們進行數學運算，因為這樣做毫無意義。想一想。什麼是「喜歡菠蘿」+「不喜歡菠蘿」？沒錯。我們不能相加它們，所以我們不應該把數字表示特徵相加。

回歸問題有一個實數(帶有小數點的數字)作為輸出。例如，我們可以使用下表中的數據來估計給定身高的人的體重。

圖像顯示了SOCR高度和權重數據集的一部分

回歸分析中使用的數據看起來類似於上圖所示的數據。我們有一個自變數(或一組自變數)和一個因變數(試圖在給定自變數的情況下猜測因變數)。例如，我們可以說高度是自變數，而重量是因變數。

此外，每行通常稱為示例、觀察或數據點，而每列(不包括標籤/因變數)通常稱為預測值、維度、自變數或特徵。

無監督的機器學習演算法使用沒有任何標籤的輸入數據——換句話說，沒有老師(標籤)告訴孩子(計算機)什麼時候是正確的，什麼時候是錯誤的，這樣它就可以自我糾正。

與試圖學習一種函數的監督學習不同，這種函數允許我們在給定一些新的未標記數據的情況下進行預測，無監督學習試圖學習數據的基本結構，從而讓我們對數據有更多的了解。

最近鄰

KNN演算法假設相似的東西存在於很近的地方。換句話說，相似的事物彼此接近。

「物以類聚。"

顯示相似數據點通常如何彼此靠近存在的圖像

請注意，在上圖中，大多數情況下，相似的數據點彼此接近。KNN演算法就是基於這個假設以使演算法有用。KNN利用與我們童年時可能學過的一些數學相似的想法(有時稱為距離、接近度或接近度)，即計算圖上點之間的距離。

注意:在繼續之前，有必要了解我們如何計算圖表上的點之間的距離。如果你不熟悉或需要複習計算方法，請完整閱讀「兩點之間的距離」，然後再回來。

還有其他計算距離的方法，其中一種方法可能更好，這取決於我們正在解決的問題。然而，直線距離(也稱為歐氏距離)是一個流行且熟悉的選擇。

KNN演算法(英文)

1. 載入數據

2. 將K初始化為你選擇的鄰居數量

3. 對於數據中的每個示例

3.1 根據數據計算查詢示例和當前示例之間的距離。

3.2 將示例的距離和索引添加到有序集合中

4. 按距離將距離和索引的有序集合從最小到最大(按升序)排序

5. 從已排序的集合中挑選前K個條目

6. 獲取所選K個條目的標籤

7. 如果回歸，返回K個標籤的平均值

8. 如果分類，返回K個標籤的模式

KNN實現(從頭開始)

fromcollectionsimportCounter

importmath

defknn(data, query, k, distance_fn, choice_fn):

neighbor_distances_and_indices = []

# 3. For each example in the data

forindex, exampleinenumerate(data):

# 3.1 Calculate the distance between the query example and the current

# example from the data.

distance = distance_fn(example[:-1], query)

# 3.2 Add the distance and the index of the example to an ordered collection

neighbor_distances_and_indices.append((distance, index))

# 4. Sort the ordered collection of distances and indices from

# smallest to largest (in ascending order) by the distances

sorted_neighbor_distances_and_indices = sorted(neighbor_distances_and_indices)

# 5. Pick the first K entries from the sorted collection

k_nearest_distances_and_indices = sorted_neighbor_distances_and_indices[:k]

# 6. Get the labels of the selected K entries

k_nearest_labels = [data[i][1]fordistance, iink_nearest_distances_and_indices]

# 7. If regression (choice_fn = mean), return the average of the K labels

# 8. If classification (choice_fn = mode), return the mode of the K labels

returnk_nearest_distances_and_indices , choice_fn(k_nearest_labels)

defmean(labels):

returnsum(labels) / len(labels)

defmode(labels):

returnCounter(labels).most_common(1)[][]

defeuclidean_distance(point1, point2):

sum_squared_distance =

foriinrange(len(point1)):

sum_squared_distance += math.pow(point1[i] - point2[i],2)

returnmath.sqrt(sum_squared_distance)

defmain():

"""

# Regression Data

#

# Column 0: height (inches)

# Column 1: weight (pounds)

"""

reg_data = [

[65.75,112.99],

[71.52,136.49],

[69.40,153.03],

[68.22,142.34],

[67.79,144.30],

[68.70,123.30],

[69.80,141.49],

[70.01,136.46],

[67.90,112.37],

[66.49,127.45],

]

# Question:

# Given the data we have, what"s the best-guess at someone"s weight if they are 60 inches tall?

reg_query = [60]

reg_k_nearest_neighbors, reg_prediction = knn(

reg_data, reg_query, k=3, distance_fn=euclidean_distance, choice_fn=mean

)

"""

# Classification Data

#

# Column 0: age

# Column 1: likes pineapple

"""

clf_data = [

[22,1],

[23,1],

[21,1],

[18,1],

[19,1],

[25,],

[27,],

[29,],

[31,],

[45,],

]

# Question:

# Given the data we have, does a 33 year old like pineapples on their pizza?

clf_query = [33]

clf_k_nearest_neighbors, clf_prediction = knn(

clf_data, clf_query, k=3, distance_fn=euclidean_distance, choice_fn=mode

)

if__name__ =="__main__":

main()

為K選擇正確的值

為了選擇適合你的數據的K，我們用不同的K值運行了幾次KNN演算法，並選擇K來減少我們遇到的錯誤數量，同時保持演算法在給定之前從未見過的數據時準確預測的能力。

以下是一些需要記住的事情：

當我們將K值降低到1時，我們的預測會變得不穩定。試想一下，圖像K = 1，我們有一個查詢點，周圍有幾個紅色和一個綠色(我在考慮上面彩色圖的左上角)，但是綠色是唯一最近的鄰居。合理地說，我們會認為查詢點很可能是紅色的，但是因為K = 1，KNN錯誤地預測查詢點是綠色的。

相反，隨著K值的增加，由於多數投票/平均，我們的預測變得更加穩定，因此更有可能做出更準確的預測(直到某一點)。最終，我們開始看到越來越多的錯誤。正是在這一點上，我們知道我們把K的價值推得太遠了。

如果我們在標籤中進行多數投票(例如，在分類問題中選擇模式)，我們通常會將K設為奇數，以便有一個決勝局。

優勢

該演算法簡單易行。

沒有必要建立模型，調整多個參數，或者做額外的假設。

該演算法是通用的。它可以用於分類、回歸和搜索(我們將在下一節中看到)。

缺點

隨著示例和/或預測器/獨立變數數量的增加，演算法變得非常慢。

KNN在實踐中

KNN的主要缺點是隨著數據量的增加變得非常慢，這使得在需要快速做出預測的環境中，變成了一個不切實際的選擇。此外，有更快的演算法可以產生更準確的分類和回歸結果。

然而，如果你有足夠的計算資源來快速處理你用來預測的數據，KNN仍然有助於解決那些有依賴於識別相似對象的解決方案的問題。這方面的一個例子是在推薦系統中使用KNN演算法，這是KNN搜索的應用。

推薦系統

從規模上看，這就像是在亞馬遜上推薦產品，在媒體上推薦文章，在Netflix上推薦電影，或者在YouTube上推薦視頻。儘管如此，我們可以肯定，由於他們處理的數據量巨大，他們都使用了更有效的方法來提出推薦。

然而，我們可以使用本文中所學的知識，以較小的規模複製其中一個推薦系統。那麼讓我們構建一個電影推薦系統的核心。

我們想回答什麼問題？

給定我們的電影數據集，與電影查詢最相似的5部電影是什麼？

收集電影數據

如果我們在Netflix、Hulu或IMDb工作，我們可以從他們的數據倉庫中獲取數據。但因為我們不在這些公司工作，所以我們必須通過其他方式獲取數據。我們可以使用來自UCI機器學習庫、IMDb數據集的一些電影數據，或者費力地創建我們自己的數據。

探索、清理和準備數據

無論我們從哪裡獲得數據，都可能存在一些問題，我們需要糾正這些問題，為KNN演算法做準備。例如，數據可能不是演算法期望的格式，或者在將數據送入演算法之前，可能缺少數據，故我們應該填充或刪除它們。

我們上面的KNN實現依賴於結構化數據。它需要表格格式。此外，該實現假設所有列都包含數字數據，並且我們數據的最後一列具有可以對其執行某些功能的標籤。因此，無論我們從哪裡獲得數據，我們都需要使其符合這些約束。

下面的數據是我們清理過的數據可能類似的一個例子。該數據包含30部電影，包括七種類型的每部電影的數據及其IMDB評級。標籤的列全為零，因為我們沒有使用這個數據集進行分類或回歸。

自製電影推薦數據集

此外，在使用KNN演算法時，電影之間有一些關係不會被考慮(例如演員、導演和主題)，這僅僅是因為數據集中缺少捕捉這些關係的數據。因此，當我們對我們的數據運行KNN演算法時，相似性將完全基於包括的類型和電影的IMDB評級。

使用演算法

想像一下。我們正在瀏覽MoviesXb網站，這是一個虛構的IMDb衍生產品，我們遇到了《郵報》。我們不確定是否想看它，但是它的類型吸引了我們；我們對其他類似的電影很好奇。我們向下滾動到「更像這個」部分，看看MoviesXb會提出什麼建議，演算法齒輪開始轉動。

MoviesXb網站向其後端發送了一個請求，要求獲得5部最類似《華盛頓郵報》的電影。後端有一個與我們完全一樣的推薦數據集。它首先為《華盛頓郵報》創建行表示(被廣泛稱為特徵向量)，然後運行類似於下面的程序來搜索與《華盛頓郵報》最相似的5部電影，最後將結果發送回MoviesXb網站。

fromknn_from_scratchimportknn, euclidean_distance

defrecommend_movies(movie_query, k_recommendations):

raw_movies_data = []

withopen("movies_recommendation_data.csv","r")asmd:

# Discard the first line (headings)

next(md)

# Read the data into memory

forlineinmd.readlines():

data_row = line.strip().split(",")

raw_movies_data.append(data_row)

# Prepare the data for use in the knn algorithm by picking

# the relevant columns and converting the numeric columns

# to numbers since they were read in as strings

movies_recommendation_data = []

forrowinraw_movies_data:

data_row = list(map(float, row[2:]))

movies_recommendation_data.append(data_row)

# Use the KNN algorithm to get the 5 movies that are most

# similar to The Post.

recommendation_indices, _ = knn(

movies_recommendation_data, movie_query, k=k_recommendations,

distance_fn=euclidean_distance, choice_fn=lambdax:None

)

movie_recommendations = []

for_, indexinrecommendation_indices:

movie_recommendations.append(raw_movies_data[index])

returnmovie_recommendations

if__name__ =="__main__":

the_post = [7.2,1,1,,,,,1,]# feature vector for The Post

recommended_movies = recommend_movies(movie_query=the_post, k_recommendations=5)

# Print recommended movie titles

forrecommendationinrecommended_movies:

print(recommendation[1])

當我們運行這個程序時，我們看到MoviesXb推薦了《為奴十二年》，《鋼鋸嶺》，《卡推女王》，《起風了》，還有《美麗心靈》。既然我們完全理解KNN演算法是如何工作的，我們就能夠準確地解釋KNN演算法是如何提出這些建議的。恭喜你！

總結

k最近鄰( KNN )演算法是一種簡單的有監督的機器學習演算法，可用於解決分類和回歸問題。這很容易實現和理解，但是有一個主要缺點，就是隨著使用中數據的大小增加速度會明顯變慢。

KNN通過查找查詢和數據中所有示例之間的距離來工作，選擇最接近查詢的指定數字示例( K )，然後選擇最常用的標籤(在分類的情況下)或平均標籤(在回歸的情況下)。

在分類和回歸的情況下，我們看到為我們的數據選擇正確的K是通過嘗試幾個K並選擇最有效的一個來完成的。

最後，我們看了一個KNN演算法如何應用於推薦系統的例子，這是KNN搜索的一個應用。

KNN就像.....「讓我看看你的朋友，我來告訴你誰是。」

附錄

[1]為了簡單起見，本文中實現的KNN電影推薦器不處理電影查詢有可能是推薦數據集的一部分的情況。 在生產系統中可能是不合理的，應該處理相同的問題。

如果你學到了一個新東西或者喜歡這篇文章，請點贊並且分享它，這樣可以讓更多的人看到。你可以自由地留下你的評論。

想要繼續查看該篇文章更多代碼、鏈接和參考文獻？

戳鏈接：

http://www.gair.link/page/TextTranslation/1027

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