1. k-近邻算法
1.1 简介
k近邻学习（kNN）是一种监督学习算法，它直接使用测试样本和训练样本，没有显式的训练过程，工作机制如下：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测。通常，对于不同类型的任务，使用的预测方法不同：
- 分类任务：投票法，选择k个样本中出现最多的类别标记作为预测结果
- 回归任务：平均法，将k个样本的实值输出标记的平均值作为预测结果
此外，还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。
1.1 计算逻辑
图示：
绿色方块要被赋予哪个类别，五角星还是三角形？假定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-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
2. 决策树
2.1 简介
决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
一个决策树包含三种类型的节点[[1]](https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91)：
- 决策节点：通常用矩形框来表示
- 机会节点：通常用圆圈来表示
- 终结点：通常用三角形来表示
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))：书中简单来讲就是划分数据集之前之后信息发生的变化，用来描述一个属性区分数据样本的能力。