4.2 机器学习 —— KNN & K-Means

这是一篇李航老师《统计学习方法（第二版）》中KNN和K-Means部分的阅读笔记，文中用到了一些书中的表述和自己的理解。

1. KNN（k 近邻算法）

1）是什么

这是一个分类算法，输入是实例的特征向量，输出为实例的类别。首先，我们有一个训练集，它是有标注的；对于一个新输入的实例，我们在训练数据集中找到与该实例最近的k个实例，然后在这k个实例中进行多数表决，最终确定新实例的类别。

2）为什么

k 近邻算法的三个基本要素是：

k 值选择，若k值较小，则只有与输入实例较近的训练实例对预测结果起作用，训练的近似误差会减小，但是由于模型对噪音数据的包容性更低，估计误差会增大，更容易发生过拟合；反之，若k较大，模型就会使用较大的邻域进行预测，这样就削弱了个别错误数据的干扰，因此估计误差会更小一些，但同时较远的实例也会对预测起作用，因此近似误差会增大。
距离度量，如欧氏距离
分类决策规则，一般使用多数表决

误分类率

3）怎么做

其实通过上面的描述也可知，当数据量非常大的时候，主要的时间消耗是 k 近邻搜索，仍然使用线性搜索的方式的话，时间开销太大。为了提高 k 近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，下面介绍 kd 树（kd tree）方法。
kd 树是一种对 m 维空间中的实例点进行存储以方便对其进行快速检索的树形数据结构。kd 树是一个二叉树，表示对 m 维空间的一个划分（partition）。构造 kd 树相当于不断地用垂直于坐标轴的超平面将 m 维空间进行切分，构成一系列的 m 维超矩形区域。kd 树的每个节点对应于一个 m 维超矩形区域。

构造方式如下：

（1）开始：构造根节点，根节点对应于包含 T 个 m 维空间的超矩形区域。
选择 m 维特征向量的第 1 维作为坐标轴，以所有实例第一维坐标值的中位数作为切分点，将数据集分为两堆，存放在左右节点上，特例（也就是坐标值等于中位数的样例）存放在根节点上；
（2）重复：对深度为 j 的节点上的集合，使用第 l 维坐标的中位数进行继续分割，直至分割的左右子区域没有实例存在。（ l = j(mod m) + 1 ）
通过上述方法得到的 kd搜索树 是平衡的，但未必是最优的（因为它不能保证平均搜索次数最少，所以不一定是最优的）

搜索方式如下：

（1）对于目标点 x ，递归地向下搜索，直到子结点为叶结点，并将改叶结点设置为“当前最近点”
（2）递归地向上回退，对每个节点执行以下操作：
- a）如果该结点保存的实例点比当前最近点到目标点的距离更近，那么更新最近点；
- b）以目标点为球心，当前最近距离为半径画超球体，判断当前节点及其子节点是否与球体相交，如果相交，说明更近点可能存在于这个结点的分值中，递归地对这个结点进行近邻搜索；若不相交，那么一定不存在更近点，向上回退即可；
（3）当回退到根节点的时候，搜索结束，当当前最近点即为 x 的最近邻点

问：如果想要最优，需要什么树结构？B+树？红黑树？

2. K-Means（k 均值聚类）

1）是什么

k 均值聚类是基于样本集合划分大的聚类算法。k 均值聚类将样本集合划分为 k 个子集，构成 k 个类，将 n 个样本分到 k 个类中，每个样本到期所属类的中心的据里最小。每个样本只能属于一个类，所以 k 均值聚类是硬聚类。分几个模块介绍：

模型：给定样本集合 $X={x_1, x_2, ..., x_n}$ 每个样本由一个特征向量表示，特征向量的维数是 $m$ 。k 均值聚类的目标是将 $n$ 个样本分到 $k$ 个不同的类或簇中。

2）为什么

策略：k 均值聚类归结为样本集合 X 的划分，或者从样本到类的函数的选择问题。其策略是通过损失函数的最小化选取最优的划分。
- 首先采用欧氏距离平方作为样本之间的距离 $d(x_i, x_j)$
- 然后定义样本与其所属类的中心之间的距离的总和为损失函数，即
  
  k 均值聚类就是求解最优化问题

3）怎么做

但由于这是一个组合优化问题，n 个样本分到 k 类的可能分法有指数级个。k 均值聚类的最优求解问题是 NP 难问题，现实中采用迭代的方法进行求解。

算法：下面就说说这个迭代的过程，每次迭代包括两个步骤。
- 首先随机选择 k 个样本点作为初始聚类中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果；
- 然后更新每个类的样本的均值，作为类的新的中心；
- 重复以上步骤，直至收敛为止（譬如聚类结果不再变化）
  k 均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果（包括数量 k 和具体位置），那么除了随机选择k和初始中心点，还有没有更好的方案呢？肯定是有的：
k 值得选取：
- 可以根据业务需求进行选取，譬如需要分为高、中、低三类，那么 k 等于3
- 不过像名词聚类这样的任务，更多是无法提前知晓类别数量的，那么我们可以用比较直接的方法推测最优的 k 值，也就是对于同一个数据集，尝试使用不同的 k 值进行聚类，然后用类的平均直径来检验各自得到聚类结果的质量，平均直径越小越好。一般来说，平均直径与类别数负相关，当类别数增加到某个值k后，平均直径不再减小或平缓减小，那么这个k就是一个较优的k值。为了加速，我们还可以用二分查找的方式确定k的值。
初始中心的选择：
- 除了随机初始化，还可以使用层次聚类的方式来获得初始中心（k 值要先确定），流程如下
  1) 将每个样例看作一类数据，计算两两之间的最小距离；
  2) 将距离最小的两个类合并成一个新类，重新计算新类与所有类之间的距离；
  3) 重复上述步骤，直到类别数量缩减为k。
  4）计算 k 个类别的中心，作为K-Means的初始中心点