1、分类任务就是确定对象属于哪个预先定义的目标类。分类任务的输入数据是记录的集合，每条记录称为样例，用元组（x,y）表示，其中x是属性的集合，y是一个特殊的属性，指出样例的类标号（也称分类属性或目标属性）。

2、分类任务就是通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y；需要注意类标号是离散属性才属于分类任务；若类标号是连续属性，则属于回归任务。

3、目标函数也称分类模型：分类模型可以用于描述性建模，即分类模型作为解释性的工具，用于区分不同类中的对象；分类模型还可以用于预测性建模，即用于预测未知记录的类标号。

4、分类技术适合预测或描述二元或标称类型的数据集；不适合序数分类，因为分类技术不考虑隐含在目标类中的序关系，对于其它形式的联系，分类计数一般也不考虑。因此下面的探讨只考虑二元或标称类型的类标号。

1、常用的分类技术（或分类法）有：决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法；解决分类问题的一般方法，首先需要一个训练集，它由类标号已知的记录组成，使用训练集建立分类模型，该模型随后将运用于检验集，检验集由类标号未知的记录组成。

2、分类模型的性能根据模型正确和错误预测的检验记录计数进行评估，这些计数存放在称作混淆矩阵的表格中。

1、决策树工作原理，通过提出一系列精心构思的的关于检验记录属性的问题，可以解决分类问题。每当一个问题得到答案，后续的问题将随之而来，直到我们得到记录的类标号。

我们把脊椎动物分成两大类，哺乳类动物和非哺乳类动物。如下就是构造的决策树，以及一个例子

2、如何建立决策树，一般采用贪心策略去考虑算法，即在选择划分数据的属性时，采取一系列局部最优决策树来构造决策树，Hunt算法就是这样的算法。Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART。

Hunt算法，通过将训练集划分成较纯的子集，以递归方式建立决策树。设是与结点相关联的训练集记录，而是类标号，算法的递归定义如下：

（1）如果中所有记录都属于同一个类，则是叶结点，用标记

（2）如果中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于属性测试条件的每个输出，创建一个子结点，并根据测试结果将中的记录分布到子结点中。然后对每个子结点，递归调用该算法。

根据以前贷款者的贷款记录，预测贷款申请者是按时还贷，还是会拖欠贷款。

选取属性测试条件是一个难点，也即选择最佳划分的度量，稍后讨论。

Hunt算法在什么情况下有效：如果属性值的每种组合都在训练集中出现，并且每组组合都有唯一的类标号，则Hunt算法才有效。但大多数情况下无法满足，因此需要附加条件处理以下的两种情况：

（1）算法的第二步中所创建的子结点可能为空，即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合，这种情况就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记录中的多数类。

（2）在第二步中，若与相关联的所有记录都具有相同的属性值（目标属性除外），则不可再进一步划分这些记录。这时，该结点为叶结点，其标号为与该结点相关联的训练记录中的多数类。

决策树归纳的学习算法需要解决的两个问题：

（1）如何分裂训练记录？算法需要为同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量。

（2）如何停止分裂过程？即需要有结束条件，终止决策树的生长过程。

3、不同类型属性的属性测试条件

（1）二元属性：二元属性测试条件会产生两个输出

（2）标称属性：标称属性的测试条件有两种方法；多路划分和二元划分

（3）序数属性：二元或多路划分均可，但要保持序数属性值的有序性

（4）连续属性：需要注意有序性

4、选择最佳划分的度量

选择最佳划分的度量可以解决让哪个属性测试条件作为第一个、划分成哪种形式最合适，判断的标准就是采用该测试条件后，能得到纯度更高的类，即在划分后的类的分布越不平衡越好。举例如下：采用性别划分后，子结点中的类分布是（0.6，0.4）和（0.4，0.6）显然通过性别划分后的类别并不是很纯；而用车型进行划分后的类分布更不平衡，即纯度更高。

重新整理语言就是，选择最佳划分的度量通常是根据划分后子结点不纯性的程度，不纯的程度越低，即类分布越倾斜，也即该种划分越好。如类分布为（0，1）的结点具有0不纯性，而均衡分布（0.5，0.5）的结点具有最高的不纯性。不纯性度量可以有下面三种方式：

计算实例如下：

进一步，我们需要比较测试条件的效果，则需要比较父结点（划分前）的不纯性度量和子结点（划分后）的不纯性度量，它们的差越大，测试条件的效果越好。

由于I(parent)相对每个测试条件来说是一个不变的值，所以最大化增益等价于最小化子结点的不纯性度量的加权平均值。

5、例子：不同类型属性的划分，对上述度量方法的测试

（1）二元属性：如下图，若有两种方式A和B对父节点进行划分，应该选择哪一种方式？

分析：在三种不纯性度量方式中，若采用Gini的度量方式，则划分前（父结点）的Gini值为0.5若选择A方式对父节点进行划分，则结点N1的Gini指标是0.4898，而N2的Gini指标是0.480，经过A划分后的子结点的不纯性度量（Gini指标）的加权平均值为（7/12）*0.4898+（5/12）*0.480=0.486；类似经过B方法得到的子结点的不纯性度量（Gini指标）的加权平均值为0.375；因为最大化增益等价于最小化子结点的不纯性度量的加权平均值，所以选择B方式较好。

（2）标称属性

（3）连续属性的划分

对记录排序，以中间值作为候选划分点，得到55,65,72等候选划分点。算的所有的Gini指标，最后97是产生最小Gini指标值的点，即将97作为二元划分点。

进一步优化：可以看到在排序完后，前三个值都属于同一类No，同样的后四个值也在同一类No，因此只需要算两个点的Gini指标值，即比较80和97两个点的Gini指标值，结果97产生的Gini指标值最小，故作为二元划分点。

6、增益率的引入

从下图可以看出，车型作为测试条件更好，因为可以得到更纯的分类。但是与顾客ID作为划分条件，后者可以产生更纯的划分。但该种划分却不好，因为与每个划分相关联的记录太少，不能做出可靠的预测。

解决该问题有两种策略：

增益率定义如下：

7、决策数归纳算法

对算法的分析：算法采用递归的方式，选择最优的属性来划分数据，并扩展叶结点，直到满足条件。

stopping_cond()是用来检查是否所有记录都属于同一个类，或者都具有相同的属性值，决定是否终止决策树的增长。

createNode()表示创建新结点；结点有两种，要么是测试条件node.test_cond，要么是类标号node.label

Classify()为叶结点确定类标号

find_best_split()确定应当选择哪个属性作为划分训练记录的测试条件，返回值是测试条件结点类型

8、决策树归纳的特点

以下内容是各种分类法中共同具有的问题

1、概念

2、造成过分拟合的几个可能原因

3、泛化误差的估计

估计决策树的泛化误差的原因是为了确定一个较好的模型，它具有较低的泛化误差。估计方法有如下几种：

（1）使用再带入进行估计：假设训练数据集可以很好地代表整体数据，则可以用训练误差（也称再带入误差）提供对泛化误差的乐观估计。在这样的假设下，选择训练误差最小的模型作为最终的模型即可。通常这是一种很差的估计

（2）结合模型的复杂度：通常，模型越复杂，过拟合的可能性越大。两种将模型复杂度和分类模型评估结合的方法：

最小描述长度原则（MDL）

（3）估计统计上界：泛化误差可以用训练误差的统计修正来估计，通常泛化误差倾向于比训练误差大，所以取训练误差的上界，作为泛化误差的估计。

（4）使用确认集：将原始的训练数据集保留三分之一用作误差估计。

4、处理决策树归纳中的过分拟合

1、保持方法：将被标记的原始数据分成两个不相交的集合，分别作为训练集（2/3）和检验集（1/3）。在训练集上归纳分类模型，在检验集上评估模型的性能。分类器的准确率根据在检验集上的准确率估计。该种方法的局限性：

2、随机二次抽样：多次重复保持方法来改进对分类器性能的评估。

3、交叉验证：每个记录用于训练的次数相同，并且用于检验恰好一次。比如，将数据分成2份，首先，选择一个子集作为训练集，另一个作为检验集；然后，交换两个集合的角色；最后求得估计的平均值。

4、自助法：上述3种方式都是假定训练记录不放回抽样，训练集和检验集中没有重复的记录。自助法中，采用有放回抽样。

比较不同分类器的性能，以确定在给定的数据集上哪个分类器效果更好。

（1）例子：考虑分类模型A和B，假设A在包含30个记录的检验集上的准确率达到85%，而B在包含5000个记录的不同检验集上达到75%的准确率。该例子涉及两个关键问题：

（2）估计准确率的置信区间

通过将分类任务用二项式实验建模推到置信区间，准确率acc的置信区间计算公式如下：

举例：若一个模型在100个检验记录上具有80%的准确率。在95%的置信水平下，模型的真实准确率的置信区间是多少？

从上述表格中可以看到95%的置信水平下，Z=1.96，代入公式得置信区间在71.1%到86.7%之间。表明模型的真实准确率有95%的可能性会落在71.1%到86.7%之间。