第6章现代数据挖掘技术与发展前沿课件

第6章现代数据挖掘技术与发展

本章学习目标：(1)通过知识挖掘系统的体系结构的学习掌握知识发现的定义和知识发现系统的结构。(2)通过现代挖掘技术及应用的学习掌握规则型、神经网络型、遗传算法型、粗糙集型和决策树型现代挖掘技术。(3)通过知识发现工具与应用的学习掌握知识挖掘工具的系统结构、运用中的问题和知识挖掘的价值。(4)经过数据挖掘技术的发展的学习了解文本挖掘、Web挖掘、可视化数据挖掘、空间数据挖掘和分布式数据挖掘。1现代数据挖掘技术与发展

6.1知识挖掘系统的体系结构

6.2现代挖掘技术及应用

6.3知识发现工具与应用6.4数据挖掘技术的发展

练习

26.1知识挖掘系统的体系结构

6.1.1知识发现的定义

·知识发现是用一种简洁的方式从大量数据中抽取信息的一种技术，所抽取的信息是隐含的、未知的，并且具有潜在应用价值。·知识发现可看成是一种有价值信息的搜寻过程，它不必预先假设或提出问题，仍然能够找到那些非预期的令人关注的信息，这些信息表示了不同研究对象之间的关系和模式。它还能通过全面的信息发现与分析，找到有价值的商业规则。·知识发现意味着在数据仓库或数据集市的几千兆、几万兆字节数据中寻找预先未知的商业模式与事实。6.1.2知识发现系统的结构

知识发现系统的结构由知识发现系统管理器、知识库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价和知识发现描述等部分组成（图6.1）。3

数据仓库知识库数据库接口数据选择知识发现引擎知识发现评价知识发现描述知识发现管理器商业分析员图6.1知识发现系统结构41.知识发现系统管理器控制并管理整个知识发现过程

2.知识库和商业分析员知识库包含了源于各方面的知识。商业分析员要按一种有效的方式指导关注信息的发现。3.数据仓库的数据库接口知识发现系统的数据库接口可以直接与数据仓库通信。

4.数据选择确定从数据仓库中需要抽取的数据及数据结构

5.知识发现引擎将知识库中的抽取算法提供给数据选择构件抽取的数据6.发现评价有助于商业分析员筛选模式，选出那些关注性的信息

7.发现描述发现、评价并辅助商业分析员在知识库中保存关注性发现结果以备将来引用,并保持知识发现与管理人员的通信。56.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(“30..40”)=>buys(x,“IBMcomputer”)(6.3)age(“30..40”)=>buys(x,“computer”)(6.4)关联规则（6.2）可以用下面的SQL查询语句完成。SelectC,P.item_namefromPurchases，PgroupbyCust.IDhaving(Cust.age>=30.and.Cust.age<=40).and.(Cust.income>=42000andCust.income<=50000)and(p.item_name=’high_resolution_TV’)6

2.关联规则的应用目标置信度或正确率可以定义为：

(6.5)

覆盖率可以定义为“兴趣度”为目标的关联规则7

3.关联规则的算法Apriori算法1．找出所有支持度大于最小支持度的项集，这些项集称为频集，包含k个项的频集称为k-项集。2．使用第1步找到的频集产生所期望的规则。Apriori算法的第1步采用了递归方法，算法表示为L1={large1-itemsets};//产生频繁1项集L1for(k=2;Lk-1≠○;k++)do//循环产生频繁2项集L2直到某个r使Lr为空beginCk=apriori-gen(Lk-1);//产生k-项集的候选集foralltransactionst∈DdobeginCt=subset(Ck,t);//事务t中包含的候选集forallcandidatesc∈Ctdoc.count++;endLk={c∈Ck|c.count≥minsup}endAnswer=UkLk8第2步算法较为简单。如果只考虑规则的右边只有一项的情况，给定一个频集Y=I1,I2,I3,…,Ik,k≥2,Ij∈I，那么只有包含集合{I1,I2,I3,…,Ik}中的项的规则最多有k条。这种规则形如I1,I2,I3,…Ii-1,Ii+1…,Ik→Ii,。这些规则置信度必须大于用户给定的最小置信度。9数据库DC1L1

事务标识项集项集支持度项集支持度A11,3,4扫描数据库D{1}2{1}2A22,3,5{2}3比较支持度{2}3A31,2,3,5{3}3{3}3A42,5{4}1{5}3{5}3由L1产生C2

C2

L2

项集项集支持度项集支持度{1,2}扫描数据库D{1,2}1{1,2}2{1,3}{1,3}2比较支持度{2,3}2{1,5}{1,5}1{2,5}3{2,3}{2,3}2{3,5}2{2,5}{2,5}3{3,5}{3,5}2项集扫描数据库D项集支持度{2,3,5}{2,3,5}2由L2产生C3L3104.关联规则的应用前件和后件规则中的正确率和覆盖率规划覆盖率和正确率的平衡

前件后件正确率覆盖率百吉饼奶油干酪80%5%百吉饼橙汁40%3%百吉饼咖啡40%2%百吉饼鸡蛋25%2%面包牛奶35%30%黄油牛奶65%20%鸡蛋牛奶35%15%奶酪牛奶40%8%规划覆盖率正确率低正确率高覆盖率高规划很少是正确的，但可以使用规划多数情况下是正确的，而且可以经常使用覆盖率低规划很少是正确的，一般不被使用规划多数情况下是正确的，但很少被使用116.2.2神经网络型现代挖掘技术

1.神经网络及其学习方法神经网络的工作过程主要分两个阶段：学习阶段和工作阶段。学习方式则有三种：有教师（监督）学习、无教师（监督）学习和强化学习。

126.2.2神经网络型现代挖掘技术

2.基于神经网络的数据挖掘（1）基于自组织神经网络的数据挖掘技术一种无教师学习过程、可以提取一组数据中的重要特征或某种内在知识

（2）模糊神经网络类型数据挖掘技术模糊BP网络、模糊Kohonen聚类网络、模糊推理网络、模糊ART模型等

模糊BP网络中，样本的希望输出值改为样本相对各类的希望隶属度

输出表达方面实现了模糊化，而且将样本的隶属度引入了权系数的修正规则中，使权系数的修正规则也实现了模糊化。

136.2.2神经网络型现代挖掘技术

3.后向传播模型（BP,BackPropagation）及其算法具体过程如下：⑴选定p个样本；⑵权值初始化（随机生成）；⑶依次输入样本；⑷依次计算各层的输出；⑸求各层的反传误差；⑹按权值调整公式修正各权值和阀值；⑺按新权值计算各层的输出，直到误差小于事先设定阀值；变换函数可以采用这样几种：⑴阶跃函数、⑵S型函数、⑶比例函数、⑷符号函数、⑸饱和函数、⑹双曲函数

146.2.2神经网络型现代挖掘技术

4.神经网络的应用47岁收入6500元节点借贷拖欠？连接0.470.650.39Weight=0.7Weight=0.1年龄收入0.47（0.7）+0.65（0.1）＝0.39156.2.3遗传算法型现代挖掘技术

1.遗传算法的基本原理达尔文的“适者生存”理论、继承的信息由基因携带、多个基因组成了染色体、基因座、等位基因、基因型和表现型染色体对应的是一系列符号序列，通常用0、1的位串表示进行生物的遗传进化。在这一过程中包括三种演化操作：在父代基因群中的双亲选择操作、两个父代双亲产生子代基因的交叉操作和在子代基因群体中的变异操作。两种数据转换：从表现型到基因型的转换，另一种是从基因型到表现型的转换遗传算法实质上是一种繁衍、检测和评价的迭代算法最大优点是问题的最优解与初始条件无关，而且搜索最优解的能力极强166.2.3遗传算法型现代挖掘技术

2.遗传算法的处理过程

（1）编码并生成祖先群体要用遗传算法解决问题，首先要定义有待解决的问题：F=f(a,b,c),F∈R,(a,b,c)∈ΩF=f(a,b,c)是属于实数域R的一个实数，也是每一组解(ai,bi,ci)∈Ω的适应度的度量，算法的目标是找一个(ao,bo,co)，使F=f(ao,bo,co)取最大值。（2）计算当前基因群体中所有个体的环境适合度（3）用适应函数评价每一个体对环境的适应度（4）选择适应度好的生物个体进行复制（5）选择适应度好的生物个体进行复制交叉配对繁殖（6）新生代的变异操作176.2.3遗传算法型现代挖掘技术

编码并生成祖先群体计算当前基因群体中所有个体的适合度是否满足最优解条件？选择群体中适应值高的个体进行复制交叉操作变异操作终止186.2.3遗传算法型现代挖掘技术

3.遗传算法的应用用四个染色体来定义客户类型：基因1：客户的年龄下限基因2：客户的年龄上限基因3：客户的收入水平基因4：客户的人口状况（人口状况可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三种状况）客户ID年龄累计购买金额收入家庭人口性别10985461843中等4女18595490中等2男47382613628低5男749123618463高6女95623298463高3男8552632274中等2男58753521846低2女64957480中等3女769572721634高5男6583945842低1女196.2.3遗传算法型现代挖掘技术

所有的生物个体按顺序排放在一张二维表格上，使每个生物体的上、下、左、右都与其它生物体相邻接。（1）竞争复制（2）杂交繁殖（3）异变处理

年龄下限年龄上限高收入中等收入低收入人口少人口一般人口多客户群13864是是否否是是客户群22650是否是是否是客户群32040否是是是否否206.2.4粗糙集型现代挖掘技术1．粗糙集技术2.粗糙集的应用表中的970230、980304、990211客户的“赞扬竞争对手的产品”属性是相似的；980304、990327客户的“挑选产品时间很长”和“客户流失”属性是相似的；970230、990211客户的“赞扬竞争对手的产品”、“挑选产品时间很长”和“距最后一次销售时间”属性是相似的；这样，围绕“赞扬竞争对手的产品”属性就可以产生两个初等集合：{970230、980304、990211}和{970102、980625、990327}；而“赞扬竞争对手的产品”和“挑选产品时间很长”属性可以生成三个初等集合：{970102、980625、990327}、{970230、990211}和{980304}。客户编号赞扬竞争对手产品否挑选产品时间很长距最后一次销售时间客户流失否970102否是长是970230是否长是980304是是很长是980625否是正常否990211是否长否990327否是很长是216.2.4粗糙集型现代挖掘技术因为客户970230已经流失，而客户990211没有流失，由于属性“赞扬竞争对手的产品”、“

挑选产品时间很长”和“距最后一次销售时间”是相似的。因此，客户流失不能以属性“赞扬竞争对手的产品”、“

挑选产品时间很长”和“距最后一次销售时间”作为特征进行描述。而970230、990211就是边界实例，即它们不能根据有效知识进行适当的分类。余下的客户970102、980304和990327所显示的特征，可以将他们确定为已经流失的客户。当然，也不能排除970230和990211已经流失，而980625毫无疑问没有流失。所以客户集合中“流失”的下近似集合是{970102、980304、990327}，上近似集合是{970102、970230、980304、990211、990327}。同样，980625没有流失，但是不能排除970230和990211流失。因此，客户“没有流失”概念的下近似是{980625}，上近似是{970230、980625、990211}。226.2.5决策树型现代挖掘技术1．决策树技术ID3，该算法建立在推理系统和概念学习系统的基础之上，基本步骤是。（1）创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。（2）否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。（3）对测试属性中的每一个值，创建相应的一个分支，并据此划分样本。（4）使用同样的过程自顶向下的递归，直到满足下面的三个条件中的一个时，就停止递归。(a)给定节点的所有样本都属于同一类。(b)没有剩余的属性可以用来进一步划分。(c)继续划分得到的改进不明显。236.2.5决策树型现代挖掘技术1．决策树技术信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。信息增益是指划分前后进行正确预测所需的信息量之差。选择具有最高信息增益的属性作为当前节点的测试属性。一个给定的样本分类所需要的期望信息为由A划分成子集的熵或期望信息是246.2.5决策树型现代挖掘技术1．决策树技术为第j个子集的权，等于子集（A值为aj）中的样本数除以S中的样本数。对于给定的子集Sj，

I(s1j,s2j,…,smj)可用下式计算是Sj中的样本属于类Ci的概率由A划分的信息增益是Gain(A)=I(s1,s2,…,sm)-E(A)

256.2.5决策树型现代挖掘技术2.决策树的应用年龄学生信誉等级会购买不会购买会购买会购买不会购买≤3031~40``>40否是一般良好266.2.5决策树型现代挖掘技术编号年龄学生信誉等级类别标号1<=30是良好会购买2<=30是一般会购买3>40否一般会购买4>40否良好不会购买5>40否一般会购买631~40是一般会购买7<=30否良好不会购买8>40是一般会购买9<=30否良好不会购买10>40否良好不会购买11<=30否一般不会购买1231~40是一般会购买1331~40否一般会购买1431~40是良好会购买276.2.5决策树型现代挖掘技术“年龄”在各个属性中具有最大的信息增益，所以选择“年龄”属性作为第一个测试属性，创建一个节点，用“年龄”标记。计算剩余各个属性的相应的信息增益，选择信息增益最大的属性作为测试属性，这时信息增益最大的是“学生”属性，创建一个节点，用“学生”标记。286.3知识发现工具与应用6.3.1知识挖掘工具的系统结构1.无耦合（nocoupling）DM系统不利用DB或DW系统的任何功能2.松散耦合（loosecoupling）DM系统将使用DB/DW的某些工具3.半紧密耦合（semitightcoupling）DM系统连接到一个DB/DW系统，一些基本数据挖掘原语可以在DB/DW系统中实现。4.紧密耦合（tightcoupling）DM系统被平滑地集成到DB/DW系统中

296.3知识发现工具与应用6.3.2知识挖掘工具运用中的问题1.数据挖掘技术应用中的共性问题(1)数据质量(2)数据可视化(3)极大数据库(vLDB)的问题(4)性能和成本(5)商业分折员的技能(6)处理噪声和不完全数据(7)模式评估——兴趣度问题306.3知识发现工具与应用6.3.2知识挖掘工具运用中的问题2.数据挖掘技术应用中的个性问题(1)规则归纳应用中的问题主要用于显式描述数据抽取的规则、找到所有的规则，工作量是巨大的(2)神经网络应用中的问题受训练过度的影响、神经网络的训练速度问题(3)遗传算法应用中的问题316.3知识发现工具与应用6.3.3知识挖掘的价值1.了解商业活动2.发现商业异常3.预测模型6.3.4现代数据挖掘工具简介1.DBMiner的体系结构2.DBMiner的数据挖掘类型326.4数据挖掘技术的发展6.4.1文本挖掘1.文本分析和语义网络⑴文本分析①为一个大型文本集合提供内容概况例如，可以发现一个客户反馈集合中文档的显著簇，这样可能会发现公司的产品或服务在哪里需要改进。②指出对象间的隐藏结构在组织一个企业内部网站时，文本分析可以找出对象间的隐藏结构，这样有关联的文档就能被超链接连接起来。③提高发现相似或相关信息搜索过程的效率和有效性例如，可以从一个新闻服务机构搜索文章和发现独有的文档，这些文档含有到现在为止在别的文章中没有提到过的新趋势或技术的线索。④侦察存档中的重复文档文本分析可以用于大量文本需要分析的地方。虽然自动处理不能达到人类阅读分析的深度，但它可以被用来抽取关键点、产生总结、分类文档等。336.4数据挖掘技术的发展⑵语义网络一个有效文本分析的第一步是创建该文本的一个语义网络。一个语义网络是一系列来自分析的文本的最重要概念（词与词的组合）以及文本中这些概念间的语义联系。一个语义网络为分析的文本提供了一个简明和非常准确的总结。与人工神经网络一样，语义网络的每个元素——概念都被它的权重和一组与此网络其他元素的联系所标识——一个上下文结点。一旦为调查研究的文本构造的一组准确的语义网络建立起来，所有文本分析任务就可以执行。在现有的大部分算法中，一个语义网络是在一些已定义的规则和概念的基础上建立起来的。不过，也存在一些比较强大的算法，这些算法不需要任何关于主题的预先背景知识，可以仅仅在一个调查研究文本的基础上完全自动建立起一个语义网络。346.4数据挖掘技术的发展2.文本挖掘⑴文本总结从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释。用户不需要浏览全文就可以了解文档或文档集合的总体内容。⑵基于关键字的关联分析首先收集经常一起出现的关键字或词汇，然后找出其关联或相互关系。在这类分析中，每一个文档被视为一个事务，文档中的关键字组可视为事务中的一组事务项。这样，这种基于关键字的关联分析就变成事务数据库中事务项的关联挖掘问题。一组经常连续出现或紧密相关的关键字可形成一个词或词组。关联分析有助于找出复合关联，即领域相关的词或词组，如[中国，长江，三峡]。还有助于找出非复合关联，即领域不相关的词或词组，如[人民币，交易，总额，证券，佣金，参股]。基于这些词或词组关联的挖掘被称为“词级关联挖掘”。利用这种词和词组的识别，词级挖掘可以用于找出词或关键字之间的关联。356.4数据挖掘技术的发展2.文本挖掘⑶文档分类分析在已有的数据基础上学会一个分类函数或构造出一个分类模型。对文档进行分类。文档的分类分析，一般是先把一组预先分类过的文档作为训练集，然后对训练集加以分析以便得出分类模式。这种分类模式一般要经过一定的测试过程，不断细化。最后用分类模式对其他文档加以分类。常用的一种对文档分类的有效方法是基于关联的分类。这种分类方法是基于一组相关联的、经常出现的文本模式对文档加以分类。其处理过程为：首先，通过简单的信息检索技术或关联分析技术提出关键字或词汇。然后，使用已有的词类，或基于专家知识，或用关键字分类系统，生成关键字和词的概念层次。最后，使用词级关联挖掘方法发现一组关联词。这样，每一类文档相关有一组关联规则表示。这些分类规则可以基于其出现频率和识别能力，加以排序，并用于对新的文档进行分类。366.4数据挖掘技术的发展⑷文档聚类分析文档聚类是把文档集分成不同组的自动过程。没有预先定义好主题类别，它的目标是将文档集合分成若干个组，要求同一组内文档内容的相似度尽可能大，而不同组间的相似度尽可能小。当文档的内容作为聚类的基础时，不同组是对应于集合中讨论的不同主题或论题。因此，聚类是找出集合所含内容的一条途径。为帮助识别出一组主题，聚类工具可以识别出在此组文档中频繁出现的术语或词的列表。聚类也能根据文档的属性集实施，例如它们的长度、日期等进行聚类。376.4数据挖掘技术的发展⑸文本挖掘的应用利用文本挖掘构造的电子邮件路由，可以对电子邮件进行文本挖掘以后，确定由哪一个部门、哪一个人来处理这些电子邮件，并可以根据电子邮件的内容进行相关统计。文本挖掘可以帮助组织对成千上万的文档实现有效的管理，可以使组织很快地了解到所需要查找的文档所在位置，以及其包含的主要内容。可以利用文本挖掘建立一个客户自动问答系统，对客户所邮寄的信件、电子邮件进行文本挖掘以后，根据其反映的主要问题，能够确定客户的需求置信度后，就可以自动给客户发送合适的回信。企业并且还可以利用联机文本挖掘系统对因特网上所出现的特定词、概念、主题进行挖掘统计，对市场进行客观的统计分析。企业甚至可以利用一些具有文本挖掘功能的自动智能网络爬虫来收集与企业有关的市场、竞争对手和市场环境的信息，给出总结性的分析报告。386.4数据挖掘技术的发展6.4.2Web挖掘技术Web的特点Web的庞大性、Web的动态性、Web的异构性、非结构化的数据结构、用户群体多种多样2.Web内容挖掘⑴基于文本信息的挖掘和通常的平面文本挖掘比较类似。Web文档多为HTML、XML等语言，因此可以利用Web文档中的标记，如<Title>、<Heading>等额外信息，利用这些信息来提高Web文本挖掘的性能。在对Web文档进行分类分析中，可以基于一组预先分类好的文档，从预定义好分类目录中为每一文档赋予一个类标签。例如，Yahoo!的文档和其相关文档可以作为训练集，用于导出Web文档的分类模式，这一模式可以用于对新的Web文档加以分类。由于超链接包含了有关页面内容的高质量信息，因此，可以利用这些信息对Web文档进行分类。这种分类比基于关键字的分类方法要更准确、更完美。396.4数据挖掘技术的发展⑵基于多媒体信息的挖掘基于音频的挖掘、基于图片的静态图像的挖掘和基于视频的动态图像挖掘。3.Web结构挖掘从WWW的组织结构和链接关系中推导知识有助于用户找到相关主题的权威站点，并且可以指向众多权威站点的相关主题站点。从一个页面指向另一个页面的超链接。超链接包含了大量人类潜在的语义，它有助于自动分析出权威性语义。当一个Web页面的作者建立起指向另一页面的指针时，这就可以看作是作者对另一页面的注解，也就是对另一页面的认可。把一个页面的来自与不同作者的注解收集起来，就可以用来反映页面的重要性。Hub页面是指一个或多个Web页面，它提供了指向权威页面的链接集合。对于一个Hub页面来说，它本身可能并不突出，但是，它却提供了指向某个话题的权威页面的链接。好的Hub是指向许多好的权威页面；好的权威页面是指有好的Hub页面指向的页面。用Hub页面和权威页面之间的这种相互作用来用于权威页面的挖掘和高质量Web结构和资源的自动发现。406.4数据挖掘技术的发展4.Web使用记录的挖掘通过挖掘Web日志文件和相关数据，发现用户访问Web页面的模式。Internet的用户一旦连接到一个在线的服务器上，就在服务器上的日志文件留下了所请求的URL，发出请求的IP地址和时间戳。这些日志纪录提供了Web数据挖掘源，可提取有关用户的知识：用户的访问行为、频度、内容，得到关于用户的行为和方式模式。改进站点的结构，或为用户提供个