阿里雲機器學習算法(三):K近鄰(k-nearest neighbors)初探

2021-02-19 機器學習實戰python

前面的話：

最近被安利了風犬少年的天空這部劇，美好而又接地氣，永遠也無法拒絕溫暖的情感。順便平安夜大家記得吃蘋果喲，平平安安，順順遂遂。

這裡先給出阿里雲機器學習訓練營地址：

https://tianchi.aliyun.com/s/5f7fc113c530028add3c2b9fc80e7aee

大家可以進行一個代碼的學習，可以將其代碼下載進行學習或者參加最後一個任務的比賽。

本文章同見於csdn博客：(歡迎關注csdn)

https://blog.csdn.net/handsomeandge/article/details/111648990

歡迎一起討論代碼，一起進步呀！

1 KNN的介紹和應用1.1 KNN的介紹

kNN(k-nearest neighbors)，中文翻譯K近鄰。我們常常聽到一個故事：如果要了解一個人的經濟水平，只需要知道他最好的5個朋友的經濟能力， 對他的這五個人的經濟水平求平均就是這個人的經濟水平。這句話裡面就包含著kNN的算法思想。

示例 ：如上圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由於紅色三角形所佔比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由於藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

1) KNN建立過程

1 給定測試樣本，計算它與訓練集中的每一個樣本的距離。
2 找出距離近期的K個訓練樣本。作為測試樣本的近鄰。
3 依據這K個近鄰歸屬的類別來確定樣本的類別。

2) 類別的判定

①投票決定，少數服從多數。取類別最多的為測試樣本類別。

②加權投票法，依據計算得出距離的遠近，對近鄰的投票進行加權，距離越近則權重越大，設定權重為距離平方的倒數。

1.2 KNN的應用

KNN雖然很簡單，但是人們常說"大道至簡"，一句"物以類聚，人以群分"就能揭開其面紗，看似簡單的KNN即能做分類又能做回歸， 還能用來做數據預處理的缺失值填充。由於KNN模型具有很好的解釋性，一般情況下對於簡單的機器學習問題，我們可以使用KNN作為 Baseline，對於每一個預測結果，我們可以很好的進行解釋。推薦系統的中，也有著KNN的影子。例如文章推薦系統中， 對於一個用戶A，我們可以把和A最相近的k個用戶，瀏覽過的文章推送給A。

機器學習領域中，數據往往很重要，有句話叫做:"數據決定任務的上限, 模型的目標是無限接近這個上限"。可以看到好的數據非常重要，但是由於各種原因，我們得到的數據是有缺失的，如果我們能夠很好的填充這些缺失值， 就能夠得到更好的數據，以至於訓練出來更魯棒的模型。接下來我們就來看看KNN如果做分類，怎麼做回歸以及怎麼填充空值。

補充：

KNN可以說是最簡單的分類算法之一，同時，它也是最常用的分類算法之一，注意KNN算法是有監督學習中的分類算法，它看起來和另一個機器學習算法Kmeans有點像（Kmeans是無監督學習算法），但卻是有本質區別的。KNN的全稱是K Nearest Neighbors，意思是K個最近的鄰居，從這個名字我們就能看出一些KNN算法的蛛絲馬跡了。K個最近鄰居，毫無疑問，K的取值肯定是至關重要的。KNN的原理就是當預測一個新的值x的時候，根據它距離最近的K個點是什麼類別來判斷x屬於哪個類別。

KNN算法優點

簡單易用，相比其他算法，KNN算是比較簡潔明了的算法。即使沒有很高的數學基礎也能搞清楚它的原理。

模型訓練時間快，上面說到KNN算法是惰性的，這裡也就不再過多講述。

預測效果好。

對異常值不敏感

KNN算法缺點

對內存要求較高，因為該算法存儲了所有訓練數據

預測階段可能很慢

對不相關的功能和數據規模敏感

2 實驗室手冊2.1 實驗環境

1. python3.7
2. numpy >= '1.16.4'
3. sklearn >= '0.23.1'

2.2 學習目標

了解KNN怎麼做分類問題

了解KNN如何做回歸

了解KNN怎麼做空值填充, 如何使用knn構建帶有空值的pipeline

2.3 代碼流程

二維數據集--knn分類

Step1: 庫函數導入

Step2: 數據導入

Step3: 模型訓練&可視化

Step4: 原理簡析

鶯尾花數據集--kNN分類

Step1: 庫函數導入

Step2: 數據導入&分析

Step3: 模型訓練

Step4: 模型預測&可視化

模擬數據集--kNN回歸

Step1: 庫函數導入

Step2: 數據導入&分析

Step3: 模型訓練&可視化

馬絞痛數據--kNN數據預處理+kNN分類pipeline

Step1: 庫函數導入

Step2: 數據導入&分析

Step3: KNNImputer空值填充--使用和原理介紹

Step4: KNNImputer空值填充--歐式距離的計算

Step5: 基於pipeline模型預測&可視化

2.4 算法實戰2.4.1 Demo數據集--kNN分類

Step1: 庫函數導入

import numpy as npimport matplotlib.pyplot as pltfrom matplotlib.colors import ListedColormap
from sklearn.neighbors import KNeighborsClassifierfrom sklearn import datasets
Step2: 數據導入
iris = datasets.load_iris()X = iris.data[:, :2]y = iris.target
Step3: 模型訓練&可視化
k_list = [1, 3, 5, 8, 10, 15]h = .02cmap_light = ListedColormap(['orange', 'cyan', 'cornflowerblue'])cmap_bold = ListedColormap(['darkorange', 'c', 'darkblue'])
plt.figure(figsize=(15,14))for ind,k in enumerate(k_list):        clf = KNeighborsClassifier(k)            clf.fit(X, y)                x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1            xx, yy = np.meshgrid(np.arange(x_min, x_max, h),                         np.arange(y_min, y_max, h))                Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])                    Z = Z.reshape(xx.shape)        
    plt.subplot(321+ind)             plt.pcolormesh(xx, yy, Z, cmap=cmap_light)                        plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold,                edgecolor='k', s=20)            plt.xlim(xx.min(), xx.max())    plt.ylim(yy.min(), yy.max())            plt.title("3-Class classification (k = %i)"% k)    
plt.show()
Step4: 原理簡析
如果選擇較小的K值，就相當於用較小的領域中的訓練實例進行預測，例如當k=1的時候，在分界點位置的數據很容易受到局部的影響，圖中藍色的部分中還有部分綠色塊，主要是數據太局部敏感。當k=15的時候，不同的數據基本根據顏色分開，當時進行預測的時候，會直接落到對應的區域，模型相對更加魯棒。
2.4.2 鶯尾花數據集--kNN分類
Step1: 庫函數導入
import numpy as npfrom sklearn import datasetsfrom sklearn.neighbors import KNeighborsClassifierfrom sklearn.model_selection import train_test_split
Step2: 數據導入&分析
iris = datasets.load_iris()
X = iris.datay = iris.targetX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
Step3: 模型訓練
這裡我們設置參數k(n_neighbors)=5, 使用歐式距離(metric=minkowski & p=2)
clf = KNeighborsClassifier(n_neighbors=5, p=2, metric="minkowski")clf.fit(X_train, y_train)
Step4:模型預測&可視化
X_pred = clf.predict(X_test)acc = sum(X_pred == y_test) / X_pred.shape[0]print("預測的準確率ACC: %.3f" % acc)
2.4.3 模擬數據集--kNN回歸
Step1: 庫函數導入
import numpy as npimport matplotlib.pyplot as pltfrom sklearn.neighbors import KNeighborsRegressor
Step2: 數據導入&分析
np.random.seed(0)
X = np.sort(5 * np.random.rand(40, 1), axis=0)
T = np.linspace(0, 5, 500)[:, np.newaxis]
y = np.sin(X).ravel()
y[::5] += 1 * (0.5 - np.random.rand(8))
Step3: 模型訓練&預測可視化
n_neighbors = [1, 3, 5, 8, 10, 40]plt.figure(figsize=(10,20))for i, k in enumerate(n_neighbors):        clf = KNeighborsRegressor(n_neighbors=k, p=2, metric="minkowski")        clf.fit(X, y)            y_ = clf.predict(T)            plt.subplot(6, 1, i + 1)            plt.scatter(X, y, color='red', label='data')                    plt.plot(T, y_, color='navy', label='prediction')                    plt.axis('tight')            plt.legend()            plt.title("KNeighborsRegressor (k = %i)" % (k))
plt.tight_layout()plt.show()
Step4:模型分析
當k=1時，預測的結果只和最近的一個訓練樣本相關，從預測曲線中可以看出當k很小時候很容易發生過擬合。
當k=40時，預測的結果和最近的40個樣本相關，因為我們只有40個樣本，此時是所有樣本的平均值，此時所有預測值都是均值，很容易發生欠擬合。
一般情況下，使用knn的時候，根據數據規模我們會從[3, 20]之間進行嘗試，選擇最好的k，例如上圖中的[3, 10]相對1和40都是還不錯的選擇。
2.4.4 馬絞痛數據--kNN數據預處理+kNN分類pipeline
Step1: 庫函數導入
import numpy as npimport pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.impute import KNNImputer
from sklearn.metrics.pairwise import nan_euclidean_distances
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedStratifiedKFoldfrom sklearn.pipeline import Pipelineimport matplotlib.pyplot as pltfrom sklearn.model_selection import train_test_split
Step2: 數據導入&分析
數據中的'?'表示空值，如果我們使用KNN分類器，'?'不能數值，不能進行計算，因此我們需要進行數據預處理對空值進行填充。
這裡我們使用KNNImputer進行空值填充，KNNImputer填充的原來很簡單，計算每個樣本最近的k個樣本，進行空值填充。
我們先來看下KNNImputer的運行原理：
Step3: KNNImputer空值填充--使用和原理介紹
X = [[1, 2, np.nan], [3, 4, 3], [np.nan, 6, 5], [8, 8, 7]]
imputer = KNNImputer(n_neighbors=2, metric='nan_euclidean')imputer.fit_transform(X)
帶有空值的歐式距離計算公式
nan_euclidean_distances([[np.nan, 6, 5], [3, 4, 3]], [[3, 4, 3], [1, 2, np.nan], [8, 8, 7]])
input_file = './horse-colic.csv'df_data = pd.read_csv(input_file, header=None, na_values='?')
data = df_data.valuesix = [i for i in range(data.shape[1]) if i != 23]X, y = data[:, ix], data[:, 23]
for i in range(df_data.shape[1]):    n_miss = df_data[[i]].isnull().sum()            
    perc = n_miss / df_data.shape[0] * 100    if n_miss.values[0] > 0:                print('>Feat: %d, Missing: %d, Missing ratio: (%.2f%%)' % (i, n_miss, perc))
print('KNNImputer before Missing: %d' % sum(np.isnan(X).flatten()))
imputer = KNNImputer()
imputer.fit(X)
Xtrans = imputer.transform(X)
print('KNNImputer after Missing: %d' % sum(np.isnan(Xtrans).flatten()))
Step5: 基於pipeline模型訓練&可視化
什麼是Pipeline, 我這裡直接翻譯成數據管道。任何有序的操作有可以看做pipeline，例如工廠流水線，對於機器學習模型來說，這就是數據流水線。是指數據通過管道中的每一個節點，結果除了之後，繼續流向下遊。對於我們這個例子，數據是有空值，我們會有一個KNNImputer節點用來填充空值， 之後繼續流向下一個kNN分類節點，最後輸出模型。
results = list()strategies = [str(i) for i in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 16, 18, 20, 21]]for s in strategies:        pipe = Pipeline(steps=[('imputer', KNNImputer(n_neighbors=int(s))), ('model', KNeighborsClassifier())])                            scores = []    for k in range(20):                X_train, X_test, y_train, y_test = train_test_split(Xtrans, y, test_size=0.2)        pipe.fit(X_train, y_train)                score = pipe.score(X_test, y_test)        scores.append(score)        results.append(np.array(scores))    print('>k: %s, Acc Mean: %.3f, Std: %.3f' % (s, np.mean(scores), np.std(scores)))plt.boxplot(results, labels=strategies, showmeans=True)plt.show()
Step 6: 結果分析
我們的實驗是每個k值下，隨機切分20次數據, 從上述的圖片中, 根據k值的增加，我們的測試準確率會有先上升再下降再上升的過程。[3, 5]之間是一個很好的取值，上文我們提到，k很小的時候會發生過擬合，k很大時候會發生欠擬合，當遇到第一下降節點，此時我們可以 簡單認為不在發生過擬合，取當前的k值即可。
2.5 KNN原理介紹
k近鄰方法是一種惰性學習算法，可以用於回歸和分類，它的主要思想是投票機制，對於一個測試實例x, 我們在有標籤的訓練數據集上找到和最相近的k個數據，用他們的label進行投票，分類問題則進行表決投票，回歸問題使用加權平均或者直接平均的方法。knn算法中我們最需要關注兩個問題：k值的選擇和距離的計算。kNN中的k是一個超參數，需要我們進行指定，一般情況下這個k和數據有很大關係，都是交叉驗證進行選擇，但是建議使用交叉驗證的時候，k∈[2,20]，使用交叉驗證得到一個很好的k值。
k值還可以表示我們的模型複雜度，當k值越小意味著模型複雜度變大，更容易過擬合，(用極少數的樣例來絕對這個預測的結果，很容易產生偏見，這就是過擬合)。我們有這樣一句話，k值越多學習的估計誤差越小，但是學習的近似誤差就會增大。

相關焦點

  • 機器學習入門:K-近鄰算法
    簡單的說，k-近鄰算法採用了測量不同特徵值之間的距離方法進行分類。，通常k為不大於20的整數，最後，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。：計算已知數據集中點到當前點之間的距離按照距離遞增次序排序選取與當前點距離最小的k個點確定前k個點所在類別的出現頻率返回前k個點中頻次最高的類別作為預測類別接著定義函數：# inX: 用於分類的輸入向量# dataSet：輸入的訓練集# labels：標籤向量# k：選擇近鄰項目的個數
  • 人工智慧推薦算法庫- 推薦電影
    比如有三個文件，aaa.c、bbb.c和ccc.h。可以對這三個文件做一個基線，取aaa.c的版本1.1，取bbb.c的版本1.3，取ccc.h的版本1.0。(1.1,1.3,1.0)就是一個基線。2）代表文檔的一個穩定狀態。
  • KNN算法中的K有多重要
    K-最近鄰（KNN）是一種有監督的機器學習算法，可用於解決分類和回歸問題。它基於一個非常簡單的想法，數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此，k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5，則檢查5個最近點的類別。也可以根據多數類進行回歸預測，同樣，KNN回歸取5個最近點的平均值。
  • 七個關鍵因素:如何選擇出優秀機器學習算法?
    任意的機器學習問題都可以應用多種算法，生成多種模型。例如，垃圾郵件檢測分類問題可以使用多種模型來解決，包括樸素貝葉斯模型、邏輯回歸模型和像BiLSTMs這樣的深度學習技術。擁有豐富的選擇是好的，但難點在於，如何決定在生產中實現哪個模型。
  • KNN算法介紹
    KNN(K-Nearest Neighbor)是最簡單的機器學習算法之一，可以用於分類和回歸，是一種監督學習算法。從上述例子看到，KNN本質是基於一種數據統計的方法，其實很多機器學習算法也是基於數據統計的。同時， KNN是一種instance-based learning，屬於lazy learning， 即它沒有明顯的前期訓練過程，而是程序開始運行時，把數據集加載到內存後，就可以直接開始分類。
  • 如何用聚類模型(k-means)做數據分析?
    k-means屬於無監督學習算法，無監督算法的內涵是觀察無標籤數據集自動發現隱藏結構和層次，在無標籤數據中尋找隱藏規律。聚類模型在數據分析當中的應用：既可以作為一個單獨過程，用於尋找數據內在規律，也可以作為分類等其他分析任務的前置探索。
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。
  • 短小精悍的多源最短路徑算法—Floyd算法
    答案是有的，這就是易寫但稍需要理解的Floyd算法。一個求多元最短路徑算法。算法介紹先看看百度百科的定義吧：Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。
  • 圖注意力網絡一作:圖表徵學習在算法推理領域的研究進展
    機器之心整理演講者：Petar Veličković整理：Racoon、張倩這是一份來自 DeepMind 研究員、圖注意力網絡一作 Petar Veličković 的演講，他為我們介紹了圖表徵學習在算法推理領域的研究進展
  • 沒有完整圖時,如何使用圖深度學習?你需要了解流形學習2.0版本
    機器之心編譯編輯：陳萍流形學習，自 2000 年在著名的科學雜誌《Science》被首次提出以來，已成為信息科學領域的研究熱點。可能很多人會問，流形學習有什麼用呢？首先流形學習可以作為一種數據降維的方式，第二，流形能夠刻畫數據的本質。
  • 沒有完整圖時,如何使用圖深度學習?需要了解流形學習2.0版本
    機器之心編譯編輯：陳萍流形學習，自 2000 年在著名的科學雜誌《Science》被首次提出以來，已成為信息科學領域的研究熱點。可能很多人會問，流形學習有什麼用呢？首先流形學習可以作為一種數據降維的方式，第二，流形能夠刻畫數據的本質。
  • 和平精英k城的密室在哪裡 和平精英k城的密室密碼
    和平精英k城地下室具體位置，和平精英k城保險箱在哪，和平精英k城地下室怎麼出去，獲取到k城地下室保險箱的密碼，可以幫助你玩火力對決2.0輕鬆找到豪華裝備還能幫你解鎖劇情，超多關卡密碼幫你提供讓你順利通關！喜歡的玩家記得進來看看哦。和平精英k城的密室密碼是什麼？
  • 聽k大和餘文樂聊牛仔褲
    k:你與 Levi's® 合作有三四年之久，建立了彼此十分信任的關係，當初是基於什麼樣的契機能夠達成長期的合作計劃呢？S:大家有共同的想法，我覺得這是非常重要的一點。彼此的信任在這些年之中，通過工作的磨合，彼此的溝通，才能逐漸累積起來，我很開心在這一路上能夠與客戶變成朋友！這也是一件十分難得的事情！
  • 日本模型原型師橫山宏 Ma.k
    橫山宏 Ma.k（よこやま こう Kow Yokoyama）（1956年6月15日～）日本插畫家，模型原型師，出生於福岡県北九州市，武蔵野美術大學畢業，代表作《Maschinen Krieger ZbV3000》簡稱：Ma.k.
  • ​大牛的《深度學習》筆記,Deep Learning速成教程
    咱們先來了解下機器學習（人工智慧的核心）的背景。|二、背景機器學習（Machine Learning）是一門專門研究計算機怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能的學科。機器能否像人類一樣能具有學習能力呢？
  • 卡爾曼濾波器算法介紹
    我們現在要學習的卡爾曼濾波器，正是源於他的博士論文和1960年發表的論文《A New Approach to Linear Filtering and Prediction Problems》（線性濾波與預測問題的新方法）。簡單來說，卡爾曼濾波器是一個「最優化自回歸數據處理算法」。對於解決很大部分的問題，他是最優，效率最高甚至是最有用的。
  • k金戒指會掉色嗎?k金戒指發黃了怎麼辦
    K金戒指不會掉色k金戒指本身不會掉色。K金是黃金與其他金屬熔合而成的合金。根據金屬的不同，K金主要有三種顏色：玫瑰K金=75%黃金+銅+銀+鋅黃色K金=75%黃金 +鎳+銀+鋅白色K金=75%黃金+銀+鎳+鉑+鋅或75%+鈀熔合而成的金屬沒有掉色之說，因此純粹的k金戒指自然也不會掉色。
  • 最安全的加密算法RSA
    Merkle）提出了一種新的構想：可以公開加密規則，然後可以在不傳遞解密規則的情況下完成解密。1976年惠特菲爾德·迪菲（Bailey Whitfield Diffie）和馬丁·赫爾曼（Martin Edward Hellman）找到一種算法實現了這種構思。這個方法稱為Diffie–Hellman–Merkle密鑰交換。