数据仓库与数据挖掘技术1决策树

《数据仓库与数据挖掘技术1决策树》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘技术1决策树（36页珍藏版）》请在金锄头文库上搜索。

1、第六章 数据挖掘的基本算法主要内容n分类规则挖掘的基本思想是什么？n预测分析与趋势分析规则的基本思想是什么？n关联算法的基本思想是什么？n聚类算法的基本思想是什么？n统计分析算法的基本思想是什么？n品种优化算法的基本思想是什么？n数据挖掘的进化算法的基本思想是什么？11.分类规则挖掘的基本思想是什么？2分类（classification）l分类是指把数据样本映射到一个事先定义 的类中的学习过程，即给定一组输入的属 性向量及其对应的类，用基于归纳的学习 算法得出分类。 l主要目的是分析输入数据，通过在训练集 中的数据表现出来的特性，为每一类找到 一种准确的描述或模型。3分类（classifica

2、tion）l分类问题是数据挖掘领域中研究和应用最为广 泛的技术之一l分类问题在商业、银行业、医疗诊断、生物学 、文本挖掘和因特网筛选等领域都有广泛应用 。银行业，可以辅助工作人员将正常信用卡用户和欺诈信 用卡用户进行分类，从而采取有效措施减少银行的损失 ；医疗诊断，可以帮助医疗人员将正常细胞和癌变细胞进 行分类，从而及时制定救治方案，挽救病人的生命；因特网筛选，可以协助网络工作人员将正常邮件和垃圾 邮件进行分类，从而制定有效的垃圾邮件过滤机制，防 止垃圾邮件干扰人们的正常生活。4数据分类的基本步骤（参见P126127）l 数据分类过程主要包含两个步骤 学习建模 分类测试5数据分类步骤一：学习建

3、模l 建立一个描述已知数据集类别或概念的模型；该模型是 通过对数据库中各数据行内容的分析而获得的。 每一数据行都可认为是属于一个确定的数据类别， 其类别值是由一个属性描述（被称为类别标记属性） 。（分类问题数据集的表示） 分类学习方法所使用的数据集称为训练样本集合， 因此分类学习又可称为监督学习（learning by example ），它是在已知训练样本类别情况下，通过学习建立 相应模型；而无教师监督学习则是训练样本的类别与 类别个数均未知的情况下进行的。l通常分类学习所获得的模型可以表示为分类规则形式、 决策树形式，或数学公式形式。6学习建模举例l例如：给定一个顾客信用信息数据库，通过学

4、 习所获得的分类规则可用于识别顾客是否是具 有良好的信用等级或一般的信用等级。利用训练数据集学习并获得分类规则知识（模型）7数据分类步骤二：分类测试l 就是利用所获得的模型进行分类操作 首先对模型分类准确率进行估计，holdout方法就是一 种简单的估计方法。它利用一组带用类别的样本进行分 类测试（测试样本随机获得且与训练样本相互独立）。 对于一个给定数据集所构造出模型的准确性可以通过 由该模型所正确分类的（测试）数据样本个数所占总测 试样本比例得到。 对于每一个测试样本，其已知的类别与学习所获模型 的预测类别进行相比较。若模型的准确率是通过对学习 数据集的测试所获得的，这样由于学习模型倾向于

5、过分 逼近训练数据，从而造成对模型测试准确率的估计过于 乐观。 因此需要使用一个测试数据集来对学习所获模型的准 确率进行测试工作。8分类测试举例利用学习获得的分类规则（模型），对已知测试数据进行模型准确率的 评估，以及对未知（类别）的新顾客（类别）进行分类预测。9分类问题中使用的数据集是用什么形式来表示的呢？AgeSalaryClass 30highC1 25highC2 21lowC2 43highC1 18lowC2 33lowC1 分类问题的示例数据集描述属性类别属性10可以将分类问题中使用的数据集表示为 X=(xi,yi)|i=1,2,totall其中数据样本xi(i=1,2,tota

6、l)用d维特征向量xi =(xi1,xi2,xid)来表示，xi1,xi2,xid分别对应d个描 述属性A1, A2,Ad的具体取值；yi表示数据样本 xi的类标号。l假设给定数据集包含m个类别，则yic1, c2,cm,其中c1, c2,cm是类别属性c的具体取值 ，也称为类标号，对于未知类标号的数据样本x ，用d维特征向量x =(x1,x2,xd)来表示。11应用举例一l现有一个顾客邮件地址数据库。 利用这些邮件地址可以给潜在 顾客发送用于促销的新商品宣传册和将要开始的商品打折信息 。 该数据库内容就是有关顾客情况的描述，包括年龄、收入、职业 和信用等级等属性描述，顾客被分类为是否会成为在

7、本商场购买 商品的顾客。 当新顾客的信息被加入到数据库中时，就需要对该顾客是否会成 为电脑买家进行分类识别（即对顾客购买倾向进行分类），以决 定是否给该顾客发送相应商品的宣传册。 考虑到不加区分地给每名顾客都发送这类促销宣传册显然是一种 很大浪费，而相比之下，有针对性给最大的购买可能的顾客发送 其所需要的商品广告才是一种高效节俭的市场营销策略。 显然为 满足这种应用需求就需要建立顾客（购买倾向）分类规则模型， 以帮助商家准确判别之后每个新加入顾客的可能购买倾向。 此外若需要对顾客在一年内可能会在商场购买商品的次数（为有 序值）进行预测时，就需要建立预测模型以帮助准确获取每个新 顾客在本商店可能

8、进行的购买次数。12应用举例二l 客户跳槽数据集 （P127表6.1）13估值l 与分类的区别与分类的描述的是离散型变量的输出不同，估 值处理的是连续值的输出。分类的类别是确定的数目，估值的量是不确定 的l如：根据购买模式，估计一个家庭的收入l与分类的联系估值可作为分类的前一步工作l即通过估值，得到未知的连续变量的值，然后根据 预先设定的阈值，进行分类l例如，银行处理家庭贷款业务，先运用估值给各个 客户记分，然后根据阈值，将贷款级别分类。14最为典型的分类方法决策树（参见P128）l所谓决策树，就是一个类似流程图的树型结构，其中树的 每个内部结点代表对一个属性（取值）的测试，其分支就 代表测试

9、的每个结果；而树的每个叶结点就代表一个类别 。树的最高层结点就是根结点。 决策树有两种结点： 决策结点（引出若 干树枝，每个树枝代 表一个决策方案，每 个方案树枝连接到一 个新的结点） 状态结点（对应着 叶结点，表示一个具 体的最终状态）u 优点：可理解性和直观性（结构简单、效率高） u 难点：如何选择一个好的分支方法进行取值15决策树分类算法决策树分类过程16决策树举例C1C2C2C2C117决策树的构造l决策树是以实例为基础的归纳学习算法。它从一组无次 序、无规则的元组中推理出决策树表示形式的分类规则 ；采用自顶向下的递归方式，在决策树的内部节点进行 属性值的比较，并根据不同的属性值从该节

10、点向下分支 ，而叶节点是要学习划分的类。从根节点到叶节点的一 条路径就对应着一条合取规则，整个决策树就对应着一 组析取表达式规则。l目前已有多种决策树算法：CLS、ID3、CHAID、C4.5 、CART、SLIQ、SPRINT等。l著名的ID3（Iterative Dichotomiser3）算法是 J.R.Quinlan在1986年提出的，该算法引入了信息论中 的理论，是基于信息熵的决策树分类算法。18决策树ID3算法l ID3算法的核心是：在决策树各级节点上选择属 性时，用信息增益作为属性的选择标准，以使 得在每一个非叶节点进行测试时能获得关于被 测试记录最大的类别信息。l具体方法：检测

11、所有的属性，选择信息增益最 大的属性产生决策树结点，由该属性的不同取 值建立分枝，再对各分支的子集递归调用该方 法建立决策树结点的分枝，直到所有子集仅包 含同一类别的数据为止，最后得到一棵决策树 ，它可以用来对新的样本进行分类。19选择属性方法l在决策树归纳方法中，通常使用信息增益方法 来帮助确定生成每个结点时所应采用的合适属 性。这样就可以选择具有最高信息增益（熵减少的程度最 大）的属性作为当前结点的测试属性，以便使对之后 所划分获得的训练样本子集进行分类所需要信息最小 ，也就是说，利用该属性进行当前（结点所含）样本 集合划分，将会使得所产生的各样本子集中的“不同 类别混合程度”降为最低。因

12、此采用这样一种信息论方法将帮助有效减少对象分 类所需要的次数，从而确保所产生的决策树最为简单 ，尽管不一定是最简单的。20分类所需要的信息量21利用属性A划分当前样本集合所需要的信息（熵）22信息增益23算法ID3的一种描述24序号年 龄收 入是否学生信 用购买PC140中否中是540低是中是640低是优否73140低是优是840中是中是1140中否优否一个商场顾客数据库【例】 用决策树考察某顾客是否会购买PC（P130）25= 0.94年龄=“40”： c13=3，c23=2 I (c13，c23)=0.9711) 创建根结点由给定训练集，类标号属性为购买PC，它有两个不同的值 (“是”、“

13、否”)，即有两个不同的类，m=2；设c1对应“是”，c2 对应“否”，则c1=9，c2=5；样本总数s=14。所以训练集中 两个类别的先验概率分别为：计算对给定样本分类所需的期望信息下面计算每个属性的熵。从年龄开始计算26如果样本按年龄划分，对一个给定的样本分类所需的期望信 息如下：因此，这种划分的信息增益是：Gain(年龄)=I(C1，C2) - E(年龄)=0.24627找出最大的字段信息增益：MAX(Gain(年龄), Gain(收入), Gain(学生否),Gain(信用) = Gain(年龄)所以以“年龄”字段为结点，并根据年龄字段 的3各不同的取值产生3各不同的分支。Gain(年龄

14、)=0.246 Gain(收入)=0.029 Gain(是否学生)=0.151 Gain(信用)=0.048同理可得282) 分支建立考虑分支“学生=否”的结点，由于所有记录属于同一类别“否”，所以分支“学生 =否”的结点为叶结点。 考虑分支“学生=是”的结点，由于所有记录属于同一类别“是”，所以分支“学生 =是”的结点为叶结点。 考虑分支“信用=优”的结点，由于所有记录属于同一类别“否”，所以分支“信用 =否”的结点为叶结点。 考虑分支“信用=中”的结点，由于所有记录属于同一类别“是”，所以分支“信用 =是”的结点为叶结点。考虑分支“年龄=40”的结点 因为Gain (收入)= 0.02，G

15、ain(学生)= 0.02，Gain(信用)= 0.971 所以分支“年龄=40”结点的测试属性为“信用”。考虑分支“年龄=3140”的结点，由于所有记录属于同一类别“是” ，所以分支“年龄=3140”的结点为叶结点。考虑分支“年龄=30”的结点 因为Gain(收入)= 0.571，Gain(学生)=0.971，Gain(信用)= 0.02 所以分支“年龄=30”结点的测试属性为“学生”。29建立的决策树由决策树提取分类规则：对从根到树叶的每条路 径创建一个形如IFTHEN 的规则。沿着给定路径上 的内部“结点分支”对形 成规则前件（“IF”部分）， 叶结点形成规则后件（ “THEN”部分）。

16、30树的修剪l 在一个决策树刚刚建立起来的时候，它其中的许 多分支都是根据训练样本集合中的异常数据（由 于噪声等原因）构造出来。 树枝修剪正是针对这类数据过分近似（overfitting ）问题而提出的。 树枝修剪方法通常利用统计方法删去最不可靠的 分支（树枝），以提高今后分类识别的速度和分 类识别新数据的能力。 两种方法：l 事前修剪（先剪枝）l 事后修剪（后剪枝）31事前修剪l该方法通过提起停止分支生成过程，即通过在当前结点 熵就判断是否需要继续划分该结点所含训练样本集来实 现。一旦停止分支，当前结点就成为一个叶结点。该叶 结点中可能包含多个不同类别的训练样本。l 在建造一个决策树时，可以利用统计上的重要性检测x2 或信息增益等来对分支生成情况（优劣）进行评估。 如果在一个结点上划分样本集时，会导致（所产生 的）结点中样本数少于指定的阈值，则就要