算法概述
分类算法:也可以转化为回归.
分类算法利用训练样本集获得分类模型(分类器)，从而实现将数据集中的样本划分到各个类中。分类模型通过学习训练样本中属性集与类别之间的潜在关系，并以此为依据对新样本属于哪一类进行预测。(输入一个数据,得到一个类别)
决策特征怎么选.
用于分类(粗略划分) 用于回归(不断细分)
决策树通过把数据样本分配到某个叶子结点来确定数据集中样本所属的分类 决策树由决策结点、分支和叶子结点组成
- 决策结点表示在样本的一个属性上进行的划分
- 分支表示对于决策结点进行划分的输出
- 叶结点代表经过分支到达的类。 从决策树根结点出发，自顶向下移动，在每个决策结点都会进行1次划分，通过划分的结果将样本进行分类，导致不同的分支，最后到达个叶子结点，这个过程就是利用决策树进行分类的过程
树的组成
怎么构建是重点.
常用方法:
这里主要学习 ID3算法
基本思路🌟🌟 (递归直到类别的结果统一或者样本数到达一定数量或者层数到达上限) 首先根据某种分类规则得到最优的划分特征，计算最优特征子函数，并创建特征的划分节点，按照划分节点将数据集划分为若干子数据集；
然后，在子数据集上重复使用判别规则，构建出新的节点，作为树的新分支；
重复递归执行，直到满足递归终止条件。
算法基本思想
训练难,测试简单
如何切分特征(选择节点)
三种经典的决策树生成算法
- 基于信息增益的ID3算法
- 基于信息增益率的C4.5算法
- 基于基尼指数的CART算法
ID3算法：以信息增益最大的属性为分类特征，基于贪心策略自顶向下地搜索遍历决策树空间，通过递归方式构建决策树。
信息——信息熵(一个事的不确定性的多少)
增益——偏差值
(注意H(x)的公式的负号)
pi: 发生的概率
分类后熵越小越好
信息熵公式:
只有一个类别的熵为0
信息增益 ID3决策树算法使用信息增益确定决策树分支的划分依据，每次选择信息增益最大的特征作为结点。信息增益即决策树某个分支上整个数据集信息熵与当前结点信息熵的差值。
请记住,节点是分类的特征,分支是样本的特征.
ID3算法找信息增益最大的(或信息熵最小的,因为都是由Info(D)来减,Info(D)是确定的,所以Info_A(D)越小越好)🌟
案例🌟
- 计算总的信息熵
- 计算属性信息熵
- 求增益
案例
案例
特点:
- ID3算法中根据信息论的信息增益评估和选择特征。每次选择信息增益最大的候选特征，作为判断模块。
- 信息增益与属性的值域大小成正比。属性取值种类越多，越有可能成为分裂属性。
- ID3也不能处理连续分布的数据特征。
缺点:
显然是生成了一颗含有17个结点的树，这棵树没有任何的泛化能力，这也是ID3算法的一个缺点。
C4.5算法
增益率
例子
- C4.5算法使用信息增益率代替信息增益，进行特征选择，克服了信息增益选择特征时偏向于特征值个数较多的不足；
- 其具体算法步骤与ID3类似；
- C4.5能够完成对连续属性的离散化处理；能够对不完整数据进行处理；
- 分类规则易于理解、准确率较高；
- 效率低，只适合于能够驻留于内存的数据集。
C5.0算法 C5.0算法是Quinlan在C4.5算法的基础上提出的商用改进版本，目的是对含有大量数据的数据集进行分析
C5.0算法与C4.5算法相比有以下优势：
- 决策树构建时间要比C4.5算法快上数倍，同时生成的决策树规模也更小，拥有更少的叶子结点数
- 使用了提升法(boosting)，组合多个决策树来做出分类，使准确率大大提高
- 提供可选项由使用者视情况决定，例如是否考虑样本的权重、样本错误分类成本等
CART算法
