《数据仓库与数据挖掘》(分类规则)

第9章

分类规则挖掘与预测

主要内容

•分类与预测的基本概念

•决策树方法

•分类规则挖掘的ID3算法

•其他分类规则挖掘算法

•分类规则的评估

・微软决策树及其应用

第9章分类规则挖掘与预测

9.1分类与预测的基本概念

1.什么是分类

2

数据分类(dataclassfication)是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产

生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。

数据分类(dataclassfication)是一个两个步骤的过程：

•第1步：建立一个模型，描述给定的数据类集或概念集(简称训练集)。通过分析由属性描

述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立

模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此

该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习(聚类)。

学习模型可用分类规则、决策树和数学公式的形式给出。

•第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组

按模型进行分类。

---------

i分类规则

训练数二5分类算法占-17

坦---------------1--

模型评估R________三

新数据分

一

测试数u―___J

新数

—_

___

第9章分类规则挖掘与预测

(b)分类

图9-1数据分类过程

2.常用的分类规则挖掘方法

分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用

于不同特点的数据：

•决策树方法

•贝叶斯方法

•人工神经网络方法

•约略集方法

•遗传算法

典型的分类规则挖掘算法有：

•ID3

•C4.5

DBlearn等

4

3.什么是预测

预测(prediction)是构造和使用模型评估无标号样本类，或评估给定的样本可能具有的属性或

区间值。分类和回归是两类主要的预测问题。分类是预测离散值，回归用于预测连续或有序值。

4.分类和预测数据的预处理

•数据清理：使用平滑技术消除或减少噪声；处理空缺值。

•相关性分析：删除与分类或预测无关的属性；删除冗余属性。

•数据变换：使用概念分层将数据概化到高的层次；连续值属性概化为离散区间；数据规范化，即

将某一属性的所有值按比例缩放，使其落入指定的区间。

5.分类方法的评估标准

•准确率：模型正确预测新数据类标号的能力。

•速度：产生和使用模型花费的时间。

•健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。

•伸缩性：对于给定的大量数据，有效地构造模型的能力。

•可解释性：学习模型提供的理解和观察的层次。

第9章分类规则挖掘与预测

9.2决策树方法

决策树方法的起源是概念学习系统CLS,然后发展到由Quiulan研制ID3方法，然后到著名的C4.5

算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策

树方法。

1.什么是决策树

决策树(DecisionTree)又称为判定树，是运用于分类的一种树结构。其中的每个内部结点(internalnode)

代表对某个属性的一次测试，每条边代表一个测试结果，叶结点(leaf)代表某个类(class)或者类的分布

(classdistribution),最上面的结点是根结点。

决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的

一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。

K例』图9-2给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PC

(buys-computer)的知识，用它可以预测某条记录(某个人)的购买意向。

图9-2buys_computer的决策树

这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机"buys_computer”。

每个内部结点(方形框)代表对某个属性的一次检测。每个叶结点(椭圆框)代表一个类：

buys_computers=yes或者

buys_computers=no

在这个例子中，样本向量为：

(age,student,credit_rating;buys_computers)

被决策数据的格式为：

(age,student,credit_rating)

第9章分类规则挖掘与预测

输入新的被决策的记录，可以预测该记录隶属于哪个类。

2.使用决策树进行分类

构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属

性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各

个子集。反之，则作为叶结点。

决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点

（非叶结点）一般表示为一个逻辑判断，如形式为（a=b）的逻辑判断，其中a是属性，b是该属性的某个属

性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个

属性值，就有几条边。树的叶结点都是类别标记。

使用决策树进行分类分为两步：

•第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取

知识，进行机器学习的过程。

•第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性

值，直到到达某个叶结点，从而找到该记录所在的类。

问题的关键是建立一棵决策树。这个过程通常分为两个阶段：

•建树（TreeBuilding）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。

8

•剪枝(TreePruning)：剪枝是目的是降低由于训练集存在噪声而产生的起伏。

9.3分类规则挖掘的ID3算法

由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树

归纳(InductionofDecisionTree)。早期的ID算法只能就两类数据进行挖掘(如正类和反类)；经过

改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具

有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。

LID3算法的基本思想

由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特

定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一

般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分

类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最

好”的决策树是一个NP完全问题。

ID3使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树一可

能不是最简单的。

TD3算法的基本思想描述如下：

step1.任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；

第9章分类规则挖掘与预测

step2.用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为

标记标识此叶结点；如果所有的叶结点都有类标记，则算法终止；

step3.否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性

所有的取值继续创建树的分支；重复算法步骤step2；

这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。

显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。

在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高

信息量的属性，也就是说，生成最少分支决策树的那个属性。

2.ID3算法的描述

算法：Generate_decision_tree由给定的训练数据产生一棵决策树

输入：训练数据集samples,用离散值属性表示；候选属性的集合attribute_list。

输出：一棵决策树

方法：

(1)创建结点N；

(2)ifsamples都在同一个类Cthen

10

(3)返回N作为叶结点，用类C标记；

(4)ifattribute_list为空then

(5)返回N作为叶结点，标记samples中最普通的类；

〃多数表决

(6)选择attributejist中具有最高信息增益的属性test_attribute；〃用信息增益作为属性选择度量

(7)标记结点N为test_attribute；

(8)foreachtest_attribute中的已知值ai〃划分samples

(9)由结点N生长出一个条件为test_attribute=ai的分枝；

(10)设si为samples中test_attribute=ai的样本集合；

〃一个划分

(11)ifsi为空then

(12)加上一个叶结点，标记为标记samples中最普通的类；

〃多数表决

(13)else力口上一个由Generate_decision_tree(si,attribute_list-test_attribute)返回的结点；

2.属性选择度量

在Generate_decision_tree算法的Step6,算法需选择attributejist中具有最高信息增益的属性

第9章分类规则挖掘与预测

test_attributeoID3算法在树的每个结点上以信息增量(informationgain)作为度量来选择测试属性。

这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益(或最大牖压缩)的属性作

为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵

简单的(但不一定是最简单的)决策树。

InformationGain指标的原理来自于信息论。1948年，香农(C.E.Shannon)提出了信息论。其中给出了

关于信息量(Information)和埔(Entropy)的定义，端实际上是系统信息量的加权平均，也就是系统的

平均信息量。

设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci

si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：

I(S1,S2,...,Sm)=—sMi=ipilog2(pi)i

其中pi是任意样本属于Ci的概率，可用si/s来估计。

设属性A具有k个不同值{al,a2,…,ak},则可用属性A将S划分为k个子集{S1,S2,…,Sk},Sj中包含的

样本在属性A上具有值ajo如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的

分枝。设su是子集Sj中类Ci的样本数，则按照A划分成子集的端为：

M

E(A)=Sj=i((Slj+S2j+...+Srnj)/Slj)*I(Sl,S2,...,Sm)

信息增益(InformationGain),表示系统由于分类获得的信息量。由系统牖的减少值定量描述。用属性

A分类后的信息增益为：

12

Gain(A)=I(si,s2,...,sm)-E(A)

牖是一个衡量系统混乱程度的统计量。燃越大，表示系统越混乱。分类的目的是提取系统信息，使

系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使埔减少量最大的分裂方

案。燧减少量就是InformationGain,所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，这个最佳方

案是用“贪心算法+深度优先搜索”得到的。

因为这是一个递归过程，所以仅仅需要讨论对某个特定结点N的分裂方法。

(1)分裂前

设指向N的训练集为S,其中包含m个不同的类，它们区分了不同的类G(fori=l,…，m)。设由是S

中属于类G的记录的个数。那么分裂之前，系统的总埔：

I(Sl,S2,...,Sm)="LMi=lPiIOg2(Pi)

容易看出，总燧是属于各个类的记录的信息量的加权平均。

(2)分裂后

现在属性A是带有k个不同值的属性{ai,a2,…ak},A可以把S分成k个子集{Si,S2,Sk}其中&={x

|Xes&X.A=aj}0如果A被选为测试属性，那么那些子集表示从代表集合S的出发的所有树枝。设Sij表

示在&中类为G的记录个数。那么，这时按A的每个属性值(更一般的是取A的一个子集)进行分裂后

的信息量，也就是系统总烯为：

E(A)=j=i((sij+S2j+..+smj)/s)*I(sij+S2j+..+smj)

((Slj+S2j+“+Smj)/S)表示第j个子集的权重，S=|S|o子集Sj的信息量(子集的总埔)：

I(Slj+S2j+..+Smj)="1\=1PijIOg2(Pij)

第9章分类规则挖掘与预测

总端E(A)是各个子集信息量的加权平均。

算法计算每个属性的信息增益，具有最高信息增益的属性选择作为给定训练数据集合S的测试属性。创

建一个结点，并以该属性为标记，对属性的每一个值创建分枝，并据此划分样本。

K例U顾客数据库训练数据集如下表所示：

RIDageincomestudentcredit_ratingClass:

Buys_computer

1<=30highnofairno

2<=30highnoexcellentno

331…40highnofairyes

4>40mediumnofairyes

5>40lowyesfairyes

6>40lowyesexcellentno

731…40lowyesexcellentyes

8<=30mediumnofairno

9<=30lowyesfairyes

10>40mediumyesfairyes

11<=30mediumyesexcellentyes

1231...40mediumnoexcellentyes

1331…40highyesfairyes

14>40mediumnoexcellentno

计算每一个属性的信息增益：

Gain(age)=1(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”，该分枝的

端点应该创建一个叶结点。

31...40

incomestudent--c-r--e-d;-il-^--^^^^Class

Crating>

highnofairno

highnoexcellentno

mediumnofairno

lowyesfairyes

mediumyesexcellentyes

3.剪枝

剪枝常常利用统计学方法，去掉最不可靠、可能是噪音的一些枝条。剪枝方法主要有两类：同步修剪

和迟滞修剪。

第9章分类规则挖掘与预测

(1)先剪枝(pre-pruning)

在建树的过程中，当满足一定条件，例如InformationGain或者某些有效统计量达到某个预先设定

的阈值时，结点不再继续分裂，内部结点成为一个叶结点。叶结点取子集中频率最大的类作为自己的标识,

或者可能仅仅存储这些实例的概率分布函数。

(2)后剪枝(pos-pruning)

与建树时的训练集独立的训练数据进入决策树并到达叶结点时，训练数据的classlabel与叶结点的

classlabel不同，这时称为发生了分类错误。当树建好之后，对每个内部结点，算法通过每个枝条的出错

率进行加权平均，计算如果不剪枝该结点的错误率。如果裁减能够降低错误率，那么该结点的所有儿子就

被剪掉，而该结点成为一片叶。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能

小的决策树。

如果在测试集中出现了类交叉的情况，也就是说，在待挖掘的数据中出现矛盾和不一致的情况。

则在算法步骤3中将出现这样一种情况：在一个树结点中，所有的实例并不属于一个类却找不到可

以继续分支的属性。ID3使用以下两种方案解决这个问题：

①选择在该结点中所占比例最大的类为标记标识该结点；

②根据该结点中不同类的概率分布为标记一一标识该结点。

如果在测试集中出现了某些错误的实例，也就是说，在待挖掘的数据中，本来应该属于同一结

点的数据因为某些错误的属性取值而继续分支。则在最终生成的决策树中可能出现分支过细和错误

分类的现象。ID3设置了一个阈值来解决这个问题：只有属性的信息量超过这个阈值时才创建分支，

否则以类标志标识该结点。该阈值的选取对决策树的正确创建具有相当的重要性。如果阈值过小，

可能没有发挥应有的作用；如果阈值过大，又可能删除了应该创建的分支。

4.由决策树提取分类规则

可以提取由决策树表示的分类规则，并以IF—THEN的形式表示。具体方法是：从根结点到叶

结点的每一条路径创建一条分类规则，路径上的每一个“属性一值”对为规则的前件（即IF部分）

的一个合取项，叶结点为规则的后件（即THEN部分）。

K例U对于buys_computer的决策树可提取以下分类规则:

IFage='<=30'ANDstudent='no'

THENbuys_computer='no'

IFage='<=30'ANDstudent='yes'

THENbuys_computer='yes

IFage=30...40'THENbuys_computer=yes

IFage='>40'ANDcredit_rating=*excellent?

第9章分类规则挖掘与预测

THENbuys_computer='no'

IFage='>40'ANDcredit_rating='fair'

THENbuys_computer='yes'

5.ID3算法的改进

（1）离散化

ID3算法对符号性属性的知识挖掘比较简单，也就是说，该算法对离散性属性的挖掘更为直观。

算法将针对属性的所有符号创建决策树分支。但是，如果属性值是连续性的，如一个人的身高，体重

等，如果针对属性的所有不同的值创建决策数，则将由于决策树过于庞大而使该算法失效。

为了解决该问题，在用ID3算法挖掘具有连续性属性的知识时，应该首先把该连续性属性离散化。

最简单的方法就是把属性值分成4WN和A,>N两段。如身高可以分为1米以下，1米以上或者分为1.5

米以下，1.5米以上。如何选择最佳的分段值呢？对任何一个属性，其所有的取值在一个数据集中是有

限的。假设该属性取值为（匕»，•・”,■），则在这个集合中，一共存在m-1个分段值，ID3算法采用计算信

18

息量的方法计算最佳的分段值，然后进一步构建决策树。

(2)属性选择度量

ID3算法中采用信息增量作为属性选择度量，但它仅适合于具有许多值的属性。已经提出了一些

其他的属性选择度量方法，如增益率，它考虑了每个属性的概率。

(3)空缺值处理

常用的空缺值处理方法有：若属性A有空缺值，则可用A的最常见值、平均值、样本平均值

等填充。

(4)碎片、重复和复制处理

通过反复地将数据划分为越来越小的部分，决策树归纳可能面临碎片、重复和复制等问题。所

谓碎片是指在一个给定的分枝中的样本数太少，从而失去统计意义。

解决的方法是：将分类属性值分组，决策树结点可以测试一个属性值是否属于给定的集合。另

一种方法是创建二叉判定树，在树的结点上进行属性的布尔测试，从而可以减少碎片。

当一个属性沿树的一个给定的分枝重复测试时，将出现重复。复制是拷贝树中已经存在的子树。

通过由给定的属性构造新的属性(即属性构造)，可以防止以上问题的发生。

(5)可伸缩性

ID3算法对于相对较小的训练数据集是有效的，但对于现实世界中数据量很大的数据挖掘，有

效性和可伸缩性将成为必须关注的问题。面临数以百万计的训练数据集，需要频繁地将训练数据在

主存和高速缓存换进换出，从而使算法的性能变得低下。

第9章分类规则挖掘与预测

解决的方法是：将训练数据集划分为子集，使得每个子集能够放在内存；然后由每个子集构造

一棵决策树；最后，将每个子集得到的分类规则组合起来，得到输出的分类规则。

最近，已经提出了一些强调可伸缩性的决策树算法，如：SLIQ、SPRINT等。这两种算法都

使用了预排序技术，并采用了新的数据结构，以利于构造决策树。

ID3算法对大部分数据集有效，但它不能挖掘域知识。同时，决策树在计算机中存储的方式决

定了该分类规则相对于其他形式的分类规则（如公式）而言更晦涩难懂。因此，一般在算法结束后，

需要把决策树以用户可视的方法显示出来。

K例X以下表所示的训练数据集为例，其中Salary为工资，Education为教育程度，Class为信用

级别。假设以20,000作为Salary的分段值，则创建的决策树如图9-3所示；假设以16,000作为

Salary的分段值，则创建的决策树如图9-4所示。

SalaryEducationClass

10,000高中一般

20

40,000学士较好

15,000学士一般

75,000硕士较好

18,000硕士较好

训练数据集T

第9章分类规则挖掘与预测

图9.3分段值为20,000的决策树

图9.4分段值为16,000的决策树

由图9.3和图9.4可以看出，Salary的分段值不一样，构建的决策树也不一样。

6.决策树方法的评价

22

与其他分类算法相比，决策树有如下优点：

(1)速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件

就能够唯一确定一条分类的谓词。例如，沿着结点Age->CreditRating->no走下来就能得到一条谓词：

ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuya

computer.

(2)准确性高：挖掘出的分类规则准确性高，便于理解。

一般决策树的劣势：

(1)缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在

Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB,2000条记录。而现代的数据仓库动辄存

储几个G-Bytes的海量数据。用以前的方法是显然不行的。

(2)为了处理大数据集或连续量的种种改进算法(离散化、取样)不仅增加了分类算法的额外开销，而且

降低了分类的准确性。

9.4分类规则挖掘的其他算法

9.4.1分类规则挖掘的C4.5算法

1.C4.5算法概述

C4.5算法是ID3算法的扩展，但是它比ID3算法改进的部分是它能够处理连续型的属性。首先将连续型

属性离散化，把连续型属性的值分成不同的区间，依据是比较各个属性Gian值的大小。

2.，，离散化”的方法

把连续型属性值“离散化”的具体方法是：

第9章分类规则挖掘与预测

1)寻找该连续型属性的最小值，并把它赋值给MIN,

寻找该连续型属性的最大值，并把它赋值给MAX；

2)设置区间［MIN,MAX］中的N个等分断点Ai,它们分别是

Ai=MIN+((MAX-MIN)/N)*i

其中，i=l,2,...,N

3)分别计算把［MIN,Ai］和(Ai,MAX)(i=1,2,,N)作为区间值时的Gain值，并进行比较

4)选取Gain值最大的Ak做为该连续型属性的断点，把属性值设置为［MIN,Ak］和(Ak,MAX)两个区

间值。

3.Gain函数

决策树是建立在信息理论(InformationTheory)的基础上的，决策树的方法循环地寻找某一标准，它

能够带来与本次分类相关的最大信息。构造好的决策树的关键在于如何选择好的属性。对于同样一组记录集,

可以有很多决策树能符合这组记录集。人们研究出，一般情况下，树越小则树的预测能力越强。要构造尽可

能小的决策树，关键在于选择恰当属性。属性选择依赖于各种对例子子集的不纯度(impurity)度量方法。

不纯度度量方法包括信息增益(informatingain)、信息增益比(gainratio)、Gini-index、距离度量(distance

measure)>J-measure、G统计、x2统计、证据权重(weightofevidence)、最小描述长(MLP)、正交法

(ortogonalitymeasure相关度(relevance)和Reliefo不同的度量有不同的效果，特别是对于多值属性。

C4.5算法使用信息增益(informationgain)的概念来构造决策树，其中每个分类的决定都与前面所选择的

目标分类有关。

24

(1)信息理论(InformationTheory)和墉(Entropy)

考虑一个任意的变量，它有两个不同的值A和B。假设已知这个变量不同值的概率分配，将估测该概率分配

的不纯度。

情况1.如果P(A)=1和P(B)=0,那么知道这个变量的值一定为A,不存在不纯度，因此已知变量结果

值不会带来任何的信息。

情况2.如果P(A)=P(B)=0.5,那么它的不纯度明显地高于P(A)=0.1和P(B)=0.9的情况。在这

种情况下，已知变量的结果值就会携带信息。

不纯度的最佳评估方法是平均信息量，也就是信息端(Entropy)：

S=-S(pi*log(Pi))

在上面的例子中，情况1和情况2的信息燧分别是：

S1=-(1*log1+0*log0)=0

S2=-(0.5*log0.5+0.5*log0.5)=0.301

(2)信息增益(informationgain)

信息增益是指信息端的有效减少量(通常用“字节”衡量)，根据它能够确定在什么样的层次上选择什么

样的变量来分类。

4.C4.5算法描述

FunctionC4.5(R:asetofnon-goalattributessomeofwhichwithcontinuousvalues,

C:thegoalattribute,

S:atrainingset)returnsadecisiontree;

begin

IfSisemptythen

第9章分类规则挖掘与预测

returnasinglenodewithvalueFailure;

IfSconsistsofrecordsallwiththesamevalueforthegoalattributethen

returnasinglenodewiththatvalue;

IfRisemptythen

returnasinglenodewithasvaluethemostfrequentofthevaluesofthegoalattribute

thatarefoundinrecordsofS;

[notethatthentherewillbeerrors,thatis,recordsthatwillbeimproperlyclassified];

forallattributesofR(Ri)do

ifvaluesofRiarecontinuousthen

begin

LetAlbetheminimumofRi;

LetAmbethemaximumofRi;{m值手工设置}

forjfrom2tom-1doAj=Al+j*(Al-Am)/m;

LetAbethevaluepointofRiwithlargestGain(Ri,S)based

on{<=Aj,>Aj};

end;

LetDbetheattributewithlargestGain(D,S)

amongattributesinR;

Let{dj|j=l,2,m}bethevaluesofattributeD;

26

Let{Sj|j=l,2,m}bethesubsetsofSconsisting

respectivelyofrecordswithvaluedjforattributeD;

ReturnatreewithrootlabeledDandarcslabeled

dl,d2,dmgoingrespectivelytothetrees

C4.5(R-{D},C,SI),C4.5(R-{D},C,S2),C4.5(R-{D},C,Sm);

endC4.5o

但是，所用的基于分类挖掘的决策树算法没有考虑噪声问题，生成的决策树很完美，这只不过是理论

上的，在实际应用过程中，大量的现实世界中的数据都不是以的意愿来定的，可能某些字段上缺值(missing

values)；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。另外决策树

技术本身也存在一些不足的地方，例如当类别很多的时候，它的错误就可能出现甚至很多。而且它对连续性

的字段比较难作出准确的预测。而且一般算法在分类的时候，只是根据一个属性来分类的。

在有噪声的情况下，完全拟合将导致过分拟合(overfitting),即对训练数据的完全拟合反而不具有很

好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。另外，决策树技

术也可能产生子树复制和碎片问题。

在算法具体实现时必须考虑以上这些问题。

9.4.2DBlearn算法

1.DBlearn算法概述

DBlearn算法用域知识生成基于关系数据库的预定义子集的描述。DBlearn算法采用自底向上的

搜索策略，使用以属性层次形式的域知识，同时该算法使用了关系代数。该算法的事务集是一个关系

第9章分类规则挖掘与预测

表，即一个具有若干个属性的n元组。

系统采用关系表作为知识结构：对每一类，它构建一个关系表。这个关系表的属性是实例集属性的子

集。一个元组可以看作是一个属性值关联的逻辑公式。搜索空间的开始是整个实例集，而最终目的是

为了生成一个类描述的表。类描述表的大小不能超过用户定义的阈值。阈值的大小决定了类描述表的

大小。如果阈值太小，则生成的规则更简单，但同时也可以能丢失了一些有用的信息从而产生过度一

般化的问题；如果阈值太大，则生成的规则比较详细，但同时也可能产生没有完全一般化和规则复杂

的问题。

一些属性域被局部排序从而构成一个层次结构，每一个值都是该值所在层次下面全部值的一般

化。

在从关系表中生成分类规则时，DBIearn算法使用了两个基本的算子：

(1)删除：如果在关系表中有属性之间存在着关联关系，则删除直到只剩下彼此互不关联的属性。

如年龄和出生年月这两个属性存在着年龄=现在时间一出生年月的关联关系，因此必须删除其中一个

属性，保留另一个属性。

(2)一般化：属性的值被一般化为层次在它之上的值从而生成规则。如就年龄这个属性而言，5岁以

下都可以一般化为幼年，5-12岁可以一般化为童年等。

28

在一个关系表上运行以上两个算子有可能产生完全一样的元组，DBlearn算法通过删除多余的

元组来缩减关系表的大小从而得到类描述表。

2.DBlearn算法描述

DBlearn算法创建一个完全但不一定一致的分类规则，即该分类规则覆盖所有的实例集（包括那

些错误的实例）。

DBlearn算法描述如下：

stepl.从数据库中选择和任务相关的数据，如一个包含且只包含一类数据的数据表。

step2.在该数据表上执行一般化操作：如果在某个属性上存在很多不同的值同时提供了一个更高级

别的值，则该属性被一般化为更高级别的值；如果在某个属性上存在很多不同的值而不能提供一个更

高级别的值，则该属性被删除。删除重复的元组直到表的大小达到用户定义的阈值。

step3.简化结果。例如，如果该数据表上的一些元组除了一个属性不一样，其他的属性值都是一模

一样的，而这个不一样的属性的取值可以一般化为一个更高层次的符号且这个属性的取值范围包含了

该更高层次符号所代表的全部数据。则这些元组可以用一个元组代替，这个元组的属性就是那个不一

样的属性，它的值用那个符号表示。

step4.把这个数据表转换成公式。

DBlearn算法是一个相对比较简单的分类规则挖掘算法，通过对属性取值不断进行一般化操作从而最

终获得规则。在数据挖掘的过程中，该算法是域知识挖掘的一个典型例子。该算法经过改进可以挖掘

那些包含噪声数据的不纯净数据，同时可以做增量学习。

第9章分类规则挖掘与预测

9.4.3分类规则挖掘的OC1算法

1.OC1算法概述

OC1算法是ObliqueClassifier1的缩写，即斜面分类1算法。它基于线性规划的理论，以斜面

超平面的思想为基础，采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树。

在执行OC1决策树算法前，首先需要对搜索空间做净化和清理工作以消除条件属性间的函数依

赖关系。净化后的搜索空间中的每一个元组(记录)可以看作是一个m+1维向量(％,小…,%，0,其中

匕(IViKm)对应于第i个实数类型的条件属性，c对应于决策属性(元组的类)。所有的条件属性可以

看作是一个m维向量(i2,…，匕“)。

K定义HR"是一个n维欧几里得空间，设peR"且p#0,be*,则集合｛xIpOi.R"｝称为中的一

个超平面(*4)。(当n=2时，集合确定一条直线；当n=3时，集合确定一个平面。)

(定义H一个超平面将R"分成两个半空间，记为『(A/)=。|人。2份和犷(4力)=。|4。")。其中H"b)

是R"中满足4U泊的向量U构成的半空间，是R"中满足4UW。的向量U构成的半空间。

k定义1一组单位向量(1,0,0,0),(0,1,0,0),(0,0,0,1)是R"中的一组

30

基，用符号当，配，…，，来表示该组单位向量。

K定义X设「是一个超平面，如果p7=W,（lKiK〃），则「是一个轴平行超平面，否则「是一个斜面超平

面。

K引理》ID3决策树的每一个结点等价于一个轴平行超平面。（证明略）

大部分决策树都是在每一个结点检查某个属性的值，或者对该数值属性进行分段检查。因此，称

这种决策树为“轴平行”决策树。

K定理H用超平面把一组n个的d维向量分成两个半空间，如果n>d+l则存在2*汇：=0（泮））种方法；

如果n<d+l则存在2"种方法。

（证明略）

2.0C1算法的基本思想

根据以上定理，最多存在有限种不同的决策树。从理论上可以采用一种穷举的方法来寻找一棵最

优决策树，但在实际中这是不可行的算法。如前所述，寻找一棵最优决策树是一个NP完全问题。寻

找一棵斜面超平面决策树也是一个NP完全问题。因此，用OC1算法只能找到一棵比较小的决策树,

但不一定找到一棵最小的决策树。

OC1算法构建一棵斜面超平面决策树，其基本思想是：采用自顶向下的方法从条件属性都是正

实数类型的搜索空间开始创建斜面决策树。如果搜索空间都属于同一类，则算法终止，否则，在搜索

空间中寻找一个“最佳”划分搜索空间的斜面超平面，以此斜面超平面标识当前结点，把搜索空间分

第9章分类规则挖掘与预测

成两个半空间搜索空间（左子树和右子树）。反复在每个半空间搜索空间继续寻找“最佳”斜面超平

面直至算法终止。

3.OC1算法描述

step1.就当前搜索空间创建决策树的根结点，该结点的斜面超平面把搜索空间分为左半空间和右半

空间；

step2.用这棵树来对搜索空间进行分类，如果一个半空间的所有实例都属于同一类，则以该类为标

记标识此半空间；如果所有的半空间都有类标记，则算法终止；

step3.否则，分别以左半空间和右半空间为搜索空间，继续创建根结点的左子树和右子树；重复算

法步骤steplo

OC1算法在每一个决策树结点处的算法描述如下：

/*寻找当前搜索空间的“最佳”斜面超平面参数刃

stepl.寻找当前搜索空间的“最佳”轴平行超平面区,计算该轴平行超平面乩的纯洁度/〃；

step2.随机选择一个斜面超平面”。，令“最佳”斜面超平面乩等于该斜面超平面％,计算该斜面超

平面打。的纯洁度/。；

step3.重复R次以下步骤：

32

step3.1：重复执行｛

依次振荡斜面超平面”。的系数；

｝直到纯洁度没有进一步改进；

step3.2：重复最多1次｛

选择一个随机方向，以该随机方向改变斜面超平面久;

如果改变后的斜面超平面纯洁度/"得到改进，转到步骤1;

)

step3.3：如果斜面超平面”。的纯洁度小于“最佳”轴平行超平面%的纯洁度/〃，令1=小

否则令1=/。;

step4.输出纯洁度I对应的超平面。

根据OC1算法描述可以看出，最重要的算法实现方式包括：

⑴在决策数的每一个结点处如何生成一个斜面超平面”。；

⑵计算超平面纯洁度的方法；

4.OC1算法的改进

(1)0C1算法改进的基本思想

第9章分类规则挖掘与预测

OC1算法采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树，如果条件

属性是符号型则不能适用该算法。关于符号型条件属性的问题，很容易想到的解决办法就是将其对应

到正实数类型上，再在其上采用OC1算法挖掘分类规则。如对条件属性“性别”，符号“男”对应“1”,

符号“女”对应“2”。针对不同的条件属性，可以创建不同的编码表，从而使OC1算法适用于符号

型条件属性的分类规则挖掘。

但是这样创建的编码表具有很强的随意性和主观性，不能真正反应数据的真实状况。如在搜索空间T

中，条件属性“性别”为“男”的实例占了97%,而为“女”的实例只有3%。假设在编码表中符号

“男”对应的编码为“1000”，符号“女”对应的编码为“2000”，根据斜面超平面方程EQ”，把实例

7；代入方程E。”，可以得到表达式显然，尽管性别为“女”的实例在搜索空间的比

例很小，但由于其对应的编码远远大于性别为“男”的实例，因此“别的取值只能在很小的范围振荡，

从而影响进一步选择“最佳”斜面超平面。

为了解决这个问题，可采用了一种基于分布的编码方式。首先，扫描整个搜索空间(实例集)，

得到所有条件属性为符号型的离散数据，创建编码表，计算每个离散数据在该搜索空间出现的频率。

根据每个符号对应的概率创建编码表，可以有效地解决上文中所提出的问题。

(2)OC1改进算法的描述

34

该部分的算法描述如下：

step1.扫描搜索空间；

step2.统计每一个符号属性出现的次数；

step3.计算每一个符号属性的概率分布值；

step4.生成编码表；

（3）结果分析

下表给出了OC1算法和改进的OC1算法在同一个搜索空间，同样的随机改进系数（随机跳跃次

数45）,同样的振荡次数（420）下搜索的正确率比较分析。该搜索空间是基于塔斯马尼亚州大学计

算机科学系捐赠的塔斯马尼亚州（澳大利亚州名）基础工业渔业部的鲍鱼数据库的数据仓库的一个采

样切片。

由根据表可以看出，改进的OC1算法在同样的搜索空间和一样的搜索系数情况下，决策树的正确度

无论是从平均值、最大值还是最小值进行比较，都远远高于原算法，大大增强了决策树（分类规则）

的正确性和可预测性。

次数OC1算法OC1改进算法

第一次0.760.84

第9章分类规则挖掘与预测

第二次0.700.77

第三次0.660.80

第四次0.730.78

第五次0.690.78

平均值0.7080.794

最大值0.760.84

最小值0.660.77

表OC1算法和OC1改进算法的比较

9.4.4分类规则挖掘的SLIQ算法

1.SLIQ算法概述

SLIQ快速可伸缩算法（SupervisedLearningInQuest,其中Quest是IBMAlmaden研究中心的数据挖

掘项目）是IBMAlmadenResearchCenter于1996年提出的一种高速可调节的数据挖掘分类算法。该算法

通过预排序技术，着重解决当训练集数据量巨大，无法全部放入内存时，如何高速准确地生成决策树。能同

时处理离散字段和连续字段。

36

SLIQ的优点：

(1)运算速度快，对属性值只作一次排序。

(2)利用整个训练集的所有数据，不做取样处理，不丧失精确度。

(3)轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据。

(4)更快的，更小的目标树。

(5)低代价的MDL剪枝算法

2.SLIQ算法的关键技术

(1)可伸缩性指标

一般决策树中，使用信息量作为评价结点分裂质量的参数。SLIQ算法中，使用gini指标(giniindex)

代替信息量(Information),gini指标比信息量性能更好，且计算方便。对数据集包含n个类的数据集S,

gini(S)定义为：

gini(S)=1-Lpj*pj

Pj是S中第j类数据的频率。gini越小，InformationGain越大。

(2)属性的分裂方法

区别于一般的决策树，SLIQ采用二分查找树结构。对每个结点都需要先计算最佳分裂方案，然后执行

分裂。

对于数值型连续字段(numericattribute)分裂的形式A<=v。所以，可以先对数值型字段排序，假设排序后

的结果为VI,V2,…,Vn,因为分裂只会发生在两个结点之间，所以有11-1种可能性。通常取中点(Vi+Vi+])/2

作为分裂点。从小到大依次取不同的splitpoint,取InformationGain指标最大(gini最小)的一个就是分

裂点。因为每个结点都需要排序，所以这项操作的代价极大，降低排序成本成为一个重要的问题，SLIQ算

法对排序有很好的解决方案，在后面对算法的描述中，将很详细的看到这一点。

对于离散型字段(categoricalattribute),设S(A)为A的所有可能的值，分裂测试将要取遍S的所有子集

S\寻找当分裂成和S-S，两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，这是一

第9章分类规则挖掘与预测

个对集合S的所有子集进行遍历的过程，共需要计算2⑻次，代价也是很大的。SLIQ算法对此也有一定程

度的优化。

(3)剪枝

SLIQ的剪枝算法MDL属于后剪枝605叩1*111111逾)[3.1.1.2]算法。通常的后剪枝的数据源采用一个Training

Set的一个子集或者与TrainingSet独立的数据集进行操作。

3.算法描述

输入数据：训练集，配置信息(决策树大小)；

输出数据：用线性表方式表示的二叉决策树。

算法：

Createnode(root);

Preparefordataofattributelistandclasslist;〃数据准备

Enterqueue(root);〃算法的控制结构是一个队列，

该队列存放当前的所有叶结点

While(notempty(queue))do

EvaluateSplits();//计算最佳分裂

foralltheleafnodesinthequeuedo

UpdateLabels();〃升级结点(创建子结点、执行结点分裂)

Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;〃对应该分裂的类

表进行更改

Letthenewleafnodeenterthequeue;

38

MDLpruning(root);//利用MDL算法进行剪枝

©

图9-3计算分裂指标的例子一一当前待分裂属性Sala或；,右边为classhistogram的变化过程。属性表从上往

_Updntcdas*histo(>rani<tnnd

下扫描，叶队列里面的结点有®2$N3甘nrMsP,ilfornodcZ3(salary<-40)

BGBG

N3

AgeIndexSalaryIndexCiass

152G

*后1

图9-5执行结疾小二tfV例J阖N3分裂成N6、N7；N3转为内

60

651

753(Newvalue)

1005

AgeListSalaryListClassList

第9章分类规则挖掘与预测

部结点。

9.4.5CART算法

1.CART算法概述

CART算法可用来自动探测出高度复杂数据的潜在结构，重要模式和关系.这种探测出的知识又可用来构造精确和可靠的

预测模型，应用于分类客户、准确直邮、侦测通信卡及信用卡诈骗和管理信用风险。

技术上讲，CART技术可称为二元回归分化技术.因为根结点总是被分为两个子结点并不断分化，故称为二元回归。

CART分析的技术要点包括一系列规则，可用于：

（1）分裂树点

（2）确定何时结束分裂

（3）为每一叶结点指定类型或预测值

2.CART算法的分裂规则的选择

将一个结点分化成两个子结点，CART总是问些“是”或“非”的问题。来分化根结点成二个子结点，以“是”为回答

的案例