1 KNN算法

KNN算法，又译K-近邻算法，是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间中的 k 个最接近的训练样本。
* 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k 个最近邻居（k 为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若 k = 1，则该对象的类别直接由最近的一个节点赋予。
* 在k-NN回归中，输出是该对象的属性值。该值是其 k 个最近邻居的值的平均值。

邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。

如图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
* 如果K=3，绿色圆点的最近的3个邻居是2个红色三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
* 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的样本数目成正比，也就是说，如果训练集中样本总数为n，那么 KNN 的分类时间复杂度为O(n)。由于 KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

1.1 K近邻算法

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

输入：训练数据集 $T= {(x_1,y_1 ),(x_2,y_2 ),(x_3,y_3 ),…,(x_N,y_N)}$
其中，$x_i∈ℵ⊆R^n$为实例的特征向量，$y_i∈Y, Y={c_1,c_2,…,c_k}$为实例的类别，$i=1,2,3,…,N$；
输出：实例x的关系类别。
（1）根据给定的距离度量，在训练集T中找到与x最邻近的k个点，涵盖这k个点的x的领域记为$N_k (x)$；
（2）在$N_k (x)$中根据分类决策规则（如多数表决）决定x的类别y：
$y= {argmax}_{c_j}{∑_{x_j∈N_k (x)} I(y_i=c_j )}$ $i=1,2,…,N; j=1,2,…,K$ (1)
上式中，I为指示函数，即当$y_i=c_j$时I为1，否则I为0.

1.2 K近邻法的模型及三个基本要素

K近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。模型由三个基本要素——距离度量、k值选择和分类决策规则决定。

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

1.2.1 距离度量

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

设特征空间ℵ是n维实数向量空间$R^n$，$x_i,x_j∈ℵ, x_i=(x_i^{(1)} ,x_i^{(2)},…,x_i^{(n)})^T$， $x_j=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)} )^T$，$x_i,x_j$的$L_p$距离定义为
$L_p (x_j,x_i )= (∑_{l=1}^n|x_i^{(l)} -x_j^{(l)} |^p )^{1/p}$
这里p>=1，当p=2时，称为欧氏距离，即
$L_2 (x_j,x_i )= (∑_{(l=1)}^n|x_i^{(l)}-x_j^{(l)} |^2 )^{(1/2)}$
当p=1时，称为曼哈顿距离，即
$L_1 (x_j,x_i )= ∑_{(l=1)}^n|x_i^{(l)} -x_j^{(l)}|$
当p=∞时，它是各个坐标距离的最大值，即
$L_p (x_i,x_j )=max_l |x_i^{(l)}-x_j^{(l)} |$

使用的距离不同，k近邻的结果也会不同的，即由不同的距离度量所确定的最邻近点是不同的。

1.2.2 k值选择

k值选择会对k近邻法的结果产生重大影响。

1） 选择较小的K值，相当于用较小的领域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用，但“学习”的估计误差会增大，预测结果对近邻的实例点非常敏感。k值的减小意味着整体模型变得复杂，容易发生过拟合；

2） 选择较大的k值，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。k值的增大意味着整体的模型变得简单；

在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最有的 K 值

1.2.3 分类决策规则

K近邻法的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
解释：如果分类的损失函数为0-1损失函数，分类函数为$f=R^n⟶{c_1,c_2,…,c_k}$
那么误分类的概率是$P(Y≠f(X))=1-P(Y=f(X))$
对给定实例x，其最近邻的k个训练实例点构成集合$N_k (x)$。如果涵盖N_k (x)的区域的类别是c_j，那么误分类率是
$1/k ∑_{x_i∈N_k (x)}I(y_i≠c_j ) =1-1/k ∑_{x_i∈N_k (x)}I(y_i=c_j )$
要使误分类率最小即经验风险最小，就要使$∑_{x_i∈N_k (x)}I(y_i=c_j )$ 最大，所以多数表决等价于经验风险最小化。

1.3 K近邻法的实现方法--kd树

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速K近邻搜索。

1.3.1 构造kd树

Kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。Kd树是二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间划分，构成一系列k维超矩形区域。

算法：
输入：k维空间数据集$T={x_1,x_2,…,x_N}$，
其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^{T},i=1,2,…,N$；
输出：kd树。
1）开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域。
选择$x^{(1)}$为坐标轴，以T中所有实例的$x^{(1)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域，切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。由根结点生成深度为1的左、右节点。
2）重复：对深度为j的结点，选择$x^{(l)}$为切分的坐标轴，l=j(mod k)+1，以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。
3）直到两个子区域没有实例存在停止。

例：6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}

1.3.2 搜索kd树

利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。这里以最近邻为例。

算法：
输入：已构造的kd树，目标点x；
输出：x的最近邻。
1）在kd树种找出包含目标点x的叶结点：从根结点出发，递归的向下访问kd树。若目标点x当前维的坐标小于切分点的时候，则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。
2）以此结点为“当前最近点”。
3）递归地向上回退，在每个结点进行以下操作：
a）如果该结点保存的实例点比当前最近点距离目标点更近，更新“当前最近点”；
b）检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。做法，检查另一个结点对应的区域是否与以目标点为球心、以目标点和“当前最近点”间距离为半径的超球体相交。 如果相交，可能在另一个子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点，递归进行最近邻搜索；如果不想交，向上回退。
4）当回退到根结点时，搜索结束，最后的“当然最近点”即为x的最近邻点。

如果实例点是随机分布的，kd树搜索的平均计算复杂度为O(logN).

例：6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}建立的kd树 搜索（2,4.5）的最近邻点。

---

2 决策树

决策树模型成树形结构，在分类问题中，表示基于特征对实例进行分类的过程，它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
主要优点：模型具有可读性，分类速度快；学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，预测时，对新的数据，利用决策树模型进行分类。
决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。

2.1 决策树模型与学习

定义：分类决策模型是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成。结点有两种类型，内部结点（表示一个特征或属性）和叶结点（表示一个类）。
分类：从根结点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶结点。最后将实例分到叶结点的类中。
决策树示意图如下，圆和方框分别代表内部结点和叶结点

学习：假设给定数据集$D={(x_1,y_1 ),(x_2,y_3 ),…,(x_N,y_N )}$，其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T$为输入实例，n为特征个数，$y_i∈{1,2,…,k}$为类标记，$i=1,2,…,N$，N为样本容量。学习的目标是根据给定的训练数据集建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习的算法通常是一个递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择。
决策树学习算法包含特征选择、决策树生成与决策树剪枝过程。

2.2 特征选择

特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。

信息增益

熵：$H(X)=-∑_{i=1}^np_i logp_i$ $P(X=x_i )=p_i$ $i=1,2,…,n$
条件熵：$H(Y│X)=∑_{i=1}^np_i H(Y|X=x_i)$ $p_i=P(X=x_i )$, $i=1,2…,n$
当熵和条件熵中的概率由数据估计得到时，所对应的熵与条件熵称为经验熵和经验条件熵。
信息增益：特征A对训练数据集D的信息增益，定义为集合D的经验熵与特征A给定条件下D的经验条件熵之差，即 $g(D,A)=H(D)-H(D|A)$
信息增益表示得知特征X的信息而使得类Y的信息的不确定减少的程度。

根据信息增益准则的特征选择方法是：对训练数据集D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

信息增益的计算：
设训练数据集D，|D|表示样本容量，设有K个类$C_k$，$k=1,2,…,K$，$|C_k|$为属于类$C_k$的样本个数，$∑_{k=1}^K|C_k |=|D|$。设特征A有n个不同的取值${a_1,a_2,…,a_n}$，根据特征A的取值将D划分为n个子集$D_1,D_2,…,D_n$，$|D_i |$为$D_i$的样本个数，记子集$D_i$属于类$C_k$的样本集合为$D_{ik}$，$|D_{ik} |$为$D_{ik}$的样本个数。

$$H(D)=-∑_{(k=1}^K\frac{|C_k |}{|D|}log_2\frac{|C_k |}{|D|}$$
$$H(D│A)=∑_{i=1}^n\frac{|D_i |}{|D| } H(D_i )=-∑_{i=1}^n\frac{|D_i |}{|D|}∑_{k=1}^K\frac{|D_{ik} |}{|D_i|} log_2 \frac{|D_{ik} |}{|D_i|}$$
$$g(D,A)=H(D)-H(D|A)$$

信息增益比

$g_R (D,A)=\frac{g(D,A)}{H_A (D)}$
其中$H_A (D)=-∑_{i=1}^n\frac{|D_i |}{|D| }log_2\frac{ |D_i |}{|D|}$，是巡检数据集D关于特征A的值的熵，n是特征A取值个数。
信息增益比校正了以信息增益选取特征时存在的偏向于选择取值较多的特征的问题。

2.3 决策树的生成

ID3算法

核心：在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

过程：
输入：训练数据集D，特征集A，阈值ε；
输出：决策树T。
1）若D中所有实例属于同一类$C_k$，则T为单结点树，并将类$C_k$作为该结点的类标记，返回T；
2）若A=∅，则T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T；
3）否则，按照信息增益的计算公式计算A中各特征对D的信息增益，选择信息增益最大的特征$A_g$；
4）如果$A_g$的信息增益小于阈值，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T；
5）否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将D分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
6）对第i个子结点，以$D_i$为训练集，以$A-{A_g}$为特征集，递归地调用1）~5），得到子树$T_i$，返回$T_i$。

C4.5算法

C4.5算法对ID3算法进行了改进，C4.5在生成过程中，用信息增益比来选择特征。

例：

A = {年龄，有工作，有自己的房子，信贷情况}

1）计算各特征对数据集D的信息增益：
$g(D,A1) = 0.083, g(D,A2) = 0.324, g(D,A3) = 0.420, g(D,A4) = 0.363$
由于特征A3(有自己的房子)的信息增益最大，所以选择特征A3作为根结点的特征。它将数据集D划分为两个子集D1(A3的取值为“是”)和D2(A3的取值为“否”)。D1只有同一个类的样本，所以它成为一个叶结点，类标记为“是”。

2）对D2则需从特征A1（年龄）、A2（有工作）和A4（信贷情况）中选择特征：
$g(D2,A1) = 0.251, g(D2,A2) = 0.918, g(D2,A4) = 0.474$
选择特征A2（有工作）作为结点的特征。从这一结点引出的两个子结点都成为叶结点。

2.4 决策树的剪枝

决策树生成算法递归产生决策树的过程容易出现过拟合现象，解决这个问题的办法是对已生成的决策树进行简化，这个简化的过程成为剪枝。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有$N_t$个样本，其中k类的样本有$N_{tk}$个，$k=1,2,…,K$，$H_t (T)$为叶结点t上的经验熵，$α≥0$，则损失函数可以定义为
$C_α (T)=∑_{t=1}^{|T|}N_t H_t (T)+α|T|$
其中经验熵为

$$H_t(T)=-∑_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$
将$C_α (T)$第一项记作$C(T)$，则$C_α (T)=C(T)+α|T|$，这里$C(T)$表示模型与训练数据的拟合程度，|T|表示模型复杂度。
剪枝，就是当α确定时，选择损失函数最小的模型。

剪枝算法：
输入：生成算法产生的整个树T，参数α；
输出：修剪后的子树$T_α$。
1）计算每个结点的经验熵；
2）递归地从树的叶结点向上回缩；
设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_A$，其对应的损失函数分别为$C_α (T_B )$与$C_α (T_A )$，如果$C_α (T_B ) ≥C_α (T_A )$，则进行剪枝，即父结点变成新的叶结点。
3）返回2），直至不能继续为止，得到损失函数最小的子树$T_α$。

2.5 CART(classification and regression tree)算法

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。
CART**假设决策树是二叉树**，这样的决策树等价于递归地二分每个特征，将输入空间划分为有限个单元，并在这些单元上确定预测的概率分布。
CART算法由以下两步组成：
1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

2.5.1 CART生成

决策树的生成就是递归构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数：分类问题中，假设有K个类，样本点属于第k类的概率为p_k，则概率分布的基尼指数定义为$Gini(p)= ∑_{k=1}^Kp_k (1-p_k)=1-∑_{k=1}^Kp_k^2$
对于给定的样本集合D，其基尼指数为
$Gini(D)=1-∑_{k=1}^K(\frac{|C_k |}{|D|})^2$
这里，$C_k$是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一个值a被分割成D1和D2两部分，即
$D_1={(x,y)∈D│A(x)=a}, D_2=1-D_1$
在特征A的条件下，集合D的基尼指数定义为
$Gini(D,A)=\frac{|D_1 |}{|D|} Gini(D_1 )+\frac{|D_2 |}{|D|} Gini(D_2 )$ （1）
基尼指数Gini(D)表示结合D的不确定性，Gini(D)表示经A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也越大。

CART生成算法
输入：训练数据集D，停止条件；
（停止条件是结点中的样本上小于预定阈值，或样本集的基尼指数小于预定阈值，或没有更多特征）
输出：CART决策树。
根据训练数据集，从根结点开始，递归的对每个节点进行以下操作：
1）结点数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，根据对A=a的测试为“是”或“否”将数据集分成两部分，根据（1）计算A=a时的基尼指数；
2）在所有可能的特征A和他们可能的切分点a中，选择基尼指数最小的特征及其对应的切分点。从现结点生成两个子结点。
3）对两个子结点递归调用1）和2），直至满足停止条件。
4）生成CART决策树。

2.5.2 CART剪枝

在剪枝过程中，计算子树的损失函数：$C_α (T)=C(T)+α|T|$， 其中，T为任意子树，$C(T)$为对训练数据的预测误差，|T|为子树的叶结点数。

Breiman等人证明：可以用递归的方法对树进行剪枝。将α从小增大，产生一系列区间$[αi,α{(i+1)} ),i=0,1,…,n$；剪枝得到的子树序列对应着区间$α∈[αi,α{(i+1)} ),i=0,1,…,n$的最优子树序列${T_0,T_1,…,T_n}$，序列中的子树是嵌套的。

对整体树$T_0$的任意内部结点t，以t为单结点树的损失函数：$C_α (t)=C(t)+α$
以t为根结点的子树T_t的损失函数是：$C_α (T_t )=C(T_t )+α|T_t |$
当$α=\frac{C(t)-C(T_t)}{|T_t |-1}$，$T_t$与t有相同的损失函数，而t的结点少，因此t为$T_t$更可取，对$T_t$剪枝。

CART剪枝算法:

问题：步骤（6）中“回到步骤（4）”是不是应该是“回到步骤（3）”？？？

这里的A就是算法中的g(t)。（是不是应该也计算t1的g(t)，因为t1也是内部结点？？？）