机器学习（一）k近邻算法

K 近邻算法

K 近邻算法是一种基本的分类与回归方法。K 近邻算法没有显式的学习过程，实际上式利用训练数据集对特征向量空间进行划分。
其任务与数据如下：

$$Data = \lbrace (x_{1},y_{1}),(x_{2},y_{2})...(x_{n},y_{n}) \rbrace$$ $$x^{i} \in \mathcal{X} \subseteq \mathbb{R}^{n}$$ $$y^{i} \in \mathcal{Y} = \lbrace (c^{1},c^{2},...,c^{k}) \rbrace$$

其中$y^{i}$是实例的类别。
任务是输出实例x的类别y。
k近邻算法的三个要素是：
1.k值选择 2.度量距离 3.分类决策规则
该算法流程如下：
根据给定的距离度量，在训练集中找出与x最近邻的k个点，涵盖这k个点的邻域记作$N^{k}(x)$
在$N^{k}(x)$中根据分类决策规则决定x的类别y：

$$\displaystyle y = \mathop{\arg\min}_{\mathbf c_{j} } \sum^{x^{i} \in N^{k}(x)} I(y^{i}=c^{i}) , \ i=1,2,...,N; \ j=1,2,...,k$$

其中 I 为指示函数当$y^{i} = c^{i}$时 I 为 1，否则为 0。当 k=1 时，该算法又可称最近邻算法。

距离度量

该算法的距离度量往往采用$L_{p}$距离。其定义为：

$$\displaystyle L_{p} (x^{i},x^{j}) = (\sum^{l=1}_n \vert x^{i}_{(l)}-x^{j}_{(l)} \vert ^p)_{1/p}$$

k 值选择

k 值不易选取过大，应在较小的值中选取，选取不同的 k 值并进行交叉验证来选取最优值。

分类决策规则

一般采用多数表决（majority voting rule），其误分类率是：

$$\displaystyle 1/k \sum_{x_{i} \in N_{k}(x)} I(y_{i} \neq c_{j})$$

那么要使其最小就是使$\displaystyle \sum_{x_{i} \in N_{k}(x)} I(y_{i} = c_{j})$最大，多数表决函数可以等价于经验风险最小化。

实现

往往利用 kd 树方式构造：
构造根结点，不妨选择$x^{(1)}$为坐标轴，以 T 中所有的实例的$x^{(1)}$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。由根节点生成深度为 1 的左右子节点；左子节点对应坐标$x^{(1)}$小于切分点的子区域，右子节点对应于坐标$x^{(1)}$大于切分点的子区域。将落在切分超平面上的点将被保存在根节点。
之后对深度为 j 的节点重复这种操作，选择$x^{(l)} \ l = j(mod k)+1$进行。
当两个子区域没有实例存在时停止。从而形成 kd 树的区域划分。