k近鄰法(KNN)原理小結

2021-01-18 成長NLPer

目錄

本博客中使用到的完整代碼請移步至我的github：https://github.com/qingyujean/Magic-NLPer，求贊求星求鼓勵~~~


1. k 近鄰法算法

k-nearest neighbors （k-NN），k 近鄰法，用於分類和回歸。

KNN做回歸和分類的主要區別在於最後做預測時候的決策方式不同，KNN做分類預測時，一般是使用多數表決法；KNN做回歸時，一般是使用平均法，即最近的K個樣本的樣本輸出的平均值作為回歸預測值。本文以分類算法展開介紹。

k-近鄰法沒有顯示的學習過程，是一種lazy learning algorithm。

k-近鄰法的輸入：實例的特徵向量，對應於特徵空間的點，輸出：實例的類別。

k-近鄰法：利用訓練數據集對特徵向量空間進行劃分，並作為其分類的「模型」。分類時，對於新實例，根據其 k 個最近鄰的訓練實例的類別，通過多數表決等方式進行預測。

k-近鄰模型的三要素：k值的選擇、距離度量（作為"最鄰近"的衡量標準）、分類決策規則（例如」多數表決「）

knn算法可總結為3個步驟：

1.Choose the number of k and a distance metric.2.Find the k-nearest neighbors of the sample that we want to classify.3.Assign the class label by majority vote.2. k 近鄰法模型

k近鄰法使用的模型，實際上對應於特徵空間的劃分。

模型三要素：k值的選擇、距離度量（作為"最鄰近"的衡量標準）、分類決策規則（例如」多數表決「）

2.1 k值的選擇

k值的選擇會對k近鄰法的結果產生重大影響。應用中，k值一般去 較小 的數值，通常可使用 交叉驗證法 來取得最優的k值。

k值過小，近似誤差會減小，但估計誤差會增大。劃分粒度變細，模型越複雜，容易發生過擬合。對鄰近點非常敏感。k值過大，估計誤差減小，但近似誤差會增大，模型變得過於簡單（考慮極端情況k等於訓練樣本數，預測就只是簡單的為類別最多的那一類），與輸入實例相距較遠（不相似）的訓練實例也會對其產生影響。

k 值的選擇反映了對近似誤差和估計誤差之間的權衡。

近似誤差，可以理解為對現有訓練集的訓練誤差。更關注於「訓練」。
估計誤差：可以理解為對測試集的測試誤差。更關注於「測試」、「泛化」。
2.2 距離度量
特徵空間中2個實例點的距離，是2個實例點 相似程度 的反映。
不同的距離度量所確定的最近鄰點是不同的。
設特徵空間 
2.3 分類決策規則
多數表決法，多數表決規則等價於經驗風險最小化（經驗風險：模型關於訓練集的平均損失）。
3. k 近鄰法實現：kd（k-dimension）樹 
k近鄰法，主要考慮的問題：如何對訓練數據進行快速k近鄰搜索。尤其是特徵空間維數大以及訓練數據量大時，尤為重要。
簡單實現：線性掃描。需要計算輸入實例與每個訓練實例的距離。訓練集很大時，計算非常耗時，不可取。
kd樹實現，提高k鄰近搜索效率，以特殊的結構（例如kd tree，還有很多其他方法）存儲訓練數據，減少了計算距離的次數。
【注意】：kd 樹中的k 是指樣本特徵的維度，KNN中的k是指k個最近的樣本實例。
3.1 構造kd樹
kd 樹是一種對 k 維空間的實例點進行存儲以便對其進行快速檢索的樹形數據結構。kd 樹是二叉樹，表示對 k 維空間的一個劃分。kd 樹的每個結點對應一個 k 維的超矩形區域。
通常，依次選擇坐標軸對空間切分（或者分別計算n個特徵的取值的方差，然後取方差最大的第k維特徵n_k對應的坐標軸來對空間進行切分（改進方法））。選擇切分點時 為訓練實例點在對應坐標軸上（投影）的中位數，這樣得到的kd 樹是平衡的。注意：平衡的kd 樹搜索時的效率未必是最優的。
kd 樹的本質其實就是 二叉搜索樹 。
構造平衡二叉樹3.2 搜索kd樹
利用kd 樹，搜索可以限制在空間的局部區域上，可以省去對大部分數據點的搜索，從而減少搜索的計算量（主要是由於很多樣本點由於所在的超矩形區域和超球體不相交，根本不需要計算距離）。
搜索kd樹
kd 樹搜索的平均計算複雜度是 O(logN)，N為訓練實例數。kd 數適合於 N >> k 的情況，當 N ~ k 接近時，效率尋找下降，幾乎接近 線性掃描。
3.3 kd 樹預測
kd樹的預測：在kd樹搜索最近鄰的基礎上，我們選擇到了第一個最近鄰樣本，就把它置為已選。在第二輪中，我們忽略置為已選的樣本，重新選擇最近鄰，這樣跑k次，就得到了目標的K個最近鄰，然後根據多數表決法，如果是KNN分類，預測為K個最近鄰裡面有最多類別數的類別。如果是KNN回歸，用K個最近鄰樣本輸出的平均值作為回歸預測值。
4. 代碼示例 
可用於分類和回歸任務，下面的示例：使用KNN完成鳶尾花分類任務。
引入包和加載數據：
from matplotlib import pyplot as plt
from matplotlib.colors import ListedColormap

from sklearn import datasets
from sklearn.model_selection import train_test_split
import numpy as np
from sklearn.neighbors import KNeighborsClassifier

iris = datasets.load_iris()
print(iris['data'].shape, iris['target'].shape) # (150, 4) (150,)
X = iris.data[:,[2,3]]
y = iris.target
print('Class labels:', np.unique(y))
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)
print(X_train.shape, y_train.shape)
輸出：
(150, 4) (150,)
Class labels: [0 1 2]
(105, 2) (105,)
繪製決策邊界函數：
# 訓練，並繪製分類決策邊界：
def plot_decision_regions(X, y, classifier, test_idx=None, resolution=0.02):
     # setup marker generator and color map
     markers = ('s', 'x', 'o', '^', 'v')
     colors = ('red', 'blue', 'lightgreen', 'gray', 'cyan')
     cmap = ListedColormap(colors[:len(np.unique(y))])

     # plot the decision surface
     x1_min, x1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
     x2_min, x2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
     xx1, xx2 = np.meshgrid(np.arange(x1_min, x1_max, resolution),
                            np.arange(x2_min, x2_max, resolution))
     Z = classifier.predict(np.array([xx1.ravel(), xx2.ravel()]).T)
     Z = Z.reshape(xx1.shape)
     plt.contourf(xx1, xx2, Z, alpha=0.3, cmap=cmap)
     plt.xlim(xx1.min(), xx1.max())
     plt.ylim(xx2.min(), xx2.max())

     for idx, cl in enumerate(np.unique(y)):
         plt.scatter(x=X[y == cl, 0], y=X[y == cl, 1],
         alpha=0.8, c=colors[idx],
         marker=markers[idx], label=cl,
         edgecolor='black')

     # highlight test samples
     if test_idx:
         # plot all samples
         X_test, y_test = X[test_idx, :], y[test_idx]
         plt.scatter(X_test[:, 0], X_test[:, 1],
                     c='', edgecolor='black', alpha=1.0,
                     linewidth=1, marker='o',
                     s=100, label='test set')
訓練：
# 標準化數據
from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit(X_train)
X_train_std = sc.transform(X_train)
X_test_std = sc.transform(X_test)

X_combined_std = np.vstack((X_train_std, X_test_std))
y_combined = np.hstack((y_train, y_test))

# 訓練，k=5, 距離度量為
knn = KNeighborsClassifier(n_neighbors=5, p=2, metric='minkowski')
knn.fit(X_train_std, y_train)

print('Training accuracy:', knn.score(X_train_std, y_train))
print('Testing accuracy:', knn.score(X_test_std, y_test))
輸出：
Training accuracy: 0.9619047619047619
Testing accuracy: 1.0
繪製決策邊界：
# 繪製決策邊界
plot_decision_regions(X_combined_std, y_combined, classifier=knn, test_idx=range(105,150))
plt.xlabel('petal length [standardized]')
plt.ylabel('petal width [standardized]')
plt.legend(loc='upper left')
plt.show()
分類決策邊界5. 模型評價 
模型評價參考自劉建平老師的K近鄰法(KNN)原理小結。
KNN簡單、直觀，其主要優點有：
1） 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸3） 訓練時間複雜度比支持向量機之類的算法低，僅為O(n) （建樹的過程）4） 和樸素貝葉斯之類的算法比，對數據沒有假設，準確度高，對異常點不敏感5） 由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合6）該算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種算法比較容易產生誤分
KNN的主要缺點有：
4）使用懶散學習方法（a lazy learning algorithm），基本上不學習，導致預測時速度比起邏輯回歸之類的算法慢完整代碼地址 
完整代碼請移步至我的github：https://github.com/qingyujean/Magic-NLPer，求贊求星求鼓勵~~~
最後：如果本文中出現任何錯誤，請您一定要幫忙指正，感激~
參考 
[1] 統計學習方法（第2版） 李航
[2] K近鄰法(KNN)原理小結   劉建平https://www.cnblogs.com/pinard/p/6061661.html
[3] Python_Machine_Learning_2nd_Edition

相關焦點

  • KNN算法中的K有多重要
    import matplotlib.pyplot as pltplt.figure(figsize=(12,8))plt.scatter(X[:,0], X[:,1], c=y)選擇最優k值是建立一個合理、精確的knn模型的必要條件。如果k值太低，則模型會變得過於具體，不能很好地泛化。它對噪音也很敏感。
  • 教你學Python26-knn臨近算法
    KNN 概述k-近鄰（kNN, k-NearestNeighbor）算法是一種基本分類與回歸方法，我們這裡只討論分類問題中的 k-近鄰算法。一句話總結：近朱者赤近墨者黑！工作原理： 存在一個樣本數據集合，也稱作為訓練樣本集，並且樣本集中每個數據都存在標籤，即我們知道樣本集中每一個數據與所屬分類的對應關係。輸入沒有標籤的新數據後，將新的數據的每個特徵與樣本集中數據對應的特徵進行比較，然後算法提取樣本最相似數據(最近鄰)的分類標籤。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大於20的整數。
  • AI產品經理必懂算法:k-近鄰(KNN)算法
    今天我們就從一個最為簡單、易懂的「k-近鄰（KNN）算法」聊起，KNN屬於監督學習算法，即可以用於分類，也可以用於回歸，後續還會逐步為大家介紹一些常用的其他算法。我們之所以要了解算法，不僅僅有利於和算法同學的溝通，更能深入的理解人工智慧為產品賦能的過程，只有將這個過程了解透徹，才能清晰明確的把握產品的方向，挖掘產品的亮點。
  • Python機器學習之K近鄰分類器
    最簡單的分類器是近鄰分類器。近鄰算法搜索訓練集，尋找與用作測試的新個體最相似的觀測記錄。講到這裡，弄清楚訓練集和測試集這兩個概念很重要。如果確實只有一個數據集，也沒關係，重要的是不要使用同一份數據同時用於訓練和測試。鑑於此，把數據集分為兩部分：一部分專門用於訓練算法，另一部分用於驗證算法。
  • 比KNN快380倍!我們有了新選擇
    最近鄰的搜索從最頂層開始粗略搜索，繼而向下層遞進，直至在最下層使用貪心算法的線路來遍歷全圖，找到所需數字的近鄰。HNSW圖的結構。在最頂層開始最近鄰的搜索（粗略搜索），在最底層結束搜索（精細搜索）。ann_neighbor_indices, ann_distances = p.knn_query(features, k)KNNvs. ANN 基準實驗首先下載一個有50萬行以上的大型數據集。接著用預先訓練好的 fasttext句子向量，將文本列轉換為 300d的嵌入向量。
  • 利用k-近鄰算法模擬原油黏度
    利用k-近鄰算法模擬原油黏度本篇文章來自伊朗阿米爾卡比爾工業大學和美國普林斯頓大學等單位Modeling viscosity of crude oil using k-nearest neighbor algorithmMohammad
  • 機器學習:基於Knn算法的用戶屬性判斷方案設計
    knn算法簡介K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。knn的基本思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。如下圖所示，如何判斷綠色圓應該屬於哪一類，是屬於紅色三角形還是屬於藍色四方形？
  • 教你用OpenCV實現機器學習最簡單的k-NN算法
    簡單而言，k-NN算法認為一個數據點很可能與它近鄰的點屬於同一個類。思考一下：如果我們的鄰居是紅隊球迷，我們很可能也是紅隊球迷，否則我們可能很早之前就搬家到其他地方了。對於藍隊球迷而言也是這樣。當然，有些社區可能稍微複雜一些。在這種情況下，我們將不僅僅考慮我們最近鄰的類別（即k=1），而是考慮k個最近鄰的類別。
  • 在機器學習的世界裡打怪升級——KNN算法篇
    boss技能綜述 先來看看該boss的整體技能（原理）綜述： 要想預測一個新數據，只需把它放到訓練數據集中（「舊數據」），看它離哪些數據近，就把它預測為這些數據的類別（分類）；或者把它預測為這些數據的均值（回歸）。
  • KNN分類算法的python實現
    前言 K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：在特徵空間中，如果一個樣本附近的k個最近(即特徵空間中最鄰近)樣本的大多數屬於某一個類別，則該樣本也屬於這個類別。。
  • 基於KNN和Kmeans算法利用MNIST數據集實現手寫數字識別
    作者： 陳千鶴 來源：人工智慧學習圈 KNN算法發展狀況K-最近鄰法(K-Nearest Neighbor, KNN)最初由Cover和Hart於1968年提出，是一個在理論上比較成熟的分類算法。這是一種基於模板匹配思想的算法，雖然簡單，但很有效，至今仍在被使用。
  • 使用NumPy從頭開始進行K最近鄰分類
    在訓練過程之前，我們選擇一個數字作為我們的超參數（k）。因此，例如，當k=5時，我們指的是前5個最近的數據點。在上面的kneighbors函數中，我們找到測試數據集(我們要分類的數據點)中的每個點與數據集其餘部分(即訓練數據)之間的距離。我們將這些距離存儲在point_dist中，其中每一行對應一個測試數據點到所有訓練數據之間的距離列表。
  • XGBoost算法原理小結
    前言XGBoost（eXtreme Gradient Boosting）全名叫極端梯度提升，XGBoost是集成學習方法的王牌，在Kaggle數據挖掘比賽中，大部分獲勝者用了XGBoost，XGBoost在絕大多數的回歸和分類問題上表現的十分頂尖，本文較詳細的介紹了XGBoost的算法原理。
  • 音速噴嘴法氣體流量標準裝置的基本原理
    引 言 標準表法流量標準裝置的方法很多，下面介紹一種用音速文丘利噴嘴作標準表的氣體流量標準裝置。音速噴嘴法氣體流量標準裝置適用於對各種氣體流量計的檢測和校準, 可以檢測質量流量計、速度式流量計、容積式流量計、轉子流量計、差壓式流量計或其它種類的流量計。 　 裝置結構 音速噴嘴法氣體流量標準裝置的結構如圖1所示。
  • 點到平面的距離求法小結--中國數字科技館
    文章數 點到平面的距離求法小結2009-12-09 01:59:23
  • 譜聚類(spectral clustering)原理總結
    下面我們就對譜聚類的算法原理做一個總結。 1.1 譜聚類概述 譜聚類是從圖論中演化出來的算法，後來在聚類中得到了廣泛的應用。它的主要思想是把所有的數據看做空間中的點，這些點之間可以用邊連接起來。從上式可見，兩點間的權重要不就是ϵ,要不就是0，沒有其他的信息了。距離遠近度量很不精確，因此在實際應用中，我們很少使用ϵ-鄰近法。