最近鄰居分類(k-nearest neighbors, k-NN)的概念相當簡單：一個資料點在空間中跟哪個類別的點最接近，就說它是屬於那一個類別。這個方法不需要訓練過程，或者說訓練就是把所有資料記起來；而在預測的階段，則是將待測點與其他資料點計算距離，找出最接近的 k 的點，並依據這 k 的點所屬的類別或值進行投票，來做為待測點的預測結果。

我們使用 scikit-learn 的 neighbors.KNeighborsClassifier 來幫我們執行 k-NN 演算法，使用的資料集是 Wine Data Set，該資料集在 scikit-learn 有內建一版，你可以直接透過 import 相關函式來使用，不必自己下載：

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

dataset = load_wine()
print('Data shapes:', dataset.data.shape, dataset.target.shape)

X_train, X_test, y_train, y_test = train_test_split(dataset.data, dataset.target)
print('Training data shapes:', X_train.shape, y_train.shape)
print('Test data shapes:', X_test.shape, y_test.shape)

model = KNeighborsClassifier(n_neighbors=1)
model.fit(X_train, y_train)
pred = model.predict(X_test)
print('Accuracy (sklearn): {:.2f}%'.format(100*np.mean(pred==y_test)))

pred = []
for p_te in X_test:
    dists = [np.sum((p_tr - p_te) ** 2) ** 0.5 for p_tr in X_train]
    pred.append(y_train[np.argmin(dists)])

pred = np.array(pred)
print('Accuracy (for loop): {:.2f}%'.format(100*np.mean(pred==y_test)))

在上述範例中，由於 train_test_split 是隨機進行，因此每次執行時，準確度可能會有所變化。此外，範例的下半部同時也示範了自行實作最近鄰居分類的參考方式，其中的 n_neighbors 與前半部同樣為 1，距離則是使用 2-norm。

下面對 KNeighborsClassifier 的部分參數進行一些說明，若需要更多細節，可以參考官方文件。

• n_neighbors: 一次要選幾個鄰居。上述範例使用一個鄰居，你也可以試試看多一點的效果。一般來說，鄰居數目會選用與類別數目不相等的奇數，以盡可能避開票數相同的狀況。
• weights: 距離的權重，或是說投票的方式。預設是相等權重，也提供了距離愈遠則權重愈輕的計算方式，你也可以撰寫一個函式來自行定義權重。
• algorithm: 找最鄰居的演算法，除了最簡單的暴力法以外，也提供了一些 tree-based 的近似方法。預設會幫你自動選擇。

K-NN 在 k = 1 時，每個點的勢力範圍，會是一個 Voronoi Diagram，其中每一條邊界線，就是相鄰樣本的中垂線，範例如下：

import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d

points = np.random.rand(10, 2)
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.axis('equal')
plt.show()

K-NN 演算法在看待不同維度時是一視同仁的，亦即對各個特徵維度給予相同權重，並不會自動區分哪些維度具有判別力。因此若你的資料中，包含有很多雜訊維度的話，則很有可能讓 k-NN 演算法的準確度變差，稱為「高維詛咒」。以下範例是在固定只有兩個有效維度的狀況下，依次加入愈來愈多雜訊維度的範例：

import matplotlib.pyplot as plt
import numpy as np

from sklearn.datasets import make_classification
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

dimensions = [2, 5, 10, 20, 50, 100]
accs_knn = []
accs_another = []

for d in dimensions:
	X, y = make_classification(
		n_samples=2000,
		n_features=d,
		n_informative=2,
		n_redundant=0,
		n_repeated=0,
		n_classes=2,
	)

	X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)

	knn = KNeighborsClassifier(n_neighbors=3)
	knn.fit(X_train, y_train)
	accs_knn.append(knn.score(X_test, y_test))

	clf = LogisticRegression(max_iter=1000)
	clf.fit(X_train, y_train)
	accs_another.append(clf.score(X_test, y_test))

plt.figure()
plt.plot(dimensions, accs_knn, label='KNN')
plt.plot(dimensions, accs_another, label='Another method')
plt.xlabel("# Features")
plt.ylabel("Accuracy")
plt.legend()
plt.show()

在上述範例中，make_classification 函式是用來產生範例資料的，範例中的設定是產生兩類分類問題的資料，有用的維度有兩個，其餘都是雜訊。此外，我們同時使用了另一個叫做 Logistic Regression 的分類器，於本篇中，各位只需要知道並不是每種分類方式都會受到雜訊維度的影響即可。