【人工智能Ⅰ】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=1n∣xi(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=1∑npi∗log2(pi)
2:信息增益
划分数据集前后,信息熵的差值
决策树过程
1:选择根节点
计算决策的信息熵H,和每个属性的信息熵
信息增益是【H – 选定属性的信息熵】
选取信息增益最大的属性作为根节点
2:选择新的节点
3:构建完整树
4:剪枝
减少树的高度,避免过拟合
(1)预剪枝干:设定一个树高度,当构建树达到高度时停止
(2)后剪枝:任由决策树构建完成,从底部开始判断哪些枝干应该剪掉
预剪枝更快,后剪枝更精确
决策树总结
1: 一棵决策树包含一个根节点、若干个内部结点和若干个叶结点
2:在决策过程中提出的每个判定问题都是对某个属性的“测试”(节点)
3:每个测试的结果或导出最终结论,或导出进一步的判定问题
4:根节点包含了样本全集,其中叶节点对应于决策结果(是或否),其他每个结点对应于一个属性测试
5:从根节点到每个叶节点的路径对应一个判定测试序列
决策树叶子节点的生成
递归过程
导致递归返回的情况:
1:当前节点包含的样本全属于同一类别,无需划分
2:当前属性为空或所有样本在所有属性上取值相同,无需划分。把当前节点标记为叶节点,并将其类别设定为该节点所含样本最多的类别
3:当前节点包含的样本集为空,不能划分,同样把当前节点标记为叶节点
决策树学习的生成算法
根据不同的目标函数,算法分为ID3、C4.5、CART
建立决策树的关键,即在当前状态下选择哪个属性作为分类依据
算法类别 | ID3 | C4.5 | CART |
---|---|---|---|
划分标准 | 信息增益 | 信息增益率 | 基尼指数(最小) |
决策树优缺点
优点
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 机器学习概念回顾
有监督学习:分类,回归
无监督学习:聚类,降维