《数据仓库与数据挖掘》

《数据仓库与数据挖掘》

分类规则挖掘与预测

要紧内容

•分类与预测的基本概念

•决策树方法

•分类规则挖掘的ID3算法

•其他分类规则挖掘算法

•分类规则的评估

•微软决策树及其应用

9.1分类与预测的基本概念

1.什么是分类

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

生关于类别的精确描述。这种类别通常由分类规则构成，能够用来对未来的数据进行分类与预测。

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

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

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

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

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

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

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

模型进行分类。

分类算法分类规则

模型评估

新数据分

新数

(b)分类------

图9-1数据分类过程

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

分类规则挖掘有着广泛的应用前景。关于分类规则的挖掘通常有下列几种方法，不一致的方法适

用于不一致特点的数据：

•决策树方法

•贝叶斯方法

•人工神经网络方法

•约略集方法

•遗传算法

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

•ID3

•C4.5

•DBlearn等

3.什么是预测

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

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

值。

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

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

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

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

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

5.分类方法的评估标准

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

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

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

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

•可解释性：学习模型提供的懂得与观察的层次。

9.2决策树方法

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

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

树方法。

1.什么是决策树

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

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

布（classdistribution）,最上面的结点是根结点。

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

一棵决策树，从中能够看到决策树的基本构成部分：决策结点、分支与叶结点。

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

（buys_computer）的知识，用它能够预测某条记录（某个人）的购买意向。

<=30?///30...40图9^3x>iniys_computer的决策树

每个内部结点《两形框）代春对府属班的一次检测W晦个叶结点（椭圆框）代表一个类:

;_computets=；

buys_efi(fiftputers=noexcellen

件中，样本向题一

tingjifcuysicomputers

的格式为：、-一一,

(age,student,credit_rating)

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

2.使用决策树进行分类

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

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

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

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

点(非叶结点)通常表示为一个逻辑推断，如形式为(a=b)的逻辑推断，其中a是属性，b是该属性的某个

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

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

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

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

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

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

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

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

•建树(TreeBuilding)：决策树建树算法见下，能够看得出，这是一个递归的过程，最终将得到一棵树。

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

9.3分类规则挖掘的ID3算法

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

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

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

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

1.ID3算法的基本思想

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

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

常根据分类的准确度与树的大小来决定决策树的质量。假如两棵决策树都能准确地在测试集进行分

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

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

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

能不是最简单的。

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

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

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

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

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

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

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

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

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

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

2.ID3算法的描述

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

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

输出：一棵决策树

方法：

(1)创建结点N；

(2)ifsamples都在同一个类Cthen

(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_Iist-test_attribute)返回的结点；

2.属性选择度量

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

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

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

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

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

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

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

平均信息量。

设S是有s个训练样本数据的集合，类标号属性具有m个不一致值，定义m个不一致类Ci(i=l,2,...,m),

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

I(Si,S2,…，Sm)=­2Mi=ipiIog2(pi)i

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

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

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

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

E(A)=2"i=i((Slj+S2j+...+Smj)/Slj)*I(Sl,S2,...,Sm)

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

A分类后的信息增益为：

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)=-EMi=lPi10g2(Pi)

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

(2)分裂后

现在属性A是带有k个不一致值的属性{ai,a2,…ak},A能够把S分成k个子集{Si,S2,…,Sk}其中S,>=

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

表示在Sj中类为C的记录个数。那么，这时按A的每个属性值(更通常的是取A的一个子集)进行分裂

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

k

E(A)=Xj=l((Slj+S2j+..+Smj)/S)*I(Slj+S2j+..+Smj)

((Slj+S2j+..+Smj)/S)表示第j个子集的权重，S=ISI。子集Sj的信息量(子集的总燧)：

I(Slj+S2j+..+Smj)=£i=lPij10g2(PU)

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

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

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

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

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”，该分枝的

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

incomestudent加,

_rating31..

highnofairno

highnoexcellentno

mediumnofairno

lowyesfairyes

mediumyesexcellentyes

3.剪枝

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

与迟滞修剪。

(1)先剪枝(pre-pruning)

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

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

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

(2)后剪枝(pos-pruning)

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

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

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

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

能小的决策树。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k例』关于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'

THENbuys_computer='no'

IFage='>40'ANDcredit_rating='fair'

THENbuys_computer='yes'

5.ID3算法的改进

(1)离散化

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

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

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

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

最简单的方法就是把属性值分成与A,〉N两段。如身高能够分为1米下列，1米以上或者者分为

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

是有限的。假设该属性取值为(%,%••…,”)，则在这个集合中，一共存在m-1个分段值，ID3算法使用计

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

(2)属性选择度量

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

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

(3)空缺值处理

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

等填充。

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

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

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

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

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

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

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

(5)可伸缩性

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

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

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

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

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

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

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

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

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

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

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

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

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

SalaryEducationClass

10,000高中通常

40,000学士较好

15,000学士通常

75,000硕士较好

18,000硕士较好

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

Salary>16,000

/39.4分段值为16,000的决策:

〜斗图9.4能够看出，Salary的分节，构建的决策树也不一样。

的评价

与其他方美舁JEd比,决策树有如下优点:给

(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•"离散化''的方法

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

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函数

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

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

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

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

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

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

(ortogonalitymeasure)＞有关度(relevance)与Reliefo不一致的度量有不一致的效果，特别是关于多值

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

选择的目标分类有关。

(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

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;

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算法使用自底向上的

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

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

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

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

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

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

常化的问题；假如阈值太大，则生成的规则比较全面，但同时也可能产生没有完全通常化与规则复杂

的问题。

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

化。

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

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

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

属性，保留另一个属性。

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

列都能够通常化为幼年，5-12岁能够通常化为童年等。

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

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

2.DBlearn算法描述

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

些错误的实例)。

DBIearn算法描述如下：

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

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

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

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

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

一样的，而这个不一样的属性的取值能够通常化为一个更高层次的符号且这个属性的取值范围包含了

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

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

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

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

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

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

9.4.3分类规则挖掘的OC1算法

1.OC1算法概述

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

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

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

靠关系。净化后的搜索空间中的每一个元组(记录)能够看作是一个m+1维向量(%,1•••/“”)，其中

匕(14i«m)对应于第i个实数类型的条件属性，c对应于决策属性(元组的类)。所有的条件属性能够

看作是一个m维向量(h,匕,

(定义』是一个n维欧几里得空间，设peR"且PHO,beR',则集合｛x|p，x=4xeQ｝称之R"中的一

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

K定义』一个超平面将R"分成两个半空间，记为H+(A/)=(U|AUN力与”-(A，=(U|AW)。其中H+(A,b)

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

工定义X一组单位向量(1,0,0,0),(0,1,0,0),…，(0,0,0,…，1)是R"中的一组

基，用符号配，••七”来表示该组单位向量。

(定义1设『是一个超平面，假如p，=5(14iW〃)，则「是一个轴平行超平面，否则「是一个斜面超平

面。

R引理』ID3决策树的每一个结点等价于一个轴平行超平面。(证明略)

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

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

工定理U用超平面把一组n个的d维向量分成两个半空间，假如n>d+l则存在2*£，(泮))种方法；

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

(证明略)

2.0C1算法的基本思想

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

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

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

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

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

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

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

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

面直至算法终止。

3.OC1算法描述

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

空间；

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

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

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

法步骤steplo

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

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

step1.寻找当前搜索空间的“最佳”轴平行超平面乩，计算该轴平行超平面乩的纯洁度小

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

平面“0的纯洁度小

step3.重复R次下列步骤：

step3.1；重复执行｛

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

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

step3.2：重复最多J次｛

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

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

)

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

否则令1=/°;

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

根据OC1算法描述能够看出，最重要的算法实现方式包含：

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

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

4.OC1算法的改进

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）OC1改进算法的描述

该部分的算法描述如下：

step1.扫描搜索空间；

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

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

step4.生成编码表；

（3）结果分析

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

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

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

样切片。

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

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

的正确性与可预测性。

次数OC1算法OC1改进算法

第一次0.760.84

第二次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年提出的一种高速可调节的数据挖掘分类算法。该算法

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

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

SLIQ的优点：

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

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

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

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

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

2.SLIQ算法的关键技术

(1)可伸缩性指标

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

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

gini(S)定义为：

gini(S)=1-Epj*pj

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

(2)属性的分裂方法

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

分裂。

关于数值型连续字段(numericattribute)分裂的形式A<=v。因此，能够先对数值型字段排序，假设排序后

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

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

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

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

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

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

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

度的优化。

(3)剪枝

SLIQ的剪枝算法MDL属于后剪枝(pos-prunning)[]算法。通常的后剪枝的数据源使用一个Training

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

3.算法描述

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

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

算法：

Createnode(root);

Preparefordataofattributelistandclasslist;〃数据准备

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

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

While(notempty(queue))do

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

foralltheleafnodesinthequeuedo

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

Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;〃对应该分裂的类

表进行更换

Letthenewleafnodeenterthequeue;

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

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

下扫描兄;卅队列里面的结点有峡N36BN3

SnlnryInclc、

InitialHistograms

GN2

厨二结底能扮裂成解门逋;N3转为内

N3

N2N3

BN3

UpdntcdnsshistORramsand

N3EvaluatefirstsplitfornodeN2<salary•<«=■15)

Z3BB

SalaryListCZIQSSI.ist

R0R

N2

Updateclasshistogram*nnd

EvaluatefirstsplitfornodeN3(salaryv-40)

N6

1.CART算法概述

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

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

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

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

(1)分裂树点

(2)确定何时结束分裂

(3)为每一叶结点指定类型或者预测值

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

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

答的案例归入左子树结点，而“否”为回答的案例归为右子树结点。

K例X贷款申请中风险分析。有训练集包含100个高风险与100个低风险的测试案例，构造一棵二叉树如图1