[第六章]决策树分类算法

分类过程

学习阶段

建立分类模型

• 离散域→离散属性

• 连续域→连续属性

• 类别属性C=（c1,c2…cm）

• 训练数据集X1=(c1,c2…cm,C)

• 不同分类算法得到不同分类模型

• 准确率：正确预测新样本所属类别的能力

• 速度：建立模型的开销

• 强壮性：

• 可伸缩性

• 可解释性

评估模型的准确率

• 正确率

• 召回率

• 调和平均

• 准确率

• AUC函数介于x周的面积
• x轴是FP，y轴是TP

分类阶段

决策树分类

决策树

• 结点
• 根节点
• 对应分类属性集的一个属性
• 内部节点
• 对应分类属性集的一个属性
• 叶子节点
• 对应分类标签中的一个分类

• 如何选择测试属性

• 如何停止划分样本
• 子区域同类或空
• 深度到达一定程度或样本个数少于某数

ID3算法

信息增益

• 描述属性（1≤k≤m）
• 每一个属性（1≤j≤v）的值域为
• S中描述属性C取值为ci的元组个数为

• 类别属性C取值为（1≤i≤u）其值域为
• S中类别属性C取值为的元组个数为

• 描述属性取（1≤j≤v）且类别属性C取值为（1≤i≤u）的元组个数为

自信息量

• 概率与自信息量成反比

• 反应不确定性

无条件熵

• 如果每一个种类的可能性基本相同，不确定性最大

条件熵

信息增益

• 越大，说明这个条件属性影响更大

构造

• 计算所有条件属性的信息增益

• 信息增益大的作为根节点，其取值作为子树的分类

• 每一个子树当作根节点分别计算剩下条件属性的信息结点增益

• 直到该孩子的类别属性同类或为空，停止划分，叶节点为该类别属性

C4.5算法

信息增益率

连续属性离散化

• 排序

• 两个相邻值的平均点作为分割点
• 计算分割点划分样本集S的信息增益，选择具有最大信息增益的分割点作为最终的划分点

空值的处理

比较

• C4.5与ID3的比较

SQL Server决策树分类

电子商务数据的决策树分类