机器学习day9-决策树

决策树

决策树自上而下,对样本数据进行树形分类的过程。决策树由结点和有向边组成。结点又分内部结点和叶结点。每个内部结点表示一个特征或属性,叶子结点表示类别。
从顶部开始,所有样本聚在一起,经过根结点的划分,样本分入不同的子结点,再根据子结点的特征进一步划分,直到所有的样本被归入到一个类别。
决策树是最基础且常见的监督学习模型,可以用于处理分类问题和回归问题。
决策树的生成包括:特征选择,树的构造,树的剪枝三个过程。

决策树常用的启发函数

常用的决策树算法有:ID3,C4.5和CART,那么它们的启发式函数是什么?

ID3-最大信息增益

对于样本集合D,类别数为K,数据集D的经验熵表示:

机器学习day9-决策树
其中,是样本集合D中属于第k类的样本子集,表示该子集的元素个数,|D|表示样本集合的样本个数。
然后计算某特征A对于数据集D的经验条件熵H(D|A):
机器学习day9-决策树其中,表示D中特征A取第i个值得样本子集,表示中属于dik类的样本子集。
因此,信息增益g(D,A)可以表示为二者之差,
机器学习day9-决策树信息增益最大,一般是最后具体划分类别的结点。

C4.5-最大信息增益比

特征A对于数据集D的信息增益比定义:

机器学习day9-决策树其中
机器学习day9-决策树称为数据集D关于A的取值熵。

CART-最大基尼指数(Gini)

Gini描述的是数据的纯度,与信息熵含义类似
机器学习day9-决策树CART每次迭代时选择基尼指数最小的特征及其对应的切分点进行分类。CART是二叉树,每一步数据按照特征A的取值切成两份,分别进入左右子树。特征A的Gini指数定义:
机器学习day9-决策树

三种启发函数

ID3使用信息增益作为评价标准。C4.5基于ID3进行了优化,引入了信息增益比,对取值较多的特征进行惩罚,避免了一定程度的过拟合。提高决策树的泛化能力。
ID3应用于离散变量,C4.5和CART都可以用于连续变量。
ID3和C4.5用于分类任务,CART,Classification and Regression Tree,分类回归树用于回归和分类问题。
最后,ID3对于样本特征缺失值比较敏感,CART和C4.5会自己处理,C4.5通过剪枝,CART则是直接利用全部数据发现所有可能的树结构进行对比。


上一篇:uniapp 购物车页面解决实时刷新的问题


下一篇:流畅的python学习笔记(三):把函数视作对象(2:使用一等函数实现设计模式 )