1 概念
分类：分类任务就是通过学习得到一个目标函数（target function）f，把每个属性集x映射到一个预先定义的类标号y。
注意：类标号必须是离散属性，这是区别分类与回归（regression）的关键特征。回归是一种预测建模任务，其中目标属性y是连续的。
2 解决分类问题的一般方法
首先，需要一个训练集（training set），其由类标号已知的记录组成。使用训练集建立分类模型，该模型随后将用于检验集（test set），检验集由类标号未知的记录组成。 分类模型的性能根据模型正确和错误预测的检验记录计数进行评估，这些计数存放在称作混淆矩阵（confusion matrix）的表格中
准确率𝑎𝑐𝑐𝑢𝑟𝑎𝑐𝑦=(𝑓11+𝑓00)/(𝑓11+𝑓10+𝑓01+𝑓00)
3 决策树归纳
决策树组成： 根结点(root node)：没有入边，但有零条或多条出边。 内部结点（internal node）：恰有一条入边和两条或多条出边。 叶结点（leaf node）或终结点（terminal node）：恰有一条入边，但没有出边。
3.1 决策树建立
3.2 Hunt算法
Hunt算法是ID3、C4.5和CART决策树算法的基础。
在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。设Dt是与结点t相关联的训练记录集，而$y是类标号，Hunt算法的递归定义如下：
（1）如果Dt中所有记录都属于同一个类yt，则t是叶结点，用yt标记
（2）如果Dt中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将Dt中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。
如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类标号，则Hunt算法是有效的。但是对于大多数实际情况，这些假设太苛刻，因此需要附加的条件来处理以下的情况：
3.2.1 决策树归纳的设计问题
（1）如何分裂训练记录
树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。为了实现这个步骤，算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量
（2）如何停止分裂过程
需要有结束条件，以终止决策树的生长过程。一个可能的策略是分裂节点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但是还可以使用其他的标准提前终止树的生长过程
3.2.2 表示属性测试条件的方法
二元属性：二元属性的测试条件产生两个可能得输出。 标称属性：由于标称属性有多个属性值，它的测试条件可以用用两种方法表示。 序数属性：序数属性也可以产生二元或多路划分 连续属性：对于连续属性而言，测试条件可以是具有二元输出的比较测试（𝐴＜𝑣）或（𝐴≥𝑣），也可以是具有形如𝑣𝑖≤𝐴＜𝑣𝑖+1(i=1, ..., k)输出的查询范围
3.2.3 选择最佳划分的度量
设𝑝(𝑖|𝑡) 表示给定结点t中属于类i的记录所占比例。 不纯性度量：
其中c是类的个数，并且0log20=0。 选择最佳划分的度量通常就是根据划分后子女结点的不纯性的程度。不纯的程度越低，类分布就越倾斜。 为了确定测试条件的效果，我们需要父结点的不纯程度和子女结点的不纯程度，其差越大，测试条件的效果就越好，可用增益𝛿 表示
其中，𝐼(.)是给定结点的不纯性度量，𝑁是父节点上的记录综述，𝑘是属性值的个数，𝑁(𝑣𝑗)是与子女结点𝑣𝑗相关联的记录个数。 决策树归纳算法通常选择最大化增益𝛿的测试条件，且对所有的测试条件来说，𝐼(𝑝𝑎𝑟𝑒𝑛𝑡)是一个不变的值，因此最大化增益等价于最小化子女结点的不纯性度量的加权平均值。 当选择熵（entropy）作为不纯性度量时，熵的差就是信息增益（information gain）Δ𝑖𝑛𝑓𝑜
京公网安备 11010502036488号