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

The concept of k-nearest neighbors (k-NN) classification is quite simple: a data point is said to belong to whichever class its nearest points in space belong to. This method does not require a training process, or you could say that "training" simply means memorizing all the data. At the prediction stage, the distance between the point to be tested and all other data points is calculated, the k nearest points are found, and a vote is taken based on the class or value of these k points to produce the prediction for the point being tested.

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

We use scikit-learn's neighbors.KNeighborsClassifier to run the k-NN algorithm, using the Wine Data Set. This dataset is built into scikit-learn, so you can use it directly by importing the relevant functions, without needing to download it yourself:

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[:, np.newaxis])))

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[:, np.newaxis])))

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

In the example above, since train_test_split is performed randomly, the accuracy may vary slightly each time you run it. In addition, the second half of the example also demonstrates a reference implementation of k-nearest neighbors classification from scratch, where n_neighbors is also set to 1, matching the first half, and the distance metric used is the 2-norm.

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

Below is an explanation of some of the parameters of KNeighborsClassifier. For more details, please refer to the official documentation.

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

When k = 1, the region of influence of each point in K-NN forms a Voronoi Diagram, where each boundary line is the perpendicular bisector between neighboring samples. An example is shown below:

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 演算法的準確度變差，稱為「高維詛咒」。以下範例是在固定只有兩個有效維度的狀況下，依次加入愈來愈多雜訊維度的範例：

The K-NN algorithm treats different dimensions equally, meaning that it assigns the same weight to every feature dimension and does not automatically distinguish which dimensions are discriminative. Therefore, if your data contains many noisy dimensions, the accuracy of the k-NN algorithm is likely to deteriorate, a phenomenon known as the "curse of dimensionality." The example below keeps a fixed number of two informative dimensions, while progressively adding more and more noisy dimensions:

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 的分類器，於本篇中，各位只需要知道並不是每種分類方式都會受到雜訊維度的影響即可。

In the example above, the make_classification function is used to generate sample data. The settings in the example generate data for a two-class classification problem, with two informative dimensions and the rest being noise. In addition, we also used another classifier called Logistic Regression. For this section, you only need to understand that not every classification method is equally affected by noisy dimensions.