Peter Harrington-《机器学习实战》学习笔记

Author： Anleeno
发布时间：October 1, 2020
2709 views
No comments
3037 words
Categories：机器学习

## 1. k-近邻算法

### 1.1 简介

k近邻学习（kNN）是一种监督学习算法，它直接使用测试样本和训练样本，没有显式的训练过程，工作机制如下：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测。通常，对于不同类型的任务，使用的预测方法不同：

* 分类任务：投票法，选择k个样本中出现最多的类别标记作为预测结果
* 回归任务：平均法，将k个样本的实值输出标记的平均值作为预测结果

此外，还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

优点：精度高、对异常值不敏感、无数据输入假定。
</div>
<div class="tip inlineBlock warning">

缺点：计算复杂度高、空间复杂度高。
</div>
<div class="tip inlineBlock share">

适用数据范围：数值型和标称型。
</div>

### 1.1 计算逻辑

图示：
![](https://www.anleenoxu.top/usr/uploads/2020/11/329091499.jpg)

绿色方块要被赋予哪个类别，五角星还是三角形？假定k等于5（虚线），蓝色三角形占比为3/5，大于五角星2/5，那么绿色方块将被赋予蓝色三角形那个类。如果k=10，则五角星所占比例6/10大于三角形所占比例4/10，那么绿色方块将被赋予五角星那个类。

> （1）给定测试对象，计算它与训练集中的每个对象的**距离**。
> （2）圈定距离**最近的k个**训练对象，作为测试对象的邻居。
> （3）根据这k个近邻对象所属的类别，找到**占比最高**的那个类别作为测试对象的预测类别。

影响KNN算法准确度的两个关键因素：K的选择和距离。

对于距离度量，一般使用两种计算公式：曼哈顿距离和欧式距离。

### 1.2 一般流程

> （1）收集数据：可以使用任何方法
> （2）准备数据：距离计算所需要的数值，最好是结构化的数据格式
> （3）分析数据：可以使用任何方法
> （4）训练算法：此步骤不适用于k-近邻算法（kNN为懒惰学习的著名代表，此类学习在训练阶段仅仅是把训练样本保存起来，训练时间开销为0，待收到测试样本之后再进行处理。）
> （5）测试算法：计算错误率
> （6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

<button class="btn m-b-xs btn-success btn-addon" onclick='window.open("https://github.com/Anleeno-Xu/MLInAction/tree/master/chapter02","_blank")'><i class="iconfont icon-github-copy"></i>k-近邻算法代码</button>

## 2. 决策树

### 2.1 简介

[决策树](https://baike.baidu.com/item/%E5%86%B3%E7%AD%96%E6%A0%91/10377049)(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法[ID3](https://baike.baidu.com/item/ID3), [C4.5](https://baike.baidu.com/item/C4.5)和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

一个决策树包含三种类型的节点[[1]](https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91)：

1. 决策节点：通常用矩形框来表示
2. 机会节点：通常用圆圈来表示
3. 终结点：通常用三角形来表示

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
</div>
<div class="tip inlineBlock warning">

缺点：可能会产生过度匹配的问题。
</div>
<div class="tip inlineBlock share">

适用数据范围：数值型和标称型。
</div>

### 2.2 一般流程

> （1）收集数据：可以使用任何方法
> （2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
> （3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
> （4）训练算法：构造树的数据结构
> （5）测试算法：使用经验树计算错误率
> （6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义

### 2.3 一些概念

信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为$P_k(k=1,2,...,|y|)$，则D的信息熵定义为

$$
Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k.
$$

Ent(D)的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值：$\left\{a^1 , a^2 , … , a^V \right\}$ ，若第v个分支结点包含了D中所有在属性a上取值为$a^v$的样本，记为$D^v$。每个分支节点的权重：$\dfrac{|D^v|}{|D|}$，即样本数越多的结点影响越大，于是属性a对样本集D进行划分所获得的信息增益为

$$
Gain(D,a)=Ent(D)-\sum^V_{v=1}\dfrac{|D^{v}|}{|D|}Ent(D^v).
$$

一般而言，信息增益越大，表示用属性a作为划分属性所获得的“纯度提升”越大。

信息增益[[2]](https://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E5%A2%9E%E7%9B%8A/8864911?fr=aladdin)[[3]](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA))：书中简单来讲就是划分数据集之前之后信息发生的变化，用来描述一个属性区分数据样本的能力。

<button class="btn m-b-xs btn-success btn-addon" onclick='window.open("https://github.com/Anleeno-Xu/MLInAction/tree/master/chapter03","_blank")'><i class="iconfont icon-github-copy"></i>决策树代码</button>

Last modification：November 10, 2020