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):

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

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。

缺点:可能会产生过度匹配的问题。

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)):书中简单来讲就是划分数据集之前之后信息发生的变化,用来描述一个属性区分数据样本的能力。

Last modification:November 10, 2020
喜欢就加个鸡腿吧!