第4章：决策树2017v2学习课件.pptx

第4章(1)分类：决策树

;;分类的是利用一个分类函数（分类模型、分类器），该模型能把数据库中的数据映射到给定类别中的一个。

;训练样本、学习

测试、分类

属性

分类界限or分类规则

;分类;基本概念;数据分类——一个两步过程(1);数据分类——一个两步过程(2);有监督的学习VS.无监督的学习;分类模型的构造方法;;一个决策树的例子;决策树的另一个例子;用决策树归纳分类;为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性进行测试，从决策树的根节点到叶节点的一条路径就形成了相应对象的类别测试。决策树可以很容易转换为分类规则

;决策树分类任务;一个决策树的例子;应用决策树进行分类;应用决策树进行分类;应用决策树进行分类;应用决策树进行分类;应用决策树进行分类;应用决策树进行分类;决策树分类;;决策树;Hunt算法;Hunt算法;决策树构建;怎样选择最佳划分？;怎样找到最佳划分？;结点不纯性的测量;停止分裂过程;三种著名的决策树;决策树;;;ID3使用信息增益作为属性选择度量。该度童基于香农(ClaudeShannon)在研究消息的值或信息内容的信息论方面的先驱工作。设结点N代表或存放分区D的元组。

选择具有最高信息增益的属性作为结点N的分裂属性。

该属性使结果分区中对元组分类所需要的信息量最小，并反映这些分区中的最小随机性或不纯性。这种方法使得对一个对象分类所需要的期望测试数目最小，并确保找到一棵简单的(但不必是最简单的)树。;对D中的元组分类所需要的期望信息由下式给出:

其中，Pi是D中任意元组属于类Ci的非零概率，并用

估计。

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

Info(D)又称为D的熵(entropy)

非负性：Info(D)大于等于0

连续性：Info(D)对任意q连续

极值性：当q都等于1\K时Info(D)达到最大值logK

;ID3算法——计算Entropy的例子;现在，假设我们要按某属性A划分D中的元组，其中属性A根据训练数据的观测具有v个不同值

如果A是离散值的，则这些值直接对应A上测试的v个输出。可以用属???A将D划分为v个分区或子集

其中，Dj包含D中的元组，它们的A值为aj。

这些分区对应于从结点N生长出来的分枝。理想情况下，我们希望该划分产生元组的准确分类。即我们希望每个分区都是纯的。然而，这些分区多半是不纯的(例如，分区可能包含来自不同类而不是来自单个类的元组)。

(在此划分之后）为了得到准确的分类，我们还需要多少信息？这个量由划分A的期望信息度量;划分的期望信息

项充当第j个分区的权重。InfoA(D)是基于按A划分对D的元组分类所需要的期望信息。需要的期望信息越小，分区的纯度越高。

信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后1)之间的差。即

;信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后1)之间的差。即

换言之，Gain(A)告诉我们通过A上的划分我们得到了多少。它是知道A的值而导致的信息需求的期望减少。

选择具有最高信息增益Gain(A)的属性A作为结点N的分裂属性。这等价于在“能做最佳分类”的属性A上划分，使得完成元组分类还需要的信息最小(即最小化Gain(A))。

;Trainingdataset:Buys_computer

Thedatasetfollowsanexample

ofQuinlan’sID3(PlayingTennis)

Resultingtree:;一个标记类的元组的训练集D，随机地从AlIElectronics顾客数据库中选取。

在这个例子中，每个属性都是离散值的，连续值属性已经被离散化。

类标号属性buys_compter有两个不同值(即{yes,no})，因此有两个不同的类(即m=2)。设类C1对应于yes，而类C2对应于no。

类yes有9个元组，类no有5个元组。为D中的元组创建(根)结点N。为了找出这些元组的分裂准则，必须计算每个属性的信息增益。

;下一步，需要计算每个属性的期望信息需求。从属性age开始。需要对age的每个类考察yes和no元组的分布。

;=30;;信息增益度量偏向具有许多输出的测试。换句话说，它倾向于选择具有大量值的属性。

例如，考虑充当唯一标识符的属性，如product_ID。在product_