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

第9章分类规则挖掘与预测1第9章分类规则挖掘与预测主要内容分类与预测的基本概念决策树方法分类规则挖掘的ID3算法其他分类规则挖掘算法分类规则的评估微软决策树及其应用第9章分类规则挖掘与预测29.1分类与预测的基本概念1.什么是分类数据分类（dataclassfication）是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。数据分类（dataclassfication）是一个两个步骤的过程：第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。（a）学习（b）分类训练数据分类规则练数据分类算法训练数据分类算法分类算法分类规则新数据新元组数据分类分类规则数据分类规则分模型评估类测试数据数据新数据新数据模型评估模型评估模型评估模型评估新数据分类新数据分类新数据分第9章分类规则挖掘与预测3图9-1数据分类过程2.常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：决策树方法贝叶斯方法人工神经网络方法约略集方法遗传算法典型的分类规则挖掘算法有：ID3C4.5DBlearn等3.什么是预测预测（prediction）是构造和使用模型评估无标号样本类，或评估给定的样本可能具有的属性或区间值。分类和回归是两类主要的预测问题。分类是预测离散值，回归用于预测连续或有序值。4.分类和预测数据的预处理数据清理：使用平滑技术消除或减少噪声；处理空缺值。相关性分析：删除与分类或预测无关的属性；删除冗余属性。数据变换：使用概念分层将数据概化到高的层次；连续值属性概化为离散区间；数据规范化，即将某一属性的所有值按比例缩放，使其落入指定的区间。第9章分类规则挖掘与预测45.分类方法的评估标准准确率：模型正确预测新数据类标号的能力。速度：产生和使用模型花费的时间。健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。伸缩性：对于给定的大量数据，有效地构造模型的能力。可解释性：学习模型提供的理解和观察的层次。9.2决策树方法决策树方法的起源是概念学习系统CLS，然后发展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。还有CART算法和Assistant算法也是比较有名的决策树方法。1.什么是决策树决策树（DecisionTree）又称为判定树，是运用于分类的一种树结构。其中的每个内部结点（internalnode）代表对某个属性的一次测试，每条边代表一个测试结果，叶结点（leaf）代表某个类（class）或者类的分布（classdistribution），最上面的结点是根结点。决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。下例是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分：决策结点、分支和叶结点。第9章分类规则挖掘与预测5Age?Credit_rating?student?yesnoyesyesno=30?4030…40yesnofairexcellent〖例〗图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章分类规则挖掘与预测62.使用决策树进行分类构造决策树是采用自上而下的递归构造方法。以多叉树为例，如果一个训练数据集中的数据有几种属性值，则按照属性的各种取值把这个训练数据集再划分为对应的几个子集（分支），然后再依次递归处理各个子集。反之，则作为叶结点。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点（非叶结点）一般表示为一个逻辑判断，如形式为(a=b)的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树（ID3）的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶结点都是类别标记。使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。问题的关键是建立一棵决策树。这个过程通常分为两个阶段：建树（TreeBuilding）：决策树建树算法见下，可以看得出，这是一个递归的过程，最终将得到一棵树。第9章分类规则挖掘与预测7剪枝（TreePruning）：剪枝是目的是降低由于训练集存在噪声而产生的起伏。9.3分类规则挖掘的ID3算法由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法。ID3即决策树归纳（InductionofDecisionTree）。早期的ID算法只能就两类数据进行挖掘（如正类和反类）；经过改进后，现在ID算法可以挖掘多类数据。待挖掘的数据必须是不矛盾的、一致的，也就是说，对具有相同属性的数据，其对应的类必须是唯一的。在ID3算法挖掘后，分类规则由决策树来表示。1.ID3算法的基本思想由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。寻找一棵“最好”的决策树是一个NP完全问题。ID3使用一种自顶向下的方法在部分搜索空间创建决策树，同时保证找到一棵简单的决策树—可能不是最简单的。ID3算法的基本思想描述如下：step1．任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；step2．用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果第9章分类规则挖掘与预测8所有的叶结点都有类标记，则算法终止；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的分枝；第9章分类规则挖掘与预测9（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，算法需选择attribute_list中具有最高信息增益的属性test_attribute。ID3算法在树的每个结点上以信息增量（informationgain）作为度量来选择测试属性。这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。InformationGain指标的原理来自于信息论。1948年，香农（C.E.Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci（i=1,2,…,m），si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：I(s1,s2,…,sm)＝－ΣMi=1pilog2(pi)i第9章分类规则挖掘与预测10其中pi是任意样本属于Ci的概率，可用si/s来估计。设属性A具有k个不同值{a1,a2,…,ak}，则可用属性A将S划分为k个子集{S1,S2,…,Sk}，Sj中包含的样本在属性A上具有值aj。如果选择A作为测试属性，则这些子集对应于由包含集合S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数，则按照A划分成子集的熵为：E（A）＝ΣMi=1（（s1j+s2j+…+smj）/s1j）*I(s1,s2,…,sm)信息增益（InformationGain），表示系统由于分类获得的信息量。由系统熵的减少值定量描述。用属性A分类后的信息增益为：Gain(A)=I(s1,s2,…,sm)–E(A)熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是InformationGain，所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，这个最佳方案是用“贪心算法+深度优先搜索”得到的。因为这是一个递归过程，所以仅仅需要讨论对某个特定结点N的分裂方法。（1）分裂前第9章分类规则挖掘与预测11设指向N的训练集为S，其中包含m个不同的类，它们区分了不同的类Ci(fori=1,…,m)。设si是S中属于类Ci的记录的个数。那么分裂之前，系统的总熵：I(s1,s2,…,sm)=-∑Mi=1pilog2(pi)容易看出，总熵是属于各个类的