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

1、决策支持系统的核心数据挖 决策支持系统的核心决策支持系统的核心 数据挖掘方法与技术数据挖掘方法与技术 决策支持系统的核心数据挖 0 决策支持系统（决策支持系统（DSS） 数据数据 模型模型 推理推理知识知识 决策决策 人机人机 交互交互 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘（数据挖掘（DM）的产生背景的产生背景 n随着数据库技术的迅速发展以及数据库随着数据库技术的迅速发展以及数据库 管理系统的广泛应用，企业和组织积累管理系统的广泛应用，企业和组织积累 的数据越来越多的数据越来越多 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数

2、据挖掘（数据挖掘（DM）的产生背景的产生背景 n数据库系统可以高效地实现数据的录入、数据库系统可以高效地实现数据的录入、 查询、统计等功能，但无法发现数据中查询、统计等功能，但无法发现数据中 存在的关系和规则，无法根据现有的数存在的关系和规则，无法根据现有的数 据预测未来的发展趋势，据预测未来的发展趋势， 从而出现从而出现“数数 据爆炸但知识贫乏据爆炸但知识贫乏”的现象的现象 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘（数据挖掘（DM）的产生背景的产生背景 n大量数据背后隐藏着许多重要的信息，大量数据背后隐藏着许多重要的信息， 企业和组织的管理决策者希望能够

3、对其企业和组织的管理决策者希望能够对其 进行更高层次的分析。进行更高层次的分析。 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘（数据挖掘（DM）的产生背景的产生背景 nGartner Group的一次高级技术调查结果的一次高级技术调查结果 将数据挖掘和人工智能列为将数据挖掘和人工智能列为“将对未来三将对未来三 到五年内工业产生深远影响的五大关键技到五年内工业产生深远影响的五大关键技 术术”之首；之首； n世界世界500强企业中强企业中80%都涉足数据挖掘的都涉足数据挖掘的 前瞻性研究。前瞻性研究。 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本

4、概念 n数据挖掘数据挖掘的概念的概念 数据挖掘又称为数据库中的知识发现数据挖掘又称为数据库中的知识发现 （Knowledge Discovery from Database, KDD），它是一个从大量的、不完全的、有噪），它是一个从大量的、不完全的、有噪 声的、模糊的、随机的实际应用数据中抽取挖声的、模糊的、随机的实际应用数据中抽取挖 掘出隐含其中的、事先未知的、有价值的模式掘出隐含其中的、事先未知的、有价值的模式 或规律等知识的复杂过程，该过程如下图所示。或规律等知识的复杂过程，该过程如下图所示。 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 数据清洗与集成数据清洗与集

5、成 任务相关数据集任务相关数据集 选择与转换选择与转换 数据挖掘数据挖掘 评估与表示评估与表示 数据仓库数据仓库 数据库数据库 知识知识 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的概念的概念 n数据挖掘涉及多学科技术的集成：数据数据挖掘涉及多学科技术的集成：数据 库技术，统计学，机器学习，高性能计库技术，统计学，机器学习，高性能计 算，模式识别，神经网络，数据可视化，算，模式识别，神经网络，数据可视化， 信息检索，图象与信号处理和空间数据信息检索，图象与信号处理和空间数据 分析。分析。 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本

6、概念 n数据挖掘数据挖掘的概念的概念 n数据挖掘功能用于指定数据挖掘任务中数据挖掘功能用于指定数据挖掘任务中 要找的模式类型。数据挖掘任务一般分要找的模式类型。数据挖掘任务一般分 两类：两类： n描述式数据挖掘：刻画数据库或数据仓库中描述式数据挖掘：刻画数据库或数据仓库中 数据的一般特性。数据的一般特性。 n预测式数据挖掘：在当前数据上进行推断，预测式数据挖掘：在当前数据上进行推断， 以进行预测。以进行预测。 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的功能的功能 n概念描述（概念描述（Concept description）：利用）：利用 数据属性

7、中更广义的（属性）内容对其进行数据属性中更广义的（属性）内容对其进行 归纳和总结归纳和总结 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的功能的功能 n关联分析（关联分析（Association Analysis）：从）：从 给定的数据集中发现频繁出现的项集模式知给定的数据集中发现频繁出现的项集模式知 识识 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的功能的功能 n分类（分类（Classification）：找出一组能够描）：找出一组能够描 述数据集合典型特征的函数，以便能够识别述数据集合典型特征的函数，以便

8、能够识别 未知数据的归属或类别，即将未知事例映射未知数据的归属或类别，即将未知事例映射 到某个离散类别到某个离散类别 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的功能的功能 n聚类分析（聚类分析（Clustering Analysis）：根据）：根据 “各聚集（各聚集（cluster）之内数据对象的相似）之内数据对象的相似 度最大化和各聚集之间数据对象相似度最小度最大化和各聚集之间数据对象相似度最小 化化”这一原则将数据对象划分为若干组这一原则将数据对象划分为若干组 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖

9、掘的功能的功能 n孤立点分析（孤立点分析（Outlier Analysis）：寻找不）：寻找不 符合大多数数据对象所构成的规律（模型）符合大多数数据对象所构成的规律（模型） 的数据对象的数据对象 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 n数据挖掘数据挖掘的功能的功能 n演化分析（演化分析（Evolution Analysis）：对随）：对随 时间变化的数据对象的变化规律和趋势进行时间变化的数据对象的变化规律和趋势进行 建模描述建模描述 决策支持系统的核心数据挖 1 数据挖掘的基本概念数据挖掘的基本概念 工具特点工具特点 分析重点分析重点 分析目的分析目的 数据大小数

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

11、度均是庞大的 数据与系统启动，数据与系统启动， 少量的控制人员少量的控制人员 发展中发展中 数据挖掘工具与传统数据分析工具的比较数据挖掘工具与传统数据分析工具的比较 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 n关联规则的基本概念关联规则的基本概念 n关联规则挖掘发现大量数据中项集之间有关联规则挖掘发现大量数据中项集之间有 趣的关联或相关联系。趣的关联或相关联系。 n从大量商业事务记录中发现有趣的关联关从大量商业事务记录中发现有趣的关联关 系，可以帮助许多商务决策的制定，如分系，可以帮助许多商务决策的制定，如分 类设计、交叉购物和促销分析等。类设计、交叉购物和促销分

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

13、划和分 类设计。类设计。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 n购物篮分析购物篮分析 n若设商店中所有销售商品为一个集合，则每若设商店中所有销售商品为一个集合，则每 个商品均为一个布尔变量，表示该商品是否个商品均为一个布尔变量，表示该商品是否 被（一个）顾客购买。因此每个购物篮就可被（一个）顾客购买。因此每个购物篮就可 以用一个布尔向量表示。以用一个布尔向量表示。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 n购物篮分析购物篮分析 n分析相应布尔向量，得到反映商品频繁关联分析相应布尔向量，得到反映商品频繁关联 或同时购买的购买模式

14、，并可用关联规则的或同时购买的购买模式，并可用关联规则的 形式表示模式。例如，购买计算机也趋向于形式表示模式。例如，购买计算机也趋向于 同时购买财务管理软件可用以下关联规则表同时购买财务管理软件可用以下关联规则表 示：示： 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 n购物篮分析购物篮分析 n关联规则的支持度（关联规则的支持度（support）2% 表示分表示分 析中的全部事务的析中的全部事务的2% 同时购买计算机和同时购买计算机和 财务管理软件。财务管理软件。 n关联规则的置信度（关联规则的置信度（confidence）60%表表 示：购买计算机的顾客示：购买计算

15、机的顾客60% 也购买财务管也购买财务管 理软件。理软件。 %60%,2 _ confidencesupport softwaremanagementfinancialcomputer 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 nApriori算法是根据有关频繁项集性质的先算法是根据有关频繁项集性质的先 验知识而命名。该算法使用一种逐层搜索的验知识而命名。该算法使用一种逐层搜索的 迭代方法，利用迭代方法，利用k-项集探索项集探索(k+1)-项集。项集。 n具体做法：首先找出频繁具体做法：首先找出频繁1-项集的集合，记项集的集合，记 为为L

16、1 ；再用；再用L1找频繁找频繁2-项集的集合项集的集合L2；再用；再用 L2找找L3 如此下去，直到不能找到频繁如此下去，直到不能找到频繁k-项项 集为止。找每个集为止。找每个Lk需要一次数据库扫描。需要一次数据库扫描。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 nApriori算法的有效性算法的有效性，在于它利用了一个在于它利用了一个 非常重要的原理非常重要的原理，即即Apriori性质性质：如果一：如果一 个项集是频繁的，则这个项集的任意一个非个项集是频繁的，则这个项集的任意一个非 空子集都是频繁的。空子集都是频繁的。 nAprio

17、ri性质性质基于如下观察：如果项集基于如下观察：如果项集I不满不满 足最小支持度阈值足最小支持度阈值min_sup，则，则I 不是频繁不是频繁 的。如果增加项的。如果增加项A到到I，则结果项集不可能，则结果项集不可能 比比I更频繁出现。因此，也不是频繁的。更频繁出现。因此，也不是频繁的。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n该性质属于一种特殊的分类，也称作反单调该性质属于一种特殊的分类，也称作反单调 性。意指如果一个集合不能通过测试，则它性。意指如果一个集合不能通过测试，则它 的所有超集也都不能通过相同的测试。的所有超集也都不能通

18、过相同的测试。 n反单调性能迅速减值，提高搜索频繁项集的反单调性能迅速减值，提高搜索频繁项集的 处理效率。处理效率。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n整个过程由连接和剪枝两步组成，即整个过程由连接和剪枝两步组成，即 n连接步：为找连接步：为找Lk，可通过，可通过Lk-1与自己连接，与自己连接， 产生一个候选产生一个候选k-项集的集合，该候选项集的项集的集合，该候选项集的 集合记作集合记作Ck 。 剪枝步确定频繁项集连接步产生候选项集 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算

19、法 n设设l1和和l2是是Lk-1中的项集，记号中的项集，记号li j表示表示li的第的第 j项。为方便计，假定事务或项集中的项按项。为方便计，假定事务或项集中的项按 字典次序排序。字典次序排序。 n执行连接执行连接 ， 其中其中Lk-1的元素是可的元素是可 连接的，如果它们前连接的，如果它们前(k-2)个项相同。个项相同。 Lk-1Lk-1 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n即即Lk-1的元素的元素l1和和l2是可连接的，如果是可连接的，如果 （ l11 = l21 l12 = l22 l1k- 2 = l2k-2 l1k-1

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

21、核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n剪枝步剪枝步 n为了压缩为了压缩 Ck ，可利用，可利用Apriori性质：任何非性质：任何非 频繁的频繁的(k-1)-项集都不可能是频繁项集都不可能是频繁k-项集的子项集的子 集。因此，若一个候选集。因此，若一个候选k-项集的项集的(k-1)-项子集项子集 不在不在 Lk-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的， 从而可以从从而可以从 Ck 中删除。中删除。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 【例】一个Apriori的 具体例子，该例基 于右图某商

22、店的事 务DB。DB中有9个事 务，Apriori假定事 务中的项按字典次 序存放。 TID项ID的列表 T100I1，I2，I5 T200I2，I4 T300I2，I3 T400I1，I2，I4 T500I1，I3 T600I2，I3 T700I1，I3 T800I1，I2，I3，I5 T900I1，I2，I3 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （1）在算法的第一次迭代，每个项都是在算法的第一次迭代，每个项都是候选候选1-1-项项 集集的集合的集合C1的成员。算法简单地扫描所有的事的成员。算法简单地扫描所有的事 务，对每个项的出现次数计数。务，对每个项的

23、出现次数计数。 扫描D D,对每 个候选计数 项集支持度计数 I16 I27 I36 I42 I52 C1 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （2 2）设最小支持计数为）设最小支持计数为2 2，可以确定频繁，可以确定频繁1-1-项项 集的集合集的集合Lk-1。它由具有最小支持度的候选。它由具有最小支持度的候选1-1-项项 集组成。集组成。 项集支持度计数 I16 I27 I36 I42 I52 比较候选支持度计数 与最小支持度计数 L1 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （3 3）为发现频繁）为发现频繁2-2-项集的集

24、项集的集 合合L2，算法使用，算法使用 产生产生 候选候选2-2-项集集合项集集合C2。 L1L1 项集 I1，I2 I1，I3 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I3，I4 I3，I5 I4，I5 C2 由L1产生候选C2 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （4 4）扫描）扫描D D中事务，计中事务，计 算算C2中每个候选项集的中每个候选项集的 支持计数。支持计数。 项集支持度计数 I1，I24 I1，I34 I1，I41 I1，I52 I2，I34 I2，I42 I2，I52 I3，I40 I3，I51 I4，I50 扫描D,

25、对每 个候选计数 C2 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （5 5）确定频繁）确定频繁2-2-项集的集项集的集 合合L2，它由具有最小支持，它由具有最小支持 度的度的C2中的候选中的候选2-2-项集组项集组 成。成。 项集支持度计数 I1，I24 I1，I34 I1，I52 I2，I34 I2，I42 I2，I52 比较候选支持度计数 与最小支持度计数 L2 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （6 6）候选）候选3-3-项集的集合项集的集合C3的产生如下：的产生如下： 连接：连接： C3= = I1,I2，I1,I3，

26、 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,I5 L2L2 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （6 6）候选）候选3-3-项集的集合项集的集合C3的产生如下：的产生如下： 利用利用Apriori性质剪枝：频繁项集的所有子集必性质剪枝：频繁项集的所有子集必 须是频繁的。存在候选项集，判断其子集是否频须是频繁的。存在候选项集，判断其子集是否频 繁。繁。 I1,I2,I3的的2

27、-项子集项子集是是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-项子集项子集是是I1,I3，I1,I5和和 I3,I5，I3,I5不是不是L2的元素，因而不是频繁的，的元素，

28、因而不是频繁的， 由由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的元素，因而不是频的元素，因而不是频 繁的，由繁的，由C3中删除中删除 I2,I3

29、,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，I3 I1，I2，I5 由L2产生候选C3 C3 扫描D,对每 个候选计

30、数 项集支持度计数 I1，I2，I32 I1，I2，I52 C3 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 （8 8）算法使用算法使用 产生产生候选候选4-项集项集的集合的集合C4。 尽管连接产生结果尽管连接产生结果 I1,I2,I3,I5，这个项这个项 集将被剪去，因为它的子集集将被剪去，因为它的子集I2,I3,I5不是频不是频 繁的。则繁的。则 C4 = ，因此算法终止，找出了所有，因此算法终止，找出了所有 的频繁项集。的频繁项集。 项集支持度计数 I1，I2，I32 I1，I2，I52 比较候选支持度计数 与最小支持度计数 L3 L3L3 决策支持系统的核心

31、数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n基于上例结果，假定数据包含频繁项集基于上例结果，假定数据包含频繁项集 l=I1，I2，I5。可以由。可以由l产生哪些关联规产生哪些关联规 则？则？ nl的非空子集有的非空子集有I1，I2、I1，I5、I2， I5、I1、I2和和I5，则结果关联规则，则结果关联规则 如下（每个都列出置信度）。如下（每个都列出置信度）。 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 10022confidenceI2,I1I5 2972confidenceI5,I1I2 3362c

32、onfidenceI5,I2I1 10022confidenceI1,I5I2 10022confidenceI2,I5I1 5042confidenceI5,I2I1 % % % % % % % % % % 决策支持系统的核心数据挖 2 数据挖掘功能数据挖掘功能关联规则关联规则 nApriori算法算法 n如果最小置信度阈值为如果最小置信度阈值为70%，那么只有，那么只有 第第2、3、6个规则可以作为最终的输出，个规则可以作为最终的输出， 因为只有这些是产生的强规则。因为只有这些是产生的强规则。 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与

33、预测的基本知识基本知识 n基于判定树的分类基于判定树的分类 n简单贝叶斯分类简单贝叶斯分类 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与预测的基本知识基本知识 n分类和预测是数据分析的两种形式，可以用分类和预测是数据分析的两种形式，可以用 来提取描述重要数据类的模型或预测未来的来提取描述重要数据类的模型或预测未来的 数据趋势数据趋势 n分类：预测离散或分类属性分类：预测离散或分类属性 n预测：预测连续或有序值预测：预测连续或有序值 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与预测的基本知识基

34、本知识 n数据分类数据分类 n（1）学习：建立一个描述已知数据集类别或概）学习：建立一个描述已知数据集类别或概 念的模型。该模型是通过对念的模型。该模型是通过对DB中元组属性的分中元组属性的分 析而构造的。假定每个元组属于一个预定义的析而构造的。假定每个元组属于一个预定义的 类，由类标号属性确定。为建立模型所使用的类，由类标号属性确定。为建立模型所使用的 元组形成训练数据集。其中的单个元组称作训元组形成训练数据集。其中的单个元组称作训 练样本，并随机地从样本群体中选取。由于提练样本，并随机地从样本群体中选取。由于提 供了每个训练样本的类标号，该步也称作有指供了每个训练样本的类标号，该步也称作有

35、指 导的学习导的学习 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与预测的基本知识基本知识 n数据分类数据分类 n通常学习模型用通常学习模型用分类规则分类规则、判定树判定树或或数学公式数学公式 的形式提供的形式提供 n例如：给定一个顾客信用信息例如：给定一个顾客信用信息DB，通过学习获，通过学习获 得的分类规则，可用于识别顾客是否具有良好得的分类规则，可用于识别顾客是否具有良好 的信用等级或一般的信用等级的信用等级或一般的信用等级 决策支持系统的核心数据挖 姓名年龄收入信用等级 王明=30=30低良 张小丽=304040中良 方菲4040中良

36、刘力音31-4031-40高优 训练数据 分类算法 分类规则 if 年龄=“31-40” and 收入=“高” then 信用等级=“优” （1）学习：用分类算法分析 训练数据 类标号属性是信用等级， 学习模型以分类规则形式 提供 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与预测的基本知识基本知识 n数据分类数据分类 n（2）分类：使用学习得到的模型进行分类。首）分类：使用学习得到的模型进行分类。首 先评估模型的预测准确率。有多种方法可以用先评估模型的预测准确率。有多种方法可以用 来评估分类的准确率，保持（来评估分类的准确率，保持（holdo

37、ut）方法是）方法是 一种利用类标号样本测试集的简单方法。这些一种利用类标号样本测试集的简单方法。这些 样本随机选取，并独立于训练样本。对于每个样本随机选取，并独立于训练样本。对于每个 测试样本，将已知的类标号与学习所获模型的测试样本，将已知的类标号与学习所获模型的 预测类别进行比较。模型在给定测试集上的准预测类别进行比较。模型在给定测试集上的准 确率是正确被模型分类的测试样本的百分比确率是正确被模型分类的测试样本的百分比 决策支持系统的核心数据挖 姓名年龄收入信用等级 苏寺华4040高良 汪洋=30=30低良 刘宾31-4031-40高优 （2）分类：测试数据用于评估分类规则的准 确率（若准

38、确率可以接受，则规则可用于新的数据元 组分类） 测试数据 分类规则 新数据 (刘宾，31-40，高) 信用等级？ 优 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n分类与预测的分类与预测的基本知识基本知识 n数据预测数据预测 n预测是构造和使用模型评估无标号样本类，或预测是构造和使用模型评估无标号样本类，或 评估给定样本可能具有的属性值或值区间评估给定样本可能具有的属性值或值区间 n为了提高分类与预测过程的准确性、有效性和为了提高分类与预测过程的准确性、有效性和 可伸缩性，可对数据进行预处理。一般使用：可伸缩性，可对数据进行预处理。一般使用： 数据清理，相关性分

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

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

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

42、已知的值，创建一个分枝，对测试属性的每个已知的值，创建一个分枝， 并具此划分样本并具此划分样本 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n（1）判定树归纳：）判定树归纳： n算法使用同样的过程，递归地形成每个划分算法使用同样的过程，递归地形成每个划分 上的样本判定树。一个属性一旦出现在某个上的样本判定树。一个属性一旦出现在某个 节点上，就不再考虑该节点的任何后代节点上，就不再考虑该节点的任何后代 n递归划分操作仅当下列条件之一成立时停止：递归划分操作仅当下列条件之一成立时停止： na）给定节点的所有样本属于同一类）给定节点

43、的所有样本属于同一类 nb）没有剩余属性可用来进一步划分样本）没有剩余属性可用来进一步划分样本 nc）测试属性的一个分枝没有样本）测试属性的一个分枝没有样本 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n（2）属性选择方法：）属性选择方法： n在判定树的每个节点上使用在判定树的每个节点上使用信息增益度量信息增益度量选选 择测试属性。选择具有择测试属性。选择具有最高信息增益最高信息增益的属性的属性 作为当前节点的测试属性，可以使结果划分作为当前节点的测试属性，可以使结果划分 中的样本分类需要的信息量最小，并反映划中的样本分类需要

44、的信息量最小，并反映划 分的最小随机性。这种信息论方法使得对一分的最小随机性。这种信息论方法使得对一 个对象分类所需的期望测试数目达到最小，个对象分类所需的期望测试数目达到最小， 并确保找到一棵简单的树。并确保找到一棵简单的树。 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n信息增益度量信息增益度量 n设设S是训练样本的集合，其中每个样本的类标是训练样本的集合，其中每个样本的类标 号已知号已知 n假定有假定有m个类，设个类，设S包含包含si个个Ci类样本，类样本， i=1,2,m n任意一个样本属于类任意一个样本属于类Ci的可

45、能性为的可能性为si /s，其中，其中 s是集合是集合S中样本的总数。中样本的总数。 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n信息增益度量信息增益度量 n一个决策树可用于对数据对象进行分类一个决策树可用于对数据对象进行分类,因此因此 决策树可以看成是决策树可以看成是Ci的一个信息源的一个信息源,为产生相为产生相 应信息需要的信息熵（应信息需要的信息熵（entropy）为：）为： s s s s sssI i m i i m2 1 21log, 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n

46、基于判定树的分类基于判定树的分类 n信息增益度量信息增益度量 n若属性若属性A的取值为的取值为a1, a2, an，且该属性用，且该属性用 作决策树的一个结点时，则可将作决策树的一个结点时，则可将S划分为子集划分为子集 S1, S2, Sn。其中。其中Sj包含属性包含属性A取同一值取同一值aj 的数据行。记的数据行。记sij为为Sj包含类包含类Ci的样本个数。的样本个数。 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n信息增益度量信息增益度量 n根据属性根据属性A的取值对当前数据集划分所获得的的取值对当前数据集划分所获得的 信

47、息就称为属性信息就称为属性A的熵。它的计算公式如下：的熵。它的计算公式如下： 12 1 ,2 , 1 ( ), n jjmj jjmj j sss E AI sss s 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n信息增益度量信息增益度量 nA上该划分得到的信息增益定义为上该划分得到的信息增益定义为:： 1,2,( ),( )mGain AI s ssE A 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n（2）属性选择方法：）属性选择方法： n判定树归纳算法

48、计算每个属性的信息增益，判定树归纳算法计算每个属性的信息增益， 并挑选具有最高信息增益的属性作为给定集并挑选具有最高信息增益的属性作为给定集 合的测试属性。创建一个节点，并以该属性合的测试属性。创建一个节点，并以该属性 标记。对属性的每个值创建分枝，并据此划标记。对属性的每个值创建分枝，并据此划 分样本。分样本。 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n【例例】下表给出一个商场顾客下表给出一个商场顾客DB数据元组数据元组 训练集，类标号属性训练集，类标号属性buys_compute有两个有两个 不同值，即不同值，即yes

49、，no ，因此训练集中有两，因此训练集中有两 个不同的类（个不同的类（m= 2）。设类）。设类C1对应于对应于yes， 而类而类C2对应对应no。类。类C1有有9个样本，类个样本，类C2有有5 个样本。我们用前面的一组公式计算每个属个样本。我们用前面的一组公式计算每个属 性的信息增益。性的信息增益。 决策支持系统的核心数据挖 RIDRID年龄年龄收入收入学生学生信用级信用级购买电脑购买电脑 1 1=30=30高高NoNo良良NoNo 2 2=304040中中NoNo良良YesYes 5 54040低低YesYes良良YesYes 6 64040低低YesYes优优NoNo 7 73131404

50、0低低YesYes优优YesYes 8 8=30=30中中NoNo良良NoNo 9 9=304040中中YesYes良良YesYes 1111=304040中中NoNo优优NoNo 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n首先计算给定样本分类所需的信息增益首先计算给定样本分类所需的信息增益: n接着计算每个属性的熵接着计算每个属性的熵,从属性从属性age开始开始: 0.94 14 5 log 14 5 14 9 log 14 9 59IssI 2221 ),(),( 0.971ssI 3 s2s30age 2111211

51、1 , :”“ 0ssI 0 s4s4031age 22122212 , :”“ 0.971ssI 2 s3s40age 23132313 , :”“ 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n若样本按若样本按age划分，对一个给定的样本分类划分，对一个给定的样本分类 所需的期望信息为：所需的期望信息为： n这种划分的信息增益是这种划分的信息增益是: ),(),(),()(0.694ssI 14 5 ssI 14 4 ssI 14 5 ageE 231322122111 0.246ageEssIageGain 21 )()

52、,()( 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n类似地，可计算：类似地，可计算： n由于由于age在属性中具有最高信息增益，它被在属性中具有最高信息增益，它被 选作测试属性。创建一个节点，用选作测试属性。创建一个节点，用age标记，标记， 并对每个属性值引出一个分枝。样本据此划并对每个属性值引出一个分枝。样本据此划 分，见下图：分，见下图： 029.0)(incomeGain ()0.151Gain student 048.0)_(ratingcreditGain 决策支持系统的核心数据挖 收入学生?信用级购买? 高N

53、o良No 高No优No 中No良No 低Yes良Yes 中Yes优Yes 收入学生?信用级购买? 中No良Yes 低Yes良Yes 低Yes优No 中Yes良Yes 中No优No 收入学生?信用级购买? 高No良Yes 低Yes优Yes 中No优Yes 高Yes良Yes 年龄? =30303031-4031-40 决策支持系统的核心数据挖 年龄？ 学生？信用级？yes yesyesnono =3040 noyes 良优 算法返回的最终判定树如下： 决策支持系统的核心数据挖 3 数据挖掘功能数据挖掘功能分类与预测分类与预测 n基于判定树的分类基于判定树的分类 n判定树归纳算法被广泛应用到许多进行分类判定树归纳算法被广泛应用到许多进行分类 识别的应用领域，这类算法无需相关领域知识别的应用领域，这类算法无需相关领域知 识。归纳的学习与分类识别的操作处理速度识。归纳的学习与分类识别的