当前位置 > CPDA数据分析师 > “数”业专攻 > 数据分析培训系列—分类算法之决策树(一)

数据分析培训系列—分类算法之决策树(一)

来源:数据分析师 CPDA | 时间:2015-07-29 | 作者:admin

从零开始学挖掘——分类算法之决策树(一)

分类任务就是确定对象属于哪个预定义的目标类,它有许多不同的应用场景,如根据电子邮件的标题和内容检查出是否为垃圾邮件,根据核磁共振的结果区分肿瘤是恶性还是良性。

分类任务的输入数据是记录的集合,每条记录用(x,y)表示,其中x是属性的集合,而y是一个特殊的属性,指出每条记录的类标号,如下表中,列出一个样本数据集,用来将脊椎动物进行分类,其中属性集合指明脊椎动物的性质,如体温、繁殖后代的方式等。

1前

记录的属性可以是离散的,也可以是连续的,但类标号却必须是离散属性。

准确的说,分类任务就是通过学习得到一个目标函数,把每个属性集影射到一个预先定义的类标号上,这里目标函数也称分类模型。

分类模型可以用于描述性建模和预测性建模两种目的。首先,分类模型可以作为解释性工具,用于区分不同类中的对象。其次,分类模型也可以用于预测未知记录的类标号。如下图所示,分类模型可以看作是一个黑箱,当给定未知记录的属性集上的值时,它自动地赋予未知样本类标号。

1

分类技术非常适合预测或描述二元或标称类型的数据集,对于序数分类(例如收入的高中低三类),分类技术不太有效,因为分类技术不考虑隐含在目标类中的序关系。本系列余下的部分只考虑二元的或标称类型的类标号。

分类法的例子包括决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法,这些技术都使用一种学习算法(learning algorithm)确定分类模型,该模型能够很好的拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好的拟合输入数据,还要能够正确地预测未知样本的类标号。因此,训练算法的主要目标是建立具有很好的泛华能力模型,即建立能够准确地预测未知样本类标号的模型。

下图展示了解决分类问题的一般方法。首先,需要一个训练集(training set),它是类标号已知的记录组成。使用训练集建立分类模型,该模型随后将运用于检验集(test set),检验集由类标号未知的记录组成。

2

分类模型的性能根据模型正确和错误预测的检验记录计算来进行评估,这些计数存放于混淆矩阵中。如下表中每个表项目fij表示实际类标号为i但被预测为类j的记录数。

2后

一般使用准确率和错误率来衡量分类模型的性能。

准确率=正确预测数/预测总数=(f11+f00)/(f11+f10+f01+f00)

错误率=错误预测数/预测总数=(f10+f01)/(f11+f10+f01+f00)

大多数分类算法都在寻求这样一些模型,当把它们应用于检验集时具有最高的准确率,或者相应的最低的错误率。我们将在之后的讨论中继续探讨模型的评估问题。

下面为大家介绍决策树(decision tree)分类发,这是一种简单但却广泛使用的分类技术,我们将分别通过决策树的工作原理、决策树的建立、表示属性测试条件的方法、选择最佳划分的度量、决策树归纳算法、决策树归纳的特点等6个角度来进行介绍。

 

  • 决策树的工作原理

假设科学家发现了一个新物种,怎么判断它是哺乳类动物还是非哺乳类动物呢?一种方法是针对物种的特征提出一系列问题。

第一个问题可能是,该物种是冷血动物还是恒温动物,如果冷血,则肯定是非哺乳动物;如果恒温,它是鸟类或某种哺乳类动物;

对于恒温动物,第二个问题可能是,该物种是由雌性产崽进行繁殖的吗?如果是,则肯定是哺乳动物,否则它有可能是非哺乳动物。

上面的例子表明,通过提出一系列精心构思的关于检验记录属性的问题,可以解决分类问题。每当一个问题得到答案,后续的问题将随之而来,直到我们得到记录的类标号。这一系列的问题和这些问题的可能回答可以组织成决策树的形式,它是由一种由结点和有向边组成的层次结构。

3

一旦构造了决策树,对检验记录进行分类就相当容易了。从树的根结点开始,将测试条件用于检验记录,跟俊测试结果选择适当的分支。沿着该分支或者到达另一个内部节点,使用心得测试条件,或者到达一个叶结点,进而该记录被赋予这个叶结点的类标号。例如下表未标记的数据,路径终止于类标号为非哺乳动物的叶结点。

3后

4

那么既然决策树可以用来对检验记录进行分类,那么我们该如何建造决策树呢,我们将在下一节中详细介绍决策树的建造方法、表示属性测试条件的方法,以及选择最佳划分的度量。