统计学习---K近邻法

K近邻

假设给定的一个训练数据集，其中的实例类别已定。分类时，根据其K个最近邻的训练实例的类别，通过多数表决等方式进行预测。

利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

K值得选择，距离度量，分类决策规则，三个基本要素

离它最近的最多的是那一个类就把它划到那一个类里面。

 

K近邻算法

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分为这个类。

 

K近邻模型

是对特征空间的划分。

三要素：距离度量，K值的选择，分类决策规则

K近邻法中，当训练集、距离度量、K值及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一地确定。

 

距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。

P=2,欧式距离；p=1，曼哈顿距离；p=无穷大，它是各个坐标距离的最大值。

 

K值的选择

k值的减小就意味着整体模型变得复杂，容易发生过拟合。

k值较大，就相当于在较大领域中进行训练。

通常采用交叉验证法来选取最优的K值。

一般就是这样，中国的思想：中庸。太大不好，太小也不好

分类决策规则

多数表决：由输入实例的k个邻近的训练实例中的多类决定输入实例的类。

 

K近邻法的实现：kd树

如何对训练数据进行快速k近邻搜索。

kd树是能够快速检索的树形数据结构，是二叉树，

 

构造kd数

不断用垂直于坐标轴的超平面将k维空间划分，构成一系列的k维超矩形区域。

每个结点对应于一个k维超矩形区域。

 

构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对k维空间进行划分，生成子结点。

在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。

依次选择坐标轴对空间划分，选择训练实例点在选定坐标轴上的中位数为切分点。

如果对于一个二维的空间的数据集，第一步比较x的值选出中位数，将空间分为两部分；第二步看左区域的数据的y值，选出中位数，再将左边的区域划分为两部分；右边相同，l维的话就一直这样切分下去，每一个实例点最后都在切分的线上。

 

搜索kd树

首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最近邻的结点，当确定不可能存在更近的结点时终止。

目标点先和一个最近的叶结点画一个圆，看下上层中父结点的另一个子结点和这个圆相交不，不想交，再往上走，查看相交不。因为要是有最近的，那肯定是在与圆相交的内部。