k 近邻法 (k-NN) 是一种基于实例的学习方法，无法转化为对参数空间的搜索成绩（参数最优化 成绩）。它的特点是对特征空间停止搜索。除了k近邻法，本章还对以下几个成绩停止较深化的讨 论:
切比雪夫间隔 的计算"近似误差" 与“估计误差" 的含义k-d树搜索算法图解
一、算法
输入：训练集 为实例特征向 为实例的类别,
输入：实例 所属的类
设在给定间隔度量下，涵盖最近k个点的邻域为
其中示性函数 为真为假
寻觅使得函数 获得最大值的变量 也就是说, 看看间隔 最近的k个点外面哪一类别最多，以此作为输入。
二、模型
根据模型的分类, k-NN模型属于非概率模型。
观察 可发现它与感知机不同的之处, 作为决策函数, 它并不需求任何未知参数（感知机需求确定W和b），直接从训练集的数据得到输入。
1. 间隔度量
k-NN的基本思想是，特征空间中的间隔反映了两个点的相似程度, 因此 “间隔" 是作出分类判别 的基本根据。向量空间 的间隔有多种度量方式：
(1) 不同间隔度量
普通方式是闵可夫斯基间隔（ 范数）：
当p=1时, 称为曼哈顿间隔（ 范数）：
当p=2时，称为欧几里得间隔（ 范数），也就是最常用的间隔：:
import mathfrom itertools import combinationsdef L(x, y, p=2): # x1 = [1, 1], x2 = [5,1] if len(x) == len(y) and len(x) > 1: sum = 0 for i in range(len(x)): sum += math.pow(abs(x - y), p) return math.pow(sum, 1 / p) else: return 0
下图表示平面上A、B两点之间不同的间隔：
只允许沿着坐标轴方向行进, 就像曼哈顿街区的出租车走过的间隔两点之间直线最短, 经过勾股定理计算斜边的间隔只剩下一个维度, 即最大的分量方向上的间隔
可见p取值越大，两点之间的间隔越短。
(2) 成绩：为什么切比雪夫间隔
其实这个成绩等价于：为什么 即 空间中的向量 它的切比雪 夫长度等于它的最大分量方向上的长度。
证明: 设
不妨设 即
留意：最大分量的长度独一, 但最大分量能够并不唯 一,设有x^{(1)}, x^{(2)}, \ldots x^{(k)}等个分量的长度都等于\left|x^{(1)}\right|$
当 即 为 时
当 即 为非最大长度分量时
计算 的切比雪夫长度:
由于已知 等于0或1，且有k个分量结果为1, 所以
因此
即 得证。
以上证明参考
(3) 平面上的圆
在平面上的图像:
假如圆形的定义是 “到某一点间隔相等的曲线围成的图形" ，那么在不同的间隔度量下，圆形的形 状可以完全不同。为何 正则化在平面上的等高线为同心正方形, 不就很容易了解吗?
李航教师书中引入了“近似误差”和“估计误差”两个概念，但没有给出详细定义。
这里简单总结一下：
右侧两项分别是 "估计误差" 和 "近似误差"
估计误差：训练集与有限数据集得到的模型的差距近似误差：限制假设空间与有限制假设空间得到的模型的差距 k值越小 单个样本影响越大 模型越复杂 假设空间越大 近似误差越小 (估计误差 越大），容易过拟合;k值越大 单个样本影响越小 模型越简单 假设空间越小 近似误差越大（估计误差 越小），容易欠拟合。
普统统过交叉验证来确定最优的 k 值。
k 近邻的决策规则就是 “多数表决" ，即多数服从多数, 用数学表达式表示为
等号左侧为误分类率，要是误分类率最小，就要使得 最大, 即选择集合 中最多的一类。
三、kd树
kd 树的结构
kd树是一个二叉树结构，它的每一个节点记载了 [特征坐标, 切分轴, 指向左枝的指针, 指向右枝的指针] 。 其中, 特征坐标是线性空间 中的一个点
切分轴由一个整数 表示, 这里 是我们在 维空间中沿第 维停止一次分割。 节点的左枝和右枝分别都是 kd 树, 并且满足：假如 是左枝的一个特征坐标, 那么 并且假如 是右 枝的一个特征坐标，那么
给定一个数据样本集 和切分轴 以下递归算法将构建一个基于该数据集的 kd 树, 每一次循环制造一 个节点:
假如 记录 中独一的一个点为当前节点的特征数据, 并且不设左枝和右枝。 指集合 中元素 . 的数量) 假如假如 将 S 内一切点按照第 个坐标的大小停止排序;选出该陈列后的中位元素 (假如一共有偶数个元素, 则选择中位左边或左边的元素, 左或右并无影响)，作为当前节点的特征坐标, 并且记录切分轴 将 设为在 中一切陈列在中位元素之前的元素; 设为在 中一切陈列在中位元素后的元素;当前节点的左枝设为以 为数据集并且 为切分轴制造出的 树; 当前节点的右枝设为以 为数据集并且 为切分轴制造出 的 kd 树。再设 这里, 我们想轮番沿着每一个维度进 行分割; 是由于一共有 个维度, 在 沿着最后一个维度停止分割之后再重新回到第一个维度。)
构造 kd 树的例子
下面笼统的定义和算法的确是很不好了解，举一个例子会清楚很多。首先随机在 中随机生成 13 个点作为我们的数据集。起始的切分轴 这里 对应 轴, 而 对应 轴。
首先先沿 x 坐标停止切分，我们选出 x 坐标的中位点，获取最根部节点的坐标
并且按照该点的x坐标将空间停止切分，一切 x 坐标小于 6.27 的数据用于构建左枝，x坐标大于 6.27 的点用于构建右枝。
在下一步中对应轴左右两边再按照轴的排序停止切分，中位点记裁于左右枝的节点。得到下面的树，左边的x 是指这该层的节点都是沿 x 轴停止分割的。
空间的切分如下
下一步中 对应 轴, 所以下面再按照 除标停止排序和切分,有
最后每一部分都只剩一个点，将他们记在最底部的节点中。由于不再有未被记录的点，所以不再停止切分。
就此完成了 kd 树的构造。
kd 树上的 kNN 算法
给定一个构建于一个样本生的 kd 树, 下面的算法可以寻觅间隔某个点 最近的 个样本。
设 为一个有 个空位的列表, 用于保存已搜索到的最近点.根据 的坐标值和每个节点的切分向下搜素（也就是选，假如树的节点是按照 停止切分，并且 的 坐标小于 则向左枝停止搜索: 反之则走右枝）。当达到一个底部节点时，将其标记为访问过. 假如 里不足 个点. 则将当前节点的特征坐标加人 如 果 L不为空并且当前节点 的特征与 的间隔小于 里最长的间隔，则用当前特征音换掉 中离 最远的点假如当前节点不是整棵树最顶而节点, 执行 下（1）：反之. 输入 算法完成. （1） . 向上爬一个节点。假如当前 (向上爬之后的) 节点未管被访问过, 将其标记为被访问过, 然后执行 1和2：假如当前节点被访 问过, 再次执行 (1)。 假如此时 里不足 个点, 则将节点特征加入 假如 中已满 个点, 且当前节点与 的间隔小于 里最长的间隔。 则用节点特征豐换掉 中帝最远的点。计算 和当前节点切分綫的间隔。假如该间隔大于等于 中间隔 最远的间隔井且 中已有 个点。则在切分线另一边不会有更近的点, 执行3: 假如该间隔小于 中最远的间隔或者 中不足 个点, 则切分綫另一边能够有更近的点, 因此在当前节点的另一个枝从 末尾执行.
来看下面的例子：
首先执行1，我们按照切分找到最底部节点。首先，我们在顶部末尾
和这个节点的 x轴比较一下，
ppp 的 x 轴更小。因此我们向左枝停止搜索：
这次对比 y 轴，
p 的 y 值更小，因此向左枝停止搜索：
这个节点只要一个子枝，就不需求对比了。由此找到了最底部的节点 (−4.6,−10.55)。
在二维图上是
此时我们执行2。将当前结点标记为访问过, 并记录下 访问过的节点就在二叉树 上显示为被划掉的好了。
然后执行 3，不是最顶端节点。执行 (1)，我爬。下面的是 (−6.88,−5.4)。
执行 1，由于我们记录下的点只要一个，小于k=3，所以也将当前节点记录下，有 L=[(−4.6,−10.55),(−6.88,−5.4)]。再执行 2，由于当前节点的左枝是空的，所以直接跳过，回到步骤3。3看了一眼，好，不是顶部，交给你了，(1)。于是乎 (1) 又往上爬了一节。
1 说，由于还是不够三个点，于是将当前点也记录下，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)。当然，当前结点变为被访问过的。
2又发现，当前节点有其他的分枝，并且经计算得出 p 点和 L 中的三个点的间隔分别是 6.62,5.89,3.10，但是 p 和当前节点的分割线的间隔只要 2.14，小于与 L 的最大间隔：
因此，在分割线的另一端能够有更近的点。于是我们在当前结点的另一个分枝从头执行 1。好，我们在红线这里：
要用 p 和这个节点比较 x 坐标:
p 的x 坐标更大，因此探求右枝 (1.75,12.26)，并且发现右枝曾经是最底部节点，因此启动 2。
经计算，(1.75,12.26)与 p 的间隔是 7.48，要大于 p 与 L 的间隔，因此我们不将其放入记录中。
然后 3 判别出不是顶端节点，呼出 (1)，爬。
1出来一算，这个节点与 p 的间隔是 4.91，要小于 p 与 L 的最大间隔 6.62。
因此，我们用这个新的节点替代 L 中离 p 最远的 (−4.6,−10.55)。
然后 2又来了，我们比对 p 和当前节点的分割线的间隔
这个间隔小于 L 与 p 的最小间隔，因此我们要到当前节点的另一个枝执行 1。当然，那个枝只要一个点，直接到 2。
计算间隔发现这个点离 p 比 L 更远，因此不停止替代。
3发现不是顶点，所以呼出 (1)。我们向上爬，
这个是曾经访问过的了，所以再来（1），
好，（1）再爬，
啊！到顶点了。所以完了吗？当然不，还没轮到 3 呢。如今是 1的回合。
我们停止计算比对发现顶端节点与p的间隔比L还要更远，因此不停止更新。
然后是 2，计算 p 和分割线的间隔发现也是更远。
因此也不需求检查另一个分枝。
然后执行 3，判别当前节点是顶点，因此计算完成！输入间隔 p 最近的三个样本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)].
python
class kdtree(object): # 创建 kdtree # point_list 是一个 list 的 pair，pair[0] 是一 tuple 的特征，pair[1] 是类别 def __init__(self, point_list, depth=0, root=None): if len(point_list)>0: # 轮换按照树深度选择坐标轴 k = len(point_list[0][0]) axis = depth % k # 选中位线，切 point_list.sort(key=lambda x:x[0][axis]) median = len(point_list) // 2 self.axis = axis self.root = root self.size = len(point_list) # 造节点 self.node = point_list[median] # 递归造左枝和右枝 if len(point_list[:median])>0: self.left = kdtree(point_list[:median], depth+1, self) else: self.left = None if len(point_list[median+1:])>0: self.right = kdtree(point_list[median+1:], depth+1, self) else: self.right = None # 记录是按哪个方向切的还有树根 else: return None # 在树上加一点 def insert(self, point): self.size += 1 # 分析是左还是右，递归加在叶子上 if point[0][self.axis]<self.node[0][self.axis]: if self.left!=None: self.left.insert(point) else: self.left = kdtree([point], self.axis+1, self) else: if self.right!=None: self.right.insert(point) else: self.right = kdtree([point], self.axis+1, self) # 输入一点 # 按切分寻觅叶子 def find_leaf(self, point): if self.left==None and self.right==None: return self elif self.left==None: return self.right.find_leaf(point) elif self.right==None: return self.left.find_leaf(point) elif point[self.axis]<self.node[0][self.axis]: return self.left.find_leaf(point) else: return self.right.find_leaf(point) # 查找最近的 k 个点，复杂度 O(DlogN)，D是维度，N是树的大小 # 输入一点、一间隔函数、一k。间隔函数默许是 L_2 def knearest(self, point, k=1, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))): # 往下戳到最底叶 leaf = self.find_leaf(point) # 从叶子网上爬 return leaf.k_down_up(point, k, dist, result=[], stop=self, visited=None) # 从下往上爬函数，stop是到哪里去，visited是从哪里来 def k_down_up(self, point,k, dist, result=[],stop=None, visited=None): # 选最长间隔 if result==[]: max_dist = 0 else: max_dist = max([x[1] for x in result]) other_result=[] # 假如离分界限的间隔小于现有最大间隔，或者数据点不够，就从另一边的树根末尾刨 if (self.left==visited and self.node[0][self.axis]-point[self.axis]<max_dist and self.right!=None)\ or (len(result)<k and self.left==visited and self.right!=None): other_result=self.right.knearest(point,k, dist) if (self.right==visited and point[self.axis]-self.node[0][self.axis]<max_dist and self.left!=None)\ or (len(result)<k and self.right==visited and self.left!=None): other_result=self.left.knearest(point, k, dist) # 刨出来的点放一同，选前 k 个 result.append((self.node, dist(point, self.node[0]))) result = sorted(result+other_result, key=lambda pair: pair[1])[:k] # 到停点就前往结果 if self==stop: return result # 没有就带着现有结果接着往上爬 else: return self.root.k_down_up(point,k, dist, result, stop, self) # 输入 特征、类别、k、间隔函数 # 前往这个点属于该类别的概率 def kNN_prob(self, point, label, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))): nearests = self.knearest(point, k, dist) return float(len([pair for pair in nearests if pair[0][1]==label]))/float(len(nearests)) # 输入 特征、k、间隔函数 # 前往该点概率最大的类别以及相对应的概率 def kNN(self, point, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))): nearests = self.knearest(point, k , dist) statistics = {} for data in nearests: label = data[0][1] if label not in statistics: statistics[label] = 1 else: statistics[label] += 1 max_label = max(statistics.iteritems(), key=operator.itemgetter(1))[0] return max_label, float(statistics[max_label])/float(len(nearests)) |
