统计学习(3)--k近邻和k均值
摘要
k-NN和k-mean介绍
1.k近邻算法
k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归方法。
k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。
具体对于新的实例x，在训练集中找到与之相邻的k个实例，这k个实例的多数属于哪一类，就把这个实例分到哪一类中。当k为1时，称为最近邻算法。
2.k近邻模型
k近邻的算法非常简单，主要在于距离度量、k值和分类决策三者的选取。
- 度量距离
- 欧氏距离
- Lp距离（Lp distance）
- Minkowski距离（Minkowski distance）
- k值
- 选小会比较敏感
- 增大意味着整体模型变得简单
- 分类决策
- 多数表决等价于经验风险最小化
3.kd树
k近邻没有给出一个显式的表达式，而是每一次判定都是需要计算所有点到实例的距离，然后选取最近的k个点表决。所以当总量N越来越大时，算法会变得越来越慢。
为实现快速k近邻搜索，可以采用特殊结构存储，称为kd树。kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
3.1 构造
输入：实例
输出：kd树
具体构造方式如下：
输入k维空间数据集：
\[ \mathrm{T}=\left\{\mathrm{x}_{1}, \mathrm{x}_{2}, \ldots, \mathrm{x}_{\mathrm{N}}\right\} \]
其中
\[ x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(k)}\right)^{\mathrm{T}} , i =1,2, \ldots, \mathrm{N} \]
- 构造根节点
选取\(x^{(1)}\)为坐标轴（这里也可以从方差最大的开始选），以所有数据的\(x^{(1)}\)特征的中位数作为切分点，生出深度为1的左右子节点。左小右大。
- 重复分割
对深度为j的节点，选取\(x^{(l)}\)为切分坐标轴，\(l=j(mod\enspace k)+1\)
生成j+1的左右子节点。
- 直到两个子区域没有实例
3.2 搜索
输入：kd树，目标x
输出：x的最近邻点
从根节点出发递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直 到子结点为叶结点为止。
记当前叶节点为最近点
检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，移动到另一个子结点进行递归最近邻搜索；如果不相交，向上回退。如果存在更近点则更新最近点。
(4)退回根节点后的最近点即为最近点。
4.k-mean
k-means是一种聚类算法，是无监督学习算法。它将训练数据分为k组，每一组是一个簇，随机选择k个实例作为初始的聚类中心点，对于每一个实例，计算它和这k个聚类中心的距离，然后把它分配到与它距离最近的聚类中心所在的簇中去；计算每个簇中所有实例的平均值，作为新的聚类中心点，以此往复，直至聚类中心点不再发生明显变化。