k近邻法学习笔记

k近邻法

算法介绍

K近邻算法(KNN,k-nearest,neighbor)给定训练集,对于新输入的实例找到离它最近的k个点,然后根据多数表决原则判断新的实例的类别.

距离的度量有不同的方法,总结起来就是闵氏距离(可见多元分析中的介绍).

为了精确分类,k的取值有讲究,太小会导致整体模型复杂,容易发生过拟合(噪声的影响会突出),如果太多,则会导致误差变大,一般通过交叉验证来取最优的k值.

kd树

对于多个点,如果暴力枚举会导致复杂度太高,kd树能有效降低算法复杂度(特别是点的个数远大于维数的时候).

kd树的构造

• 选择某一个维度$x^{(1)}$为起点构造根节点,以T中所有实例在$x^{(1)}$维度的中位数为切分点,将其分成两个子区域.
• 对于每一个子区域,对于深度为j的节点,取维度$x^{(l)}(l = j(mod)k+1,k是维度)$为根节点,该区域中所有实例中中位数为切分点,分成两个区域.
• 如果子区域为空则停止切分.

kd树的查找

类似平衡二叉树,左子树是小于切分点的点,右子树是大于切分点的点.

kd树的搜索

对于新输入点寻找最近邻

• 按照查找的逻辑向下递归到叶节点,令当前最近点为该节点
• 递归向上回退,对于每一个结点做下列判断
• • 如果该结点比当前最近点离新输入点更近,则该点为当前最近点
• • 若该结点的子节点为当前最近点,检查该结点的另一个子区域是否与以目标点为半径,当前最近点与目标点长度为半径的超球体相交,如果相交则检查另一个子区域是否有更近的点.
• 退回到根节点,算法结束.