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

决策支持系统的核心 数据挖掘方法与技术 0决策支持系统 DSS 数据 模型 推理 知识 决策 人机交互 1数据挖掘的基本概念 数据挖掘 DM 的产生背景随着数据库技术的迅速发展以及数据库管理系统的广泛应用 企业和组织积累的数据越来越多 1数据挖掘的基本概念 数据挖掘 DM 的产生背景数据库系统可以高效地实现数据的录入 查询 统计等功能 但无法发现数据中存在的关系和规则 无法根据现有的数据预测未来的发展趋势 从而出现 数据爆炸但知识贫乏 的现象 1数据挖掘的基本概念 数据挖掘 DM 的产生背景大量数据背后隐藏着许多重要的信息 企业和组织的管理决策者希望能够对其进行更高层次的分析 1数据挖掘的基本概念 数据挖掘 DM 的产生背景GartnerGroup的一次高级技术调查结果将数据挖掘和人工智能列为 将对未来三到五年内工业产生深远影响的五大关键技术 之首 世界500强企业中80 都涉足数据挖掘的前瞻性研究 1数据挖掘的基本概念 数据挖掘的概念数据挖掘又称为数据库中的知识发现 KnowledgeDiscoveryfromDatabase KDD 它是一个从大量的 不完全的 有噪声的 模糊的 随机的实际应用数据中抽取挖掘出隐含其中的 事先未知的 有价值的模式或规律等知识的复杂过程 该过程如下图所示 1数据挖掘的基本概念 1数据挖掘的基本概念 数据挖掘的概念数据挖掘涉及多学科技术的集成 数据库技术 统计学 机器学习 高性能计算 模式识别 神经网络 数据可视化 信息检索 图象与信号处理和空间数据分析 1数据挖掘的基本概念 数据挖掘的概念数据挖掘功能用于指定数据挖掘任务中要找的模式类型 数据挖掘任务一般分两类 描述式数据挖掘 刻画数据库或数据仓库中数据的一般特性 预测式数据挖掘 在当前数据上进行推断 以进行预测 1数据挖掘的基本概念 数据挖掘的功能概念描述 Conceptdescription 利用数据属性中更广义的 属性 内容对其进行归纳和总结 1数据挖掘的基本概念 数据挖掘的功能关联分析 AssociationAnalysis 从给定的数据集中发现频繁出现的项集模式知识 1数据挖掘的基本概念 数据挖掘的功能分类 Classification 找出一组能够描述数据集合典型特征的函数 以便能够识别未知数据的归属或类别 即将未知事例映射到某个离散类别 1数据挖掘的基本概念 数据挖掘的功能聚类分析 ClusteringAnalysis 根据 各聚集 cluster 之内数据对象的相似度最大化和各聚集之间数据对象相似度最小化 这一原则将数据对象划分为若干组 1数据挖掘的基本概念 数据挖掘的功能孤立点分析 OutlierAnalysis 寻找不符合大多数数据对象所构成的规律 模型 的数据对象 1数据挖掘的基本概念 数据挖掘的功能演化分析 EvolutionAnalysis 对随时间变化的数据对象的变化规律和趋势进行建模描述 1数据挖掘的基本概念 数据挖掘工具与传统数据分析工具的比较 2数据挖掘功能 关联规则 关联规则的基本概念关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系 从大量商业事务记录中发现有趣的关联关系 可以帮助许多商务决策的制定 如分类设计 交叉购物和促销分析等 2数据挖掘功能 关联规则 购物篮分析购物篮分析是关联规则挖掘的最初形式假定作为某商店经理 你想更加了解你的顾客的购物习惯 例如 什么商品组或集合顾客多半会在一次购物时同时购买 为解答这个问题 可以在商店顾客事务零售数据上运行购物篮分析 分析的结果可用于市场规划 广告策划和分类设计 2数据挖掘功能 关联规则 购物篮分析若设商店中所有销售商品为一个集合 则每个商品均为一个布尔变量 表示该商品是否被 一个 顾客购买 因此每个购物篮就可以用一个布尔向量表示 2数据挖掘功能 关联规则 购物篮分析分析相应布尔向量 得到反映商品频繁关联或同时购买的购买模式 并可用关联规则的形式表示模式 例如 购买计算机也趋向于同时购买财务管理软件可用以下关联规则表示 2数据挖掘功能 关联规则 购物篮分析关联规则的支持度 support 2 表示分析中的全部事务的2 同时购买计算机和财务管理软件 关联规则的置信度 confidence 60 表示 购买计算机的顾客60 也购买财务管理软件 2数据挖掘功能 关联规则 Apriori算法Apriori算法是根据有关频繁项集性质的先验知识而命名 该算法使用一种逐层搜索的迭代方法 利用k 项集探索 k 1 项集 具体做法 首先找出频繁1 项集的集合 记为L1 再用L1找频繁2 项集的集合L2 再用L2找L3 如此下去 直到不能找到频繁k 项集为止 找每个Lk需要一次数据库扫描 2数据挖掘功能 关联规则 Apriori算法Apriori算法的有效性 在于它利用了一个非常重要的原理 即Apriori性质 如果一个项集是频繁的 则这个项集的任意一个非空子集都是频繁的 Apriori性质基于如下观察 如果项集I不满足最小支持度阈值min sup 则I不是频繁的 如果增加项A到I 则结果项集不可能比I更频繁出现 因此 也不是频繁的 2数据挖掘功能 关联规则 Apriori算法该性质属于一种特殊的分类 也称作反单调性 意指如果一个集合不能通过测试 则它的所有超集也都不能通过相同的测试 反单调性能迅速减值 提高搜索频繁项集的处理效率 2数据挖掘功能 关联规则 Apriori算法整个过程由连接和剪枝两步组成 即连接步 为找Lk 可通过Lk 1与自己连接 产生一个候选k 项集的集合 该候选项集的集合记作Ck 2数据挖掘功能 关联规则 Apriori算法设l1和l2是Lk 1中的项集 记号li j 表示li的第j项 为方便计 假定事务或项集中的项按字典次序排序 执行连接 其中Lk 1的元素是可连接的 如果它们前 k 2 个项相同 2数据挖掘功能 关联规则 Apriori算法即Lk 1的元素l1和l2是可连接的 如果 l1 1 l2 1 l1 2 l2 2 l1 k 2 l2 k 2 l1 k 1 l2 k 1 条件 l1 k 1 l2 k 1 可确保不产生重复的项集 2数据挖掘功能 关联规则 Apriori算法剪枝步Ck是Lk的超集 即它的成员不一定都是频繁项集 但所有的频繁k 项集都包含在Ck中扫描数据库 确定Ck中每个候选项集的计数 从而确定Lk 然而 Ck可能很大 这样所涉及的计算量就很大 2数据挖掘功能 关联规则 Apriori算法剪枝步为了压缩Ck 可利用Apriori性质 任何非频繁的 k 1 项集都不可能是频繁k 项集的子集 因此 若一个候选k 项集的 k 1 项子集不在Lk 1中 则该候选也不可能是频繁的 从而可以从Ck中删除 2数据挖掘功能 关联规则 例 一个Apriori的具体例子 该例基于右图某商店的事务DB DB中有9个事务 Apriori假定事务中的项按字典次序存放 2数据挖掘功能 关联规则 1 在算法的第一次迭代 每个项都是候选1 项集的集合C1的成员 算法简单地扫描所有的事务 对每个项的出现次数计数 C1 2数据挖掘功能 关联规则 2 设最小支持计数为2 可以确定频繁1 项集的集合Lk 1 它由具有最小支持度的候选1 项集组成 L1 2数据挖掘功能 关联规则 3 为发现频繁2 项集的集合L2 算法使用产生候选2 项集集合C2 C2 2数据挖掘功能 关联规则 4 扫描D中事务 计算C2中每个候选项集的支持计数 C2 2数据挖掘功能 关联规则 5 确定频繁2 项集的集合L2 它由具有最小支持度的C2中的候选2 项集组成 L2 2数据挖掘功能 关联规则 6 候选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 I5 2数据挖掘功能 关联规则 6 候选3 项集的集合C3的产生如下 利用Apriori性质剪枝 频繁项集的所有子集必须是频繁的 存在候选项集 判断其子集是否频繁 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 候选3 项集的集合C3的产生如下 I1 I3 I5 的2 项子集是 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 候选3 项集的集合C3的产生如下 I2 I3 I5 的2 项子集是 I2 I3 I2 I5 和 I3 I5 其中 I3 I5 不是L2的元素 因而不是频繁的 由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 扫描D中事务 以确定L3 它由具有最小支持度的C3中的候选3 项集组成 C3 C3 2数据挖掘功能 关联规则 8 算法使用产生候选4 项集的集合C4 尽管连接产生结果 I1 I2 I3 I5 这个项集将被剪去 因为它的子集 I2 I3 I5 不是频繁的 则C4 因此算法终止 找出了所有的频繁项集 L3 2数据挖掘功能 关联规则 Apriori算法基于上例结果 假定数据包含频繁项集l I1 I2 I5 可以由l产生哪些关联规则 l的非空子集有 I1 I2 I1 I5 I2 I5 I1 I2 和 I5 则结果关联规则如下 每个都列出置信度 2数据挖掘功能 关联规则 Apriori算法 2数据挖掘功能 关联规则 Apriori算法如果最小置信度阈值为70 那么只有第2 3 6个规则可以作为最终的输出 因为只有这些是产生的强规则 3数据挖掘功能 分类与预测 分类与预测的基本知识基于判定树的分类简单贝叶斯分类 3数据挖掘功能 分类与预测 分类与预测的基本知识分类和预测是数据分析的两种形式 可以用来提取描述重要数据类的模型或预测未来的数据趋势分类 预测离散或分类属性预测 预测连续或有序值 3数据挖掘功能 分类与预测 分类与预测的基本知识数据分类 1 学习 建立一个描述已知数据集类别或概念的模型 该模型是通过对DB中元组属性的分析而构造的 假定每个元组属于一个预定义的类 由类标号属性确定 为建立模型所使用的元组形成训练数据集 其中的单个元组称作训练样本 并随机地从样本群体中选取 由于提供了每个训练样本的类标号 该步也称作有指导的学习 3数据挖掘功能 分类与预测 分类与预测的基本知识数据分类通常学习模型用分类规则 判定树或数学公式的形式提供例如 给定一个顾客信用信息DB 通过学习获得的分类规则 可用于识别顾客是否具有良好的信用等级或一般的信用等级 3数据挖掘功能 分类与预测 分类与预测的基本知识数据分类 2 分类 使用学习得到的模型进行分类 首先评估模型的预测准确率 有多种方法可以用来评估分类的准确率 保持 holdout 方法是一种利用类标号样本测试集的简单方法 这些样本随机选取 并独立于训练样本 对于每个测试样本 将已知的类标号与学习所获模型的预测类别进行比较 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比 3数据挖掘功能 分类与预测 分类与预测的基本知识数据预测预测是构造和使用模型评估无标号样本类 或评估给定样本可能具有的属性值或值区间为了提高分类与预测过程的准确性 有效性和可伸缩性 可对数据进行预处理 一般使用 数据清理 相关性分析 数据变换 概念分层或规范化 3数据挖掘功能 分类与预测 基于判定树的分类判定树判定树是一个类似流程图的树型结构 其中每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 而每个树叶节点代表类或类分布判定树归纳是构造判定树的基本算法 在判定树构造时 许多分枝可能反映的是训练数据中的噪声或孤立点 可用树剪枝方法检测和剪去这类分枝 以提高在未知数据上分类的准确性 3数据挖掘功能 分类与预测 基于判定树的分类 1 判定树归纳 以自顶向下递归的分而治之方式构造判定树 算法的基本策略如下 判定树以代表训练样本的单个节点开始若一个节点的样本均为同一类别 则该节点成为树叶 并用该类进行标记 3数据挖掘功能 分类与预测 基于判定树的分类 1 判定树归纳 否则 算法使用信息增益度量作为启发信息 选择能够最好地将样本分类的属性 作为该节点的 测试 属性 在此算法中 所有的属性都是分类的 即取离散值 对连续值的属性必须离散化对测试属性的每个已知的值 创建一个分枝 并具此划分样本 3数据挖掘功能 分类与预测 基于判定树的分类 1 判定树归纳 算法使用同样的过程 递归地形成每个划分上的样本判定树 一个属性一旦出现在某个节点上 就不再考虑该节点的任何后代递归划分操作仅当下列条件之一成立时停止 a 给定节点的所有样本属于同一类b 没有剩余属性可用来进一步划分样本c 测试属性的一个分枝没有样本 3数据挖掘功能 分类与预测 基于判定树的分类 2 属性选择方法 在判定树的每个节点上使用信息增益度量选择测试属性 选择具有最高信息增益的属性作为当前节点的测试属性 可以使结果划分中的样本分类需要的信息量最小 并反映划分的最小随机性 这种信息论方法使得对一个对象分类所需的期望测试数目达到最小 并确保找到一棵简单的树 3数据挖掘功能 分类与预测 基于判定树的分类信息增益度量设S是训练样本的集合 其中每个样本的类标号已知假定有m个类 设S包含si个Ci类样本 i 1 2 m任意一个样本属于类Ci的可能性为si s 其中s是集合S中样本的总数 3数据挖掘功能 分类与预测 基于判定树的分类信息增益度量一个决策树可用于对数据对象进行分类 因此决策树可以看成是Ci的一个信息源 为产生相应信息需要的信息熵 entropy 为 3数据挖掘功能 分类与预测 基于判定树的分类信息增益度量若属性A的取值为 a1 a2 an 且该属性用作决策树的一个结点时 则可将S划分为子集 S1 S2 Sn 其中Sj包含属性A取同一值aj的数据行 记sij为Sj包含类Ci的样本个数 3数据挖掘功能 分类与预测 基于判定树的分类信息增益度量根据属性A的取值对当前数据集划分所获得的信息就称为属性A的熵 它的计算公式如下 3数据挖掘功能 分类与预测 基于判定树的分类信息增益度量A上该划分得到的信息增益定义为 3数据挖掘功能 分类与预测 基于判定树的分类 2 属性选择方法 判定树归纳算法计算每个属性的信息增益 并挑选具有最高信息增益的属性作为给定集合的测试属性 创建一个节点 并以该属性标记 对属性的每个值创建分枝 并据此划分样本 3数据挖掘功能 分类与预测 基于判定树的分类 例 下表给出一个商场顾客DB数据元组训练集 类标号属性buys compute有两个不同值 即 yes no 因此训练集中有两个不同的类 m 2 设类C1对应于yes 而类C2对应no 类C1有9个样本 类C2有5个样本 我们用前面的一组公式计算每个属性的信息增益 3数据挖掘功能 分类与预测 基于判定树的分类首先计算给定样本分类所需的信息增益 接着计算每个属性的熵 从属性age开始 3数据挖掘功能 分类与预测 基于判定树的分类若样本按age划分 对一个给定的样本分类所需的期望信息为 这种划分的信息增益是 3数据挖掘功能 分类与预测 基于判定树的分类类似地 可计算 由于age在属性中具有最高信息增益 它被选作测试属性 创建一个节点 用age标记 并对每个属性值引出一个分枝 样本据此划分 见下图 3数据挖掘功能 分类与预测 基于判定树的分类判定树归纳算法被广泛应用到许多进行分类识别的应用领域 这类算法无需相关领域知识 归纳的学习与分类识别的操作处理速度较快 相应的分类准确率较高 3数据挖掘功能 分类与预测 基于判定树的分类 3 树剪枝 在判定树构造时 许多分枝可能反映的是训练数据中的噪声或孤立点 可用树剪枝方法检测和剪去这类分