KNN原理及Python代码实现（超详细版）

一、原理

1. 概述

K近邻法（k-nearest neighbors,KNN）是一种有监督的学习算法，也是机器学习中最简单、且不那么依靠各类假设的算法（基本上所有算法都会有假设的前提条件，在数据分布符合算法的假设条件时，其效果往往会更好）。

1.1 核心思想
物以类聚，人以群分。俗话说，“看一个男人好不好，就看他身边的朋友绝对没错”，对我们要学习和预测的样本来说，道理也是一样的。我们要判断一个样本属于什么类别，可以通过围在他身边的样本来判断，在特征空间内与这个样本距离最近的 k 个样本应该与待预测样本是一伙的，所以如果这 k 个样本大多属于类别A，那么认为待预测样本也属于类别A。

1.2 用途
KNN可以用于分类（二分类多分类都可以，且算法不需要作修改），也可以用于回归，用于分类还是回归主要在于算法输出结果的计算方式，分类问题多是通过对待预测样本附近的k个样本对所属类别进行投票，根据投票结果来决定待分类样本的类别，即多数表决法（少数服从多数）；回归问题是对待预测样本最近的k个样本的输出进行平均，均值作为待预测样本的输出，即平均法。

1.3 KNN优缺点
优点：

• 对数据的分布没有假设，可以适用于各种分布形式的数据集，不过一般来说密集一些的数据更好，太稀疏的数据更难控制 k 的取值，易被误导；
• 算法思想简单，容易理解和实现，而且可以分类也可以回归；

缺点：

• KNN基本没有根据数据训练和学习的过程，每次分类都要跑一次整个分类过程，速度慢；
• 对样本不均衡情况比较敏感，容易被样本量大的类别干扰（可以考虑使用距离来加权，增大距离最近的数据的影响）；
• 暴力实现计算量大，KD树等实现耗内存。

2. 算法流程及实现

2.1 KNN算法流程（以KNN分类算法为例）

输入：训练集，其中为样本的特征向量，为样本的类别
输出：样本 x 所属的类别 y
（1）选定距离度量方法，在训练集T中找出与待预测样本 x 最接近的 k个样本点，包含这 k个点的 x 的邻域记作；
（2）在中根据分类决策规则（如多数表决法）来决定 x 所属的类别 y。

由上述KNN算法流程可以发现，在运算中存在四个需要关注的重点：

• 距离度量方式的选择；
• k值的选取；
• 怎样找出这k个近邻的样本点；
• 分类决策规则的选择。

其中度量方式、k值、分类决策规则称为KNN算法的三要素，会影响算法的效果，非常重要；而怎样找出这k个近邻的样本点则直接决定了KNN算法的实现后的具体计算过程，影响算法的复杂度。接下来就详细分析这四个要点：

（1）距离度量方式：一般来说距离度量方式主要包括欧式距离、曼哈顿距离、闵可夫斯基距离，欧式距离是我们比较常用的，这是比较基础的内容，本文不再赘述。

（2）k值的选取：k值的选取没有很好的办法，一般才用交叉验证来选择合适的k值，比如使用gridsearchcv工具。k值的选择会对预测的结果造成比较大的影响，k值越小，模型越复杂（k越大模型越简单，比如k＝n，所有待预测样本都被划分为同一类了，模型就很简单），这时模型的偏差bias减小，方差variance增大，模型容易过拟合，所以对k值的选取要慎重。

（3）分类决策规则的选择，分类问题大多才用多数表决法。

（4）怎样找出这k个近邻的样本点，常用的方法有三种：

a. 暴力实现，即直接遍历得到训练集中所有样本点与预测点的距离，然后排序取前k个最近邻点，所以其计算的时间复杂度为O(n)；

b. KD树，使用暴力实现没有利用到数据本身蕴含的结构信息，在样本量较大时效率太低，计算复杂度高，在实际工程应用中，对成百上千个特征几百万的样本量计算比较困难，因此可以通过索引树，对搜索空间进行层次划分，以此来优化计算，其时间复杂度为O(logn)，详细内容在后面会讲到；

c. 球数，球树和KD树类似，但不会像KD树一样做一些多余的计算，主要区别在于KD树得到的是节点样本组成的超矩形体，而球树得到的是节点样本组成的最小超球体，这个超球体要比对应的KD树的超矩形体小，这样在做最近邻搜索的时候，可以避免一些无谓的搜索。

接下来，对基于KD树实现的 KNN 进行详述，为什么写KD树不写球树呢？一是两者差不多，二是KD树看起来跟凯文杜兰特好像有什么莫名其妙的联系。

2.2 KD树

KD树（K-dimension tree），即K个特征维度的树，这个树的功能就是可以帮我们快速找到跟目标点相近的数据点，想想这个功能，是不是很像我们玩的猜数字的游戏，一个人偷偷想一个数字（目标数据点），其他人不停的猜数字缩小范围，这不就跟我们为目标点找最相近的 k 个点是一样一样的吗？

所以，再想想我们玩猜数字常用的套路：二分法，这也是KD树的核心思想：分而治之。因此，KD树是一个二叉树，他的每个节点会将所有的数字点在某个维度上一分为二，设想一下，如果数据空间在各个维度上被我们划分成了很多个小的part，那么我们要确定一个新的数据点相近的点，只要找到这个点所在的part不就八九不离十了。

不过这个树应该在哪个维度上、怎么分呢？当然是选择能把数字分的最开的维度来开刀（比如使用方差大的，数据方差大说明沿该坐标轴方向上数据点分散的比较开，这个方向上，进行数据分割可以获得最好的分辨率）。这是不是跟决策树的思路很像？当然，决策树是可以直接用于分类的，特征选择更为复杂（比如用信息增益比），而且每个特征只会用到一次，并且并不要求特征是数值类型的，不过其基本思想还是很像的，好了不说决策树了，来看看怎么实现一个KD树。

2.2.1 KD树的构建

先举个常见的简单例子：假设有六个二维数据点，数据点位于二维空间中。根据上面的介绍，我们需要根据这些数据点把数据空间划分成很多个小的part。事实上，六个二维数据点生成的Kd-树的图，即划分结果为：

这是怎么做到的呢？

• 找到划分的特征( split )。6个数据点在 x，y 维度上的数据方差分别为6.97，5.37，所以在x轴上方差更大，用第1维特征建树；
• 确定划分点（7,2）( Node-Data )。根据 x 维上的值将数据排序，6个数据的中值(所谓中值，即中间大小的值)为6，所以划分点的数据是（7,2）（选（5,4）也可以）。这样，该节点的分割超平面就是通过（7,2）并垂直于：划分点维度的直线 x=7；
• 确定左子空间 ( left ) 和右子空间 ( right )。分割超平面 x=7 将整个空间分为两部分：x<=7 的部分为左子空间，包含3个节点 {(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点={(9,6)，(8,1)}；
• 迭代。用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6)，(8,1)}。

我们可以看出，如下图：点 (7,2) 为根结点，(5,4) 和 (9,6) 则为根结点的左右子结点，而 (2,3)，(4,7) 则为 (5,4) 的左右子，最后，(8,1) 为 (9,6) 的左子。如此，便形成了这样一棵k-d树。

从以上过程和结果的描述，我们可以总结出KD树的基本数据结构和构建流程：
k-d树的数据结构：

Kd-tree构建流程的伪代码：

输入：数据点集DataSet，和其所在的空间
输出：Kd，类型为Kd-tree

1 if DataSet is null , return null；
2 else 调用Node-Data生成程序：
 a 计算 Split。对于所有数据（高维向量），统计他们在每个维度上的方差，方差最大值所对应的维度就是 Split 域的值；
 b 计算 Node-Data。数据点集 DataSet 按照第 split 维的值排序，最靠近中位数的那个数据点被选为 Node-Data；
3 dataleft = { d 属于 DataSet & d[:split] <= Node-data[:split] }；
 Left-Range = { Range && dataleft }；
 dataright = {d 属于 DataSet & d[:split] > Node-data[:split] }；
 Right-Range = { Range && dataright }；
4 left = 由（dataleft, Left-Range）建立的Kd-tree；
 设置 left 为 KD树的Left；
 right =由（dataright,Right-Range）建立的Kd-tree；
 设置 right 为KD树的Right；
5 在left 和 right 上重复上面的过程，直到数据全部分完。

根据以上伪代码就可以写出构建KD树的程序，Python实现如下：

Kd-tree构建流程的Python代码：

class KDNode(object):
    def __init__(self, node_data, split, left, right):
        self.node_data = node_data
        self.split = split
        self.left = left
        self.right = right


class KDTree(object):
    def __init__(self, dataset):
        self.dim = len(dataset[0]) 
        self.tree = self.generate_kdtree(dataset)

    def generate_kdtree(self, dataset):
        '''
        递归生成一棵树
        '''
        if not dataset:
            return None
        else:
            split, data_node = self.cal_node_data(dataset)
            left = [d for d in dataset if d[split] < data_node[split]]
            right = [d for d in dataset if d[split] > data_node[split]]
            return KDNode(data_node, split, self.generate_kdtree(left), self.generate_kdtree(right))

    def cal_node_data(self, dataset):
        std_lst = []  # 用标准差代替方差，都一样
        for i in range(self.dim):
            std_i = np.std([d[i] for d in dataset])
            std_lst.append(std_i)
        split = std_lst.index(max(std_lst))
        dataset.sort(key=lambda x: x[split])
        indx=int((len(dataset) + 2) / 2)-1
        data_node = dataset[indx]
        return split, data_node

2.2.2 使用KD树得到 k 近邻

（1）使用KD树得到最近邻

1）顺着二叉树搜索，直到找到叶子节点中的最近邻节点，这个过程会确定一条搜索路经；
2）因为二叉树每次划分数据空间都是以某一个特征为标准进行的，所以综合考虑所有特征，根据二叉树搜索到的子节点不一定是最近邻的，不过最近邻点肯定位于以查询点为圆心且通过叶子节点的圆域内（不然就会比这个叶子节点离得远了），所以根据搜索路径进行回溯操作，找到最近邻点。

举两个例子，在之前建立的Kd树中搜索（3, 4.5）的最近邻点：

• 二叉树搜索查找（3, 4.5），得到搜索路经 <(7,2) - (5,4) - (4,7)>；
• 首先以（4,7）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为2.69；
• 然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（3, 4.5）为圆心，以2.69为半径画圆，如下图所示。发现该圆和超平面y = 4交割，因此计算（5,4）与（3, 4.5）的距离为2.06，小于2.69，更新最近邻为（5,4），更新距离为2.06，画一个绿色的圆；
• 因为画的圆进入到了（5,4）分割的另一部分区域，所以需要在这个区域查找。发现（2,3）结点与目标点距离为1.8，比（5,4）更近，更新最近邻为（2，3），以（3, 4.5）为圆心画一个蓝色的圆。
• 再回溯到（7,2），蓝色的圆与x = 7超平面不相交，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为1.8。

这是找到最近邻的过程，只找到了最近的一个点，那么怎么找 k 近邻个点呢？

（2）使用KD树得到 k 近邻

李航老师在《统计学习方法》中只提了一句，按上面的思路就能找到 k 近邻，我们就改造一下上面的思路：上面是找1个，现在要找k个，所以我们可以维护一个长度为k的有序数据集合，在搜索过程中发现更小的距离，就替换掉集合里的最大值，这样搜索结束后就得到了 k 近邻，有序数据集合我们用优先队列来实现似乎非常的合理，ok，下面来试试看：

class NodeDis(object):
    '''
    自定义将节点与其和目标距离绑定的类，并自定义根据距离比较对象的大小，因为要从大的开始pop，所以self.distance > other.distance
    '''

    def __init__(self, node, dis):
        self.node = node
        self.distance = dis

    def __lt__(self, other):
        return self.distance > other.distance


def search_k_neighbour(kdtree, target, k):
    k_queue = PriorityQueue()
    return search_path(kdtree, target, k, k_queue)


def search_path(kdtree, target, k, k_queue):
    '''
    递归找到整个树中的k近邻
    '''
    if kdtree is None:
        return NodeDis([], np.inf)
    path = []
    while kdtree:
        if target[kdtree.split] <= kdtree.node_data[kdtree.split]:
            path.append((kdtree.node_data, kdtree.split, kdtree.right))
            kdtree = kdtree.left
        else:
            path.append((kdtree.node_data, kdtree.split, kdtree.left))
            kdtree = kdtree.right
    path.reverse()
    radius = np.inf
    for i in path:
        node_data = i[0]
        split = i[1]
        opposite_tree = i[2]
        # 先判断圈定的区域与分割轴是否相交
        distance_axis = abs(node_data[split] - target[split])
        if distance_axis > radius:
            break
        else:
            distance = cal_Euclidean_dis(node_data, target)
            k_queue.put(NodeDis(node_data, distance))
            if k_queue.qsize() > k:
                k_queue.get()
                radius = k_queue.queue[-1].distance
            # print(radius,[i.distance for i in k_queue.queue])
            search_path(opposite_tree, target, k, k_queue)
    return k_queue


def cal_Euclidean_dis(point1, point2):
    return np.sqrt(np.sum((np.array(point1) - np.array(point2)) ** 2))

对例子中的数据进行测试，输出（3, 4.5）的3个近邻点结果如下图：

KD树搜索k近邻结果

2.3 基于暴力搜索与KD树的KNN分类

根据暴力搜索和上一节中使用KD树得到k近邻的方法，我们来实现一个KNN分类器：

KNN的python实现

import numpy as np
from collections import Counter
import kd_tree  # 上一节实现的KD树

class KNNClassfier(object):

    def __init__(self, k, distance='Euclidean',kdtree=True):
        '''
        初始化确定距离度量方式和k、是否使用KD树
        '''
        self.distance = distance
        self.k = k
        self.kdtree=kdtree

    def get_k_neighb(self, new_point, train_data, labels):
        '''
        暴力搜索得到k近邻的k个label
        '''
        distance_lst = [(self.cal_Euclidean_dis(new_point, point), label) for point, label in zip(train_data, labels)]
        distance_lst.sort(key=lambda x: x[0], reverse=False)
        k_labels = [i[1] for i in distance_lst[:self.k]]
        return k_labels

    def fit(self, train_data):
        '''
        使用KD树的话，可以事先将树训练好，好像有了点学习的过程一样，要提高效率的话可以将构建好的树保存起来
        '''
        kdtree = kd_tree.KDTree(train_data)
        return kdtree

    def get_k_neighb_kdtree(self, new_point, train_data, labels, kdtree):
        '''
        通过KD树搜索得到k近邻的k个label
        '''
        result = kd_tree.search_k_neighbour(kdtree.tree, new_point, self.k)
        data_dict={data:label for data,label in zip(train_data, labels)}
        k_labels=[data_dict[data.node] for data in result.queue]
        return k_labels

    def predict(self, new_point, train_data, labels,kdtree):
        if self.kdtree:
            k_labels = self.get_k_neighb_kdtree(new_point, train_data, labels,kdtree)
        else:
            k_labels = self.get_k_neighb(new_point, train_data, labels)
        # print(k_labels)
        return self.decision_rule(k_labels)

    def decision_rule(self, k_labels):
        '''
        分类决策规则：投票
        '''
        label_count = Counter(k_labels)
        new_label = None
        max = 0
        for label, count in label_count.items():
            if count > max:
                new_label = label
                max = count
        return new_label

    def cal_Euclidean_dis(self, point1, point2):
        return np.sqrt(np.sum((np.array(point1) - np.array(point2)) ** 2))

分类结果如下，两种方式实现的KNN的结果是一样的（图中的两个正方形点为待分类点）：

暴力搜索和KD树实现的KNN测试结果