KNN-近鄰算法

思路：兩個樣本如果足夠相似，那么他們可能屬于同一個類別。

原理介紹

我們先來看一個簡單的案例：
現(xiàn)在有10組數(shù)據(jù)，第一組 raw_data_x 記錄每個病人的血壓和血常規(guī),第二組 raw_data_y 記錄病人是否屬于疾病晚期(0 表示不是晚期， 1表示晚期):

raw_data_x = [
    [3.393953321, 2.331273301],
    [3.110073482, 1.781519638],
    [1.343800831, 3.368369547],
    [3.543243008, 4.686943958],
    [2.847390282, 2.867942324],
    [7.432434368, 4.683435453],
    [5.745051997, 3.533989803],
    [9.172168622, 2.511101045],
    [7.792783481, 3.424088941],
    [7.939820817, 0.791637231]
]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

對應(yīng)的圖像如下（藍(lán)點(diǎn)表示不是疾病晚期，紅點(diǎn)就是疾病晚期）：

屏幕快照 2020-02-15 上午9.26.53.png
現(xiàn)在如果來了一個新的患了同種疾病的人，已知他的血壓和血常規(guī) [3.390000766, 2.1829382999]，現(xiàn)在要預(yù)測這個人是否可能是晚期,我們就可以把這個點(diǎn)用藍(lán)色也畫在坐標(biāo)軸中如下：
屏幕快照 2020-02-15 上午9.30.34.png
從圖中可以看出，這個新的病人指標(biāo)最近的幾個點(diǎn)中，藍(lán)點(diǎn)的數(shù)量較多一些，所以我們可以初步猜測這個病人不是疾病晚期。

公式推導(dǎo)

如果要用數(shù)學(xué)做量化的話，實(shí)際上我們就是要找到和新的數(shù)據(jù)距離最近的那幾個點(diǎn)，看這幾個點(diǎn)的情況來預(yù)測新的這個點(diǎn)的情況。數(shù)學(xué)上計算兩個點(diǎn)的距離我們一般稱之為歐拉距離

  • 歐拉距離推導(dǎo)過程:
    主要用來求n維空間中的兩個點(diǎn)之間的距離，我們來回憶一下初中幾何中，用z表示維度：

    當(dāng)z = 2時, 二維平面的兩個點(diǎn)之間的距離如下：
    2dim.png
    當(dāng)z = 3時，三維空間的兩個點(diǎn)之間的距離為：
    3dim.png
    當(dāng)z = n 時，此時的空間已經(jīng)不是我們?nèi)搜鬯茏R別的了，但是我們依舊可以遞推出來兩個點(diǎn)的距離公式：
    ndim.png

    簡單點(diǎn)的寫法就是這樣：
    ndimeasy.png

設(shè)計實(shí)現(xiàn)

好了，知道了如何求n維空間的歐拉距離，我們就可以編碼實(shí)現(xiàn)我們的demo了

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
from math import sqrt

"""KNN算法實(shí)現(xiàn)過程, 目前取距離最近的前3個點(diǎn)進(jìn)行預(yù)測"""
if __name__ == "__main__":
    raw_data_x = [
        [3.393953321, 2.331273301],
        [3.110073482, 1.781519638],
        [1.343800831, 3.368369547],
        [3.543243008, 4.686943958],
        [2.847390282, 2.867942324],
        [7.432434368, 4.683435453],
        [5.745051997, 3.533989803],
        [9.172168622, 2.511101045],
        [7.792783481, 3.424088941],
        [7.939820817, 0.791637231]
    ]
    raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

    x_train = np.array(raw_data_x)
    y_train = np.array(raw_data_y)
    A = np.array([3.390000766, 2.1829382999])
    distinct = [sqrt(np.sum((x - A)**2)) for x in x_train]
    nearest = np.argsort(distinct)
    k = 3
    topK_y = [y_train[i] for i in nearest[:k]]

    votes = Counter(topK_y)
    result = votes.most_common(1)[0][0]
    result = "晚期" if result == 1 else "不是晚期"
    print("新病人：{}".format(result))

高級部分

其實(shí)python已經(jīng)有很多優(yōu)秀的庫實(shí)現(xiàn)了對KNN算法的封裝，為了穩(wěn)定性和準(zhǔn)確性我們一邊會使用一些比較業(yè)界比較經(jīng)典的機(jī)器學(xué)習(xí)算法庫。例如，scikit-learn
官網(wǎng)地址: scikit-learn(sklearn): http://scikit-learn.org
如果不想看英文，請自行百度中文版的scikit-learn api文檔，
下面看一下scikit-learn中如何使用內(nèi)置的數(shù)據(jù)集和算法庫實(shí)現(xiàn)KNN-近鄰算法：

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

if __name__ == "__main__":
    # load dataset
    iris = datasets.load_iris()
    X = iris.data
    y = iris.target

    # train_test_split
    from sklearn.model_selection import train_test_split
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=666)

    # normalization
    from sklearn.preprocessing import StandardScaler
    standardScaler = StandardScaler()
    standardScaler.fit(X_train)
    X_train = standardScaler.transform(X_train)
    X_test_standard = standardScaler.transform(X_test)

    # use KNeighborsClassifier && GridSearch
    from sklearn.model_selection import GridSearchCV
    param_grid = [
        {
            "weights": ["uniform"],
            "n_neighbors": [i for i in range(1, 11)]
        },
        {
            "weights": ["distance"],
            "n_neighbors": [i for i in range(1, 11)],
            "p": [i for i in range(1, 6)]
        },
    ]
    knn_clf = KNeighborsClassifier()

    """
    n_jobs : Number of jobs to run in parallel
    verbose : Controls the verbosity: the higher, the more messages
    iid： If True, return the average score across folds, weighted by the number of samples in each test set.  
    cv：Determines the cross-validation splitting strategy
    """
    grid_search = GridSearchCV(estimator=knn_clf, param_grid=param_grid, n_jobs=-1, verbose=2, iid=True, cv=5)

    grid_search.fit(X_train, y_train)
    knn_clf = grid_search.best_estimator_
    print(knn_clf.score(X_test_standard, y_test))

說明：我們加載了sciken-learn內(nèi)置的鳶蕊花數(shù)據(jù)集，由于數(shù)據(jù)集本身就是亂序，所以我們只需要對整個數(shù)據(jù)集進(jìn)行簡單劃分即70%的數(shù)據(jù)用于訓(xùn)練生成模型，30%的數(shù)據(jù)用來驗(yàn)證模型的一個準(zhǔn)確性，其次為了保證計算距離時每個維度能夠的平等，我們對數(shù)據(jù)進(jìn)行了一次均值-方差歸一化處理，最后我們使用網(wǎng)格搜索的方式讓模型自動選出最好的模型參數(shù)，然后將測試集推到最好的模型中進(jìn)行測試。

看不懂上面的“鳥語”也沒關(guān)系，下面我會一一說明這些詞語的含義：

拋開上面的東西，我們來思考幾個問題。

  • 我們要如何判斷機(jī)器學(xué)習(xí)的性能呢？
    關(guān)于這個問題其實(shí)我們可以想到的一個最為簡單的做法就是將原始的數(shù)據(jù)進(jìn)行打散，然后從中分出一部分?jǐn)?shù)據(jù)用來訓(xùn)練模型，另一部分用來測試便可。也就是所謂的訓(xùn)練/測試集分離（train_test_split）。
    最后，有了測試集我們就能計算出模型的分類的準(zhǔn)確度（accuracy）:
    accuracy = (預(yù)測正確的測試樣本個數(shù)/ 總測試樣本個數(shù)) 這個指標(biāo)很好理解就是拿模型最后預(yù)測的結(jié)果和測試集真實(shí)的類別進(jìn)行整除而已，這里不在贅訴。

  • 每個維度的單位不一樣，數(shù)值大小也會不一樣，這就會導(dǎo)致我們計算距離的時候，針對不同的屬性，數(shù)值相對更大的那一類屬性的權(quán)重默認(rèn)就會比數(shù)值小的那一類屬性高，邏輯上導(dǎo)致計算的距離可能是不合理的，我們要如何規(guī)避這種屬性不平等的問題呢？
    業(yè)界解決這種問題有一個專門的術(shù)語叫做數(shù)據(jù)歸一化，主要用的有兩種：

最值歸一化 （normalization）:把所有數(shù)據(jù)歸一化到0-1空間 ,具體做法如下（X \Longrightarrow X_{scale}）其中：

X_{scale} = (X-X_{min})/(X_{max}-X_{min})
下面演示一下上面的鳶蕊花數(shù)據(jù)集進(jìn)行最值歸一化的一個效果：

from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

if __name__ == "__main__":
    # load dataset
    iris = datasets.load_iris()
    X = iris.data
    y = iris.target

    # train_test_split
    from sklearn.model_selection import train_test_split
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=666)

    from sklearn.preprocessing import MinMaxScaler
    minMaxScaler = MinMaxScaler()
    minMaxScaler.fit(X_train)
    X_train = minMaxScaler.transform(X_train)
    print(X_train.shape)
    plt.scatter(X_train[:, 0], X_train[:, 1],  X_train[:, 2],  X_train[:, 3])z
    plt.show()
maxminScaler.png

數(shù)值都被歸一化到一個0-1空間

均值方差歸一化（standardization）：把所有數(shù)據(jù)歸一到均值為0方差為1的分布中，X \Longrightarrow X_{scale}）其中：：
X_{scale} = (X-avg(X))/(std(X)) 也就是每個數(shù)減去總體的均值后除以總體方差。

import numpy as np
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

if __name__ == "__main__":
    # load dataset
    iris = datasets.load_iris()
    X = iris.data
    y = iris.target
    # train_test_split
    from sklearn.model_selection import train_test_split
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=666)

    # normalization
    from sklearn.preprocessing import StandardScaler
    standardScaler = StandardScaler()
    standardScaler.fit(X_train)
    X_train = standardScaler.transform(X_train)
    plt.scatter(X_train[:, 0], X_train[:, 1])
    plt.show()
means.png
  • 真實(shí)的世界距離有好多種，如何定義距離呢?
    這是一個非常抽象的話題，可能目前我們只接觸到了歐式距離，但其實(shí)還有：
    曼哈頓距離: \sum_{k=1}^N D(X_a-X_b） 每個屬性的距離絕對值求和
    明可夫斯基距離:\sum_{k=1}^N (X_a-X_b）^p)^ {1/p} 每個維度距離的p次方的1/p；可以看出p=2時，明可夫斯基距離也是歐拉距離,除此之外，還有向量空間余弦相識度，調(diào)整余弦相識度， 皮爾森相關(guān)系數(shù)， Jaccard相似系數(shù)等，具體要用哪一種還是需要結(jié)合具體業(yè)務(wù)。
  • 關(guān)于超參數(shù)和網(wǎng)格搜素
    超參數(shù)：在運(yùn)行機(jī)器學(xué)習(xí)算法之前，需要預(yù)先決定的參數(shù)， 例如如果我們使用明可夫斯基距離那么p的值就是超參數(shù)，train_test_split中的測試集的比例(test_size)等等。
    模型參數(shù)：算法過程中學(xué)習(xí)的參數(shù)

日常情況下我們可能可以針對我們的業(yè)務(wù)設(shè)定一個比較合理的超參數(shù)來開始訓(xùn)練模型，但多數(shù)場景下我們都是靠猜。
網(wǎng)格搜索：這里所謂的網(wǎng)格搜索就是用來解決超參數(shù)問題的，基本原理就是把我們每個參數(shù)的取值范圍都排列組合然后每一組參數(shù)就會有一個模型，我們最好選出準(zhǔn)確度最高的那個模型就可以了。下面看一下具體做法：

 # use KNeighborsClassifier && GridSearch
    from sklearn.model_selection import GridSearchCV
    param_grid = [
        {
            "weights": ["uniform"],
            "n_neighbors": [i for i in range(1, 11)]
        },
        {
            "weights": ["distance"],
            "n_neighbors": [i for i in range(1, 11)],
            "p": [i for i in range(1, 6)]
        },
    ]
    knn_clf = KNeighborsClassifier()

    """
    n_jobs : Number of jobs to run in parallel
    verbose : Controls the verbosity: the higher, the more messages
    iid： If True, return the average score across folds, weighted by the number of samples in each test set.  
    cv：Determines the cross-validation splitting strategy
    """
    grid_search = GridSearchCV(estimator=knn_clf, param_grid=param_grid, n_jobs=-1, verbose=2, iid=True, cv=5)

    grid_search.fit(X_train, y_train)
    print(grid_search.best_estimator_)
    knn_clf = grid_search.best_estimator_

控制臺輸出如下：

...
[Parallel(n_jobs=-1)]: Done 300 out of 300 | elapsed:    1.7s finished
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                     metric_params=None, n_jobs=None, n_neighbors=9, p=2,
                     weights='uniform')
0.9777777777777777

可以看出我們最終的發(fā)現(xiàn)n_neighbors=9, p=2,weights='uniform' 這個組合的模型準(zhǔn)確度最高達(dá)到了97.77777777777777%

寫到最后

我們總結(jié)一下KNN-近鄰算法的優(yōu)缺點(diǎn)吧：

  • 優(yōu)點(diǎn)1：解決多分類問題，思想簡單，效果強(qiáng)大
  • 優(yōu)點(diǎn)2：解決回歸問題
  • 優(yōu)點(diǎn)3：適合對稀有事件進(jìn)行分類；
  • 優(yōu)點(diǎn)4:特別適合于多分類問題(multi-modal,對象具有多個類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好。
  • 缺點(diǎn)1：效率低下
    如果有m個樣本， 那個特征，那么復(fù)雜度為 O（m * n）
    優(yōu)化思路： 使用樹結(jié)構(gòu)： KD-tree 或者 Ball_tree
  • 缺點(diǎn)2: 高度數(shù)據(jù)相關(guān)
    依賴數(shù)據(jù)集本身的數(shù)據(jù)
  • 缺點(diǎn)3: 預(yù)測結(jié)果不具備解釋性
    整個算法的起點(diǎn)就是假設(shè)屬性相似的兩個樣本類別可能也一樣
  • 缺點(diǎn)4: 維數(shù)災(zāi)難
    隨著維數(shù)增加，兩個很近的點(diǎn)的”距離“會越來越大，而KNN高度依賴“距離“
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • K-近鄰算法采用測量不同特征值之間的距離方法進(jìn)行分類。 kNN近鄰分類算法的原理(來源網(wǎng)絡(luò)): 從上圖...
    蠟筆小虎_007閱讀 941評論 1贊 1
  • 前言 通過本文，你將了解并深刻理解什么是 KNN算法。當(dāng)然，閱讀本文前，你最好會點(diǎn)python,這樣閱讀起來才會沒...
    code_solve閱讀 4,811評論 9贊 46
  • 目錄 一、KNN近鄰算法思想 二、KNN模型三大要素 三、KNN算法實(shí)現(xiàn)步驟 四、KNN算法的KD樹實(shí)現(xiàn) 五、總結(jié)...
    易碼當(dāng)先閱讀 869評論 0贊 2
  • 【博客的主要內(nèi)容主要是自己的學(xué)習(xí)筆記，并結(jié)合個人的理解，供各位在學(xué)習(xí)過程中參考，若有疑問，歡迎提出；若有侵權(quán)，請告...
    Paullu閱讀 1,057評論 1贊 6
  • kNN近鄰算法 算法原理 樣本點(diǎn)的特性與該鄰居點(diǎn)的特性類似，可以簡單理解為“物以類聚”。因此可以使用目標(biāo)點(diǎn)的多個鄰...
    lqzzz閱讀 303評論 0贊 2

友情鏈接更多精彩內(nèi)容