《现代数据挖掘技术与发展教学提纲》由会员分享，可在线阅读，更多相关《现代数据挖掘技术与发展教学提纲（60页珍藏版）》请在金锄头文库上搜索。
1、第6章现代数据挖掘技术与发展,本章学习目标： (1) 通过知识挖掘系统的体系结构的学习掌握知识发现的定义和知识发现系统的结构 。 (2) 通过现代挖掘技术及应用的学习掌握规则型、神经网络型、遗传算法型、粗糙集型和决策树型现代挖掘技术。 (3) 通过知识发现工具与应用的学习掌握知识挖掘工具的系统结构、运用中的问题和知识挖掘的价值。 (4) 经过数据挖掘技术的发展的学习了解文本挖掘、Web挖掘、可视化数据挖掘、空间数据挖掘和分布式数据挖掘。,现代数据挖掘技术与发展,6.1知识挖掘系统的体系结构 6.2现代挖掘技术及应用 6.3知识发现工具与应用 6.4数据挖掘技术的发展 练 习,6.1知识挖掘系统
2、的体系结构,6.1.1知识发现的定义 知识发现是用一种简洁的方式从大量数据中抽取信息的一种技术，所抽取的信息是隐含的、未知的，并且具有潜在应用价值。 知识发现可看成是一种有价值信息的搜寻过程，它不必预先假设或提出问题，仍然能够找到那些非预期的令人关注的信息，这些信息表示了不同研究对象之间的关系和模式。它还能通过全面的信息发现与分析，找到有价值的商业规则。 知识发现意味着在数据仓库或数据集市的几千兆、几万兆字节数据中寻找预先未知的商业模式与事实。 6.1.2 知识发现系统的结构 知识发现系统的结构由知识发现系统管理器、知识库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价
3、和知识发现描述等部分组成（图6.1）。,频繁模式是频繁的出现在数据集中的模式 如项集、子序或者子结构 动机：发现数据中蕴含的内在规律 那些产品经常被一起购买？-啤酒和尿布？ 买了PC之后接着都会买些什么？ 哪种DNA对这种新药敏感 我们能够自动的分类WEB文档吗？ 应用 购物篮分析、WEB日志（点击流）分析、捆绑销售、DNA序列分析等,什么是频繁模式分析？,6.2现代挖掘技术及应用,揭示数据集的内在的、重要的特性 作为很多重要数据挖掘任务的基础 关联、相关和因果分析 序列、结构（e.g.子图）模式分析 时空、多媒体、时序和流数据中的模式分析 分类：关联分类 聚类分析：基于频繁模式的聚类 数据仓
4、库：冰山方体计算,频繁模式挖掘的重要性,购物篮分析,如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（e.g. 0001001100） 关联规则的两个兴趣度度量 支持度 置信度 通常，如果关联规则同时满足最小支持度阈值和最小置信度阈值，则此关联规则是有趣的,关联规则：基本概念,给定： 项的集合：I=i1,i2,.,in 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 每个事务由事务标识符TID标识； A,
5、B为两个项集，事务T包含A当且仅当 则关联规则是如下蕴涵式： 其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度c,基本概念示例,项的集合 I=A,B,C,D,E,F 每个事务T由事务标识符TID标识，它是项的集合 TID(2000)=A,B,C 任务相关数据D是数据库事务的集合,D,支持度s是指事务集D中包含 的百分比 置信度c是指D中包含A的事务同时也包含B的百分比 假设最小支持度阈值为50%，最小置信度阈值为50%，则有如下关联规则 A C (50%, 66.6%) C A (50%, 100%) 同时满足最小支持度阈值和最小置信度阈值的规则称作强规则,规则度量：支持度和置信
6、度,Customer buys diaper,Customer buys both,Customer buys beer,6.2现代挖掘技术及应用,6.2.1 规则型现代挖掘技术及应用 1.关联规则的基本概念,布尔关联规则、单维规则 buys(x,“computer”)=buys(x,“finacial_management_software”) 量化关联规则、多维关联 age(“30.40”)income(“42000.50000”)=buys(x,“high_resolution_TV”) 多层关联规则 单层关联规则 age(x,“30.40”)=buys(x,“IBM computer”
7、) (6.3) age(x,“30.40”)=buys(x,“computer”) (6.4) 关联规则（6.2）可以用下面的SQL查询语句完成。 Select Cust.name, P.item_name from Purchases，P group by Cust.ID having (Cust.age=30.and.Cust.age=42000 and Cust.income = 50000) and (p.item_name=high_resolution_TV),2.关联规则的应用目标 置信度或正确率可以定义为： (6.5) 覆盖率可以定义为 “兴趣度”为目标的关联规则,最简单的关联
8、规则挖掘，即单维、单层、布尔关联规则的挖掘。,最小支持度 50% 最小置信度 50%,对规则A C，其支持度 =50% 置信度,基本概念 k项集：包含k个项的集合 牛奶，面包，黄油是个3项集 项集的频率是指包含项集的事务数，简称为项集的频率、支持度计数或计数 项集的支持度有时称为相对支持度，而出现的频率称作绝对支持度。如果项集I的频率大于（最小支持度阈值D中的事务总数），则称该项集I为频繁项集。频繁k项集的集合通常记作Lk。,频繁项集,3.关联规则的算法 Apriori算法基本思想 1找出所有支持度大于最小支持度的项集，这些项集称为频集，包含k个项的频集称为k-项集。 2使用第1步找到的频集产
9、生所期望的规则。 Apriori算法的第1步采用了递归方法，算法表示为 L1=large 1-itemsets;/产生频繁1项集L1 for (k=2;Lk-1;k+) do /循环产生频繁2项集L2直到某个r使Lr为空 begin Ck=apriori-gen(Lk-1);/产生k-项集的候选集 for all transactions tD do begin Ct=subset(Ck,t);/事务t中包含的候选集 for all candidates cCt do c.count+; end Lk=cCk|c.countminsup end Answer=UkLk,第2步算法较为简单。如果
10、只考虑规则的右边只有一项的情况，给定一个频集Y=I1,I2,I3,Ik,k2,IjI，那么只有包含集合 I1,I2,I3,Ik中的项的规则最多有k条。这种规则形如I1,I2,I3,Ii-1,Ii+1,IkIi,。这些规则置信度必须大于用户给定的最小置信度。,Apriori频繁项集搜索算法由连接和剪枝两个步骤组成。 连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。 Lk-1中的两个元素L1和L2可以执行连接操作 的条件是 Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到L
11、k 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。,Apriori算法步骤,由L2产生C3 L3,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,4.关联规则的应用,6.2.2 神经网络型现代挖掘技术,1.神经网络及其学习方法 神经网络的工作过程主要分两个阶段：学习阶段和工作阶段。 学习方式则有三种：有教师（监督）学习、无教师（监督）学习和强化学习。,6.2.2 神经网络型现代挖掘技术,2.基于神经网
12、络的数据挖掘 （1）基于自组织神经网络的数据挖掘技术 一种无教师学习过程 、可以提取一组数据中的重要特征或某种内在知识 （2）模糊神经网络类型数据挖掘技术 模糊BP网络、模糊Kohonen聚类网络、模糊推理网络、模糊ART模型等 模糊BP网络中，样本的希望输出值改为样本相对各类的希望隶属度 输出表达方面实现了模糊化，而且将样本的隶属度引入了权系数的修正规则中，使权系数的修正规则也实现了模糊化。,6.2.2 神经网络型现代挖掘技术,3.后向传播模型（BP,Back Propagation）及其算法 具体过程如下： 选定p个样本； 权值初始化（随机生成）； 依次输入样本； 依次计算各层的输出； 求
13、各层的反传误差； 按权值调整公式修正各权值和阀值； 按新权值计算各层的输出，直到误差小于事先设定阀值； 变换函数可以采用这样几种： 阶跃函数、S型函数、比例函数、符号函数、饱和函数 、双曲函数,6.2.2 神经网络型现代挖掘技术,4.神经网络的应用,6.2.3 遗传算法型现代挖掘技术,1.遗传算法的基本原理 达尔文的“适者生存”理论、继承的信息由基因携带 、多个基因组成了染色体 、基因座、等位基因 、基因型和表现型 染色体对应的是一系列符号序列，通常用0、1的位串表示 进行生物的遗传进化。在这一过程中包括三种演化操作：在父代基因群中的双亲选择操作、两个父代双亲产生子代基因的交叉操作和在子代基因
14、群体中的变异操作。 两种数据转换：从表现型到基因型的转换，另一种是从基因型到表现型的转换 遗传算法实质上是一种繁衍、检测和评价的迭代算法 最大优点是问题的最优解与初始条件无关，而且搜索最优解的能力极强,6.2.3 遗传算法型现代挖掘技术,2.遗传算法的处理过程 （1）编码并生成祖先群体 要用遗传算法解决问题，首先要定义有待解决的问题： F=f(a,b,c),FR ,(a,b,c) F=f(a,b,c)是属于实数域R的一个实数，也是每一组解(ai,bi,ci)的适应度的度量，算法的目标是找一个(ao ,bo ,co)，使F=f(ao ,bo ,co)取最大值。 （2）计算当前基因群体中所有个体的
15、环境适合度 （3）用适应函数评价每一个体对环境的适应度 （4）选择适应度好的生物个体进行复制 （5）选择适应度好的生物个体进行复制交叉配对繁殖 （6）新生代的变异操作,6.2.3 遗传算法型现代挖掘技术,6.2.3 遗传算法型现代挖掘技术,3.遗传算法的应用 用四个染色体来定义客户类型： 基因1：客户的年龄下限 基因2：客户的年龄上限 基因3：客户的收入水平 基因4：客户的人口状况（人口状况可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三种状况）,所有的生物个体按顺序排放在一张二维表格上，使每个生物体的上、下、左、右都与其它生物体相邻接。 （1）竞争复制 （2）杂交繁殖 （3）异变
16、处理,6.2.4 粗糙集型现代挖掘技术,1粗糙集技术 2.粗糙集的应用 表中的970230、980304、990211客户的“赞扬竞争对手的产品”属性是相似的；980304、990327客户的“挑选产品时间很长”和“客户流失”属性是相似的；970230、990211客户的“赞扬竞争对手的产品”、“ 挑选产品时间很长”和“距最后一次销售时间”属性是相似的；这样，围绕“赞扬竞争对手的产品”属性就可以产生两个初等集合：970230、980304、990211和970102、980625、990327；而“赞扬竞争对手的产品”和“挑选产品时间很长”属性可以生成三个初等集合：970102、980625、990327、970230、990211和980304。,6.2.4 粗糙集型现代挖掘技术,因为客户970230已经流失，
