K 近邻¶
约 732 个字 预计阅读时间 2 分钟
问题及算法描述¶
给定数据集\(\{(x_i，y_i)\}\)， 其中\(x \in \mathbb{R}^n\)，\(y_i \in \{ c_1，c_2，....c_k\}\)， 一共有 K 种类别，现在给出一个新的数据点\(x\)，求出它的类别\(y\). 算法思想：
- 找出离 x 最近的 K 个邻居\(N_{k}(x)\)
- 由着 K 个邻居进行多数表决：
\[
y =\underset{c_j}{\operatorname{arg max}} \sum_{N_{k}(x)} I(y = c_j)
\]
其中的\(I(y = c_j)\)是指示函数，当\(y = c_j\)时，\(I(y = c_j) = 1\)，否则\(I(y = c_j) = 0\).
K 近邻的三要素¶
有了上述的算法框架后，K 近邻算法由三个要素决定：
一般来说我们使用\(L_p\)距离，即：
\[
L_p(x_i，x_j) = (\sum_{l=1}^{n}|x_i^{(l)} - x_j^{(l)}|^p)^{\frac{1}{p}}
\]
当 p 的取值为 2 时，就是欧氏距离
当 K 比较小的时候，模型比较复杂，容易过拟合； 当 K 比较大的时候，模型比较简单，容易欠拟合。 一般来说 K 值都不会选的太大。
一般使用多数表决规则，在此情景下多数表决规则等效于经验风险最小化。
用 kd 树切分空间求解 K 近邻¶
kd 树的构造¶
- 输入： \(\{(x_i，y_i)\}\)
- 开始： 取变量\(x\)的第一个维度\(x_i^(1)\)，第一个纬度的中位数\(x_j^(1)\)，将数据集分为两部分，左子树和右子树，而\(x_j^(1)\)就是根节点，左右子节点的深度为 1
- 重复： 对左右子树继续进行分割，对于 j 深度的子树，取\(x\)的第\(j+1\)维度\(x_i^(j+1)\)进行分割
- 结束： 直到左右空间都不再有子节点
课件上的例子
搜索 kd 树寻找 K 近邻¶
- 输入： kd 树，目标点\(x\)（注意此处的 x 一般而言不是数据集中的点）
- 开始： 从根节点开始，递归的向下访问 kd 树，在每个节点把对应维度跟该节点比较决定向左还是向右，直到叶子节点
- 重复： 维护一个当前的最近距离，这个当前最近距离的初始值就是跟到达叶节点的距离，仅有某个子树可能含有距离小于此最小距离的的节点时我们才访问之
- 向上回溯，首先尝试用父节点更新最小距离，然后计算一下兄弟空间是否跟以 x 为中心，以最小距离为半径的超球相交，如果相交，对兄弟子树进行 kd 树搜索
- 结束： 回溯到根的时候结束，当前维护的最近点就是全局最近点
一次搜索给出一个最近邻点，时间复杂度用为\(O(logn)\)，如果要找出 K 个最近邻点，时间复杂度为\(O(klogn)\)
PPT 上的例子
