《数据仓库与数据挖掘技术 教学课件 ppt 作者 夏火松 数据仓库与数据挖掘技术教案PPT(6-10章)》由会员分享，可在线阅读，更多相关《数据仓库与数据挖掘技术 教学课件 ppt 作者 夏火松 数据仓库与数据挖掘技术教案PPT(6-10章)（80页珍藏版）》请在金锄头文库上搜索。
1、数据仓库与数据挖掘技术,Electronic Commerce 夏火松 E-MAIL:BXXHSSINA.COM,数据仓库与数据挖掘技术教案,第6章 数据挖掘基本算法,本章内容： 6.1 分类规则挖掘 6.2 预测分析与趋势分析规则 6.3 数据挖掘的关联算法 6.4 数据挖掘的聚类算法 6.5 数据挖掘的统计分析算法 6.6 数据挖掘的品种优化算法 6.7 数据挖掘的进化算法,6.1 分类规则挖掘,6.1.1分类与估值 1 分类 为了理解事物特征并做出预测使用历史数据建立一个分类模型（即分类器）的过程 。 应用于信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等 实践应用参照课本,6.1
2、 分类规则挖掘,6.1.1分类与估值 2 估值 估值（estimation）与分类类似，不同之处在于，分类描述的是离散型变量的输出，而估值处理连续值的输出；分类的类别是确定的数目，估值的量是不确定的。 3 分类方法与步骤 方法：决策树归纳、贝叶斯分类、贝叶斯网络、神经网络。还有K-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法。 步骤：模型创建、模型使用,6.1 分类规则挖掘,6.1.1分类与估值 4 评估分类方法 要考虑的指标：预测准确率、速度、创建速度、使用速度、鲁棒性、处理噪声和丢失值、伸缩性、对磁盘驻留数据的处理能力、可解释性、对模型的可理解程度、规则好坏的评价、决策树的大小
3、和分类规则的简明性。,6.1 分类规则挖掘,6.1.2 决策树,6.1 分类规则挖掘,6.1.2 决策树 1决策树的构造过程 ID3算法应用如下：,信息量计算公式：I(s1,s2,sm)=-,（6.1） 其中，pi为si占整个类别的概率 利用属性A划分当前样本集合所需要的信息（熵）的计算公式为： E（A）=,(6.2) 信息增益公式：Gain（A）= I(s1,s2,sm)-E（A） （6.3） 例如：一个销售的顾客数据库（训练样本集合）,对购买计算机的人员进行分类： 字段为：（年龄（取值：40）；收入(高，中，低)；学生否（Y，N）；信用（一般，很好）；购买计算机否（Y，N） 记录为14个，
4、具体数据如下： X1=(40, 中,N, 一般,Y) X5=(40, 低,Y, 一般,Y)；X6=(40, 低,Y, 很好,N) X7=(40, 中,Y, 一般,Y) X11=(40,中,N, 很好,N),6.1 分类规则挖掘,6.1.2 决策树 1决策树的构造过程 决策树的构造算法： 决策树的构造算法可通过训练集T完成，其中T=，而x=(a1,a2,an)为一个训练实例，它有n个属性，分别列于属性表(A1,A2,An)中，其中ai表示属性Ai的取值。CjC=C1,C2,Cm为x的分类结果。从属性表中选择属性Ai作为分类属性；若属性Ai的取值有ki个，则将T划分为ki个子集，T1,Tki，其中
5、Tij=|T，且x的属性取值A为第i个值；接下来从属性表中删除属性Ai；对于每一个Tij(1jK1)，令T=Tij；如果属性表非空，返回第1步，否则输出。,6.1 分类规则挖掘,6.1.2 决策树 2分类器 定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。 具体步骤 ： 1）树的建立。 2）树的修剪,SLIQ采用了MDL（最小叙述长度）的方法来修剪树。,6.1 分类规则挖掘,6.1.2 决策树 3决策树的可扩展性 4基于决策树方法的数据挖掘工具 KnowledgSEEKER,6.1 分类规则挖掘,6.1.3 贝叶斯分类 1贝叶斯信
6、任网络如何工作,6.1 分类规则挖掘,6.1.3 贝叶斯分类 2贝叶斯定理与朴素贝叶斯分类 贝叶斯定理: P(H|X)=P(X|H)P(H)/P(X) 其中，P(H|X)表示条件X下H的概率，也称为条件概率或称为后验概率(posteriori probabilities)。 朴素贝叶斯分类： 假定有m个类C1, Cm,对于数据样本X,分类法将预测X属于类Ci,当且仅当 P(Ci|X) P(Cj|X),6.2预测分析与趋势分析规则,6.2.1 预言的基本方法 预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。 预测的基本步骤：
7、确定预测目标，包括预测对象、目的、对象范围； 收集分析内部和外部资料； 数据的处理及模型的选择； 预测模型的分析、修正； 确定预测值。,6.2 预测分析与趋势分析规则,6.2.2 定量分析预测 时间序列法 回归预测 非线性模型 灰色预测模型GM（1，1） 组合预测,6.2 预测分析与趋势分析规则,6.2.3预测的结果分析 预测的结果分析要考虑到的因素： 相反的预测结果 胜出裕度 成本收益分析,6.2 预测分析与趋势分析规则,6.2.4 趋势分析挖掘 分析时间序列数据需要注意以下方面 ： 长时间的走向 周期的走向与周期的变化 季节性的走向与变化 不规则的随机走向,6.3 数据挖掘的关联算法,6.
8、3.1 关联规则的概念及分类 1关联规则的概念 定义1 设I=i1、i2、i3，,im是由m个不同的数据项目组成的集合，其中的元素称为项(item)，项的集合称为项集，包含k个项的项集称为k项集,给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的一个子集，即，T有一个惟一的标积符TID；当且仅当时，称交易T包含项集X；那么关联规则就形如“X=Y”的蕴涵式；其中，即表示满足X中条件的记录也一定满足Y。关联规则X=Y在交易数据库中成立, 具有支持度s和具有置信度c 。 这也就是交易数据集D中具有支持度s，即D中至少有s%的事务包含,描述 为：support(X=Y)= 比
9、如Support(X=Y )=同时购买商品X和Y的交易数总交易数 同时交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y,描述为：confidence(X=Y)= 比如购买了商品X，同时购买商品Y可信度，confidence(X=Y)=同时购买商品X和Y的交易数购买了商品X的交易数 一般称满足一定要求的规则为强规则。通常称满足最小支持度和最小置信度的关联规则为强关联规则（strong）。一般将最小支持度简记为minsup和最小置信度简记为minconf。,6.3 数据挖掘的关联算法,6.3.1 关联规则的概念及分类 2 关联规则的分类,6.3 数据挖掘的关联算法,6.3.2
10、简单形式的关联规则算法（单维、单层和布尔关联规则） 1简单形式的关联规则的核心算法 找到所有支持度大于最小支持度的项集,即频集,有k个数据频集称为k项频集.找出所有的频集由apriori算法实现。Apriori性质具有一个频集的任一非空子集都是频集。 使用第1步找到的频集产生期望的规则 apriori算法的详细介绍见课本。,6.3 数据挖掘的关联算法,6.3.2 简单形式的关联规则算法（单维、单层和布尔关联规则） 2 频集算法的几种优化方法 基于划分的方法 基于hash的方法 基于采样的方法 减少交易的个数,6.3 数据挖掘的关联算法,6.3.2 简单形式的关联规则算法（单维、单层和布尔关联规
11、则） 3 其他的频集挖掘方法 FP-growth方法 min_hashing(MH)和locality_sensitive_hashing(LSH),6.3 数据挖掘的关联算法,6.3.3 多层和多维关联规则的挖掘 多层关联规则 多维关联规则 关联规则价值衡量的方法 6.3.4 货篮子分析存在的问题 详见课本,6.3 数据挖掘的关联算法,6.3.5 关联分析的其他算法 发现关联的更好方法 统计相关以外的 理解关联 有效可行的市场篮子分析 6.3.6 挖掘序列模式 序列模式的概念及定义 序列模式挖掘的主要算法 GSP算法描述 PrefixSpan算法,关联规则挖掘一个例子,最小值尺度 50% 最
12、小可信度 50%,对于 A C： support = support(A 、C) = 50% confidence = support(A 、C)/support(A) = 66.6% Apriori的基本思想: 频繁项集的任何子集也一定是频繁的,关键步骤：挖掘频繁集,频繁集:是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 如, 如果AB 是频繁集，则 A B 也一定是频繁集 从1到k（k-频繁集）递归查找频繁集 用得到的频繁集生成关联规则,Apriori算法,连接: 用 Lk-1自连接得到Ck 修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是
13、频繁的。 伪代码: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = frequent items; for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 wi
14、th min_support end return k Lk;,Apriori算法 例子,如何生成候选集,假定 Lk-1 中的项按顺序排列 第一步: 自连接 Lk-1 insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 第二步: 修剪 forall itemsets c in Ck do forall (k-1)-subsets s of c do i
15、f (s is not in Lk-1) then delete c from Ck,如何计算候选集的支持度,计算支持度为什么会成为一个问题？ 候选集的个数非常巨大 一笔交易可能包含多个候选集 方法: 用 hash-tree 存放候选集 树的叶子节点 of存放项集的列表和支持度 内部节点 是一个hash表 Subset 函数: 找到包含在一笔交易中的所有候选集,生成候选集的例子,L3=abc, abd, acd, ace, bcd 自连接 : L3*L3 abc 和 abd 得到 abcd acd 和 ace 得到 acde 修剪: ade 不在 L3中，删除 acde C4=abcd,提高A
16、priori效率的方法,基于Hash的项集计数: 如果一个 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。 减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集 分割: 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。 采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法 动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。,Apriori 够快了吗? 性能瓶颈,Apriori算法的核心: 用频繁的(k 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 104 个频繁1-项集要生成 107 个候选 2-项集 要找尺寸为100的频繁模式，如 a1,
