在这篇文章中，我将实现K最近邻（KNN），这是一种机器学习算法，可用于分类和回归，它属于监督学习算法的范畴。它对标记的数据集进行操作，并预测测试数据的类别（分类）或数值（回归）。

我将使用NumPy实现它，并将使用其他库来实现数据可视化。

import numpy as np
from sklearn.datasets import make_classification

我们首先导入库和函数：

• numpy：它将被用于多维数组的数值计算，因为我们正在处理高维向量。
• make_classification：我们将使用它来创建我们的分类数据集。我们可以决定所需的类和特征的数量，是否要对样本进行聚类等。

def euclidian_distance(a, b):
    return np.sqrt(np.sum((a-b)**2, axis=1))

在KNN算法中，我们需要一个函数来计算训练数据点与我们想要分类的数据之间的距离。在这里，我选择了欧氏距离，因为它在机器学习应用中被广泛使用。可以尝试使用其他距离度量，如曼哈顿距离、Chebychev距离等。

def kneighbors(X_test, return_distance=False):
       
        n_neighbors = 5
        dist = []
        neigh_ind = []
        
        point_dist = [euclidian_distance(x_test, X_train) for x_test in X_test]

        for row in point_dist:
            enum_neigh = enumerate(row)
            sorted_neigh = sorted(enum_neigh, key=lambda x: x[1])[:n_neighbors]
    
            ind_list = [tup[0] for tup in sorted_neigh]
            dist_list = [tup[1] for tup in sorted_neigh]
    
            dist.append(dist_list)
            neigh_ind.append(ind_list)
        
        if return_distance:
            return np.array(dist), np.array(neigh_ind)
        
        return np.array(neigh_ind)

数据点是否接近由上面实现的欧几里得距离函数确定。在这里，数据点之间距离的实际值并不重要，我们感兴趣的是这些距离的顺序。

在训练过程之前，我们选择一个数字作为我们的超参数（k）。因此，例如，当k=5时，我们指的是前5个最近的数据点。

在上面的kneighbors函数中，我们找到测试数据集(我们要分类的数据点)中的每个点与数据集其余部分(即训练数据)之间的距离。我们将这些距离存储在point_dist中，其中每一行对应一个测试数据点到所有训练数据之间的距离列表。我们遍历每一行，对其进行枚举，然后根据距离对它排序。我们枚举每一行的原因是，我们不想丢失用来计算距离的训练数据点的索引，因为我们将在以后引用它们。

sorted_neigh包含测试数据点的前k个最近邻，并且根据其欧氏距离对它们进行排序。然后，我们从sorted_neigh中提取索引和距离值并返回它们。

def predict(X_test, weights='uniform'):
        
        class_num = 3
        
        if weights=='uniform':
            neighbors = kneighbors(X_test)
            y_pred = np.array([np.argmax(np.bincount(y_train[neighbor])) for neighbor in neighbors])
        
            return y_pred 
    
        if weights=='distance':
        
            dist, neigh_ind = kneighbors(X_test, return_distance=True)
        
            inv_dist = 1/dist
            
            mean_inv_dist = inv_dist / np.sum(inv_dist, axis=1)[:, np.newaxis]
            
            proba = []
            
            for i, row in enumerate(mean_inv_dist):
                
                row_pred = self.y_train[neigh_ind[i]]
                
                for k in range(class_num):
                    indices = np.where(row_pred==k)
                    prob_ind = np.sum(row[indices])
                    proba.append(np.array(prob_ind))
        
            predict_proba = np.array(proba).reshape(X_test.shape[0], class_num)
            
            y_pred = np.array([np.argmax(item) for item in predict_proba])
            
            return y_pred

找到k个最近邻后，我们尝试预测我们的测试数据点所属的类。在这里，我们有k个neighbors，每个neighbor在决定类别标签时都有投票权。但是，投票机制可能会根据所选标准而有所不同。在上面的predict函数中，如果权重被选择为一致的，则意味着每个neighbor在决定类别标签时都具有相等的投票权重，而与他们的距离无关。

假设我们的测试数据点有5个最近邻，其中3个属于A类，其中2个属于B类。我们不考虑neighbors之间的距离，因为大部分neighbors都是A类的，所以我们认为测试数据点属于A类。但是，如果选择权重作为距离，那么这意味着neighbors的距离确实很重要。因此，最接近测试数据点的任何neighbor都具有与其距离的倒数成比例的最大权重（投票）。因此，对于前面的例子，如果属于类A的那2个点比其他3个点更接近测试数据点，那么，这个事实本身可能会在决定数据点的类标签时起到很大的作用。

在predict函数中，如果权重是一致的，则很容易预测数据点的标签。首先，我们获得neighbors的索引，然后使用这些索引从训练数据集中获取其相应的类标签。neighbors中的每一行对应于每个测试数据点具有的neighbors集合。然后，我们使用numpy的 bincount函数查找类标签的出现次数，并获取与预测的类标签对应的最大出现次数的索引。

这里，我们找到neighbors距离的均值倒数，并为每个测试数据点计算类概率。

def score(X_test, y_test):
    y_pred = predict(X_test)
        
    return float(sum(y_pred == y_test))/ float(len(y_test))

score函数作为一个非常简单的准确度指标广泛用于分类问题。我们只是返回正确分类标签的百分比。这很简单!

from sklearn.datasets import make_classification
X, y = make_classification(n_samples = 1000, n_features=2, n_redundant=0, n_informative=2,
                             n_clusters_per_class=1, n_classes=3, random_state=21)

mu = np.mean(X, 0)
sigma = np.std(X, 0)

X = (X - mu ) / sigma

我们利用sklearn.dataset的make_classification函数填充数据集。然后，我们通过减去平均值然后除以标准差来对每个数据点进行归一化。

data = np.hstack((X, y[:, np.newaxis]))
        
np.random.shuffle(data)

split_rate = 0.7

train, test = np.split(data, [int(split_rate*(data.shape[0]))])

X_train = train[:,:-1]
y_train = train[:, -1]

X_test = test[:,:-1]
y_test = test[:, -1]

y_train = y_train.astype(int)
y_test = y_test.astype(int)

创建数据集后，我们在训练阶段实现了随机拆分，从而获得了训练和测试集。

kneighbors(X_test)

现在该测试我们的knn实现了。

predict(X_test)

正如预期的那样，predict函数输出测试数据的预测类标签。

score(X_test, y_test)
#0.99

看起来我们的实现做得还可以，因为它的精确度很高。

K最近邻的类实现

import numpy as np

class KNearestNeighbors():
    def __init__(self, X_train, y_train, n_neighbors=5, weights='uniform'):

        self.X_train = X_train
        self.y_train = y_train

        self.n_neighbors = n_neighbors
        self.weights = weights

        self.n_classes = 3

    def euclidian_distance(self, a, b):
        return np.sqrt(np.sum((a - b)**2, axis=1))

    def kneighbors(self, X_test, return_distance=False):

        dist = []
        neigh_ind = []

        point_dist = [self.euclidian_distance(x_test, self.X_train) for x_test in X_test]

        for row in point_dist:
            enum_neigh = enumerate(row)
            sorted_neigh = sorted(enum_neigh,
                                  key=lambda x: x[1])[:self.n_neighbors]

            ind_list = [tup[0] for tup in sorted_neigh]
            dist_list = [tup[1] for tup in sorted_neigh]

            dist.append(dist_list)
            neigh_ind.append(ind_list)

        if return_distance:
            return np.array(dist), np.array(neigh_ind)

        return np.array(neigh_ind)

    def predict(self, X_test):

        if self.weights == 'uniform':
            neighbors = self.kneighbors(X_test)
            y_pred = np.array([
                np.argmax(np.bincount(self.y_train[neighbor]))
                for neighbor in neighbors
            ])

            return y_pred

        if self.weights == 'distance':

            dist, neigh_ind = self.kneighbors(X_test, return_distance=True)

            inv_dist = 1 / dist

            mean_inv_dist = inv_dist / np.sum(inv_dist, axis=1)[:, np.newaxis]

            proba = []

            for i, row in enumerate(mean_inv_dist):

                row_pred = self.y_train[neigh_ind[i]]

                for k in range(self.n_classes):
                    indices = np.where(row_pred == k)
                    prob_ind = np.sum(row[indices])
                    proba.append(np.array(prob_ind))

            predict_proba = np.array(proba).reshape(X_test.shape[0],
                                                    self.n_classes)

            y_pred = np.array([np.argmax(item) for item in predict_proba])

            return y_pred

    def score(self, X_test, y_test):
        y_pred = self.predict(X_test)

        return float(sum(y_pred == y_test)) / float(len(y_test))

在实现所有必要的函数之后，很容易创建knn的类实现。这里只有新添加的_init__函数。

将我们的实现与Sklearn的KNeighborsClassifier进行比较

from sklearn.datasets import load_iris
from KNearestNeighbors import KNearestNeighbors
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import pandas as pd


dataset = load_iris()

X = dataset.data
y = dataset.target

mu = np.mean(X, 0)
sigma = np.std(X, 0)
X = (X - mu ) / sigma

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

our_classifier = KNearestNeighbors(X_train, y_train, n_neighbors=3)
sklearn_classifier = KNeighborsClassifier(n_neighbors=3).fit(X_train, y_train)

our_accuracy = our_classifier.score(X_test, y_test)
sklearn_accuracy = sklearn_classifier.score(X_test, y_test)

pd.DataFrame([[our_accuracy, sklearn_accuracy]],
             ['Accuracy'],    
             ['Our Implementation', 'Sklearn\'s Implementation'])

我们自己的实现和sklearn的实现的准确性看起来是基本相同的。