对新的输入实例，在训练数据集中找到与该实例最邻近的\(k\)个实例，这\(k\)个实例的多数属于某个类，就把该输入实例分给这个类。
\(k\) 近邻法(\(k\)-nearest neighbor, \(k\)-NN)是一种基本分类与回归方法，这里只讨论分类问题中的\(k\)-NN。
三要素：
- \(k\)值的选择
- 距离度量
- 分类决策规则
\(k\)近邻算法
输入：训练数据集\(T = \{ (x_1,y_1), (x_2,y_2), \cdot \cdot \cdot , (x_N,y_N) \}\)，这里的\(y_i\)是实例的类别；实例特征向量\(x\)；
输出：实例\(x\)所属的类\(y\)。
- 根据给定的距离度量，在训练集中找出与\(x\)最邻近的\(k\)个点，涵盖这\(k\)个点的\(x\)的邻域记作\(N_k(x)\)；
- 在\(N_k(x)\)中根据分类决策规则（如多数表决）决定\(x\)的类别\(y\)：
\[ y = \arg \max_{c_j} \sum_{x_i \in N_k(x)} I \left(y_i = c_j \right), i = 1,2, \cdot \cdot \cdot, K \]
其中，\(I\)为指示函数，等于的时候为1，否则为0。
\(k\)近邻模型
- 模型
每个训练实例附近的cell一起构成了对特征空间的一个划分。 - 距离度量
欧氏距离，或者更一般的闵可夫斯基距离等都可以。 - \(k\)值的选择
\(k\)值的减小意味着整体模型的=变得复杂，容易过拟合。通常采用交叉验证法来选取最优的\(k\)值。 - 分类决策规则
往往使用多数表决，对应于经验风险最小化。
\(k\)近邻法的实现：\(kd\)树
线性扫描(linear scan)算出所有的距离，简单但是耗时。可以使用\(kd\)树这种数据结构来提高效率，它可以表示对\(k\)维空间的一个划分，\(kd\)树的每个节点对应一个\(k\)维超矩形区域。
构造平衡\(kd\)树
- 输入：\(k\)维空间数据集\(T={x_1, x_2,...,x_N}\)
- 输出：\(kd\)树
- 开始：构造根节点
选择\(x^{(1)}\)为坐标轴，以所有实例\(x^{(1)}\)坐标的中位数为切分点，这个超平面将空间切分为两个子区域，落在这个超平面上的实例点保存在根节点。- 重复：一个一个地细分，切分成子区域
依次循环往后选择坐标轴。- 直到子区域没有实例存在时停止
搜索\(kd\)树
- 输入：已构造的\(kd\)树；目标点\(x\)
- 输出：\(x\)的最近邻
- 找到包含\(x\)的叶结点
从根节点出发，向左或向右移动，直到找到叶结点。- 以此叶结点为“当前最近点”
- 递归地向上回退，在每个结点进行以下操作：
- 若该结点更近，则以该点为“当前最近点”
- 检查该结点的另一子结点对应的区域内是否有更近的点：
如果这个区域有可能，也就是另一子节点下边可能存在更近的点：\(rightarrow\)递归进行最近邻搜索。
否则向上回退。- 回退到根结点时结束，最后的“当前最近点”即为\(x\)的最近邻。
(注：本文为读书笔记与总结，侧重算法原理，来源为《统计学习方法》一书第三章)
作者：rubbninja
出处：http://www.cnblogs.com/rubbninja/
关于作者：目前主要研究领域为机器学习与无线定位技术，欢迎讨论与指正！