【人工智能Ⅰ】7-KNN & 决策树

7-1 KNN(K near neighbour)

思想:一个样本与数据集中的k个样本最相似,若这k个样本大多数属于某类别,则该个样本也属于这类别

距离度量

样本相似性用欧氏距离定义
L p( x i, x j)=( Σ l=1n∣ x i (l) − x j (l)∣ p ) 1/p L_p(x_i,x_j)=(Σ_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{1/p} Lp(xi,xj)=(Σl=1nxi(l)xj(l)p)1/p

流程

1:计算已知类别数据集中的点与当前点之间的距离

2:按递增排序距离

3:选取与当前点距离最小的k个点

4:统计k个点的类别及其频率

5:返回频率最高的类别,作为当前点的预测分类

优点

1:简单有效

2:适用大样本自动分类

缺点

1:类别分类不标准化

2:不均衡性

3:计算量较大

k值选择

1:误差

  • 近似误差:对现有训练集的训练误差(过小说明过拟合
  • 估计误差:对测试集的测试误差(过小说明对未知数据的预测能力好

2:k值

  • 过小:近似误差小,估计误差大
  • 过大:估计误差小,近似误差大
  • k值一般取一个较小的数,采用【交叉验证法】择优

3:交叉验证法

将数据集划分为N个大小相似的互斥子集,并且尽量保证每个子集数据分布的一致性

这样可获取N组训练 – 测试集,从而进行N次训练和测试。

7-2 决策树(Decision tree)

根据特征解决数据分类问题

  • 每个节点选择一个特征提出问题,通过判断将数据分为2类,再继续提问
  • 问题是在已知各种情况发生概率基础上,构成决策树,求取值大于等于0的概率
  • 再投入新数据时,根据树上的问题,将数据划分到合适叶子上
  • 事先确定每个样本的属性和类别,节点表示属性测试,分支表示测试输出,叶子节点表示类别

数据

1:训练数据(构造决策树,即决策机制)

2:测试数据(验证决策树的错误率)

构造树的依据

1:信息熵

表示信息的复杂程度
H=− ∑ i=1n p i∗lo g 2(pi)H=-∑_{i=1}^np_i*log_2(pi) H=i=1npilog2(pi)
2:信息增益

划分数据集前后,信息熵的差值

决策树过程

1:选择根节点

计算决策的信息熵H,和每个属性的信息熵

信息增益是【H – 选定属性的信息熵】

选取信息增益最大的属性作为根节点

2:选择新的节点

3:构建完整树

4:剪枝

减少树的高度,避免过拟合

(1)预剪枝干:设定一个树高度,当构建树达到高度时停止

(2)后剪枝:任由决策树构建完成,从底部开始判断哪些枝干应该剪掉

预剪枝更快,后剪枝更精确

决策树总结

1: 一棵决策树包含一个根节点、若干个内部结点和若干个叶结点

2:在决策过程中提出的每个判定问题都是对某个属性的“测试”(节点)

3:每个测试的结果或导出最终结论,或导出进一步的判定问题

4:根节点包含了样本全集,其中叶节点对应于决策结果(是或否),其他每个结点对应于一个属性测试

5:从根节点到每个叶节点的路径对应一个判定测试序列

决策树叶子节点的生成

递归过程

导致递归返回的情况:

1:当前节点包含的样本全属于同一类别,无需划分

2:当前属性为空或所有样本在所有属性上取值相同,无需划分。把当前节点标记为叶节点,并将其类别设定为该节点所含样本最多的类别

3:当前节点包含的样本集为空,不能划分,同样把当前节点标记为叶节点

决策树学习的生成算法

根据不同的目标函数,算法分为ID3、C4.5、CART

建立决策树的关键,即在当前状态下选择哪个属性作为分类依据

算法类别ID3C4.5CART
划分标准信息增益信息增益率基尼指数(最小)

决策树优缺点

优点

1:易于理解和实现,需要的背景知识少,直接体现数据特点

2:数据准备简单或不必要,可同时处理数据型和常规型属性

3:易于通过静态测试对模型评测(可信度)、逻辑表达式

缺点

1:对连续性的字段比较难预测

2:对有时间顺序的数据,需要预处理

3:若类别过多,错误增加快

7-3 集成学习

通过建立几个模型组合,解决单一预测问题

工作原理:生成多个分类器

集成学习方法分类

1:基于boosting(提升)

Adaboost
梯度提升决策树(GBDT)
XGBoost(extreme gradient boosting)
LightGBM

基本思想:

(1)每个样本均赋予一个权重

(2)T次迭代,每次迭代后对分类错误的样本加大权重,下次迭代更加关注分类错误的样本

特点:

前面的学习器改变后面学习器的权重,学习器采用串联方式连接

采用线性加权方式进行组合,每个基学习器都有相应的权重,对于错误率小的基学习器会有更大的权重

2:基于bagging(装袋)

随机森林(Random Forest)
极端随机树(Extremely randomized trees,Extra-Trees)

基本思想:

对原始训练样本集采用自助随机采样,即有放回的随机采样,产生n个新的训练样本子集,以此分别训练n个基学习器,最后采用某种组合策略集成为强学习器

特点:

对于分类问题,通常使用简单投票法;对于回归问题,通常使用简单平均法

Adaboost

1: 初始化训练样本的权重分布,每个样本具有相同权重

2:训练一个弱分类器,如果样本分类正确,则在构造下一个训练集中,它的权重就会被降低;反之,提高样本的权重

3:用更新过的样本集去训练下一个弱分类器

4:各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,降低分类误差率大的弱分类器的权重

5: 将所有弱分类组合成强分类器

随机森林

随机:随机选取训练样本集、随机选取分裂属性集

森林:多棵决策树

过程:决策树的生长和投票

(依靠决策树的投票选择,决定最后的分类结果)

每棵树的生成

1:有放回的采样N个样本,构成训练集

2:无放回的随机选择m个特征,计算其信息增益并择优(通常 m = sqrt(M))

3:使用一般决策树的构建方法,得到一棵分类或预测的决策树

4:重复1-3步,得到H棵决策树,将某个测试样本输入H棵树得到H个结果,使用投票机制或最终分类结果判别测试样本所属的类别

随机森林的生成

分类效果(错误率)的相关因素:

1:森林中任意2棵树的相关性

相关性越大,错误率越大

2:森林中每棵树的分类能力

每棵树的分类能力越强,整个森林的错误率越低

随机森林唯一的参数:特征选择个数m

减少m,树的相关性和分类能力会降低

袋外错误率OOB error

最优m的选择,主要依据计算袋外错误率

第k棵树的袋外样本数据:没有参与第k棵树生成的训练实例

袋外错误率:对每棵树用未被选中的训练样本点,统计每棵树的误分率,最后取平均值得到随机森林的袋外错误率

随机森林特点

优点:

1-两个随机性的引入,不容易陷入过拟合,具有很好的抗噪声能力

2-对数据集适应能力强,可处理连续型和离散型数据,数据无需规范化,可运行大数据集

3-不需要降维,可处理高维特征的输入样本

4-在生成过程中,可获得内部生成误差的无偏估计

5-可处理缺省值问题

缺点:

1-噪声较大,可能过拟合

2-对有不同级别属性的数据,级别划分较多的属性会对随机森林产生更大的影响,随机森林在这类数据上产出的属性权值不可信

投票机制

1:简单投票机制

假设每个分类器平等

一票否决
少数服从多数
有效多数
阈值表决

2:贝叶斯投票机制

基于每个基本分类器在过去的分类表现,设定一个权值,按照这个权值进行投票

7-4 机器学习概念回顾

有监督学习:分类,回归

无监督学习:聚类,降维