一.KNN演算法介紹

鄰近演算法，或者說K最鄰近（KNN，K-NearestNeighbor）分類演算法是資料探勘分類技術中最簡單的方法之一。所謂K最近鄰，就是K個最近的鄰居的意思，說的是每個樣本都可以用它最接近的K個鄰近值來代表。近鄰演算法就是將資料集合中每一個記錄進行分類的方法。

k近鄰法是一種基本的分類和迴歸方法，是監督學習方法裡的一種常用方法。k近鄰演算法假設給定一個訓練資料集，其中的例項類別已定。分類時，對新的例項，根據其k個最近鄰的訓練例項類別，通過多數表決等方式進行預測。

二.KNN演算法核心思想

KNN演算法的核心思想是，如果一個樣本在特徵空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

三.KNN演算法三要素

k近鄰法三要素：距離度量、k值的選擇和分類決策規則。常用的距離度量是歐氏距離及更一般的pL距離。k值小時，k近鄰模型更復雜，容易發生過擬合；k值大時，k近鄰模型更簡單，又容易欠擬合。因此k值得選擇會對分類結果產生重大影響。k值的選擇反映了對近似誤差與估計誤差之間的權衡，通常由交叉驗證選擇最優的k。

四.KNN演算法優缺點

優點

1.簡單，易於理解，易於實現，無需估計引數，無需訓練； 2. 適合對稀有事件進行分類； 3.特別適合於多分類問題(multi-modal,物件具有多個類別標籤)， kNN比SVM的表現要好。

缺點

1.該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 2.該方法的另一個不足之處是計算量較大，因為對每一個待分類的文字都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。

五.原始碼簡單實現

1.導包

python import numpy as np from math import sqrt from collections import Counter from metrics import accuracy_score

2.初始化kNN分類器

```python class KNNClassifier:

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

```

3.訓練資料集

```python def fit(self, X_train, y_train): """根據訓練資料集X_train和y_train訓練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

```

4.多個值的預測

```python def predict(self, X_predict): """給定待預測資料集X_predict，返回表示X_predict的結果向量""" 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)

```

5.單個值的預測

```python def _predict(self, x): """給定單個待預測資料x，返回x的預測結果值""" assert x.shape[0] == self._X_train.shape[1], \ "the feature number of x must be equal to X_train"

    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[:self.k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]

```

6.模型準確度

```python def score(self, X_test, y_test): """根據測試資料集 X_test 和 y_test 確定當前模型的準確度"""

    y_predict = self.predict(X_test)
    return accuracy_score(y_test, y_predict)

```

六.全部程式碼

```python import numpy as np from math import sqrt from collections import Counter from metrics import accuracy_score

class KNNClassifier:

def __init__(self, k):
    """初始化kNN分類器"""
    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):
    """根據訓練資料集X_train和y_train訓練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):
    """給定待預測資料集X_predict，返回表示X_predict的結果向量"""
    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):
    """給定單個待預測資料x，返回x的預測結果值"""
    assert x.shape[0] == self._X_train.shape[1], \
        "the feature number of x must be equal to X_train"

    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[:self.k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]

def score(self, X_test, y_test):
    """根據測試資料集 X_test 和 y_test 確定當前模型的準確度"""

    y_predict = self.predict(X_test)
    return accuracy_score(y_test, y_predict)

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

```

KNN演算法介紹及原始碼實現