K近邻算法的原理及实现

前言

在学习并实现完了之前的感知机算法，感觉它是比较简单的，并且只能进行处理线性分类问题。

本章节学习了K近邻算法（k-nearest neighbor,k-NN），它是一种基本分类与回归方法，在这一章节中，不介绍它在回归问题中的应用，仅仅介绍其在分类问题中的应用。K近邻算法的输入为实例的特征向量，对应于特征空间的点，输出为实例的类别。

k近邻算法

通俗的说：给定一个数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类（多数表决投票）。

输入：训练数据集$T=\{(x_1,y_1),(x_1,y_2),…,(x_N,y_N)\}$其中，$x_i\in \mathcal{X}\subseteq R^n$为实例的特征向量，$y_i\in \mathcal{Y}={c_1,c_2,…,c_k}$为实例的类别，$i=1,2,…,N$；实例特征向量$x$；
输出：在$N_k(x)$中根据分类决策规则（如多数表决）决定$x$的类别$y$:

$$y=\mathop{\arg\max}_{c_j} \sum_{x_i\in N_k (x)} I(y_i=c_j),i=1,2,…,N;j=1,2,…,K$$
I为指示函数，即当$y_i=c_i$时I为1，否则I为0.

当k近邻法的k=1时，就是特殊情形，也就是最近邻算法，对于输入的实例点（特征向量）$x$，最近邻法将训练数据集中与$x$最邻近点的类作为$x$的类。k近邻算法没有显式的学习过程。

距离度量

如《统计学习方法》概论总结中所说，距离的度量方法有很多，特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是$n$维实数向量空间$R^n$。使用的距离是欧氏距离，但也可以是其他距离，如更一般的$L_p$距离或Minkowski距离。这里就不再赘述了。

k值的选择

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

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有于输入实例相近的训练实例才会对预测结果起作用。但是缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的k值，就相当于用较大领域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单。

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

分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数为$$f:R^n \to \{c_1,c_2,…,c_k\}$$
那么误分类的概率是
$$P(Y\ne f(X))=1-P(Y=f(X))$$
对给定的实例$x\in X$，其最近邻的k个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是
$$\frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i \ne c_j)=1- \frac{1}{k} \sum_{x_i\in N_(x)} I(y_i=c_j)$$
要使误分类绿最小即经验风险最小，就要使$\sum_{x_i\in N_k(x)} I(y_i=c_j)$最大，所以多数表决规则等于经验风险最小化。

KNN的实现

code

import numpy as np
# 仅使用sklearn中的iris数据集，以及归一化、数据拆分函数
from sklearn.datasets import load_iris
from sklearn import preprocessing
from sklearn.model_selection import train_test_split

np.random.seed(33)

def getIrisData():

    data=load_iris()
    X=np.array(data.data)
    Y=np.array(data.target)

    # X数据归一化处理
    min_max_scaler = preprocessing.MinMaxScaler()
    X = min_max_scaler.fit_transform(X)

    # 数据拆分，测试数据占比0.3
    X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size = 0.2, random_state = 33)
    return X_train, X_test, y_train, y_test

class cell():
    def __init__(self,x,y):
        self.x=x
        self.y=y

class KNN():
    # k值设定，可以根据需要更改
    def __init__(self,k=11):
        self.k=k

    # 向当前knn模型中注入原始数据
    def train(self,X,Y):
        self.size=len(X[0])
        self.cells=[]
        for i in range(len(Y)):
            self.cells.append(cell(X[i],Y[i]))
        # print(self.cells)

    # 使用模型进行预测
    def predict(self,x):
        # 创建投票列表
        Nk=sorted(self.cells,key=lambda cell:np.linalg.norm(cell.x-x))[:self.k] #使用的np.linalg.norm函数在默认情况下求解的为范数为2的范式
        # 多数表决投票
        ans=np.zeros(4,float)
        for i in Nk:
            ans[i.y]+=1

        # print("*" * 10, "置信度", "*" * 10)
        ans=ans/self.k
        # print(ans)
        return ans.argmax(),ans

if __name__ == '__main__':

    X_train, X_test, y_train, y_test=getIrisData()
    knn=KNN()
    knn.train(X_train,y_train)
    print("*" * 10, "预测", "*" * 10)
    t_num=0
    for i in range(len(y_test)):
        p_y,ans=knn.predict(X_test[i])
        if p_y==y_test[i]:
            t_num+=1
        print("各参数:",X_test[i],"真实类:",y_test[i],"预测类:",p_y,"是否正确:",p_y==y_test[i],"置信度:",ans)
    print("*" * 10, "结果", "*" * 10)
    print("iris数据集中，交叉验证正确率：{:2f}".format(t_num/len(y_test)))

结果

kd树寻找最邻近算法

构造算法

构造平衡kd树算法：
输入：k维空间数据集$T=\{x_1,x_2,…,x_N\}$，
其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T$,$i=1,2,…,N;$
输出：kd树
（1）开始：构造根节点，根节点对应于包括T的k维空间的超矩形区域。
选择$x^{(1)}$为坐标轴，以T中所有实例$x^{(1)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。
由根结点生成深度为1的左、右子结点：左子结点对应坐标$x^{(1)}$小与切分点的子区域，右子结点对于坐标$x^{(1)}$大于切分点的子区域。
将落在切分超平面上的实例点保存在根结点。
（2）重复：对深度为j的结点，选择$x^{(l)}$为切分的坐标轴，$l=j(mod k)+1$，以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现。
由该结点生成深度为$j+1$的左、右子结点：左子结点对应坐标$x^{(l)}$小与切分点的子区域，右子结点对应坐标$x^{(l)}$大于切分点的子区域。
将落在切分超平面上的实例点保存在该结点。
（3）直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

搜索算法

用kd树的最邻近搜索：

输入：已够早的kd树：目标点x
输出：x的最近邻
(1)在kd树种找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树，若目标点x当前维的坐标小与切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
(2)以此叶结点为“当前最近点”
(3)递归地向上回退，在每个结点进行以下操作：

(a)如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”
(b)当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点。移动到另一个子结点，接着，递归地进行最邻近搜索。如果不相交，向上回退。

(4)当回退到根结点时，搜索结束，最后的“当前最近点”即为x的最邻近点。

kd树查找最近邻的实现

code

# 构造kd树，P41

import numpy as np
class KDnode():
    def __init__(self,dome_point,split_num,left,right):
        self.dome_point=dome_point  #此次样本点
        self.split_num=split_num    #切割的维度号
        self.left=left              #左子树
        self.right=right            #右子树

class KDtree():
    def __init__(self,data):
        k=len(data[0])              #k维度
        def CreateNode(split_num,data_set):
            if not data_set :       #data_set为空返回空
                return None
            data_set.sort(key=lambda x : x[split_num])  #按照我们想要切割的维度号进行排序
            split_pos=len(data_set)//2                  #从中间将其分割开，获得中位点标号
            middle_pos=data_set[split_pos]              #找到中位点
            split_next=(split_num+1)%k                  #下一个需要分割的维度

            return KDnode(middle_pos,split_num,
                          CreateNode(split_next,data_set[:split_pos]),
                          CreateNode(split_next,data_set[split_pos+1:]))

        self.root=CreateNode(0,data)    #创造树

# 寻找最近点，参考学习了https://www.cnblogs.com/21207-iHome/p/6084670.html
def search(tree, point):
    k = len(point)  # 数据维度

    def travel(kd_node, target, max_dist):
        if kd_node is None:
            return [0] * k, float("inf"), 0  # python中用float("inf")和float("-inf")表示正负无穷
                                            # return的参数分别是最近坐标点、最近距离和访问过的节点数

        nodes_visited = 1

        s = kd_node.split_num  # 进行分割的维度
        pivot = kd_node.dome_point  # 进行分割的“轴”

        if target[s] <= pivot[s]:  # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)
            nearer_node = kd_node.left  # 下一个访问节点为左子树根节点
            further_node = kd_node.right  # 同时记录下右子树
        else:  # 目标离右子树更近
            nearer_node = kd_node.right  # 下一个访问节点为右子树根节点
            further_node = kd_node.left

        temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域

        nearest = temp1[0]  # 以此叶结点作为“当前最近点”
        dist = temp1[1]  # 更新最近距离

        nodes_visited += temp1[2]

        if dist < max_dist:
            max_dist = dist  # 最近点将在以目标点为球心，max_dist为半径的超球体内

        temp_dist = abs(pivot[s] - target[s])  # 第s维上目标点与分割超平面的距离
        if max_dist < temp_dist:  # 判断超球体是否与超平面相交
            return nearest, dist, nodes_visited  # 不相交则可以直接返回，不用继续判断

        # ----------------------------------------------------------------------
        # 计算目标点与分割点的欧氏距离
        temp_dist=np.linalg.norm((np.array(pivot)-np.array(target)))

        if temp_dist < dist:  # 如果“更近”
            nearest = pivot  # 更新最近点
            dist = temp_dist  # 更新最近距离
            max_dist = dist  # 更新超球体半径

        # 检查另一个子结点对应的区域是否有更近的点
        temp2 = travel(further_node, target, max_dist)

        nodes_visited += temp2[2]
        if temp2[1] < dist:  # 如果另一个子结点内存在更近距离
            nearest = temp2[0]  # 更新最近点
            dist = temp2[1]  # 更新最近距离

        return nearest, dist, nodes_visited

    return travel(tree.root, point, float("inf"))  # 从根节点开始递归

#先left后right，前序遍历
def preorder(root):
    print(root.dome_point)
    if root.left:
        preorder(root.left)
    if root.right:
        preorder(root.right)

if __name__ == '__main__':
    data=[[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]     #书上P42例子
    print("*"*10,"data","*"*10)
    print(data)
    kd=KDtree(data)
    print("*"*10,"先序遍历","*"*10)
    preorder(kd.root)
    print("*"*10,"search","*"*10)
    print(search(kd,[5,6]))

结果