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