0.KNN是什么

KNN算法中文名稱叫做K近鄰算法，是眾多機(jī)器學(xué)習(xí)算法里面最基礎(chǔ)入門的算法。它是一個(gè)有監(jiān)督的機(jī)器學(xué)習(xí)算法，既可以用來(lái)做分類任務(wù)也可以用來(lái)做回歸任務(wù)。KNN算法的核心思想是未標(biāo)記的樣本的類別，由距離他最近的K個(gè)鄰居投票來(lái)決定。

K近鄰法使用的模型，實(shí)際上是特征空間的劃分。模型由三個(gè)基本要素決定：

• 距離度量
• k值
• 分類決策規(guī)則

其中兩個(gè)實(shí)例點(diǎn)之間的距離反映了相似程度。一般來(lái)說(shuō)使用歐氏距離來(lái)計(jì)算。

1.算法流程

假設(shè)X_test為待標(biāo)記的樣本，X_train為已標(biāo)記的樣本數(shù)據(jù)集：

1、求距離：遍歷X_train中的所有樣本，計(jì)算每個(gè)樣本與X_test的之間的距離(一般為歐式距離)。并且把距離保存在一個(gè)distince 的數(shù)組中。

2、排序：對(duì)distince數(shù)組進(jìn)行排序，取距離最近的K個(gè)點(diǎn)。記作X_knn。

3、統(tǒng)計(jì)：在X_knn中統(tǒng)計(jì)每個(gè)類別的個(gè)數(shù)，既class0在X_knn中有幾個(gè)樣本，class1在X_knn中有幾個(gè)樣本等。

4、投票：待標(biāo)記樣本的類別就是X_knn中樣本個(gè)數(shù)最多的那個(gè)類別。

2.算法實(shí)現(xiàn)

代碼實(shí)現(xiàn)：

###1.準(zhǔn)備數(shù)據(jù)

import numpy as np
import matplotlib.pyplot as plt

# raw_data_x是特征，raw_data_y是標(biāo)簽，0為良性，1為惡性
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343853454, 3.368312451],
              [3.582294121, 4.679917921],
              [2.280362211, 2.866990212],
              [7.423436752, 4.685324231],
              [5.745231231, 3.532131321],
              [9.172112222, 2.511113104],
              [7.927841231, 3.421455345],
              [7.939831414, 0.791631213]
             ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

# 設(shè)置訓(xùn)練組
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)

# 將數(shù)據(jù)可視化
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = 'Time')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.axis([0,10,0,5])
plt.show()

###2.求距離：求點(diǎn)x到數(shù)據(jù)集中每個(gè)點(diǎn)的距離，首先計(jì)算距離，使用歐氏距離

from math import sqrt

distances = []  # 用來(lái)記錄x到樣本數(shù)據(jù)集中每個(gè)點(diǎn)的距離
for x_train in X_train:
    d = sqrt(np.sum((x_train - x) ** 2))
    distances.append(d)
    
# 使用列表生成器，一行就能搞定，對(duì)于X_train中的每一個(gè)元素x_train都進(jìn)行前面的運(yùn)算，把結(jié)果生成一個(gè)列表
distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]

distances

輸出：
[5.611968000921151,
 6.011747706769277,
 7.565483059418645,
 5.486753308891268,
 6.647709180746875,
 1.9872648870854204,
 3.168477291709152,
 0.8941051007010301,
 0.9830754144862234,
 2.7506238644678445]

###3.排序：要找到最小的距離，要知道距離最小的k個(gè)點(diǎn)是在樣本集中的位置
nearest = np.argsort(distances)
nearest

輸出：
array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2])

###4.選k值

k = 6
topK_y = [y_train[i] for i in nearest[:k]]
topK_y

輸出：
[1, 1, 1, 1, 1, 0]

###5.決策
from collections import Counter
votes = Counter(topK_y)
votes

輸出：一個(gè)字典，原數(shù)組中值為0的個(gè)數(shù)為1，值為1的個(gè)數(shù)為5
Counter({0:1, 1:5})

# Counter.most_common(n) 找出票數(shù)最多的n個(gè)元素，返回的是一個(gè)列表，列表中的每個(gè)元素是一個(gè)元組，元組中第一個(gè)元素是對(duì)應(yīng)的元素是誰(shuí)，第二個(gè)元素是頻次
votes.most_common(1)

輸出：
[(1,5)]

predict_y = votes.most_common(1)[0][0] 
predict_y

輸出：
1

工程代碼封裝：

import numpy as np
from math import sqrt
from collections import Counter

class kNNClassifier:

    def __init__(self, k):
        """初始化分類器"""
        assert k >= 1, "k must be valid"
        self.k = k
        self._X_train = None
        self._y_train = None

    def fit(self, X_train, y_train):
        """根據(jù)訓(xùn)練數(shù)據(jù)集X_train和y_train訓(xùn)練kNN分類器"""
        assert X_train.shape[0] == y_train.shape[0], \
            "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0], \
            "the size of X_train must be at least k"
        self._X_train = X_train
        self._y_train = y_train
        return self

    def predict(self,X_predict):
        """給定待預(yù)測(cè)數(shù)據(jù)集X_predict，返回表示X_predict結(jié)果的向量"""
        assert self._X_train is not None and self._y_train is not None, \
            "must fit before predict!"
        assert X_predict.shape[1] == self._X_train.shape[1], \
            "the feature number of X_predict must be equal to X_train"
        y_predict = [self._predict(x) for x in X_predict]
        return np.array(y_predict)

    def _predict(self, x):
        distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in self._X_train]
        nearest = np.argsort(distances)
        topK_y = [self._y_train[i] for i in nearest]
        votes = Counter(topK_y)
        return votes.most_common(1)[0][0]

    def __repr__(self):
        return "kNN(k=%d)" % self.k

%run myAlgorithm/kNN.py

knn_clf = kNNClassifier(k=6)
knn_clf.fit(X_train, y_train)
X_predict = x.reshape(1,-1)
y_predict = knn_clf.predict(X_predict)
y_predict

輸出：
array([1])

很明顯KNN算法的時(shí)間復(fù)雜度為O(DNN)。其中D為維度數(shù)，N為樣本總數(shù)。從時(shí)間復(fù)雜度上我們可以很清楚的就知道KNN非常不適合高維度的數(shù)據(jù)集，容易發(fā)生維度爆炸的情況。同時(shí)我們也發(fā)現(xiàn)了一個(gè)問(wèn)題在關(guān)于K的選擇上面，我們一般也要選擇K的值應(yīng)該盡量選擇為奇數(shù)，并且不要是分類結(jié)果的偶數(shù)倍，否則會(huì)出現(xiàn)同票的情況。我們到底應(yīng)該怎么去選擇K的大小比較合適呢？答案是交叉驗(yàn)證。交叉驗(yàn)證指的是將訓(xùn)練數(shù)據(jù)集進(jìn)一步分成訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)，選擇在驗(yàn)證數(shù)據(jù)里面最好的超參數(shù)組合，也就是調(diào)參。參數(shù)一般分為模型參數(shù)和超級(jí)參數(shù)。模型參數(shù)是需要我們通過(guò)不斷的調(diào)整模型和超參數(shù)訓(xùn)練得到的最佳參數(shù)。而超參數(shù)則是我們?nèi)藶槭謩?dòng)設(shè)定的值。像在KNN中超參數(shù)就是K的值。我們可以通過(guò)交叉驗(yàn)證的方式，選擇一組最好的K值作為模型最終的K值。

3.sklearn 中的KNN

##流程：訓(xùn)練數(shù)據(jù)集 -> 機(jī)器學(xué)習(xí)算法 -fit-> 模型 輸入樣例 -> 模型 -predict-> 輸出結(jié)果

from sklearn.neighbors import KNeighborsClassifier

# 創(chuàng)建kNN_classifier實(shí)例
kNN_classifier = KNeighborsClassifier(n_neighbors=6)

# kNN_classifier做一遍fit(擬合)的過(guò)程，沒(méi)有返回值，模型就存儲(chǔ)在kNN_classifier實(shí)例中
kNN_classifier.fit(X_train, y_train)

# kNN進(jìn)行預(yù)測(cè)predict，需要傳入一個(gè)矩陣，而不能是一個(gè)數(shù)組。reshape()成一個(gè)二維數(shù)組，第一個(gè)參數(shù)是1表示只有一個(gè)數(shù)據(jù)，第二個(gè)參數(shù)-1，numpy自動(dòng)決定第二維度有多少
y_predict = kNN_classifier.predict(x.reshape(1,-1))
y_predict

輸出：
array([1])

參數(shù)及方法說(shuō)明：

class 
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)

4.注意點(diǎn)

1、大數(shù)吞小數(shù)
　　在進(jìn)行距離計(jì)算的時(shí)候，有時(shí)候某個(gè)特征的數(shù)值會(huì)特別的大，那么計(jì)算歐式距離的時(shí)候，其他的特征的值的影響就會(huì)非常的小被大數(shù)給覆蓋掉了。所以我們很有必要進(jìn)行特征的標(biāo)準(zhǔn)化或者叫做特征的歸一化。

2、如何處理大數(shù)據(jù)量
　　一旦特征或者樣本的數(shù)目特別的多，KNN的時(shí)間復(fù)雜度將會(huì)非常的高。解決方法是利用KD-Tree這種方式解決時(shí)間復(fù)雜度的問(wèn)題，利用KD樹(shù)可以將時(shí)間復(fù)雜度降到O(logDNN)。D是維度數(shù)，N是樣本數(shù)。但是這樣維度很多的話那么時(shí)間復(fù)雜度還是非常的高，所以可以利用類似哈希算法解決高維空間問(wèn)題，只不過(guò)該算法得到的解是近似解，不是完全解。會(huì)損失精確率。

3、怎么處理樣本的重要性
　　利用權(quán)重值。我們?cè)谟?jì)算距離的時(shí)候可以針對(duì)不同的鄰居使用不同的權(quán)重值，比如距離越近的鄰居我們使用的權(quán)重值偏大，這個(gè)可以指定算法的weights參數(shù)來(lái)設(shè)置。

待完善...