决策支持系统的核心数据挖

1、决策支持系统的核心决策支持系统的核心数据挖掘方法与技术数据挖掘方法与技术0 决策支持系统（决策支持系统（dss）数据数据模型模型推理推理知识知识决策决策人机人机交互交互1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘（数据挖掘（dm）的产生背景的产生背景n随着数据库技术的迅速发展以及数据库随着数据库技术的迅速发展以及数据库管理系统的广泛应用，管理系统的广泛应用，企业和组织企业和组织积累积累的数据越来越多的数据越来越多1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘（数据挖掘（dm）的产生背景的产生背景n数据库系统可以高效地实现数据的录入、数据库系统可以高效地实现数据的录入、查询、统计等功能

2、，但无法发现数据中查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数存在的关系和规则，无法根据现有的数据预测未来的发展趋势，据预测未来的发展趋势， 从而出现从而出现“数数据爆炸但知识贫乏据爆炸但知识贫乏”的现象的现象1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘（数据挖掘（dm）的产生背景的产生背景n大量数据背后隐藏着许多重要的信息，大量数据背后隐藏着许多重要的信息，企业和组织的管理决策者企业和组织的管理决策者希望能够对其希望能够对其进行更高层次的分析。进行更高层次的分析。1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘（数据挖掘（dm）的产生背景的产生背景ngartn

3、er group的一次高级技术调查结果的一次高级技术调查结果将数据挖掘和人工智能列为将数据挖掘和人工智能列为“将对未来三将对未来三到五年内工业产生深远影响的五大关键技到五年内工业产生深远影响的五大关键技术术”之首；之首；n世界世界500强企业中强企业中80%都涉足数据挖掘的都涉足数据挖掘的前瞻性研究。前瞻性研究。1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的概念的概念 数据挖掘又称为数据库中的知识发现数据挖掘又称为数据库中的知识发现（knowledge discovery from database, kdd），它是一个从大量的、不完全的、有噪），它是一个从大量的、不完全的、有噪

4、声的、模糊的、随机的实际应用数据中抽取挖声的、模糊的、随机的实际应用数据中抽取挖掘出隐含其中的、事先未知的、有价值的模式掘出隐含其中的、事先未知的、有价值的模式或规律等知识的复杂过程，该过程如下图所示。或规律等知识的复杂过程，该过程如下图所示。1 数据挖掘的基本概念数据挖掘的基本概念数据清洗与集成数据清洗与集成任务相关数据集任务相关数据集选择与转换选择与转换数据挖掘数据挖掘评估与表示评估与表示数据仓库数据仓库数据库数据库知识知识1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的概念的概念n数据挖掘涉及多学科技术的集成：数据挖掘涉及多学科技术的集成：数据数据库库技术，统计学，机器学习，

5、高性能计技术，统计学，机器学习，高性能计算，模式识别，神经网络，数据可视化，算，模式识别，神经网络，数据可视化，信息检索，图象与信号处理和空间数据信息检索，图象与信号处理和空间数据分析。分析。1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的概念的概念n数据挖掘功能用于指定数据挖掘任务中数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般分要找的模式类型。数据挖掘任务一般分两类：两类：n描述式数据挖掘：刻描述式数据挖掘：刻画画数据库或数据仓库中数据库或数据仓库中数据的一般特性。数据的一般特性。n预测式数据挖掘：在当前数据上进行推断，预测式数据挖掘：在当前数据上进行推断，

6、以进行预测。以进行预测。1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n概念描述（概念描述（concept description）：利用）：利用数据属性中更广义的（属性）内容对其进行数据属性中更广义的（属性）内容对其进行归纳和总结归纳和总结1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n关联分析（关联分析（association analysis）：从）：从给定的数据集中发现频繁出现的项集模式知给定的数据集中发现频繁出现的项集模式知识识1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n分类（分类（classificatio

7、n）：找出一组能够描）：找出一组能够描述数据集合典型特征的函数，以便能够识别述数据集合典型特征的函数，以便能够识别未知数据的归属或类别，即将未知事例映射未知数据的归属或类别，即将未知事例映射到某个离散类别到某个离散类别1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n聚类分析（聚类分析（clustering analysis）：根据）：根据“各聚集（各聚集（cluster）之内数据对象的相似）之内数据对象的相似度最大化和各聚集之间数据对象相似度最小度最大化和各聚集之间数据对象相似度最小化化”这一原则将数据对象划分为若干组这一原则将数据对象划分为若干组1 数据挖掘的基本概念

8、数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n孤立点分析（孤立点分析（outlier analysis）：寻找不）：寻找不符合大多数数据对象所构成的规律（模型）符合大多数数据对象所构成的规律（模型）的数据对象的数据对象 1 数据挖掘的基本概念数据挖掘的基本概念n数据挖掘数据挖掘的功能的功能n演化分析（演化分析（evolution analysis）：对随）：对随时间变化的数据对象的变化规律和趋势进行时间变化的数据对象的变化规律和趋势进行建模描述建模描述1 数据挖掘的基本概念数据挖掘的基本概念工具特点工具特点分析重点分析重点分析目的分析目的数据大小数据大小控制方式控制方式发展状况发展状况传统

9、数据分析工具传统数据分析工具回顾型、验证型回顾型、验证型已经发生了什么已经发生了什么从最近的销售文件中列出最大客户从最近的销售文件中列出最大客户数据量和数据维度均是少量的数据量和数据维度均是少量的企业管理人员、系统分析员、企业管理人员、系统分析员、管理顾问启动与控制管理顾问启动与控制成熟成熟数据挖掘工具数据挖掘工具发现型、预测型发现型、预测型解释发生的原因、解释发生的原因、预测未来的情况预测未来的情况锁定未来的可能客户，以减少锁定未来的可能客户，以减少未来的销售成本未来的销售成本数据量和数据维度均是庞大的数据量和数据维度均是庞大的数据与系统启动，数据与系统启动，少量的控制人员少量的控制人员发展

10、中发展中数据挖掘工具与传统数据分析工具的比较数据挖掘工具与传统数据分析工具的比较2 数据挖掘功能数据挖掘功能关联规则关联规则n关联规则的基本概念关联规则的基本概念n关联规则挖掘发现大量数据中项集之间有关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。趣的关联或相关联系。n从大量商业事务记录中发现有趣的关联关从大量商业事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析等。类设计、交叉购物和促销分析等。2 数据挖掘功能数据挖掘功能关联规则关联规则n购物篮分析购物篮分析n购物篮分析是关联规则挖掘的最初形式购物篮分析是关联

11、规则挖掘的最初形式n假定作为某商店经理，你想更加了解你的顾假定作为某商店经理，你想更加了解你的顾客的购物习惯。例如：客的购物习惯。例如：“什么商品组或集合什么商品组或集合顾客多半会在一次购物时同时购买？顾客多半会在一次购物时同时购买？”。为为解答这个问题，可以在商店顾客事务零售数解答这个问题，可以在商店顾客事务零售数据上运行购物篮分析。据上运行购物篮分析。n分析的结果可用于市场规划、广告策划和分分析的结果可用于市场规划、广告策划和分类设计。类设计。2 数据挖掘功能数据挖掘功能关联规则关联规则n购物篮分析购物篮分析n若设商店中所有销售商品为一个集合，则每若设商店中所有销售商品为一个集合，则每个商

12、品均为一个布尔变量，表示该商品是否个商品均为一个布尔变量，表示该商品是否被被（一个一个）顾客购买。因此每个购物篮就可顾客购买。因此每个购物篮就可以用一个布尔向量表示。以用一个布尔向量表示。2 数据挖掘功能数据挖掘功能关联规则关联规则n购物篮分析购物篮分析n分析相应布尔向量，得到反映商品频繁关联分析相应布尔向量，得到反映商品频繁关联或同时购买的购买模式，并可用关联规则的或同时购买的购买模式，并可用关联规则的形式表示模式。例如，购买计算机也趋向于形式表示模式。例如，购买计算机也趋向于同时购买财务管理软件可用以下关联规则表同时购买财务管理软件可用以下关联规则表示：示：2 数据挖掘功能数据挖掘功能关联

13、规则关联规则n购物篮分析购物篮分析n关联规则的支持度关联规则的支持度（support）2% 表示分表示分析中的全部事务的析中的全部事务的2% 同时购买计算机和同时购买计算机和财务管理软件。财务管理软件。n关联规则的置信度关联规则的置信度（confidence）60%表表示：购买计算机的顾客示：购买计算机的顾客60% 也购买财务管也购买财务管理软件。理软件。%60%,2_confidencesupportsoftwaremanagementfinancialcomputer2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法napriori算法是根据有关频繁项集性质的先算法是根据

14、有关频繁项集性质的先验知识而命名。该算法使用一种逐层搜索的验知识而命名。该算法使用一种逐层搜索的迭代方法，利用迭代方法，利用k-项集探索项集探索(k+1)-项集。项集。n具体做法：首先找出频繁具体做法：首先找出频繁1-项集的集合，记项集的集合，记为为l1 ；再用；再用l1找频繁找频繁2-项集的集合项集的集合l2；再用；再用l2找找l3 如此下去，直到不能找到频繁如此下去，直到不能找到频繁k-项项集为止。找每个集为止。找每个lk需要一次数据库扫描。需要一次数据库扫描。2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法napriori算法的有效性算法的有效性，在于它利用了一个在于

15、它利用了一个非常重要的原理非常重要的原理，即即apriori性质性质：如果一：如果一个项集是频繁的，则这个项集的任意一个非个项集是频繁的，则这个项集的任意一个非空子集都是频繁的。空子集都是频繁的。napriori性质性质基于如下观察：如果项集基于如下观察：如果项集i不满不满足最小支持度阈值足最小支持度阈值min_sup，则，则i 不是频繁不是频繁的。如果增加项的。如果增加项a到到i，则结果项集不可能，则结果项集不可能比比i更频繁出现。因此，也不是频繁的。更频繁出现。因此，也不是频繁的。2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n该性质属于一种特殊的分类，也称作反单调该

16、性质属于一种特殊的分类，也称作反单调性。意指如果一个集合不能通过测试，则它性。意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试的所有超集也都不能通过相同的测试。n反单调性能迅速减值，提高搜索频繁项集的反单调性能迅速减值，提高搜索频繁项集的处理效率。处理效率。2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n整个过程由连接和剪枝两步组成，整个过程由连接和剪枝两步组成，即即n连接步：为找连接步：为找lk，可通过，可通过lk-1与自己连接，与自己连接，产生一个候选产生一个候选k-项集的集合，该候选项集的项集的集合，该候选项集的集合记作集合记作ck 。剪枝步确定频

17、繁项集连接步产生候选项集2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n设设l1和和l2是是lk-1中的项集，记号中的项集，记号li j表示表示li的第的第j项。为方便计，假定事务或项集中的项按项。为方便计，假定事务或项集中的项按字典次序排序。字典次序排序。n执行连接执行连接 ， 其中其中lk-1的元素是可的元素是可连接的，如果它们连接的，如果它们前前(k-2)个项相同个项相同。lk-1lk-12 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n即即lk-1的元素的元素l1和和l2是可连接的，如果是可连接的，如果（ l11 = l21 l12 = l22

18、 l1k-2 = l2k-2 l1k-1 l2k-1 ）。条件）。条件（l1k-1 l2 k-1）可确保不产生重复的）可确保不产生重复的项集。项集。2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n剪枝步剪枝步nck是是lk的超集，即它的成员不一定都是频繁的超集，即它的成员不一定都是频繁项集，但所有的频繁项集，但所有的频繁k-项集都包含在项集都包含在ck中中n扫描数据库，确定扫描数据库，确定ck中每个候选项集的计数，中每个候选项集的计数，从而确定从而确定lk 。然而，。然而， ck可能很大，这样所涉可能很大，这样所涉及的计算量就很大。及的计算量就很大。2 数据挖掘功能数据挖

19、掘功能关联规则关联规则napriori算法算法n剪枝步剪枝步n为了压缩为了压缩 ck ，可利用，可利用apriori性质：任何非性质：任何非频繁的频繁的(k-1)-项集都不可能是频繁项集都不可能是频繁k-项集的子项集的子集。因此，若一个候选集。因此，若一个候选k-项集的项集的(k-1)-项子集项子集不在不在 lk-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的，从而可以从从而可以从 ck 中删除中删除。2 数据挖掘功能数据挖掘功能关联规则关联规则【例】一个apriori的具体例子，该例基于右图某商店的事务db。db中有9个事务，apriori假定事务中的项按字典次序存放。tid项

20、id的列表t100i1，i2，i5t200i2，i4t300i2，i3t400i1，i2，i4t500i1，i3t600i2，i3t700i1，i3t800i1，i2，i3，i5t900i1，i2，i32 数据挖掘功能数据挖掘功能关联规则关联规则（1）在算法的第一次迭代，每个项都是在算法的第一次迭代，每个项都是候选候选1-1-项项集集的集合的集合c1的成员。算法简单地扫描所有的事的成员。算法简单地扫描所有的事务，对每个项的出现次数计数。务，对每个项的出现次数计数。扫描d d,对每个候选计数项集支持度计数i16i27i36i42i52c12 数据挖掘功能数据挖掘功能关联规则关联规则（2 2）设最

21、小支持计数为）设最小支持计数为2 2，可以确定频繁，可以确定频繁1-1-项项集的集合集的集合lk-1。它由具有最小支持度的候选。它由具有最小支持度的候选1-1-项项集组成。集组成。项集支持度计数i16i27i36i42i52比较候选支持度计数与最小支持度计数l12 数据挖掘功能数据挖掘功能关联规则关联规则（3 3）为发现频繁）为发现频繁2-2-项集的集项集的集合合l2，算法使用，算法使用 产生产生候选候选2-2-项集集合项集集合c2。l1l1项集i1，i2i1，i3i1，i4i1，i5i2，i3i2，i4i2，i5i3，i4i3，i5i4，i5c2由l1产生候选c22 数据挖掘功能数据挖掘功能

22、关联规则关联规则（4 4）扫描）扫描d d中事务，计中事务，计算算c2中每个候选项集的中每个候选项集的支持计数。支持计数。项集支持度计数i1，i24i1，i34i1，i41i1，i52i2，i34i2，i42i2，i52i3，i40i3，i51i4，i50扫描d,对每个候选计数c22 数据挖掘功能数据挖掘功能关联规则关联规则（5 5）确定频繁）确定频繁2-2-项集的集项集的集合合l2，它由具有最小支持，它由具有最小支持度的度的c2中的候选中的候选2-2-项集组项集组成。成。项集支持度计数i1，i24i1，i34i1，i52i2，i34i2，i42i2，i52比较候选支持度计数与最小支持度计数l

23、22 数据挖掘功能数据挖掘功能关联规则关联规则（6 6）候选）候选3-3-项集的集合项集的集合c3的产生如下：的产生如下： 连接：连接： c3= = i1,i2，i1,i3，i1,i5，i2,i3，i2,i4，i2,i5 i1,i2，i1,i3，i1,i5，i2,i3，i2,i4，i2,i5 = i1,i2,i3，i1,i2,i5，i1,i3,i5，i2,i3,i4，i2,i3,i5，i2,i4,i5l2l22 数据挖掘功能数据挖掘功能关联规则关联规则（6 6）候选）候选3-3-项集的集合项集的集合c3的产生如下：的产生如下： 利用利用apriori性质剪枝：频繁项集的所有子集必性质剪枝：频繁

24、项集的所有子集必须是频繁的。存在候选项集，判断其子集是否频须是频繁的。存在候选项集，判断其子集是否频繁。繁。 i1,i2,i3的的2-项子集项子集是是i1,i2，i1,i3和和i2,i3，它们都是它们都是l2的元素。因此保留的元素。因此保留i1,i2,i3在在c3中。中。 i1,i2,i5的的2-项子集项子集是是i1,i2，i1,i5和和i2,i5, 它们都是它们都是l2的元素。因此保留的元素。因此保留i1,i2,i5在在c3中。中。2 数据挖掘功能数据挖掘功能关联规则关联规则（6 6）候选）候选3-3-项集的集合项集的集合c3的产生如下：的产生如下： i1,i3,i5的的2-项子集项子集是是

25、i1,i3，i1,i5和和i3,i5，i3,i5不是不是l2的元素，因而不是频繁的，的元素，因而不是频繁的，由由c3中删除中删除i1,i3,i5。 i2,i3,i4的的2-项子集项子集是是i2,i3，i2,i4和和i3,i4，其中其中i3,i4不是不是l2的元素，因而不是频的元素，因而不是频繁的，由繁的，由c3中删除中删除i2,i3,i4。2 数据挖掘功能数据挖掘功能关联规则关联规则（6 6）候选）候选3-3-项集的集合项集的集合c3的产生如下：的产生如下： i2,i3,i5的的2-项子集项子集是是i2,i3，i2,i5和和i3,i5，其中其中i3,i5不是不是l2的元素，因而不是频的元素，因

26、而不是频繁的，由繁的，由c3中删除中删除 i2,i3,i5。 i2,i4,i5的的2-项子集项子集是是i2,i4，i2,i5和和i4,i5，其中其中i4,i5不是不是l2的元素，因而不是频的元素，因而不是频繁的，由繁的，由c3中删除中删除i2,i4,i5 。这样，剪枝后这样，剪枝后c3 = i1,i2,i3，i1,i2,i5。2 数据挖掘功能数据挖掘功能关联规则关联规则（7 7）扫描）扫描d d中事务，以确定中事务，以确定l3，它由具有最小支，它由具有最小支持度的持度的c3中的候选中的候选3-3-项集组成。项集组成。项集i1，i2，i3i1，i2，i5由l2产生候选c3c3扫描d,对每个候选计

27、数项集支持度计数i1，i2，i32i1，i2，i52c32 数据挖掘功能数据挖掘功能关联规则关联规则（8 8）算法使用算法使用 产生产生候选候选4-项集项集的集合的集合c4。尽管连接产生结果尽管连接产生结果 i1,i2,i3,i5，这个项这个项集将被剪去，因为它的子集集将被剪去，因为它的子集i2,i3,i5不是频不是频繁的。则繁的。则 c4 = ，因此算法终止，找出了所有，因此算法终止，找出了所有的频繁项集。的频繁项集。项集支持度计数i1，i2，i32i1，i2，i52比较候选支持度计数与最小支持度计数l3l3l32 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n基于上例结

28、果，假定数据包含频繁项集基于上例结果，假定数据包含频繁项集l=i1，i2，i5。可以由。可以由l产生哪些关联规产生哪些关联规则？则？nl的非空子集有的非空子集有i1，i2、i1，i5、i2，i5、i1、i2和和i5，则结果关联规则，则结果关联规则如下（每个都列出置信度）。如下（每个都列出置信度）。2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法10022confidencei2,i1i52972confidencei5,i1i23362confidencei5,i2i110022confidencei1,i5i210022confidencei2,i5i15042confi

29、dencei5,i2i1 % % % % % %2 数据挖掘功能数据挖掘功能关联规则关联规则napriori算法算法n如果最小置信度阈值为如果最小置信度阈值为70%，那么只有，那么只有第第2、3、6个规则可以作为最终的输出，个规则可以作为最终的输出，因为只有这些是产生的强规则。因为只有这些是产生的强规则。3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n基于判定树的分类基于判定树的分类n简单贝叶斯分类简单贝叶斯分类3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n分类和预测是数据分析的两种形式，可以用分类和预测

30、是数据分析的两种形式，可以用来提取描述重要数据类的模型或预测未来的来提取描述重要数据类的模型或预测未来的数据趋势数据趋势n分类：预测离散或分类属性分类：预测离散或分类属性n预测：预测连续或有序值预测：预测连续或有序值3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n数据分类数据分类n（1）学习：建立一个描述已知数据集类别或概）学习：建立一个描述已知数据集类别或概念的模型。该模型是通过对念的模型。该模型是通过对db中元组属性的分中元组属性的分析而构造的。假定每个元组属于一个预定义的析而构造的。假定每个元组属于一个预定义的类，由类标号属性确定。为建立模型所

31、使用的类，由类标号属性确定。为建立模型所使用的元组形成训练数据集。其中的单个元组称作训元组形成训练数据集。其中的单个元组称作训练样本，并随机地从样本群体中选取。由于提练样本，并随机地从样本群体中选取。由于提供了每个训练样本的类标号，该步也称作有指供了每个训练样本的类标号，该步也称作有指导的学习导的学习3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n数据分类数据分类n通常学习模型用通常学习模型用分类规则分类规则、判定树判定树或或数学公式数学公式的形式提供的形式提供n例如：给定一个顾客信用信息例如：给定一个顾客信用信息db，通过学习获，通过学习获得的分类

32、规则，可用于识别顾客是否具有良好得的分类规则，可用于识别顾客是否具有良好的信用等级或一般的信用等级的信用等级或一般的信用等级姓名年龄收入信用等级王明=30=30低良张小丽=304040中良方菲4040中良刘力音31-4031-40高优训练数据分类算法分类规则if 年龄=“31-40” and 收入=“高” then 信用等级=“优”（1）学习：用分类算法分析训练数据类标号属性是信用等级，学习模型以分类规则形式提供3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n数据分类数据分类n（2）分类：使用学习得到的模型进行分类。首）分类：使用学习得到的模型进行分

33、类。首先评估模型的预测准确率。有多种方法可以用先评估模型的预测准确率。有多种方法可以用来评估分类的准确率，保持（来评估分类的准确率，保持（holdout）方法是）方法是一种利用类标号样本测试集的简单方法。这些一种利用类标号样本测试集的简单方法。这些样本随机选取，并独立于训练样本。对于每个样本随机选取，并独立于训练样本。对于每个测试样本，将已知的类标号与学习所获模型的测试样本，将已知的类标号与学习所获模型的预测类别进行比较。模型在给定测试集上的准预测类别进行比较。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比确率是正确被模型分类的测试样本的百分比姓名年龄收入信用等级苏寺华4040高

34、良汪洋=30=30低良刘宾31-4031-40高优（2）分类：测试数据用于评估分类规则的准确率（若准确率可以接受，则规则可用于新的数据元组分类）测试数据分类规则新数据(刘宾，31-40，高)信用等级？ 优3 数据挖掘功能数据挖掘功能分类与预测分类与预测n分类与预测的分类与预测的基本知识基本知识n数据预测数据预测n预测是构造和使用模型评估无标号样本类，或预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间评估给定样本可能具有的属性值或值区间n为了提高分类与预测过程的准确性、有效性和为了提高分类与预测过程的准确性、有效性和可伸缩性，可对数据进行预处理。一般使用：可伸缩性，可

35、对数据进行预处理。一般使用：数据清理，相关性分析，数据变换（概念分层数据清理，相关性分析，数据变换（概念分层或规范化）或规范化）3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n判定树判定树n判定树是一个类似流程图的判定树是一个类似流程图的树型结构树型结构，其中，其中每个每个内部节点内部节点表示在一个属性上的测试，每表示在一个属性上的测试，每个个分枝分枝代表一个测试输出，而每个代表一个测试输出，而每个树叶节点树叶节点代表类或类分布代表类或类分布n判定树归纳判定树归纳是构造判定树的基本算法。在判是构造判定树的基本算法。在判定树构造时，许多分枝可能反映的是训练数定

36、树构造时，许多分枝可能反映的是训练数据中的噪声或孤立点。可用据中的噪声或孤立点。可用树剪枝树剪枝方法检测方法检测和剪去这类分枝，以提高在未知数据上分类和剪去这类分枝，以提高在未知数据上分类的准确性的准确性3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（1）判定树归纳：以自顶向下递归的分）判定树归纳：以自顶向下递归的分而治之方式构造判定树。算法的基本策而治之方式构造判定树。算法的基本策略如下：略如下：n判定树以代表训练样本的单个节点开始判定树以代表训练样本的单个节点开始n若一个节点的样本均为同一类别，则该节点若一个节点的样本均为同一类别，则该节点成为树叶，并

37、用该类进行标记成为树叶，并用该类进行标记3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（1）判定树归纳：）判定树归纳：n否则，算法使用信息增益度量作为启发信息，否则，算法使用信息增益度量作为启发信息，选择能够最好地将样本分类的属性，作为该选择能够最好地将样本分类的属性，作为该节点的节点的“测试测试”属性。在此算法中，所有的属性。在此算法中，所有的属性都是分类的，即取离散值。对连续值的属性都是分类的，即取离散值。对连续值的属性必须离散化属性必须离散化n对测试属性的每个已知的值，创建一个分枝，对测试属性的每个已知的值，创建一个分枝，并具此划分样本并具此划分样本

38、3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（1）判定树归纳：）判定树归纳：n算法使用同样的过程，递归地形成每个划分算法使用同样的过程，递归地形成每个划分上的样本判定树。一个属性一旦出现在某个上的样本判定树。一个属性一旦出现在某个节点上，就不再考虑该节点的任何后代节点上，就不再考虑该节点的任何后代n递归划分操作仅当下列条件之一成立时停止：递归划分操作仅当下列条件之一成立时停止：na）给定节点的所有样本属于同一类）给定节点的所有样本属于同一类nb）没有剩余属性可用来进一步划分样本）没有剩余属性可用来进一步划分样本nc）测试属性的一个分枝没有样本）测试属性的

39、一个分枝没有样本3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（2）属性选择方法：）属性选择方法：n在判定树的每个节点上使用在判定树的每个节点上使用信息增益度量信息增益度量选选择测试属性。选择具有择测试属性。选择具有最高信息增益最高信息增益的属性的属性作为当前节点的测试属性，可以使结果划分作为当前节点的测试属性，可以使结果划分中的样本分类需要的信息量最小，并反映划中的样本分类需要的信息量最小，并反映划分的最小随机性。这种信息论方法使得对一分的最小随机性。这种信息论方法使得对一个对象分类所需的期望测试数目达到最小，个对象分类所需的期望测试数目达到最小，并确保

40、找到一棵简单的树。并确保找到一棵简单的树。3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n信息增益度量信息增益度量n设设s是训练样本的集合，其中每个样本的类标是训练样本的集合，其中每个样本的类标号已知号已知n假定有假定有m个类，设个类，设s包含包含si个个ci类样本，类样本，i=1,2,mn任意一个样本属于类任意一个样本属于类ci的可能性为的可能性为si /s，其中，其中s是集合是集合s中样本的总数。中样本的总数。3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n信息增益度量信息增益度量n一个决策树可用于对数据对象进行分类一

41、个决策树可用于对数据对象进行分类,因此因此决策树可以看成是决策树可以看成是ci的一个信息源的一个信息源,为产生相为产生相应信息需要的信息熵（应信息需要的信息熵（entropy）为：）为：sssssssiimiim2121log,3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n信息增益度量信息增益度量n若属性若属性a的取值为的取值为a1, a2, an，且该属性用，且该属性用作决策树的一个结点时，则可将作决策树的一个结点时，则可将s划分为子集划分为子集s1, s2, sn。其中。其中sj包含属性包含属性a取同一值取同一值aj的数据行。记的数据行。记sij为为s

42、j包含类包含类ci的样本个数。的样本个数。3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n信息增益度量信息增益度量n根据属性根据属性a的取值对当前数据集划分所获得的的取值对当前数据集划分所获得的信息就称为属性信息就称为属性a的熵。它的计算公式如下：的熵。它的计算公式如下： 121 ,2 ,1( ),njjmjjjmjjssse ai ssss 3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n信息增益度量信息增益度量na上该划分得到的信息增益定义为上该划分得到的信息增益定义为:： 1,2,( ),( )mgain ai s

43、sse a 3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（2）属性选择方法：）属性选择方法：n判定树归纳算法计算每个属性的信息增益，判定树归纳算法计算每个属性的信息增益，并挑选具有最高信息增益的属性作为给定集并挑选具有最高信息增益的属性作为给定集合的测试属性。创建一个节点，并以该属性合的测试属性。创建一个节点，并以该属性标记。对属性的每个值创建分枝，并据此划标记。对属性的每个值创建分枝，并据此划分样本。分样本。3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n【例】下表给出一个商场顾客【例】下表给出一个商场顾客db数据元

44、组数据元组训练集，类标号属性训练集，类标号属性buys_compute有两个有两个不同值，即不同值，即yes，no ，因此训练集中有两，因此训练集中有两个不同的类（个不同的类（m= 2）。设类）。设类c1对应于对应于yes，而类而类c2对应对应no。类。类c1有有9个样本，类个样本，类c2有有5 个样本。我们用前面的一组公式计算每个属个样本。我们用前面的一组公式计算每个属性的信息增益。性的信息增益。ridrid年龄年龄收入收入学生学生信用级信用级购买电脑购买电脑1 1=30=30高高nono良良nono2 2=304040中中nono良良yesyes5 54040低低yesyes良良yesye

45、s6 64040低低yesyes优优nono7 731403140低低yesyes优优yesyes8 8=30=30中中nono良良nono9 9=304040中中yesyes良良yesyes1111=304040中中nono优优nono3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n首先计算给定样本分类所需的信息增益首先计算给定样本分类所需的信息增益:n接着计算每个属性的熵接着计算每个属性的熵,从属性从属性age开始开始:0.94145log145149log14959issi2221),(),(0.971ssi 3 s2s30age21112111, :

46、”“0ssi 0 s4s4031age22122212, :”“0.971ssi 2 s3s40age23132313, :”“3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n若样本按若样本按age划分，对一个给定的样本分类划分，对一个给定的样本分类所需的期望信息为：所需的期望信息为：n这种划分的信息增益是这种划分的信息增益是: ),(),(),()(0.694ssi145ssi144ssi145agee2313221221110.246ageessiagegain21)(),()(3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树

47、的分类n类似地，可计算：类似地，可计算：n由于由于age在属性中具有最高信息增益，它被在属性中具有最高信息增益，它被选作测试属性。创建一个节点，用选作测试属性。创建一个节点，用age标记，标记，并对每个属性值引出一个分枝。样本据此划并对每个属性值引出一个分枝。样本据此划分，见下图：分，见下图：029.0)(incomegain()0.151gain student 048.0)_(ratingcreditgain收入学生?信用级购买?高no良no高no优no中no良no低yes良yes中yes优yes收入学生?信用级购买?中no良yes低yes良yes低yes优no中yes良yes中no优no

48、收入学生?信用级购买?高no良yes低yes优yes中no优yes高yes良yes年龄?=30303031-4031-40年龄？学生？信用级？yesyesyesnono=3040noyes良优算法返回的最终判定树如下：3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n判定树归纳算法被广泛应用到许多进行分类判定树归纳算法被广泛应用到许多进行分类识别的应用领域，这类算法无需相关领域知识别的应用领域，这类算法无需相关领域知识。归纳的学习与分类识别的操作处理速度识。归纳的学习与分类识别的操作处理速度较快，相应的分类准确率较高。较快，相应的分类准确率较高。 3 数据挖掘功能数据挖掘功能分类与预测分类与预测n基于判定树的分类基于判定树的分类n（3）树剪枝：）树剪枝：n在判定树构造时，许多分枝可能反映的是训在判定树构造时，许多分枝可能反映的是训练数据中的噪声或孤立点。可用树剪枝方法练数据中