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

第9第9章分类规则挖掘与预测#第9章分类规则挖掘与预测主要内容•分类与预测的基本概念•决策树方法分类规则挖掘的ID3算法其他分类规则挖掘算法•分类规则的评估微软决策树及其应用9.1分类与预测的基本概念1.什么是分类数据分类(dataclassfication)是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。数据分类(dataclassfication)是一个两个步骤的过程：•第1步：建立一个模型，描述给定的数据类集或概念集(简称训练集)。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习(聚类)学习模型可用分类规则、决策树和数学公式的形式给出。•第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。图9-1数据分类过程2.常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：决策树方法•贝叶斯方法人工神经网络方法约略集方法遗传算法典型的分类规则挖掘算法有ID3■C4.5■DBlearn等3.什么是预测预测(prediction)是构造和使用模型评估无标号样本类，或评估给定的样本可能具有的属性或区间值。分类和回归是两类主要的预测问题。分类是预测离散值，回归用于预测连续或有序值。分类和预测数据的预处理■数据清理：使用平滑技术消除或减少噪声；处理空缺值。相关性分析：删除与分类或预测无关的属性；删除冗余属性。数据变换：使用概念分层将数据概化到高的层次；连续值属性概化为离散区间；数据规范化，即将某一属性的所有值按比例缩放，使其落入指定的区间。分类方法的评估标准•准确率：模型正确预测新数据类标号的能力。•速度：产生和使用模型花费的时间。健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。伸缩性：对于给定的大量数据，有效地构造模型的能力。可解释性：学习模型提供的理解和观察的层次。9.2决策树方法决策树方法的起源是概念学习系统CLS,然后发展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。什么是决策树决策树(DecisionTree)又称为判定树，是运用于分类的一种树结构。其中的每个内部结点(internalnode)代表对某个属性的一次测试，每条边代表一个测试结果，叶结点(leaf)代表某个类(class)或者类的分布(classdistribution)，最上面的结点是根结点。决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。例〗图9-2给出了一个商业上使用的决策树的例子。它表示了一个关心电子产品的用户是否会购买PCbuys_computer）的知识，用它可以预测某条记录（某个人）的购买意向。Age?图9-2buys_computer的决策树这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点（方形框）代表对某个属性的一次检测。每个叶结点（椭圆框）代表一个类：buys_computers=yes或者buys_computers=no在这个例子中，样本向量为：（age,student,credit_rating;buys_computers）被决策数据的格式为:（age,student,credit_rating）输入新的被决策的记录，可以预测该记录隶属于哪个类。使用决策树进行分类构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为（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_list。输出：一棵决策树方法：（1）创建结点N；（2）ifsamples都在同一个类Cthen（3）返回N作为叶结点，用类C标记；（4）ifattribute_list为空then（5）返回N作为叶结点，标记samples中最普通的类；//多数表决6)选择attribute_list中具有最高信息增益的属性test_attribute；//用信息增益作为属性选择度量7)标记结点N为test_attribute；8)foreachtest_attribute中的已知值ai//划分samples(9)由结点N生长出一个条件为test_attribute=ai的分枝；(10)设si为samples中test_attribute=ai的样本集合；//一个划分ifsi为空then加上一个叶结点，标记为标记samples中最普通的类；//多数表决else加上一个由Generate_decision_tree(si,attribute_list-test_attribute)返回的结点；2.属性选择度量在Generate_decision_tree算法的Step6，算法需选择attribute_list中具有最高信息增益的属性test_attribute。ID3算法在树的每个结点上以信息增量(informationgain)作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的(但不一定是最简单的)决策树。InformationGain指标的原理来自于信息论。1948年，香农(C・E.Shannon)提出了信息论。其中给岀了关于信息量(Information)和熵(Entropy)的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci(i=12,・・3)，si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：I(S],s2,・・・，sm)=—£Mi=1pilog2(pi)i其中pi是任意样本属于Ci的概率，可用si/s来估计。设属性A具有k个不同值{a1,a2,・・・,ak},则可用属性A将S划分为k个子集{S1,S2,・・・,Sk},Sj中包含的样本在属性A上具有值aj。如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分枝。设s甘是子集Sj中类Ci的样本数，则按照A划分成子集的熵为：E(A)=ZMi=1((s!j+%+…％)/%)*1(si，s2,…，sm)信息增益(InformationGain),表示系统由于分类获得的信息量。由系统熵的减少值定量描述。用属性A分类后的信息增益为：Gain(A)=I处,s”…,sm)-E(A)熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是InformationGain,所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，这个最佳方案是用“贪心算法+深度优先搜索”得到的。因为这是一个递归过程，所以仅仅需要讨论对某个特定结点N的分裂方法。分裂前设指向N的训练集为S,其中包含m个不同的类，它们区分了不同的类C.(fori=1,…,m)。设s.是S中属于类C.的记录的个数。那么分裂之前，系统的总熵11i1(si，s2,…，sm)=-Lmi=1PilOg2(Pi)容易看出，总熵是属于各个类的记录的信息量的加权平均。分裂后现在属性A是带有k个不同值的属性｛a1,a2,^ak｝,A可以把S分成k个子集｛鸟,S2,…,SJ其中S.=｛xIxeS&x.A=a.｝。如果A被选为测试属性，那么那些子集表示从代表集合S的出发的所有树枝。设，.表示在S.中类为C：的记录个数。那么，这时按A的每个属性值(更一般的是取A的一个子集)进行分裂后的信息量，也就是系统总熵为：E(A)=%=1((sij+s2j+・・+Smj)/S)*I(sij+s2j+・・%)((s1j+s2.+・・+5回於)表示第j个子集的权重，s=ISI。子集Sj的信息量(子集的总熵)：I(sij+s2j+..+smj)=-£=ip.log2(Pj)

总熵E（A）是各个子集信息量的加权平均。算法计算每个属性的信息增益，具有最高信息增益的属性选择作为给定训练数据集合S的测试属性。创建一个结点，并以该属性为标记，对属性的每一个值创建分枝，并据此划分样本。〖例〗顾客数据库训练数据集如下表所示：RIDageincomestudentcredit_ratingClass:Buyscomputer1<=30highnofairno2<=30highnoexcellentno331・・・40highnofairyes4>40mediumnofairyes5>40lowyesfairyes6>40lowyesexcellentno731・・・40lowyesexcellentyes8<=30mediumnofairno9<=30lowyesfairyes10>40mediumyesfairyes11<=30mediumyesexcellentyes1231・・・40mediumnoexcellentyes1331・・・40highyesfairyes14>40mediumnoexcellentno计算每一个属性的信息增益：Gain（age）=I（s2,s2）－E（age）=0.246Gain（income）=0.029Gain（student）=0.151Gain（credit_rating）=0.048由于属性age在所有属性中具有最高的信息增益，因此它被选择为测试属性。创建一个以age为标记的结点，并对每一个属性值引出一个分枝。落在分枝age=“31・・・40”的样本都属于同一类“yes"，该分枝的端点应该创建一个叶结点。

3.剪枝剪枝常常利用统计学方法，去掉最不可靠、可能是噪音的一些枝条。剪枝方法主要有两类：同步修剪和迟滞修剪。(1)先剪枝(pre-pruning)在建树的过程中，当满足一定条件，例如InformationGain或者某些有效统计量达到某个预先设定的阈值时，结点不再继续分裂，内部结点成为一个叶结点。叶结点取子集中频率最大的类作为自己的标识，或者可能仅仅存储这些实例的概率分布函数。(2)后剪枝(pos-pruning)与建树时的训练集独立的训练数据进入决策树并到达叶结点时，训练数据的classlabel与叶结点的classlabel不同，这时称为发生了分类错误。当树建好之后，对每个内部结点，算法通过每个枝条的出错率进行加权平均，计算如果不剪枝该结点的错误率。如果裁减能够降低错误率，那么该结点的所有儿子就被剪掉，而该结点成为一片叶。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能小的决策树。如果在测试集中出现了类交叉的情况，也就是说，在待挖掘的数据中出现矛盾和不一致的情况。则在算法步骤3中将出现这样一种情况：在一个树结点中，所有的实例并不属于一个类却找不到可以继续分支的属性。ID3使用以下两种方案解决这个问题：①选择在该结点中所占比例最大的类为标记标识该结点；根据该结点中不同类的概率分布为标记标识该结点。根据该结点中不同类的概率分布为标记标识该结点。如果在测试集中出现了某些错误的实例，也就是说，在待挖掘的数据中，本来应该属于同一结点的数据因为某些错误的属性取值而继续分支。则在最终生成的决策树中可能出现分支过细和错误分类的现象。ID3设置了一个阈值来解决这个问题：只有属性的信息量超过这个阈值时才创建分支，否则以类标志标识该结点。该阈值的选取对决策树的正确创建具有相当的重要性。如果阈值过小，可能没有发挥应有的作用；如果阈值过大，又可能删除了应该创建的分支。4.由决策树提取分类规则可以提取由决策树表示的分类规则，并以IF－THEN的形式表示。具体方法是：从根结点到叶

结点的每一条路径创建一条分类规则，路径上的每一个“属性－值”对为规则的前件（即IF部分）的一个合取项，叶结点为规则的后件（即THEN部分）。〖例〗对于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和A>N两段。如身高可以分为1米以下，1米以上或者分为1.5ii米以下，1.5米以上。如何选择最佳的分段值呢？对任何一个属性，其所有的取值在一个数据集中是有限的。假设该属性取值为C,v,,v）,则在这个集合中，一共存在m-1个分段值，ID3算法采用计算信12m息量的方法计算最佳的分段值,然后进一步构建决策树。（2）属性选择度量ID3算法中采用信息增量作为属性选择度量,但它仅适合于具有许多值的属性。已经提出了一些其他的属性选择度量方法,如增益率,它考虑了每个属性的概率。（3）空缺值处理常用的空缺值处理方法有：若属性A有空缺值,则可用A的最常见值、平均值、样本平均值等填充。（4）碎片、重复和复制处理通过反复地将数据划分为越来越小的部分,决策树归纳可能面临碎片、重复和复制等问题。所谓碎片是指在一个给定的分枝中的样本数太少，从而失去统计意义。解决的方法是：将分类属性值分组，决策树结点可以测试一个属性值是否属于给定的集合。另一种方法是创建二叉判定树，在树的结点上进行属性的布尔测试，从而可以减少碎片。当一个属性沿树的一个给定的分枝重复测试时，将出现重复。复制是拷贝树中已经存在的子树。通过由给定的属性构造新的属性（即属性构造），可以防止以上问题的发生。（5）可伸缩性ID3算法对于相对较小的训练数据集是有效的，但对于现实世界中数据量很大的数据挖掘，有效性和可伸缩性将成为必须关注的问题。面临数以百万计的训练数据集，需要频繁地将训练数据在主存和高速缓存换进换出，从而使算法的性能变得低下。解决的方法是：将训练数据集划分为子集，使得每个子集能够放在内存；然后由每个子集构造一棵决策树；最后，将每个子集得到的分类规则组合起来，得到输出的分类规则。最近，已经提出了一些强调可伸缩性的决策树算法，如：SLIQ、SPRINT等。这两种算法都使用了预排序技术，并采用了新的数据结构，以利于构造决策树。ID3算法对大部分数据集有效，但它不能挖掘域知识。同时，决策树在计算机中存储的方式决定了该分类规则相对于其他形式的分类规则（如公式）而言更晦涩难懂。因此，一般在算法结束后，需要把决策树以用户可视的方法显示出来。〖例〗以下表所示的训练数据集为例，其中Salary为工资，Education为教育程度，Class为信用级别。假设以20，000作为Salary的分段值，则创建的决策树如图9-3所示；假设以16，000作为Salary的分段值，则创建的决策树如图9-4所示。SalaryEducationClass10,000高中一般40,000学士较好15,000学士一般75,000硕士较好18,000硕士较好训练数据集T图9.3分段值为20，000的决策树

图9.4分段值为16，000的决策树由图9.3和图9.4可以看出，Salary的分段值不一样，构建的决策树也不一样。6.决策树方法的评价与其他分类算法相比，决策树有如下优点：(1)速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。例如，沿着结点Age->CreditRating->no走下来就能得到一条谓词：ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuyacomputer.（2）准确性高：挖掘出的分类规则准确性高，便于理解。一般决策树的劣势：（1）缺乏伸缩性：由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。一个例子：在Irvine机器学习知识库中，最大可以允许的数据集仅仅为700KB，2000条记录。而现代的数据仓库动辄存储几个G-Bytes的海量数据。用以前的方法是显然不行的。（2）为了处理大数据集或连续量的种种改进算法（离散化、取样）不仅增加了分类算法的额外开销，而且降低了分类的准确性。9.4分类规则挖掘的其他算法9.4.1分类规则挖掘的C4.5算法C4.5算法概述C4.5算法是ID3算法的扩展，但是它比ID3算法改进的部分是它能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个属性Gian值的大小。"离散化"的方法把连续型属性值"离散化"的具体方法是：1）寻找该连续型属性的最小值，并把它赋值给MIN，寻找该连续型属性的最大值，并把它赋值给MAX；2)设置区间［MIN，MAX］中的N个等分断点Ai,它们分别是Ai=MIN+((MAX-MIN)/N)*i其中，i=1,2,...,N分别计算把［MIN，人口和(Ai，MAX)(i=1,2,...,N)作为区间值时的Gain值，并进行比较选取Gain值最大的Ak做为该连续型属性的断点，把属性值设置为［MIN，Ak］和(Ak，MAX)两个区间值。Gain函数决策树是建立在信息理论(InformationTheory)的基础上的，决策树的方法循环地寻找某一标准，它能够带来与本次分类相关的最大信息构造好的决策树的关键在于如何选择好的属性。对于同样一组记录集，可以有很多决策树能符合这组记录集。人们研究出，一般情况下，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当属性。属性选择依赖于各种对例子子集的不纯度(impurity)度量方法。不纯度度量方法包括信息增益(informatingain)、信息增益比(gainratio)、Gini-index、距离度量(distancemeasure)>J-measure、G统计、x2统计、证据权重(weightofevidence)>最小描述长(MLP)、正交法(ortogonalitymeasure)>相关度(relevance)和Relief。不同的度量有不同的效果，特别是对于多值属性。C4.5算法使用信息增益(informationgain)的概念来构造决策树，其中每个分类的决定都与前面所选择的目标分类有关。信息理论(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=-刀(pi*log(Pi))在上面的例子中,情况1和情况2的信息熵分别是：=-(1*log1+0*log0)=0=-(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;beginIfSisemptythenreturnasinglenodewithvalueFailure;IfSconsistsofrecordsallwiththesamevalueforthegoalattributethenreturnasinglenodewiththatvalue;IfRisemptythenreturnasinglenodewithasvaluethemostfrequentofthevaluesofthegoalattributethatarefoundinrecordsofS;[notethatthentherewillbeerrors,thatis,recordsthatwillbeimproperlyclassified];forallattributesofR(Ri)doifvaluesofRiarecontinuousthenbeginLetA1betheminimumofRi;LetAmbethemaximumofRi;{m值手工设置}forjfrom2tom-1doAj=A1+j*(A1-Am)/m;LetAbethevaluepointofRiwithlargestGain(Ri,S)basedon{<=Aj,>Aj};end;LetDbetheattributewithlargestGain(D,S)amongattributesinR;Let{dj|j=1,2,..,m}bethevaluesofattributeD;Let{Sj|j=1,2,..,m}bethesubsetsofSconsistingrespectivelyofrecordswithvaluedjforattributeD;ReturnatreewithrootlabeledDandarcslabeledd1,d2,..,dmgoingrespectivelytothetreesC4.5(R-{D},C,S1),C4.5(R-{D},C,S2),..,C4.5(R-{D},C,Sm);endC4.5。但是，所用的基于分类挖掘的决策树算法没有考虑噪声问题，生成的决策树很完美，这只不过是理论上的，在实际应用过程中，大量的现实世界中的数据都不是以的意愿来定的，可能某些字段上缺值(missingvalues)；可能数据不准确含有噪声或者是错误的；可能是缺少必须的数据造成了数据的不完整。另外决策树技术本身也存在一些不足的地方，例如当类别很多的时候，它的错误就可能出现甚至很多。而且它对连续性的字段比较难作出准确的预测。而且一般算法在分类的时候，只是根据一个属性来分类的。在有噪声的情况下，完全拟合将导致过分拟合(overfitting)，即对训练数据的完全拟合反而不具有很好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。另外，决策树技术也可能产生子树复制和碎片问题。在算法具体实现时必须考虑以上这些问题。9.4.2DBlearn算法1.DBlearn算法概述DBlearn算法用域知识生成基于关系数据库的预定义子集的描述。DBlearn算法采用自底向上的搜索策略，使用以属性层次形式的域知识，同时该算法使用了关系代数。该算法的事务集是一个关系表，即一个具有若干个属性的n元组。系统采用关系表作为知识结构：对每一类，它构建一个关系表。这个关系表的属性是实例集属性的子集。一个元组可以看作是一个属性值关联的逻辑公式。搜索空间的开始是整个实例集，而最终目的是为了生成一个类描述的表。类描述表的大小不能超过用户定义的阈值。阈值的大小决定了类描述表的大小。如果阈值太小，则生成的规则更简单，但同时也可以能丢失了一些有用的信息从而产生过度一般化的问题；如果阈值太大，则生成的规则比较详细，但同时也可能产生没有完全一般化和规则复杂的问题。一些属性域被局部排序从而构成一个层次结构，每一个值都是该值所在层次下面全部值的一般化。在从关系表中生成分类规则时，DBlearn算法使用了两个基本的算子：（1）删除：如果在关系表中有属性之间存在着关联关系，则删除直到只剩下彼此互不关联的属性。如年龄和出生年月这两个属性存在着年龄=现在时间—出生年月的关联关系，因此必须删除其中一个属性，保留另一个属性。（2）一般化：属性的值被一般化为层次在它之上的值从而生成规则。如就年龄这个属性而言，5岁以下都可以一般化为幼年，5-12岁可以一般化为童年等。在一个关系表上运行以上两个算子有可能产生完全一样的元组，DBlearn算法通过删除多余的元组来缩减关系表的大小从而得到类描述表。DBlearn算法描述DBlearn算法创建一个完全但不一定一致的分类规则，即该分类规则覆盖所有的实例集（包括那些错误的实例）。DBlearn算法描述如下：step1．从数据库中选择和任务相关的数据，如一个包含且只包含一类数据的数据表。step2．在该数据表上执行一般化操作：如果在某个属性上存在很多不同的值同时提供了一个更高级别的值，则该属性被一般化为更高级别的值；如果在某个属性上存在很多不同的值而不能提供一个更高级别的值，则该属性被删除。删除重复的元组直到表的大小达到用户定义的阈值。step3．简化结果。例如，如果该数据表上的一些元组除了一个属性不一样，其他的属性值都是一模一样的，而这个不一样的属性的取值可以一般化为一个更高层次的符号且这个属性的取值范围包含了该更高层次符号所代表的全部数据。则这些元组可以用一个元组代替，这个元组的属性就是那个不一样的属性，它的值用那个符号表示。step4．把这个数据表转换成公式。DBlearn算法是一个相对比较简单的分类规则挖掘算法，通过对属性取值不断进行一般化操作从而最终获得规则。在数据挖掘的过程中，该算法是域知识挖掘的一个典型例子。该算法经过改进可以挖掘那些包含噪声数据的不纯净数据，同时可以做增量学习。9.4.3分类规则挖掘的OC1算法1.OC1算法概述OC1算法是ObliqueClassifier1的缩写，即斜面分类1算法。它基于线性规划的理论，以斜面超平面的思想为基础，采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树在执行OC1决策树算法前，首先需要对搜索空间做净化和清理工作以消除条件属性间的函数依赖关系。净化后的搜索空间中的每一个元组(记录)可以看作是一个m+1维向量(v,v,,v,c)，其中12mv(1<iVm)对应于第i个实数类型的条件属性，c对应于决策属性(元组的类)。所有的条件属性可以i看作是一个m维向量(v,v,,v)。12m〖定义〗Rn是一一个n维欧几里得空间，设pGRn且p主0，bGR1，则集合｛xIpTX二b,xGRn｝称为Rn中的一一个超平面(n>4)。(当n=2时，集合确定一条直线；当n=3时，集合确定一个平面。)〖定义〗一个超平面将Rn分成两个半空间，记为H+(A,b)二(UIA-U>b)和H-(A,b)二(UIA-U<b)。其中H+(A,b)是Rn中满足A•U>b的向量U构成的半空间，H-(A,b)是Rn中满足A•U<b的向量U构成的半空间。〖定义〗一组单位向量(1，0，0，…，0)，(0，1，0，…，0)，…，(0，0，0，…，1)是Rn中的一组基，用符号g，g，…g来表示该组单位向量。12n〖定义〗设「是一个超平面，如果pT=g(1<i<n)，则「是一个轴平行超平面，否则「是一个斜面超平i面。〖引理〗ID3决策树的每一个结点等价于一个轴平行超平面。(证明略)大部分决策树都是在每一个结点检查某个属性的值，或者对该数值属性进行分段检查。因此，称这种决策树为“轴平行”决策树。〖定理〗用超平面把一组n个的d维向量分成两个半空间，如果n>d+1则存在2*工d(心)种方法；k=0k如果n<d+1则存在2n种方法。（证明略）2.OC1算法的基本思想根据以上定理，最多存在有限种不同的决策树。从理论上可以采用一种穷举的方法来寻找一棵最优决策树，但在实际中这是不可行的算法。如前所述，寻找一棵最优决策树是一个NP完全问题。寻找一棵斜面超平面决策树也是一个NP完全问题。因此，用OC1算法只能找到一棵比较小的决策树，但不一定找到一棵最小的决策树。OC1算法构建一棵斜面超平面决策树，其基本思想是：采用自顶向下的方法从条件属性都是正实数类型的搜索空间开始创建斜面决策树。如果搜索空间都属于同一类，则算法终止，否则，在搜索空间中寻找一个“最佳”划分搜索空间的斜面超平面，以此斜面超平面标识当前结点，把搜索空间分成两个半空间搜索空间（左子树和右子树）。反复在每个半空间搜索空间继续寻找“最佳”斜面超平面直至算法终止。3.OC1算法描述step1．就当前搜索空间创建决策树的根结点，该结点的斜面超平面把搜索空间分为左半空间和右半空间；step2．用这棵树来对搜索空间进行分类，如果一个半空间的所有实例都属于同一类，则以该类为标记标识此半空间；如果所有的半空间都有类标记，则算法终止；step3．否则，分别以左半空间和右半空间为搜索空间，继续创建根结点的左子树和右子树；重复算法步骤step1。OC1算法在每一个决策树结点处的算法描述如下：/*寻找当前搜索空间的“最佳”斜面超平面参数*/step1•寻找当前搜索空间的“最佳”轴平行超平面H，计算该轴平行超平面H的纯洁度I；aaastep2．随机选择一个斜面超平面H，令“最佳”斜面超平面H等于该斜面超平面H，计算该斜面超0o0平面H的纯洁度I；0ostep3．重复R次以下步骤：step3．1：重复执行｛依次振荡斜面超平面H的系数；0｝直到纯洁度Io没有进一步改进；step3．2：重复最多J次｛选择一个随机方向，以该随机方向改变斜面超平面H；0如果改变后的斜面超平面纯洁度I得到改进，转到步骤1；o}step3．3：如果斜面超平面H的纯洁度I小于“最佳”轴平行超平面H的纯洁度I，令I=I0oaaa否则令I=I；ostep4．输出纯洁度I对应的超平面。根据OC1算法描述可以看出，最重要的算法实现方式包括：(1)在决策数的每一个结点处如何生成一个斜面超平面H；0(2)计算超平面纯洁度的方法；4.OC1算法的改进(1)OC1算法改进的基本思想OC1算法采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树，如果条件属性是符号型则不能适用该算法。关于符号型条件属性的问题，很容易想到的解决办法就是将其对应到正实数类型上，再在其上采用OC1算法挖掘分类规则。如对条件属性“性别”，符号“男”对应“1”符号“女”对应“2”。针对不同的条件属性，可以创建不同的编码表，从而使OC1算法适用于符号型条件属性的分类规则挖掘。但是这样创建的编码表具有很强的随意性和主观性，不能真正反应数据的真实状况。如在搜索空间T中，条件属性“性别”为“男”的实例占了97%，而为“女”的实例只有3%。假设在编码表中符号“男”对应的编码为“1000”，符号“女”对应的编码为“2000”，根据斜面超平面方程EQ，把实例HT.代入方程eq，可以得到表达式2dCx）+a二V。显然，尽管性别为“女”的实例在搜索空间的比jHi=1iid+1j例很小，但由于其对应的编码远远大于性别为“男”的实例，因此a的取值只能在很小的范围振荡，性别从而影响进一步选择“最佳”斜面超平面。为了解决这个问题，可采用了一种基于分布的编码方式。首先，扫描整个搜索空间（实例集），得到所有条件属性为符号型的离散数据，创建编码表，计算每个离散数据在该搜索空间出现的频率。根据每个符号对应的概率创建编码表，可以有效地解决上文中所提出的问题。（2）OC1改进算法的描述该部分的算法描述如下：step1．扫描搜索空间；step2．统计每一个符号属性出现的次数；step3．计算每一个符号属性的概率分布值；step4．生成编码表；（3）结果分析下表给出了OC1算法和改进的OC1算法在同一个搜索空间，同样的随机改进系数（随机跳跃次数＜5）,同样的振荡次数（＜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)3)4)更快的，更小的目标树。(5)低代价的MDL剪枝算法2.SLIQ算法的关键技术(1)可伸缩性指标一般决策树中，使用信息量作为评价结点分裂质量的参数。SLIQ算法中，使用gini指标(giniindex)代替信息量(Information)，gini指标比信息量性能更好，且计算方便。对数据集包含n个类的数据集S,gini(S)定义为：gini(S)=1-Sp.*Pjp.是S中第j类数据的频率。gini越小，InformationGain越大。(2)属性的分裂方法区别于一般的决策树，SLIQ采用二分查找树结构。对每个结点都需要先计算最佳分裂方案，然后执行分裂。对于数值型连续字段(numericattribute)分裂的形式Av=v。所以，可以先对数值型字段排序，假设排序后的结果为V[,v2,…,v,因为分裂只会发生在两个结点之间，所以有n-1种可能性。通常取中点(v.+v)/212nii+1作为分裂点。从小到大依次取不同的splitpoint，取InformationGain指标最大(gini最小)的一个就是分裂点。因为每个结点都需要排序，所以这项操作的代价极大，降低排序成本成为一个重要的问题，SLIQ算法对排序有很好的解决方案，在后面对算法的描述中，将很详细的看到这一点。对于离散型字段(categoricalattribute),设S(A)为A的所有可能的值，分裂测试将要取遍S的所有子集S'。寻找当分裂成S'和S-S'两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，这是一个对集合S的所有子集进行遍历的过程，共需要计算2isi次，代价也是很大的。SLIQ算法对此也有一定程度的优化。(3)剪枝SLIQ的剪枝算法MDL属于后剪枝(pos-prunning)[3・1・1・2]算法。通常的后剪枝的数据源采用一个TrainingSet的一个子集或者与TrainingSet独立的数据集进行操作。3・算法描述输入数据：训练集，配置信息(决策树大小)；输出数据：用线性表方式表示的二叉决策树。算法：Createnode(root);Preparefordataofattributelistandclasslist;//数据准备Enterqueue(root);//算法的控制结构是一个队列,该队列存放当前的所有叶结点While(notempty(queue))doEvaluateSplits();//计算最佳分裂foralltheleafnodesinthequeuedoUpdateLabels();//升级结点(创建子结点、执行结点分裂)

//对应该分裂的类Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;//对应该分裂的类Letthenewleafnodeenterthequeue;MDLpruning(root);//利用MDL算法进行剪枝图9-3计算分裂指标的例子当前待分裂属性Salary,右边为classhistogram的变化过程。属性表从上往下扫描，叶队列里面的结点有N2,N3。图9－5执行结点分裂的例子――结点N3分裂成N6、N7，N3转为内部结点。9.4.5CART算法1.CART算法概述CART算法可用来自动探测出高度复杂数据的潜在结构，重要模式和关系.这种探测出的知识又可用来构造精确和可靠的预测模型，应用于分类客户、准确直邮、侦测通信卡及信用卡诈骗和管理信用风险。技术上讲，CART技术可称为二元回归分化技术.因为根结点总是被分为两个子结点并不断分化，故称为二元回归。CART分析的技术要点包括一系列规则，可用于：（1）分裂树点（2）确定何时结束分裂（3）为每一叶结点指定类型或预测值2.CART算法的分裂规则的选择将一个结点分化成两个子结点，CART总是问些“是”或“非”的问题。来分化根结点成二个子结点，以“是”为回答的案例归入左子树结点，而”否”为回答的案例归为右子树结点。〖例〗贷款申请中风险分析。有训练集包含100个高风险和100个低风险的测试案例，构造一棵二叉树如图1所示：图9-8贷款风险分析对于上图中所得到的二叉树，CART算法先检验分析中所有变量可生出的所有分裂，再选其优者。如上图中有200个案例，假设每个案例都有10个相关的数据变量，那么CART算法要比较200X10即2000种分裂的可能。接下来需要根据分裂质量标准来评估每一个分化。最常用的一个标准是GINI标准，基本原则是根据该分化是否有效地分隔几个类别。除了GINI标准外，还可以用Twoing标准和规则Twoing标准。其中GINI标准在树成长时明显地包括费用信息，而Twoing标准和规则Twoing标准则在计算风险和结点分配时使用费用，或者把费用信息合并入先验以应用到模型。为了更有效地处理数据类型的选择，也可以运用连续自变变量的线性组合来作为分化的基础。通过质量标准评估每一个分化后，要选取一个最佳分化来构建决策树，并继续对每一个子结点重复进行“搜索和分化”的过程，直到进一步的分化不可能继续。不能继续的情况如：某个树点包含完全一致的案例，则无法进一步分化；一个结点包含太少案例时，也会停止分化。(一般取10为标准，少于10即为太少)。当决策树构建完成后，需要要对决策树的终结点的案例进行分类。一种最简单的分类方法就是对数原则，即用数量最多的种类来确定分类。如上图的决策树，假设它已经构建完成，那么按多数原则，就确定左结点为低风险类，右结点为高风险类。3.CART算法的实现以贷款申请中的风险分析为例，先确定一个训练集，如以100个高风险和100个低风险的数据集为训练集。假设每条客户记录有字段：姓名(Char)、年收入(Money)、工龄(Int)、籍贯(Char)、是否为高负债(Bool)。(为了举例字段的典型性，所以列举了上述这些字段，实际情况肯定不止这些字段，不过这些字段基本覆盖了在规则分化中要考虑的情况。)（2）根据训练集中的字段及每个案例在该字段上的取值，按顺序扫描训练集，并记录结果。a.对于类型为数字型的字段，如DateTime、Int、Float、Money等，只要依次取每条记录的该字段的取值，然后按是否大于该值来扫描训练集。建立一个表来记录结果，基于数据库中的数据一致性、减少数据冗余及方便后面对这个记录的操作，可以建立如下的表格tb_Result来存放结果。序号Resultl(int)Result2(int)1234其中序号字段每次从1开始编号，添加一条记录，则序号加1。Resultl用来记录扫描时判断为“是”的高风险的案例数,如在扫描数字型字段时就记录大于扫描值的高风险案例的数目；在扫描字符型数据时就用来记录在该字段上的字符串与扫描字符串相同的高风险的记录数；在扫描布尔型数据时，用来记录取值为“是”的高风险案例数目。Result2用来记录扫描时判断为“是”的低风险的案例数。用序号字段，而不直接用扫描字段来记录，是为了实现表的重用，节省数据库开支，这样在扫描所有的字段的时候都可以共用这个表来记录结果，而不必因为字段不同及字段类型的不同而要设计不同的表来记录结果。由于每次使用tb_Result的时候，序号都是从1开始编号的，所以tb_Result中的记录结果是与训练集中的记录一一对应的，只要根据序号的对应关系，能够很方便的获得tb_R