k近邻法（R语言实现）

$k$ 近邻法（ $k$ -nearest neighbor, $k$ -NN）是一种基本的分类和回归方法；
输入为实例的特征向量，对应特征空间的点；
输出为实例的类别，可以取多类。
$k$ 近邻法假设给定一个训练数据集，其中实例类别已定。分类时，对新的实例，根据其 $k$ 个最近邻的训练实例的类别，通过多数表决等方式进行预测。
$k$ 近邻法不具有显示学习过程， $k$ 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。
$k$ 值的选择，距离度量及分类决策规则是 $k$ 近邻法的三个基本要素。

1 k近邻算法

算法1（ $k$ 近邻法）
输入：训练数据集
$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$
其中, $x_i\in X \in R^n$ 为实例的特征向量， $y_i\in Y=\{c1,c2,...,c_k\}$ 为实例的类别， $i=1,2,...,N$ ;实例特征向量 $x$
输出:实例 $x$ 所属的类 $y$ .

根据给定的距离度量，在训练集 $T$ 中找出与 $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(y_i=c_j),i=1,2,\ldots,N;j=1,2,\ldots,K$

$I$ 为指示函数，当 $y_i==c_j$ 时， $I$ 为1，否则 $I$ 为0；
$k$ 邻近法的特殊情况是 $k=1$ 情形，称为最近邻算法。对于输入 $x$ ,最近邻法将训练数据集中与 $x$ 最近邻点的类作为 $x$ 的类。

2 K近邻模型

$k$ 近邻算法对应的模型实际上就是对特征空间的划分；
由三个基本要素：
距离度量， $k$ 值选择，分类决策规则；

2.1 模型

训练实例集完成空间的划分；

模型实例

2.2 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。
$k$ 近邻模型的特征空间一般是 $n$ 维实数向量空间 $R^N$ 。使用的距离为欧氏距离，但也可以是其他距离。

各种距离介绍：
设特征空间 $X$ 是 $n$ 维实数向量空间 $R^n$ ， $x_i,x_j\in{X}$ ， $x_i=(x_i^{\left(1\right)},x_i^{\left(2\right)},\cdots,x_i^{\left(n\right)})^T$ , $(x_j^{\left(1\right)},x_j^{\left(2\right)},\cdots,x_j^{\left(n\right)})^T$ ， $x_i,x_j$ 的 $L_p$ 距离定义为：

$L_p{(x_i,x_j)}=\left(\sum_{i=1}^n{\mid{x_i}^{\left(l\right)}-{x_j}^{\left(l\right)}\mid}^p\right)^{\frac{1}{p}} ,p\geq{1}$

当 $p=2$ 时，称为欧氏距离（Euclidean distance），即：
$L_2{(x_i,x_j)}=\left(\sum_{i=1}^n{\mid{x_i}^{\left(l\right)}-{x_j}^{\left(l\right)}\mid}^2\right)^{\frac{1}{2}}$

当 $p=1$ 时，称为曼哈顿距离（Manhattan distance），即：
$L_1{(x_i,x_j)}=\sum_{i=1}^n{\mid{x_i}^{\left(l\right)}-{x_j}^{\left(l\right)}\mid}$

当 $p=\infty$ 时，为坐标距离的最大值，即：
$L_{\infty}{(x_i,x_j)}=\max_{l}{\mid{x_i^l}-{y_j^l}\mid}$

2.3 k值的选择

$k$ 值较小，学习近似误差会减小，估计误差会增大，容易出现过拟合；
$k$ 值较大，学习近似误差会减大，估计误差会减小，模型过于简单；

近似误差：approximation error
估计误差：estimation error

2.4 分类决策规则

略；

3 k近邻法的实现：kd树

算法实现时，主要考虑的问题是如何对训练数据进行快速 $k$ 近邻搜索,这点在特征空间的维数大及训练数据容量大时尤为重要；
最简单的实现方法：线性扫描(linear scan)，计算输入实例与每一个训练实例的距离，训练集大时，计算非常耗时；
为提高效率，考虑使用特殊的结构存储训练数据，以减少计算距离的次数； $kd$ 树属于这种方法；

3.1 构造树算法描述

算法2:(构造平衡 $kd$ 树)
输入: $k$ 维空间数据集 $T=\{x_1,x_2,\ldots,x_N \},其中x_i=(x_i^{\left(1\right)},x_i^{\left(2\right)},\ldots,x_i^{\left(k\right)})^T,i=1,2,\ldots,N;$
输出: $kd$ 树

开始：构造根节点，根节点对应于包含 $T$ 的 $k$ 维空间的超矩形区域；
选择 $x^{(1)}$ 作为坐标轴，以 $T$ 中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。
由根结点生成深度为1的左、右子结点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。
将落在切分超平面上的实例点保存到根结点；
重复:对深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分的坐标轴， $l=j(mod \quad k)+1$ ，以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的巨型区域切分为两个子区域，切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。
由该结点生成深度为 $j+1$ 的左，右子结点：左子结点对应坐标 $x{(l)}$ 小于切分点的子区域，右子结点对应坐标 $x{(l)}$ 大于切分点的子区域。
将落在七分超平面上的实例点保存在该节点；
直到连个子区域没有实例存在时停止。从而形成 $kd$ 树区域划分。

3.2 构造树算法实现

算法流程图

#kd树算法举例
#the input
a<-data.frame(x=c(2,5,9,4,8,7),y=c(3,4,6,7,1,2))
attach(a)

#the output
t_list<-list()

#the initial varables
j<-0
k<-2

#the median cacuation is different w/ the standard function
my_median=function(v){
    t<-median(v)
    v_n<-sort(v)
    for(i in v_n) {
        if(i>=t){
            r<-i
            return(r)
            break
        }
    }
}

#the kd tree function
kdtree=function(d,j) {
    dim  <-j%%k+1          #dimension
    bl   <-numeric()
    bg   <-numeric()
    x    <-d[,dim]
    m    <-my_median(x)
    t_lst<-list()
    
    for(i in 1:length(x)){
        if(x[i]==m){
            t_lst[[length(t_lst)+1]]<-d[i,]
        }
        else if(x[i]<m){
            bl<-append(bl,i)
        }
        else {
            bg<-append(bg,i)
        }
    }
    
    if(length(x)==1){
        return(t_lst)
    }

    bl_df<-d[bl,]
    bg_df<-d[bg,]
    #cat(j,m,"bl=","\n")
    #print(bl_df)
    #cat(j,m,"bg=","\n")
    #print(bg_df)
    #cat("\n")

    j<-j+1
    dim<-dim+1

    if(length(bg)==0 & length(bl)==0) { 
        return(t_lst)
    }
    else if(length(bg)==0) {
        bl_lst<-kdtree(bl_df,j)
        bg_lst<-list()
    }
    else if(length(bl)==0) {
        bl_lst<-list()
        bg_lst<-kdtree(bg_df,j)
    }
    else {
        bl_lst<-kdtree(bl_df,j)
        bg_lst<-kdtree(bg_df,j)
    }

    t_lst[[length(t_lst)+1]]<-bl_lst
    t_lst[[length(t_lst)+1]]<-bg_lst

    return(t_lst)
}

res<-kdtree(a,0)
res

代码存储的数据结构如下：

每一个树结构都分为结点+左侧树+右侧树；
每一侧树又分为结点+左侧树+右侧树；
最后一级只有一个结点；

代码存储结构

3.3 搜索树算法描述

算法3:(用kd树的最近邻搜索)
输入:已构造的 $kd$ 树；目标点 $x$ ；
输出: $x$ 的最近邻。

在 $kd$ 树中找到包含目标点 $x$ 的叶节点：从根节点出发，递归地向下访问 $kd$ 树，若目标点 $x$ 当前维的坐标小于切分点的坐标，则移动到左子节点，否则为右，直到子结点为叶节点为止。
以此叶节点为“当前最近点”。
递归地往上回退，在每个结点进行如下操作：
- 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
- 当前最近点一定存在与该结点一个子结点对应的区域，检查该子结点的父结点的另一个子节点对应的区域是否有更近的点。（检查另一子结点对应的区域是否与目标点为球心，以目标点与“当前最近点”间距离为半径的超球体相交）
  - 相交：移动到另一结点，递归进行最近邻搜索；
  - 不交：向上回退。
当回退到根结点时，搜索结束。最后的“当前最近点”即为 $x$ 的最近邻点。

$kd$ 树平均计算复杂度是 $O(logN)$ ，适合训练实例数远大于空间维数的搜索，当维数与训练实例数接近时，效率迅速下降，几乎接近线性扫描；

3.4 搜索算法实现

编码略去了（累了。。。。。），思路如下：

寻找最近点(直接找到了更好，如相同点)。
根据最近点回退，更新最近点，直到更新到根结点结束；

参考1：《统计学习方法》---李航