数据仓库与数据挖掘技术第6章1决策树.ppt

1,第六章 数据挖掘的基本算法,主要内容分类规则挖掘的基本思想是什么？预测分析与趋势分析规则的基本思想是什么？关联算法的基本思想是什么？聚类算法的基本思想是什么？统计分析算法的基本思想是什么？品种优化算法的基本思想是什么？数据挖掘的进化算法的基本思想是什么？,2,1.分类规则挖掘的基本思想是什么？,3,分类（classification）,分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。主要目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每一类找到一种准确的描述或模型。,4,分类（classification）,分类问题是数据挖掘领域中研究和应用最为广泛的技术之一分类问题在商业、银行业、医疗诊断、生物学、文本挖掘和因特网筛选等领域都有广泛应用。银行业，可以辅助工作人员将正常信用卡用户和欺诈信用卡用户进行分类，从而采取有效措施减少银行的损失；医疗诊断，可以帮助医疗人员将正常细胞和癌变细胞进行分类，从而及时制定救治方案，挽救病人的生命；因特网筛选，可以协助网络工作人员将正常邮件和垃圾邮件进行分类，从而制定有效的垃圾邮件过滤机制，防止垃圾邮件干扰人们的正常生活。,5,数据分类的基本步骤（参见P126127）,数据分类过程主要包含两个步骤 学习建模 分类测试,6,数据分类步骤一：学习建模,建立一个描述已知数据集类别或概念的模型；该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可认为是属于一个确定的数据类别，其类别值是由一个属性描述（被称为类别标记属性）。（分类问题数据集的表示）分类学习方法所使用的数据集称为训练样本集合，因此分类学习又可称为监督学习（learning by example），它是在已知训练样本类别情况下，通过学习建立相应模型；而无教师监督学习则是训练样本的类别与类别个数均未知的情况下进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式，或数学公式形式。,7,学习建模举例,例如：给定一个顾客信用信息数据库，通过学习所获得的分类规则可用于识别顾客是否是具有良好的信用等级或一般的信用等级。,利用训练数据集学习并获得分类规则知识（模型）,8,数据分类步骤二：分类测试,就是利用所获得的模型进行分类操作 首先对模型分类准确率进行估计，holdout方法就是一种简单的估计方法。它利用一组带用类别的样本进行分类测试（测试样本随机获得且与训练样本相互独立）。对于一个给定数据集所构造出模型的准确性可以通过由该模型所正确分类的（测试）数据样本个数所占总测试样本比例得到。对于每一个测试样本，其已知的类别与学习所获模型的预测类别进行相比较。若模型的准确率是通过对学习数据集的测试所获得的，这样由于学习模型倾向于过分逼近训练数据，从而造成对模型测试准确率的估计过于乐观。因此需要使用一个测试数据集来对学习所获模型的准确率进行测试工作。,9,分类测试举例,利用学习获得的分类规则（模型），对已知测试数据进行模型准确率的评估，以及对未知（类别）的新顾客（类别）进行分类预测。,10,分类问题中使用的数据集是用什么形式来表示的呢？,分类问题的示例数据集,描述属性,类别属性,11,可以将分类问题中使用的数据集表示为X=(xi,yi)|i=1,2,total其中数据样本xi(i=1,2,total)用d维特征向量xi=(xi1,xi2,xid)来表示，xi1,xi2,xid分别对应d个描述属性A1,A2,Ad的具体取值；yi表示数据样本xi的类标号。假设给定数据集包含m个类别，则yic1,c2,cm,其中c1,c2,cm是类别属性c的具体取值，也称为类标号，对于未知类标号的数据样本x，用d维特征向量x=(x1,x2,xd)来表示。,12,应用举例一,现有一个顾客邮件地址数据库。利用这些邮件地址可以给潜在顾客发送用于促销的新商品宣传册和将要开始的商品打折信息。该数据库内容就是有关顾客情况的描述，包括年龄、收入、职业和信用等级等属性描述，顾客被分类为是否会成为在本商场购买商品的顾客。当新顾客的信息被加入到数据库中时，就需要对该顾客是否会成为电脑买家进行分类识别（即对顾客购买倾向进行分类），以决定是否给该顾客发送相应商品的宣传册。考虑到不加区分地给每名顾客都发送这类促销宣传册显然是一种很大浪费，而相比之下，有针对性给最大的购买可能的顾客发送其所需要的商品广告才是一种高效节俭的市场营销策略。显然为满足这种应用需求就需要建立顾客（购买倾向）分类规则模型，以帮助商家准确判别之后每个新加入顾客的可能购买倾向。此外若需要对顾客在一年内可能会在商场购买商品的次数（为有序值）进行预测时，就需要建立预测模型以帮助准确获取每个新顾客在本商店可能进行的购买次数。,13,应用举例二,客户跳槽数据集（P127表6.1）,14,估值,与分类的区别与分类的描述的是离散型变量的输出不同，估值处理的是连续值的输出。分类的类别是确定的数目，估值的量是不确定的如：根据购买模式，估计一个家庭的收入与分类的联系估值可作为分类的前一步工作即通过估值，得到未知的连续变量的值，然后根据预先设定的阈值，进行分类例如，银行处理家庭贷款业务，先运用估值给各个客户记分，然后根据阈值，将贷款级别分类。,15,最为典型的分类方法决策树（参见P128）,所谓决策树，就是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性（取值）的测试，其分支就代表测试的每个结果；而树的每个叶结点就代表一个类别。树的最高层结点就是根结点。,决策树有两种结点：决策结点（引出若干树枝，每个树枝代表一个决策方案，每个方案树枝连接到一个新的结点）状态结点（对应着叶结点，表示一个具体的最终状态）,优点：可理解性和直观性（结构简单、效率高）难点：如何选择一个好的分支方法进行取值,16,决策树分类算法,决策树分类过程,17,决策树举例,C1,C2,C2,C2,C1,18,决策树的构造,决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则；采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，而叶节点是要学习划分的类。从根节点到叶节点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。目前已有多种决策树算法：CLS、ID3、CHAID、C4.5、CART、SLIQ、SPRINT等。著名的ID3（Iterative Dichotomiser3）算法是在1986年提出的，该算法引入了信息论中的理论，是基于信息熵的决策树分类算法。,19,决策树ID3算法,ID3算法的核心是：在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，以使得在每一个非叶节点进行测试时能获得关于被测试记录最大的类别信息。具体方法：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分枝，再对各分支的子集递归调用该方法建立决策树结点的分枝，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。,20,选择属性方法,在决策树归纳方法中，通常使用信息增益方法来帮助确定生成每个结点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性作为当前结点的测试属性，以便使对之后所划分获得的训练样本子集进行分类所需要信息最小，也就是说，利用该属性进行当前（结点所含）样本集合划分，将会使得所产生的各样本子集中的“不同类别混合程度”降为最低。因此采用这样一种信息论方法将帮助有效减少对象分类所需要的次数，从而确保所产生的决策树最为简单，尽管不一定是最简单的。,21,分类所需要的信息量,22,利用属性A划分当前样本集合所需要的信息（熵）,23,信息增益,24,算法ID3的一种描述,25,一个商场顾客数据库,【例】用决策树考察某顾客是否会购买PC（P130）,26,=0.94,年龄=“40”：c13=3，c23=2 I(c13，c23)=0.971,1)创建根结点,由给定训练集，类标号属性为购买PC，它有两个不同的值(“是”、“否”)，即有两个不同的类，m=2；设c1对应“是”，c2对应“否”，则c1=9，c2=5；样本总数s=14。所以训练集中两个类别的先验概率分别为：,计算对给定样本分类所需的期望信息,下面计算每个属性的熵。从年龄开始计算,27,如果样本按年龄划分，对一个给定的样本分类所需的期望信息如下：,因此，这种划分的信息增益是：,Gain(年龄)=I(C1，C2)-E(年龄)=0.246,28,找出最大的字段信息增益：MAX(Gain(年龄),Gain(收入),Gain(学生否),Gain(信用)=Gain(年龄)所以以“年龄”字段为结点，并根据年龄字段的3各不同的取值产生3各不同的分支。,Gain(年龄)=0.246Gain(收入)=0.029Gain(是否学生)=0.151Gain(信用)=0.048,同理可得,29,2)分支建立,考虑分支“学生=否”的结点，由于所有记录属于同一类别“否”，所以分支“学生=否”的结点为叶结点。考虑分支“学生=是”的结点，由于所有记录属于同一类别“是”，所以分支“学生=是”的结点为叶结点。考虑分支“信用=优”的结点，由于所有记录属于同一类别“否”，所以分支“信用=否”的结点为叶结点。考虑分支“信用=中”的结点，由于所有记录属于同一类别“是”，所以分支“信用=是”的结点为叶结点。,考虑分支“年龄=40”的结点因为Gain(收入)=0.02，Gain(学生)=0.02，Gain(信用)=0.971所以分支“年龄=40”结点的测试属性为“信用”。,考虑分支“年龄=3140”的结点，由于所有记录属于同一类别“是”，所以分支“年龄=3140”的结点为叶结点。,考虑分支“年龄=30”的结点因为Gain(收入)=0.571，Gain(学生)=0.971，Gain(信用)=0.02所以分支“年龄=30”结点的测试属性为“学生”。,30,建立的决策树,由决策树提取分类规则：对从根到树叶的每条路径创建一个形如IFTHEN的规则。沿着给定路径上的内部“结点分支”对形成规则前件（“IF”部分），叶结点形成规则后件（“THEN”部分）。,31,树的修剪,在一个决策树刚刚建立起来的时候，它其中的许多分支都是根据训练样本集合中的异常数据（由于噪声等原因）构造出来。树枝修剪正是针对这类数据过分近似（overfitting）问题而提出的。树枝修剪方法通常利用统计方法删去最不可靠的分支（树枝），以提高今后分类识别的速度和分类识别新数据的能力。两种方法：事前修剪（先剪枝）事后修剪（后剪枝）,32,事前修剪,该方法通过提起停止分支生成过程，即通过在当前结点熵就判断是否需要继续划分该结点所含训练样本集来实现。一旦停止分支，当前结点就成为一个叶结点。该叶结点中可能包含多个不同类别的训练样本。在建造一个决策树时，可以利用统计上的重要性检测x2或信息增益等来对分支生成情况（优劣）进行评估。如果在一个结点上划分样本集时，会导致（所产生的）结点中样本数少于指定的阈值，则就要停止继续分解样本集合 但确定这样一个合理的阈值常常叶比较困难。阈值过大会导致决策树过于简单化，而阈值过小时又会导致多余树枝无法修剪,33,事后修剪,该方法从一个“充分生长”树中，修剪掉多余的树枝（分支）基于代价成本的修剪算法就时一个事后修剪方法被修剪（分支）的结点就成为一个叶结点，并将其标记为它所包含样本中类别个数最多的类别。而对于树中每个非叶结点，计算出若该结点（分支）被修剪后所发生的预期分类错误率；同时根据每个分支的分类错误率，以及每个分支的权重（样本分布），计算若该结点不被修剪时的预期分类错误率；如果修剪导致预期分类错误率变大，则放弃修剪，保留相应结点的各个分支，否则就将相应结点分支修剪删去。在产生一系列经过修剪的决策树候选之后，利用一个独立的测试数据集，对这些经过修剪的决策树的分类准确性进行评价，保留下预期分类错误率最小的（修建后）决策树。,34,决策树的应用,商业领域：决策树所能解决的典型商业问题有：客户关系管理、数据库营销、客户群体划分、交叉销售等市场分析行为，以及客户流失分析、客户信用计分及欺诈发现，等等。工业领域：故障诊断、工业生产过程控制等。医学领域：疾病诊断治疗、基因与高分子序列分析、医院信息系统挖掘及医疗政策分析等。,35,决策树的应用,现在，有许多研究机构和公司开发了一些采用决策树技术进行数据挖掘和知识发现的应用系统，如LMDT，OCI，SE-Learn，SIPINA-W，AC2，C4.5，IND，KATE-Tools，Knowledge SEEKER，SPSS CHAID，CART等。另外，还有美国Vanguard Software公司的Decision Pro3.0，Litigation Risk Analysis公司的Litigation Risk Analysis。SAS和SGI等公司的数据挖掘系统中都有决策树模块。,36,思考,在网上搜索并了解目前基于决策树方法的数据挖掘工具有哪些？主要应用在哪些方面？,