1 概述

邻近算法（k-Nearest Neighbors）：在特征空间中，如果一个样本附近的个最近(即特征空间中最邻近)样本的大多数属于某一个类别，则该样本也属于这个类别。

2 算法

2.1 k近邻算法

算法2.1（k近邻算法）
输入：训练数据集

其中，为实例的特征向量，为实例的类别，；实例特征向量；
输出：实例属于的类。
（1）根据给定的距离度量，在训练集中找出与最邻近的个点，涵盖这个点的的领域基座；
（2）在中根据分类决策规则（如多数表决）决定的类别：
(2.1)
式（1.1）中，为只是函数，即当时I为1，否则为0
近邻法的特殊情况是的情形，称为最近邻算法。对于输入的实例点（特征向量），最近邻法将训练数据集中与最近邻的类作为的类。
近邻法没有显式的学习过程。

2.2 k近邻模型

近邻法使用的模型实际上对应于特征空间的划分。模型由三个基本要素——距离度量、值的选择和分类决策规则决定。

模型

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。近邻模型的特征空间一般是维实数向量空间。使用的距离是欧氏距离，但也可以是其他距离，如更一般的距离（ distance）或Minkowski距离（Minkowski distacne）。
设特征空间是n维实数向量空间,，的距离定义为
(2.1)
这里。当时，称为欧式距离（Euclidean distance），即
(2.2)
当时，成为曼哈顿距离（Manhattan distance），即
(2.3)
当时，它是各个坐标距离的最大值，即
(2.4)

k值的选择

值的选择会对近邻法的结果产生重要影响。

• 值的减少就意味着整体模型变得复杂，容易过拟合
• 值的增大就意味着整体的模型变得简单
• 如果时，模型过于简单，完全忽略训练实例中的大量有用信息，实不可取的

在应用中，值一般取一个比较小的数值，通常采用交叉验证法来选取最优的值。

分类决策规则

近邻法中的分类决策规则往往是多数表决，即由输入实例的个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则（majority voting rule）有如下解释：如果分类的损失函数为0-1损失函数，分类函数为

那么误分类的概率是

对给定的实例，其最邻近的个训练实例点沟通集合。如果涵盖的区域的类别是，那么误分类率是

要使误分类率最小即经验风险最小，就要使最大，所以多数表决规则等价于经验风险最小化。

3 实现

3.1 一般实现（基于sklearn）

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 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_predict 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 __repr__(self):
        return "KNN(k=%d)" % self.k
import numpy as np
from sklearn import datasets
iris = datasets.load_iris()
X = iris.data
y = iris.target
# 数据拆分成训练集和验证集合
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target)
# 数据归一化
from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()
standardScaler.fit(X_train)
X_train_standard = standardScaler.transform(X_train)
X_test_standard = standardScaler.transform(X_test)
# 训练
knn_clf = KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train_standard, y_train)
# 预测准确率
knn_clf.score(X_test_standard, y_test)

3.2 构造kd树实现

3.3 搜索kd树实现

4 实践

4.1 一般使用流程

（1）收集数据：可以使用任何方法
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式
（3）分析数据：可以使用任何方法
（4）训练算法：此步骤不适合k-邻近算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-临近算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

4.2 超参数和模型参数

• kNN算法没有模型参数
• kNN算法中的k是典型的超参数

  4.3 基于scikit-learn的使用

  5 问题集合

  1. 参照图1（待补上），在二维空间中给出实例点，画出为1和2的近邻构成的空间划分，并对其进行比较，体会值选择与模型复杂度及预测准确率的关系。
  2. 利用例题2（待补上）构造的树求的最紧邻点。
  3. 参照算法3（待补上），写出输出为的近邻的算法。

  6 继续阅读

  详见《统计机器学习》第二版参考文献

CHANGELOG

2020年12月14日20:42:31
第一版更新，结合《统计机器学习》和《机器学习实战》