【数据挖掘】第4章 分类：基本概念、决策树与模型评估

4 分类：基本概念、决策树与模型评估

一、解决分类问题的一般方法

分类: 分类任务就是通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y中。
目标函数也称分类模型。

解决分类问题的一般方法

基本概念

训练集：数据库中为建立模型而被分析的数据元组形成训练集。

• 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。
• 一个具体样本的形式可为:( v1, v2, …, vn; c );其中vi表示属性值,c表示类别。

测试集（检验集）：用于评估分类模型的准确率

分类相关概念

分类：分类任务就是通过训练（或学习），得到一个目标函数或分类规则，把未知类别的数据对象（测试样本）划分到预定义的类别中。
分类任务包含两个步骤：1）训练；2）测试（分类）

• 训练：对于其属性和类别都已知的数据对象（即训练样本），通过寻找其中的规律，得到一个目标函数或分类规则的过程。

• 测试（分类）：训练完成后，根据得到的目标函数或分类规则，将未知类别的数据对象（测试样本）划分到预定义的类别中。

• 训练样本：训练过程中所使用的属性和类别都已知的数据对象即为训练样本。训练过程通过寻找其中的规律，得到一个目标函数或分类规则。

• 测试样本：测试过程中所使用的，属性值已知但类别未知的数据对象即为测试样本。测试过程目标函数或分类规则，预测每个测试样本的类别。

二、决策树归纳

1）决策树工作原理

用决策树归纳分类

什么是决策树？

• 类似于流程图的树结构
• 每个内部节点表示在一个属性上的测试
• 每个分枝代表一个测试输出
• 每个树叶节点代表类或类分布

决策树的生成由两个阶段组成：
①决策树构建（重点）
开始时，所有的训练样本都在根节点； 递归的通过选定的属性，来划分样本 （必须是离散值）
②树剪枝（略）
许多分枝反映的是训练数据中的噪声和孤立点，树剪枝 试图检测和剪去这种分枝

决策树的使用：对未知样本进行分类 --> 通过将样本的属性值与决策树相比较

2）如何建立决策树

决策树构建
Hunt算法采用贪心策略构建决策树：在选择划分数据的属性时，采取一系列局部最优决策来构造决策树.

决策树归纳的设计问题

• 如何分裂训练记录
  怎样为不同类型的属性指定测试条件? – (表示属性测试条件的方法)
  怎样评估每种测试条件? – (选择最佳划分的度量)
• 如何停止分裂过程
  当所有的记录属于同一类时，停止分裂
  当所有的记录都有相同的属性时，停止分裂
  提前终止树的生长
  

3）ID3决策树

怎样选择最佳划分？ ——不纯性的度量（1）→ 熵
选择最佳划分的度量通常是根据划分后子结点不纯性的程度。
不纯性的程度越低，类分布就越倾斜

ID3算法——期望信息，熵

数据集D的期望信息又称熵 (entropy)，记作 Info(D)。 Info(D)又称为 D 的 熵
数据集D的熵描述了数据集D 的不纯性。
$熵：Info(D)=-\sum _{i=1}^m{p}_{i}lo{g}_2(p_i)$

Info(D)是识别D 中无组的类标号所需要的平均信息量。注意 ，此时我们所有的信息只是每个类的元组所占的百分比 。

• 非负性： Info(D)大于等于0
• 连续性： Info(D)对任意q连续
• 极值性：当q都等于1/K时 ,Info(D)达到最大值

熵的性质
数据集D的不纯度越高，期望信息，即熵的值越大
划分所依据的特征越有区分度，划分得到的数据子集D’（结 点）越纯，划分得到的数据子集D’的熵越小
即：划分所依据的特征越有区分度，划分得到的数据子集D’（结点）不纯度越小

划分A的期望信息
度量一个划分的好坏–>期望信息
$期望信息：Inf{o}_A(D)=-\sum _{j=1}^v\frac{|D_j|}{|D|}Info(D_j)$

ID3算法——信息增益

信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对 A 划分后1)之间的差。即
$信息增益：Grain(A)=Info(D)-Inf{o}_A(D)$
换言之 ，Gain(A) 告诉我们通过 A 上的划分我们得到了多少 。它是知道 A 的值而导致的信息需求的期望减少。
选择具有最高信息增益 Gain (A) 的属性 A 作为结点 N 的分裂属性。
这等价于在“能做最佳分类”的属性 A上划分，使得完成元组分类还需要的信息最小(即最小化 Gain (A) )

一个标记类的元组的训练集 D ，随机地从AlIElectronics顾客数据库中选取。
在这个例子中，每个属性都是离散值的，连续值属性已经被离散化。
类标号属性buys_compter有两个不同值(即{yes,no})，因此有两个不同的类(即m=2)。设类C1对应于yes，而类C2对应于no。
类yes有9个元组，类no有5个元组。为D中的元组创建(根)。结点N。为了找出这些元组的分裂准则，必须计算每个属性的信息增益。
下一步，需要计算每个属性的期望信息需求。从属性age开始。需要对age 的每个类考察 yes 和 no 元组的分布。

由于age在属性中具有最高的信息增益，所以它被选作分裂属性。结点N用age标记，并且每个属性值生长出一个分枝。然后元组据此划分，如图所示。

4）表示属性测试条件的方法

怎样为不同类型的属性指定测试条件?

• 依赖于属性的类型：①标称 ②序数 ③连续
• 依赖于划分的路数：①2路划分 ②多路划分

基于标称属性的划分
多路划分: 划分数（输出数）取决于该属性不同属性值的个数.
二元划分: 划分数为2，这种划分要考虑创建k个属性值的二元划分的所有$2^{k-1}-1$种方法.

基于序数属性的划分
多路划分: 划分数（输出数）取决于该属性不同属性值的个数.
二元划分: 划分数为2，需要保持序数属性值的有序性

基于连续属性的划分
多路划分: $v_i$ $\le$$A＜vi+1（i=1,\dots ,k)$
二元划分: $(A<v)$ or $(A\ge v)$ –考虑所有的划分点，选择一个最佳划分点v

5）选择最佳划分的度量

选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜

怎样选择最佳划分？ ——不纯性的度量（2）→ Gini（基尼指数）、classification error

不纯性的测量: GINI

给定结点t的Gini值计算 :
$GINI(t)=1-\sum _j[p(j|t){]}^2$
( $p(j|t)$ 是在结点t中，类j发生的概率 ).

• 当类分布均衡时，Gini值达到最大值
• 相反当只有一个类时，Gini值达到最小值0
• GINI值越小，纯度越大
  

不纯性的测量: Classification Error

给定结点t的 Classification Error值计算 :
$Error(t)=1-\underset{j}{\max }P(i|t)$

• 当类分布均衡时， error值达到最大值 ($1-1/n_c$)
• 相反当只有一个类时， error值达到最小值0
• ERROR值越小，纯度越大

不纯性度量之间的比较

三、模型的过分拟合

模型过分拟合和拟合不足

分类模型的误差大致分为两种：

• 训练误差：是分类模型在训练记录上误分类样本比例
• 泛化误差：是分类模型在未知记录上的期望误差

一个好的分类模型不仅要能够很好的拟合训练数据 ，而且对未知样本也要能准确分类。 换句话说，一个好的分类模型必须具有低训练误差和低泛化误差。
当训练数据拟合太好的模型，其泛化误差可能比具有较高训练误差的模型高，这种情况成为模型过分拟合
当决策树很小时，训练和检验误差都很大，这种情况称为模型拟合不足。出现拟合不足的原因是模型尚未学习到数据的真实结构。

模型过分拟合：

• 随着决策树中结点数的增加，模型的训练误差和检验误差都会随之下降。
• 当决策树的规模变得太大时，即使训练误差还在继续降低，但是检验误差开始增大，导致模型过分拟合
  

导致过分拟合的原因： ①训练数据中存在噪声 ②训练数据中缺乏代表性样本

处理决策树中的过分拟合

先剪枝

• 树增长算法在产生完全拟合整个训练数据集的之前就停止决策树的生长
• 为了做到这一点，需要采用更具限制性的结束条件:
  当结点的记录数少于一定阈值，则停止生长
  当不纯性度量的增益低于某个确定的阈值时，则停止生长
• 缺点：很难为提前终止选取正确的阈值:
  阈值太高，导致拟合不足
  阈值太低，导致不能充分解决过分拟合的问题。

后剪枝

• 在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长的决策树。
• 修剪有两种做法:
  用新的叶结点替换子树，该叶结点的类标号由子树下记录中的多数类确定
  用子树中最常用的分支代替子树

四、评估分类器的性能

评估分类器的性能
测试分类模型在测试集上的性能，可以得到泛化误差的无偏估计
常用的评估分类器性能的方法： 保持、随机二次抽样、交叉检验、自助法

保持方法：
将原始数据划分成两个不相交的集合——训练集和测试集。在训练集数据上归纳分类模型，在测试集数据上评估模型的性能。分类器准确率根据模型在测试集上的准确率估计。

随机二次抽样 ：
多次重复保持方法来改进对分类器性能的估计。分类器准确率是每次保持方法得到的准确率的平均值。

交叉检验：
二折交叉检验（2-fold crossValidation）、k折交叉检验（k-fold crossValidation）、留一法

k折交叉检验：
K折交叉检验就是把原始的数据随机分成K个部分。在这K个部分中，选择一个作为测试数据，剩下的K-1个作为训练数据。
交叉检验的过程实际上是把训练-分类过程重复做K次，每次都从K个部分中选择一个不同的部分作为测试数据（保证K个部分的数据都分别做过测试数据），剩下的K-1个当作训练数据进行实验，最后把得到的K个准确率计算平均值。

留一法：k折交叉检验的特殊情况，k=N（N为原始数据集的大小）

自助法：在自助（booststrap）方法中，训练数据采用有放回的抽样。

bingo~   ✨ 一鲸落，万物生  是鲸留给大海最后的温柔????

最后

以上就是清脆含羞草为你收集整理的【数据挖掘】第4章 分类：基本概念、决策树与模型评估的全部内容，希望文章能够帮你解决【数据挖掘】第4章 分类：基本概念、决策树与模型评估所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。