第9章
分类规则挖掘与预测
主要内容
●分类与预测的基本概念
●决策树方法
●分类规则挖掘的ID3算法
●其他分类规则挖掘算法
●分类规则的评估
●微软决策树及其应用
1
9.1分类与预测的基本概念
1. 什么是分类
数据分类（data classfication）是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。
数据分类（data classfication）是一个两个步骤的过程：
●第1步：建立一个模型，描述给定的数据类集或概念
集（简称训练集）。通过分析由属性描述的数据库元组
来构造模型。每个元组属于一个预定义的类，由类标号
属性确定。用于建立模型的元组集称为训练数据集，其
中每个元组称为训练样本。由于给出了类标号属性，因
此该步骤又称为有指导的学习。如果训练样本的类标号
是未知的，则称为无指导的学习（聚类）。学习模型可
用分类规则、决策树和数学公式的形式给出。
●第2步：使用模型对数据进行分类。包括评估模型的
分类准确性以及对类标号未知的元组按模型进行分类。
训练数
（a）学习
2
图9-1 数据分类过程
2. 常用的分类规则挖掘方法
分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：
●决策树方法
●贝叶斯方法
●人工神经网络方法
●约略集方法
●遗传算法
典型的分类规则挖掘算法有：
●ID3
●C4.5
●DBlearn等
3. 什么是预测
预测（prediction）是构造和使用模型评估无标号样本类，或评估给定的样本可能具有的属性或区间值。分类和回归是两类主要的预测问题。分类是预测离散值，回归用于预测连续或有序值。
4. 分类和预测数据的预处理
●数据清理：使用平滑技术消除或减少噪声；处理空缺值。
●相关性分析：删除与分类或预测无关的属性；删除冗余属性。
●数据变换：使用概念分层将数据概化到高的层次；连续值属
性概化为离散区间；数据规范化，即将某一属性的所有值
按比例缩放，使其落入指定的区间。
3
5. 分类方法的评估标准
●准确率：模型正确预测新数据类标号的能力。
●速度：产生和使用模型花费的时间。
●健壮性：有噪声数据或空缺值数据时模型正确分类或
预测的能力。
●伸缩性：对于给定的大量数据，有效地构造模型的能
力。
●可解释性：学习模型提供的理解和观察的层次。
9.2决策树方法
决策树方法的起源是概念学习系统CLS，然后发展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。
1. 什么是决策树
决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internal node）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（class distribution），最上面的结点是根结点。
决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。
4
〖例〗图9-2 给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意向。
图9-2 buys_computer的决策树
这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：
buys_computers=yes 或者
buys_computers=no
在这个例子中，样本向量为：
（age, student, credit_rating; buys_computers）
被决策数据的格式为:
（age, student, credit_rating）
输入新的被决策的记录，可以预测该记录隶属于哪个类。
5
2. 使用决策树进行分类
构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。
决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a = b)的逻辑判断，其中a 是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。
使用决策树进行分类分为两步：
●第1步：利用训练集建立并精化一棵决策树，建立决策树模型。
这个过程实际上是一个从数据中获取知识，进行机器学习的过程。
●第2步：利用生成完毕的决策树对输入数据进行分类。对输入
的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。
问题的关键是建立一棵决策树。这个过程通常分为两个阶段：●建树（Tree Building）：决策树建树算法见下，可以看得出，这
是一个递归的过程，最终将得到一棵树。
6
剪枝（Tree Pruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。
9.3 分类规则挖掘的ID3算法
由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树归纳（Induction of Decision Tree）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。
1. ID3算法的基本思想
由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最好”的决策树是一个NP完全问题。
ID3使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树—可能不是最简单的。
ID3算法的基本思想描述如下：
step 1．任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；
step 2．用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果
7
所有的叶结点都有类标记，则算法终止；
step 3．否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤step 2；
这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分支决策树的那个属性。
2. ID3算法的描述
算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练数据集samples，用离散值属性表示；候选属性的集合attribute_list。
输出：一棵决策树
方法：
（1）创建结点N；
（2）if samples 都在同一个类C then
（3）返回N作为叶结点，用类C标记；
（4）if attribute_list 为空then
（5）返回N作为叶结点，标记samples中最普通的类；
//多数表决
（6）选择attribute_list中具有最高信息增益的属性test_attribute；//用信息增益作为属性选择度量
（7）标记结点N为test_attribute；
（8）for each test_attribute中的已知值ai //划分samples （9）由结点N生长出一个条件为test_attribute＝ai的分枝；
8
（10）设si为samples中test_attribute＝ai的样本集合；
//一个划分
（11）if si为空then
（12）加上一个叶结点，标记为标记samples中最普通的类；
//多数表决
（13）else 加上一个由Generate_decision_tree（si, attribute_list-test_attribute）返回的结点；
2. 属性选择度量
在Generate_decision_tree算法的Step 6，算法需选择attribute_list中具有最高信息增益的属性test_attribute。ID3算法在树的每个结点上以信息增量（information gain）作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。
Information Gain指标的原理来自于信息论。1948年，香农（C. E. Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。
设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci（i=1,2,…,m），si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：
I (s1, s2, … , s m)＝－ΣM i=1 pi log2(pi)
i
9
其中pi是任意样本属于Ci的概率，可用si/s来估计。
设属性A具有k个不同值{a1,a2,…,ak}，则可用属性A将S划分为k个子集{S1,S2,…,Sk}，Sj中包含的样本在属性A上具有值aj。如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分枝。设s ij是子集Sj中类Ci的样本数，则按照A划分成子集的熵为：
E（A）＝ΣM i=1（（s1j+ s2j +…+s mj）/ s1j）* I (s1, s2, … , s m)
信息增益（Information Gain），表示系统由于分类获得的信息量。由系统熵的减少值定量描述。用属性A分类后的信息增益为：
Gain(A) = I (s1, s2, … , s m) – E(A)
熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是Information Gain，所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，这个最佳方案是用“贪心算法+深度优先搜索”得到的。
因为这是一个递归过程，所以仅仅需要讨论对某个特定结点N 的分裂方法。
（1）分裂前
10
设指向N的训练集为S，其中包含m个不同的类，它们区分了不同的类C i (for i=1, … , m)。设s i是S中属于类C i的记录的个数。那么分裂之前，系统的总熵：
I (s1, s2, … , s m) = -∑M i=1 p i log2(p i)
容易看出，总熵是属于各个类的记录的信息量的加权平均。（2）分裂后
现在属性A是带有k个不同值的属性{ a1,a2,…a k }，A可以把S分成k个子集{S1, S2, …, S k}其中S j = {x | x∈S & x.A = a j}。如果A被选为测试属性，那么那些子集表示从代表集合S的出发的所有树枝。设s ij表示在S j中类为C i的记录个数。那么，这时按A的每个属性值（更一般的是取A的一个子集）进行分裂后的信息量，也就是系统总熵为：
E(A) = ∑k j=1 ((s1j+s2j+..+s mj)/s) * I(s1j+s2j+..+s mj) ((s1j+s2j+..+s mj)/s)表示第j个子集的权重，s = | S |。子集Sj的信息量（子集的总熵）：
I(s1j+s2j+..+s mj) = -∑M i=1p ij log2(p ij)
总熵E(A)是各个子集信息量的加权平均。
算法计算每个属性的信息增益，具有最高信息增益的属性选择作为给定训练数据集合S的测试属性。创建一个结点，并以该属性为标记，对属性的每一个值创建分枝，并据此划分样本。
〖例〗顾客数据库训练数据集如下表所示：
11
12 计算每一个属性的信息增益：
Gain（age）=I（s2,s2）－E（age）=0.246
Gain（income）= 0.029
Gain（student）= 0.151
Gain（credit _rating）=0.048
由于属性age 在所有属性中具有最高的信息增益，因此它被
选择为测试属性。创建一个以age为标记的结点，并对每一个属性值引出一个分枝。落在分枝age=“31…40”的样本都属于同一类“yes”,该分枝的端点应该创建一个叶结点。
……
3. 剪枝
剪枝常常利用统计学方法，去掉最不可靠、可能是噪音的一
些枝条。剪枝方法主要有两类：同步修剪和迟滞修剪。
（1）先剪枝（pre-pruning）
在建树的过程中，当满足一定条件，例如Information Gain 或者某些有效统计量达到某个预先设定的阈值时，结点不再继续分裂，内部结点成为一个叶结点。叶结点取子集中频率最大的类作为自己的标识，或者可能仅仅存储这些实例的概率分布函数。
（2）后剪枝（pos-pruning）
与建树时的训练集独立的训练数据进入决策树并到达叶结点时，训练数据的class label与叶结点的class label不同，这时称为
发生了分类错误。当树建好之后，对每个内部结点，算法通过每个
枝条的出错率进行加权平均，计算如果不剪枝该结点的错误率。如
果裁减能够降低错误率，那么该结点的所有儿子就被剪掉，而该结
13
点成为一片叶。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能小的决策树。
如果在测试集中出现了类交叉的情况，也就是说，在待挖掘的数据中出现矛盾和不一致的情况。则在算法步骤3中将出现这样一种情况：在一个树结点中，所有的实例并不属于一个类却找不到可以继续分支的属性。ID3使用以下两种方案解决这个问题：
①选择在该结点中所占比例最大的类为标记标识该结点；
②根据该结点中不同类的概率分布为标记一一标识该结点。
如果在测试集中出现了某些错误的实例，也就是说，在待挖掘的数据中，本来应该属于同一结点的数据因为某些错误的属性取值而继续分支。则在最终生成的决策树中可能出现分支过细和错误分类的现象。ID3设置了一个阈值来解决这个问题：只有属性的信息量超过这个阈值时才创建分支，否则以类标志标识该结点。该阈值的选取对决策树的正确创建具有相当的重要性。如果阈值过小，可能没有发挥应有的作用；如果阈值过大，又可能删除了应该创建的分支。
4. 由决策树提取分类规则
可以提取由决策树表示的分类规则，并以IF－THEN的形式表示。具体方法是：从根结点到叶结点的每一条路径创建一条分类规则，路径上的每一个“属性－值”对为规则的前件（即IF部分）的一个合取项，叶结点为规则的后件（即THEN部分）。
〖例〗对于buys_computer的决策树可提取以下分类规则：
14
15 IF age ＝‘<=30’AND student ＝‘no ’
THEN buys_computer ＝‘no ’
IF age ＝‘<=30’AND student ＝‘yes ’
THEN buys_computer ＝‘yes ’
IF age ＝‘30…40’ THEN buys_computer ＝‘yes ’
IF age ＝‘>40’AND credit _rating ＝‘excellent ’
THEN buys_computer ＝‘no ’
IF age ＝‘>40’AND credit _rating ＝‘fair ’
THEN buys_computer ＝‘yes ’
5. ID3算法的改进
（1）离散化
ID3算法对符号性属性的知识挖掘比较简单，也就是说，该
算法对离散性属性的挖掘更为直观。算法将针对属性的所有符号
创建决策树分支。但是，如果属性值是连续性的，如一个人的身
高，体重等，如果针对属性的所有不同的值创建决策数，则将由
于决策树过于庞大而使该算法失效。
为了解决该问题，在用ID3算法挖掘具有连续性属性的知
识时，应该首先把该连续性属性离散化。最简单的方法就是把属
性值分成N A i ≤和N A i >两段。如身高可以分为1米以下，1米以
上或者分为1.5米以下，1.5米以上。如何选择最佳的分段值呢？
对任何一个属性，其所有的取值在一个数据集中是有限的。假设
16
该属性取值为()m v v v ,,,21 ，则在这个集合中，一共存在m-1个分
段值，ID3算法采用计算信息量的方法计算最佳的分段值，然后
进一步构建决策树。
（2）属性选择度量
ID3算法中采用信息增量作为属性选择度量，但它仅适合于
具有许多值的属性。已经提出了一些其他的属性选择度量方法，
如增益率，它考虑了每个属性的概率。
（3） 空缺值处理
常用的空缺值处理方法有：若属性A 有空缺值，则可用
A 的最常见值、平均值、样本平均值等填充。
（4） 碎片、重复和复制处理
通过反复地将数据划分为越来越小的部分，决策树归纳
可能面临碎片、重复和复制等问题。所谓碎片是指在一个给
定的分枝中的样本数太少，从而失去统计意义。
解决的方法是：将分类属性值分组，决策树结点可以测
试一个属性值是否属于给定的集合。另一种方法是创建二叉
判定树，在树的结点上进行属性的布尔测试，从而可以减少
碎片。
当一个属性沿树的一个给定的分枝重复测试时，将出现
重复。复制是拷贝树中已经存在的子树。通过由给定的属性
构造新的属性（即属性构造），可以防止以上问题的发生。
（5） 可伸缩性
ID3算法对于相对较小的训练数据集是有效的，但对于
现实世界中数据量很大的数据挖掘，有效性和可伸缩性将成
为必须关注的问题。面临数以百万计的训练数据集，需要频
繁地将训练数据在主存和高速缓存换进换出，从而使算法的
性能变得低下。
解决的方法是：将训练数据集划分为子集，使得每个子集能够放在内存；然后由每个子集构造一棵决策树；最后，将每个子集得到的分类规则组合起来，得到输出的分类规则。
最近，已经提出了一些强调可伸缩性的决策树算法，如：SLIQ、SPRINT等。这两种算法都使用了预排序技术，并采用了新的数据结构，以利于构造决策树。
ID3算法对大部分数据集有效，但它不能挖掘域知识。同时，决策树在计算机中存储的方式决定了该分类规则相对于其他形式的分类规则（如公式）而言更晦涩难懂。因此，一般在算法结束后，需要把决策树以用户可视的方法显示出来。
〖例〗以下表所示的训练数据集为例，其中Salary为工资，Education为教育程度，Class为信用级别。假设以20，000作为Salary的分段值，则创建的决策树如图9-3所示；假设以16，000作为Salary的分段值，则创建的决策树如图9-4所示。
训练数据集T
17
图9.3 分段值为20，000的决策树
图9.4 分段值为16，000的决策树
由图9.3和图9.4可以看出，Salary的分段值不一样，构建的决策树也不一样。
18
6. 决策树方法的评价
与其他分类算法相比，决策树有如下优点：
（1）速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。例如，沿着结点Age->Credit Rating->no走下来就能得到一条谓词：
if there is a person (age>40) and (credit rating is excellent) then he will not buy a computer.
（2）准确性高：挖掘出的分类规则准确性高，便于理解。
一般决策树的劣势：
（1）缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。
（2）为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性。
19
9.4 分类规则挖掘的其他算法
9.4.1 分类规则挖掘的C4.5算法
1. C4.5算法概述
C4.5算法是ID3算法的扩展，但是它比ID3算法改进的部分是它能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个属性Gian值的大小。
2. "离散化"的方法
把连续型属性值"离散化"的具体方法是：
1）寻找该连续型属性的最小值，并把它赋值给MIN，
寻找该连续型属性的最大值，并把它赋值给MAX；
2）设置区间[MIN，MAX] 中的N个等分断点Ai，它们分别是Ai = MIN + （（MAX – MIN）/ N）* i
其中，i = 1 , 2 , ... , N
3）分别计算把[MIN，Ai]和（Ai，MAX）（i = 1 ,2 , ... , N）作为区间值时的Gain值，并进行比较
4）选取Gain值最大的Ak做为该连续型属性的断点，把属性值设置为[MIN，Ak]和（Ak，MAX）两个区间值。
3. Gain函数
决策树是建立在信息理论（Information Theory）的基础上的，
决策树的方法循环地寻找某一标准，它能够带来与本次分类相关的
20