07 第7章 数据挖掘的技术方法.pptx

第1页：第7章数据挖掘的技术方法封面

• 第7章数据挖掘的技术方法
• 【教学目标与要求】了解数据挖掘所需处理数据源的特点以及各种挖掘技术的针对性掌握数据挖掘技术的过程和方法学会对多种数据挖掘技术的对比分析与使用了解在实际领域中的数据挖掘技术存在的问题及其处理

第2页：第7章内容目录

• 7.1决策树
• 7.2粗糙集
• 7.3关联规则
• 7.4神经网络方法
• 7.5基于案例推理
• 7.6遗传算法

第3页：导入案例：数据挖掘的学科交叉

• 【导入案例】1.背景材料2.分析数据挖掘是多学科的交叉领域，为了有效地从海量数据中获取知识，实现“数据→信息→知识→价值”的转变过程涉及数据库技术、人工智能、机器学习、神经网络、数学、统计学等多方面知识。
• 我们首先应当关注引入某类技术的目的、可以解决的问题；
• 其次应该了解实现方法，也就是如何编程实现；
• 最后再对比算法的有效性，特别要考虑的是时间效率问题，因为我们的挖掘针对的就是海量数据第7章数据挖掘的技术方法

第4页：决策树的基本概念

7.1.1基本概念决策树（decisiontree）是用于有导师学习的一种常用方法，是应用最广的归纳推理算法之一。7.1.2归纳学习中的知识表示1.规则2.决策树7.1决策树

第5页：决策树归纳学习引例

7.1.3决策树归纳学习1．例子7.1决策树

第6页：决策树对应的规则表示

决策树可以表示为如下规则：if(outlook=sunny)and(humidity≤75)thenplay.if(outlook=sunny)and(humidity>75)thendon'tplayif(outlook=overcast)thenplayif(outlook=rain)and(windy=true)thendon'tplayif(outlook=rain)and(windy=false)thenplay7.1决策树

第7页：CLS学习算法

2．CLS学习算法CLS(ConceptLearningSystem)学习算法是Hunt等人在1966年提出的，是归纳学习中最早的分治算法。目前最有名的Quinlan的ID系列算法和C4.5算法的核心仍然是CLS，由于属性的选择不同，使得分类的效率和质量大大提高CLS以一棵空决策树开始，并通过增加结点逐步求精，直到产生一棵能正确分类训练例子的决策树7.1决策树

第8页：ID3学习算法

3．ID3学习算法在ID3算法采用了基于信息熵的属性排序策略7.1决策树

第9页：决策树示例数据表

决策树分类示例数据表：下表列出根据毛型、体形、颜色判断类别的训练实例。

第10页：属性的信息增益计算

计算各个属性的信息增益：Gain(颜色,T)=Info(T)-Info(颜色,T)＝1－0.918＝0.082Gain(体形,T)=Info(T)-Info(体形,T)＝1－0.541＝0.459Gain(毛型,T)=Info(T)-Info(毛型,T)＝1－1＝0

第11页：

第12页：关于决策树的深入讨论

7.1.4关于决策树的深入讨论1．决策树的评价标准（1）．过学习（2）．决策树的有效性（3）．交叉有效性（4）．决策树的复杂程度2．测试属性的选择3．树剪枝7.1决策树

第13页：粗糙集小节目录

• 7.2.1粗糙集基本理论
• 7.2.2粗糙集概念的物理意义
• 7.2.3粗糙集理论的特点
• 7.2.4决策表达逻辑

第14页：粗糙集理论的基础

粗糙集理论

是建立在分类机制的基础上的，它将分类理解成在特定空间上的等价关系，从而构成了对该空间的划分。其关键思想是将不确定的或不精确的知识用已知的知识库中的知识来近似地刻画，是目前被使用较多的一种归纳学习方法。该理论的特点是：它不需要提供除问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述和处理相对客观。7.2粗糙集

第15页：积木分类示例数据表

积木分类示例数据表：下表按体积、形状、颜色三个属性对积木样本分类。

第16页：不可分辨关系与近似集

7.2.1粗糙集基本理论2．不可分辨关系3．上近似集和下近似集4．知识依赖度XRU/C1+B2+A3/D4+A5+C6

第17页：粗糙集概念的物理意义

7.2.2粗糙集概念的物理意义

第18页：表7-5b由7-5a表提取的规则

表7-5b由7-5a表提取的规则THENXIFR根据一定（+）能上高考成绩（A，B）R-(X1)一定（/）不能上高考成绩（D）R-(X2)可能（+）能上高考成绩（A，B，C）R-(X1)可能（/）不能上高考成绩（C，D）R-(X2)可能（+）也可能（/）高考成绩（C）BnR(X1)可能（+）也可能（/）高考成绩（C）BnR(X2)

源文件该页「表7-5b由表7-5a提取的规则」为粘连文本，行与列无法安全切分，待人工对照原图还原。

第19页：粗糙集理论的内涵

1．粗糙集理论的内涵2．与其它不确定理论的关系知识系统中的不确定性主要来自于3个方面：（1）认知对象间缺乏足够的区分度。（2）对象集合存在不确定性，这里集合的不确定性有两种解释。（3）不合适的知识表达粒度7.2.3粗糙集理论的特点

第20页：决策表与决策逻辑

7.2.4决策表达逻辑一、知识的简化oedcaU11110x101011x211001x301001x400001x511011x6

源文件该页决策表（属性a-e与样本x1-x6）为粘连文本，行与列无法安全切分，待人工对照原图还原。

第21页：知识的简化与决策表简化

• 二、决策逻辑1.决策表
• 当且仅当CD，决策表T＝(U，A，C，D)是协调的。
• 每个决策表T=(U,A,C,D)都可以唯一地分解成两个决策表一个是协调的T1=(U1,A,C,D)和另一个完全不协调的T2=(U2,A,C,D)7.2.4决策表达逻辑

第22页：决策表的简化

2.决策逻辑7.2.4决策表达逻辑三、决策表的简化

第23页：粗糙集的研究进展

1．理论研究2．应用研究3．粒度研究具体地讲，凡是在分析问题和求解问题中,应用了分组、分类和聚类手段的一切理论与方法均属于粒度计算(GranularComputing,GrC)的范畴粒计算作为信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究；这些理论都是从集会出发，采用不同的机制研究知识粒度的变换，它们之间并不是互相竞争的理论，而是互补的7.2.5粗糙集的研究进展

第24页：关联规则挖掘小节目录

• 7.3.1Apriori算法
• 7.3.2Apriori算法的改进
• 7.3.3FP-tree算法
• 7.3.4挖掘多层关联规则
• 7.3.5挖掘多维关联规则

第25页：Apriori算法描述

1．算法描述（1）发现频繁项目集（2）生成关联规则2．经典的关联规则挖掘算法分析（1）．算法（2）．算法执行举例7.3.1Apriori算法

第26页：Apriori算法的性能瓶颈与优化

1．Apriori算法的性能瓶颈问题2．Apriori算法的优化（1）基于散列的技术（散列项集计数）（2）事务压缩（压缩进一步迭代扫描的事务数）（3）划分（为找候选项集划分数据）（4）选样（在给定数据的一个子集挖掘）（5）动态项集计数（在扫描的不同点添加候选项集）7.3.2Apriori算法的改进

第27页：FP-tree算法

7.3.3FP-tree算法

第28页：挖掘多层关联规则

7.3.4挖掘多层关联规则

第29页：挖掘多维关联规则

1．第一种方法，使用量化属性的静态离散化挖掘多维关联规则。2．第二种方法，根据数据的分布，将量化属性离散化到“箱”。（1）分箱：量化属性可能具有很宽的取值范围，定义它们的域（2）找频繁谓词集（3）关联规则聚类3．第三种方法，量化属性离散化，以紧扣区间数据的语义。这种动态离散化过程考虑数据点之间的距离。7.3.5挖掘多维关联规则

第30页：使用规则限制聚焦挖掘任务

• 讨论使用规则限制对挖掘任务聚焦。规则限制指定要挖掘的规则形式。这种限制可以用元规则（规则模板）表示，如可以出现在规则前件或后件中谓词的最大或最小个数，或属性、属性值和/或聚集之间的联系。
• 这种基于限制的挖掘允许用户根据他们关注的目标，说明要挖掘的规则，因此使得数据挖掘过程更有功效。此外，可以使用复杂的挖掘查询优化程序，以便利用用户指定的限制，从而使得挖掘过程更有效率。基于限制的挖掘促进交互式探查挖掘与分析。7.3.6基于限制的关联规则挖掘

第31页：神经网络方法小节目录

• 7.4.1前馈神经网络模型
• 7.4.2前馈神经网络的学习算法
• 7.4.3FP及覆盖算法

第32页：多层前馈神经网络

1．多层前馈神经网络7.4.1前馈神经网络模型

第33页：径向基网络

2．径向基网络7.4.1前馈神经网络模型

第34页：前馈神经网络的学习算法

1．BP算法增加“惯性项”采用动态步长跳跃学习2．模拟退火算法3．径向基函数算法7.4.2前馈神经网络的学习算法

第35页：构造性神经网络与FP算法

一、构造性神经网络二、FP算法1．网络设计2．网络的性能特点7.4.3FP及覆盖算法

第36页：M-P神经元的几何意义

三、M-P神经元的几何意义7.4.3FP及覆盖算法

第37页：覆盖算法

四、覆盖算法7.4.3FP及覆盖算法

第38页：覆盖算法的重心求解

• 求重心：按照上面的方法构造一个初始领域后，求其所覆盖的点的重心，并将领域中心移至重心处，再按公式计算构造新领域，如此重复，直至覆盖的点数不增加时为止；
• 平移：n维空间中n+1个线性不相关的点决定一个超球面，平移领域中心的位置，再按公式计算构造新领域，直至超球面上含有n+1个异类点；
• 删除：通过初始构造、求重心、平移操作后，得到一个只含同类点的最大领域，将其所覆盖的样本点删除，以扩大其后构造领域的覆盖范围。7.4.3FP及覆盖算法

第39页：统计机器学习理论

一、统计机器学习理论二、支持向量机7.4.4SVM及其学习算法

第40页：SVM分类算法

1.SVM线性分类算法

第41页：基于案例推理小节目录

• 7.5.1CBR的逻辑学基础
• 7.5.2CBR智能技术
• 7.5.3相似性研究

第42页：类比推理

1．类比推理在人工智能中，如机器定理证明的归结原理，使用的是演绎推理，是从一般到特殊的推理过程，并未发现新的知识；反之，归纳推理则是从特殊到一般的推理过程，属于非标准逻辑，能根据某些已知的特殊性知识，归纳出未知的一般性知识。如果这些特殊性知识已经直接或间接包含了未知的一般性知识的所有可能情况，则归纳推理的结论完全有效，是完全归纳推理，仍然属于形式逻辑；否则结论可能有效，也可能无效，是不完全归纳推理。7.5.1CBR的逻辑学基础

第43页：类比推理的基本结构

类比推理的基本结构就

是：物体A有属性a、b、c、d，物体B有属性a、b、c；所以类似地，B亦有属性d。类比有多种形式，如方法类比、概念类比、图形类比、联想类比等，都是人类思维的体现。类比推理给出的前提虽然指明了事物各种属性的共存，但是并没有确证这些属性之间有必然联系。7.5.1CBR的逻辑学基础

第44页：非单调逻辑

2．非单调逻辑常识是人工智能研究的主要内容，因为机器智能必须处理常识和实现常识推理。然而常识并无明确的定义，而且有众多的例外。常识推理的基本特征是在知识不完全情况下进行的，要作出各种假设，具有非单调性。人类知识的增长实际上是非单调的发展过程，原因是人们推理时所依据的知识具有不完全性。假如把人们在不同认识阶段的知识用集合F表示，则是时间t的函数，F(t)表示人们再时刻t的知识总和，却不具备当t2>t1时F(t2)>F(t1)。然而，经典逻辑如形式逻辑、演绎逻辑等，对人类认知世界的处理却是单调的。7.5.1CBR的逻辑学基础

第45页：CBR的工作过程

一、CBR的工作过程7.5.2CBR智能技术

第46页：案例检索与重用

• 检索（Retrieve）：根据输入待解决的问题的有关信息，从案例库中检索相似的案例集；
• 重用（Reuse）：从检索到的一组案例中获得求解方案，判别是否符合需求，若符合，则重用这些方案（或多个方案的合并解），否则需要修正；
• 修正案例（Revise）：从相似案例中修正求解方案，使之适合于求解当前问题，得到当前问题的新求解方案；
• 保存案例（Retain）：将新案例及其解根据一定的策略存入案例库中，此乃CBR的学习方式。7.5.2CBR智能技术

第47页：案例表示

二、案例表示案例由诸多的属性组成，案例间相似性就是根据属性之间的相似度来定义的，目标案例和源案例的本质特征具有相似性关系使得类比有了基础。案例表示的研究，是整个CBR研究的基础和核心；案例的表示涉及到这样几个问题：选择什么信息存放在一个案例中、如何选择合适的案例内容描述结构、案例库如何组织和索引等1．案例表示的要求2．案例表示方法7.5.2CBR智能技术

第48页：CBR技术特点

三、CBR技术特点1．CBR的心理学模型2．CBR与思维模拟3．知识复用4．研究CBR技术的动机主要是克服在知识系统中的出现关键问题，如问题(1)克服理论不完善或信息缺失，(2)及时获取与更新知识，(3)对付计算复杂性问题，(4)辅助决策。5．增量式学习7.5.2CBR智能技术

第49页：案例相似性理论

1．案例相似性理论(1)语义相似(2)结构相似性(3)目标特征(4)个体相似性2．相似性计算(1)Tversky对比匹配函数(2)改进的Tversky匹配法(3)距离度量法或最近邻算法(4)多参数的相似性计算(5)Weber计算法7.5.3相似性研究

第50页：案例修正技术

1．案例修正方法2．修正知识获取(1)利用领域知识来学习修正规则(2)交互式修正规则的学习，一般是从专家用户处学习修正知识(3)从案例库中学习修正规则，即利用机器学习技术从案例库中获取修正知识(4)从数据库中直接地发现修正知识(5)案例推理中基于案例库的修正学习技术(6)递归修正技术：它是根据案例之间的规律来递归求解的,根据用户需求来引导并发现出修正知识7.5.4案例修正技术

第51页：遗传算法小节目录

• 7.6.1遗传算法的主要特征
• 7.6.2遗传算法的基本原理
• 7.6.3遗传算法的关键问题及方法

第52页：遗传算法的主要特征

• 遗传算法（GeneticAlgorithms，GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，大多数系统都遵循“适者生存”的仿自然法则。经过多年的发展，遗传算法取得了丰硕的应用成果和理论研究进展。求解此类问题的算法应该注意以下几点：
• 不能简单地认为只要能产生适应环境的结构就好，还要保证求解问题的时间处于合理的范围；
• 应该在保持穷举法的通用性的基础上提高效率；
• 由于不了解环境，在算法中要有存储和利用实验结果，从中获取信息的手段。
• 因而，Holland提出了模仿自然界的进化机制来解决适应性问题的优化算法——遗传算法。由于他提出的遗传算法简单实用，因而已普遍被接受采纳。7.6遗传算法

第53页：标准遗传算法工作流程

图7-18

是SGA（标准遗传算法）一种模式的工作流程图。由图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。遗传算法的遗传操作（GeneticOperation）包括：选择（Selection）、交叉（Crossover）和变异（Mutation）三个主要的遗传算子，它们使得遗传算法具有了其它传统方法所没有的特性。遗传算法的核心内容是它的五个基本要素，它们是：参数编码；初始群体的设定；适应度函数的设计；遗传操作设计；控制参数设定。7.6.1遗传算法的主要特征

第54页：

第55页：遗传算法的基本原理

• 一、模式定理(Schematatheorem)
• 二、积木块假设
• 三、欺骗问题
• 四、隐并行性7.6.2遗传算法的基本原理

第56页：遗传算法的关键问题及方法

• 一、编码（1）二进制编码（2）多字符及实数编码（3）树编码（4）自适应编码
• 二、适应度函数1.适应度函数的设定2.适应度函数定标
• 三、遗传操作1.选择算子2.交叉算子3.变异算子
• 四、未成熟收敛问题7.6.3遗传算法的关键问题及方法

第57页：挖掘关联规则的遗传算法

遗传算法挖掘出的关联规则结果表：下表列出规则前提及其可信度与支持度。

第58页：模糊技术小节目录

• 7.7.1模糊集基本概念
• 7.7.2模糊集合运算

第59页：模糊集基本概念

7.7.1模糊集基本概念一、模糊知识二、模糊集合论（一）隶属度（二）模糊集合的表示

第60页：模糊集合运算

7.7.2模糊集合运算1.模糊子集的包含和相等关系2.模糊子集的并、交、补运算

第61页：模糊度及模糊关系

7.7.3模糊度及模糊关系一、模糊度二、模糊关系三、模糊逻辑与模糊推理1.模糊命题2.模糊逻辑3.模糊推理