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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,现代数据挖掘技术与发展,6.1,知识挖掘系统的体系结构,6.2,现代挖掘技术及应用,6.3,知识发现工具与应用,6.4,数据挖掘技术的发展,练 习,6.1,知识挖掘系统的体系结构,6.1.1,知识发现的定义,知识发现是用一种简洁的方式从大量数据中抽取信息的一种技术，所抽取的信息是隐含的、未知的，并且具有潜在应用价值。,知识发现可看成是一种有价值信息的搜寻过程，它不必预先假设或提出问题，仍然能够找到那些非预期的令人关注的信息，这些信息表示了不同研究对象之间的关系和模式。它还能通过全面的信息发现与分析，找到有价值的商业规则。,知识发现意味着在数据仓库或数据集市的几千兆、几万兆字节数据中寻找预先未知的商业模式与事实。,6.1.2,知识发现系统的结构,知识发现系统的结构由知识发现系统管理器、知识库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价和知识发现描述等部分组成（图,6.1,）。,数据仓库,知识库,数据库接口,数据选择,知识发现引擎,知识发现评价,知识发现描述,知识发现管理器,商业分析员,图6.1 知识发现系统结构,2.,关联规则的应用目标,置信度或正确率可以定义为：,(6.5),覆盖率可以定义为,“兴趣度”为目标的关联规则,3.,关联规则的算法,Apriori算法,1,找出所有支持度大于最小支持度的项集，这些项集称为频集，包含,k,个项的频集称为,k-,项集。,2,使用第,1,步找到的频集产生所期望的规则。,Apriori,算法的第,1,步采用了递归方法，算法表示为,L,1,=large 1-itemsets;/,产生频繁,1,项集,L,1,for(k=2;L,k-1,;k+)do/,循环产生频繁,2,项集,L,2,直到某个,r使L,r,为空,begin,C,k,=apriori-gen(L,k-1,);/,产生,k-,项集的候选集,for all transactions t,D do,begin,C,t,=subset(C,k,t);/,事务,t,中包含的候选集,for all candidates c,C,t,do,c.count+;,end,L,k,=c,C,k,|c.count,minsup,end,Answer=U,k,L,k,第,2,步算法较为简单。如果只考虑规则的右边只有一项的情况，给定一个频集,Y=I,1,I,2,I,3,I,k,k,2,I,j,I,，那么只有包含集合,I,1,I,2,I,3,I,k,中的项的规则最多有,k,条。这种规则形如,I,1,I,2,I,3,I,i-1,I,i+1,I,k,I,i,。这些规则置信度必须大于用户给定的最小置信度。,数据库D,C,1,L,1,事务标识,项集,项集,支持度,项集,支持度,A1,1,3,4,扫描数据,库D,1,2,1,2,A2,2,3,5,2,3,比较,支持度,2,3,A3,1,2,3,5,3,3,3,3,A4,2,5,4,1,5,3,5,3,由,L,1,产生,C,2,C,2,L,2,项集,项集,支持度,项集,支持度,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,由L,2,产生C,3,L,3,4.,关联规则的应用,前件和后件规则中的正确率和覆盖率,规划覆盖率和正确率的平衡,前件,后件,正确率,覆盖率,百吉饼,奶油干酪,80%,5%,百吉饼,橙汁,40%,3%,百吉饼,咖啡,40%,2%,百吉饼,鸡蛋,25%,2%,面包,牛奶,35%,30%,黄油,牛奶,65%,20%,鸡蛋,牛奶,35%,15%,奶酪,牛奶,40%,8%,规划覆盖率,正确率低,正确率高,覆盖率高,规划很少是正确的，但可以使用,规划多数情况下是正确的，而且可以经常使用,覆盖率低,规划很少是正确的，一般不被使用,规划多数情况下是正确的，但很少被使用,6.2.2,神经网络型现代挖掘技术,1.,神经网络及其学习方法,神经网络的工作过程主要分两个阶段：学习阶段和工作阶段。,学习方式则有三种：有教师（监督）学习、无教师（监督）学习和强化学习。,6.2.2,神经网络型现代挖掘技术,2.,基于神经网络的数据挖掘,（1）基于自组织神经网络的数据挖掘技术,一种无教师学习过程,、,可以提取一组数据中的重要特征或某种内在知识,（2）模糊神经网络类型数据挖掘技术,模糊BP网络、模糊Kohonen聚类网络、模糊推理网络、模糊ART模型等,模糊BP网络中，样本的希望输出值改为样本相对各类的希望隶属度,输出表达方面实现了模糊化，而且将样本的隶属度引入了权系数的修正规则中，使权系数的修正规则也实现了模糊化。,6.2.2,神经网络型现代挖掘技术,3.,后向传播模型（,BP,Back Propagation,）及其算法,具体过程如下：,选定p个样本；,权值初始化（随机生成）；,依次输入样本；,依次计算各层的输出；,求各层的反传误差；,按权值调整公式修正各权值和阀值；,按新权值计算各层的输出，直到误差小于事先设定阀值；,变换函数可以采用这样几种：,阶跃函数、S型函数、比例函数、符号函数、,饱和函数,、,双曲函数,6.2.2,神经网络型现代挖掘技术,4.,神经网络的应用,47岁,收入6500元,节点,借贷拖欠？,连接,0.47,0.65,0.39,Weight=0.7,Weight=0.1,年龄,收入,0.47（0.7）+0.65（0.1）0.39,6.2.3,遗传算法型现代挖掘技术,1.,遗传算法的基本原理,达尔文的“适者生存”理论、继承的信息由基因携带、多个基因组成了染色体、基因座、等位基因、基因型和表现型,染色体对应的是一系列符号序列，通常用0、1的位串表示,进行生物的遗传进化。在这一过程中包括三种演化操作：在父代基因群中的双亲选择操作、两个父代双亲产生子代基因的交叉操作和在子代基因群体中的变异操作。,两种数据转换：从表现型到基因型的转换，另一种是从基因型到表现型的转换,遗传算法实质上是一种繁衍、检测和评价的迭代算法,最大优点是问题的最优解与初始条件无关，而且搜索最优解的能力极强,6.2.3,遗传算法型现代挖掘技术,2.,遗传算法的处理过程,（1）编码并生成祖先群体,要用遗传算法解决问题，首先要定义有待解决的问题：,F=f(a,b,c),FR,(a,b,c),F=f(a,b,c),是属于实数域,R,的一个实数，也是每一组解,(a,i,b,i,c,i,),的适应度的度量，算法的目标是找一个,(a,o,b,o,c,o,),，使,F=f(a,o,b,o,c,o,),取最大值。,（2）计算当前基因群体中所有个体的环境适合度,（3）用适应函数评价每一个体对环境的适应度,（4）选择适应度好的生物个体进行复制,（5）选择适应度好的生物个体进行复制交叉配对繁殖,（6）新生代的变异操作,6.2.3,遗传算法型现代挖掘技术,编码并生成祖先群体,计算当前基因群体中所有个体的适合度,是否满足最优解条件？,选择群体中适应值高的个体进行复制,交叉操作,变异操作,终止,6.2.3,遗传算法型现代挖掘技术,3.,遗传算法的应用,用四个染色体来定义客户类型：,基因1：客户的年龄下限,基因2：客户的年龄上限,基因3：客户的收入水平,基因4：客户的人口状况（人口状况可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三种状况）,客户ID,年龄,累计购买金额,收入,家庭人口,性别,10985,46,1843,中等,4,女,18595,49,0,中等,2,男,47382,61,3628,低,5,男,74912,36,18463,高,6,女,95623,29,8463,高,3,男,85526,32,274,中等,2,男,58753,52,1846,低,2,女,64957,48,0,中等,3,女,76957,27,21634,高,5,男,65839,45,842,低,1,女,6.2.3,遗传算法型现代挖掘技术,所有的生物个体按顺序排放在一张二维表格上，使每个生物体的上、下、左、右都与其它生物体相邻接。,（1）竞争复制,（2）杂交繁殖,（3）异变处理,年龄下限,年龄上限,高收入,中等收入,低收入,人口少,人口一般,人口多,客户群1,38,64,是,是,否,否,是,是,客户群2,26,50,是,否,是,是,否,是,客户群3,20,40,否,是,是,是,否,否,6.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,否,是,很长,是,6.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,。,6.2.5 决策树型现代挖掘技术,1,决策树技术,ID3,，该算法建立在推理系统和概念学习系统的基础之上，基本步骤是。,（,1,）创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。,（,2,）否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。,（3）对测试属性中的每一个值，创建相应的一个分支，并据此划分样本。,（,4,）使用同样的过程自顶向下的递归，直到满足下面的三个条件中的一个时，就停止递归。,(a),给定节点的所有样本都属于同一类。,(b),没有剩余的属性可以用来进一步划分。,(c),继续划分得到的改进不明显。,6.2.5 决策树型现代挖掘技术,1,决策树技术,信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。,信息增益是指划分前后进行正确预测所需的信息量之差。,选择具有最高信息增益的属性作为当前节点的测试属性。,一个给定的样本分类所需要的期望信息为,由A划分成子集的熵或期望信息是,6.2.5 决策树型现代挖掘技术,1,决策树技术,为第j个子集的权，等于子集（A值为aj）中的样本数除以S中的样本数。对于给定的子集Sj，,I(s1j,s2j,smj),可用下式计算,是Sj中的样本属于类Ci的概率,由A划分的信息增益是,Gain(A)=I(s1,s2,sm)-E(A),6.2.5 决策树型现代挖掘技术,2.决策树的应用,年龄,学生,信誉等级,会购买,不会购买,会购买,会购买,不会购买,30,3140,40,否,是,一般,良好,6.2.5 决策树型现代挖掘技术,编号,年龄,学生,信誉等级,类别标号,1,=30,是,良好,会购买,2,40,否,一般,会购买,4,40,否,良好,不会购买,5,40,否,一般,会购买,6,3140,是,一般,会购买,7,40,是,一般,会购买,9,40,否,良好,不会购买,11,=30,否,一般,不会购买,12,3140,是,一般,会购买,13,3140,否,一般,会购买,14,3140,是,良好,会购买,6.2.5 决策树型现代挖掘技术,“年龄”在各个属性中具有最大的信息增益，所以选择“年龄”属性作为第一个测试属性，创建一个节点，用“年龄”标记。,计算剩余各个属性的相应的信息增益，选择信息增益最大的属性作为测试属性，这时信息增益最大的是“学生”属性，创建一个节点，用“学生”标记。,6.3知识发现工具与应用,6.3.1 知识挖掘工具的系统结构,1.无耦合（no coupling）,DM系统不利用DB或DW系统的任何功能,2.松散耦合（loose coupling）,DM系统将使用DB/DW的某些工具,3.半紧密耦合（semitight coupling）,DM系统连接到一个DB/DW系统，一些基本数据挖掘原语可以在DB/DW系统中实现。,4.紧密耦合（tight coupling）,DM系统被平滑地集成到DB/DW系统中,6.3知识发现工具与应用,6.3.2 知识挖掘工具运用中的问题,1.数据挖掘技术应用中的共性问题,(1)数据质量,(2)数据可视化,(3)极大数据库(vLDB)的问题,(4)性能和成本,(5)商业分折员的技能,(6)处理噪声和不完全数据,(7)模式评估兴趣度问题,6.3知识发现工具与应用,6.3.2 知识挖掘工具运用中的问题,2.数据挖掘技术应用中的个性问题,(1)规则归纳应用中的问题,主要用于显式描述数据抽取的规则,、找到所有的规则，工作量是巨大的,(2)神经网络应用中的问题,受训练过度的影响,、神经网络的训练速度问题,(3)遗传算法应用中的问题,6.3知识发现工具与应用,6.3.3 知识挖掘的价值,1.了解商业活动,2.发现商业异常,3.预测模型,6.3.4 现代数据挖掘工具简介,1.DBMiner的体系结构,2.DBMiner的数据挖掘类型,6.4数据挖掘技术的发展,6.4.1 文本挖掘,1.文本分析和语义网络,文本分析,为一个大型文本集合提供内容概况,例如，可以发现一个客户反馈集合中文档的显著簇，这样可能会发现公司的产品或服务在哪里需要改进。,指出对象间的隐藏结构,在组织一个企业内部网站时，文本分析可以找出对象间的隐藏结构，这样有关联的文档就能被超链接连接起来。,提高发现相似或相关信息搜索过程的效率和有效性,例如，可以从一个新闻服务机构搜索文章和发现独有的文档，这些文档含有到现在为止在别的文章中没有提到过的新趋势或技术的线索。,侦察存档中的重复文档,文本分析可以用于大量文本需要分析的地方。虽然自动处理不能达到人类阅读分析的深度，但它可以被用来抽取关键点、产生总结、分类文档等。,6.4数据挖掘技术的发展,语义网络,一个有效文本分析的第一步是创建该文本的一个语义网络。一个语义网络是一系列来自分析的文本的最重要概念（词与词的组合）以及文本中这些概念间的语义联系。一个语义网络为分析的文本提供了一个简明和非常准确的总结。与人工神经网络一样，语义网络的每个元素概念都被它的权重和一组与此网络其他元素的联系所标识一个上下文结点。一旦为调查研究的文本构造的一组准确的语义网络建立起来，所有文本分析任务就可以执行。,在现有的大部分算法中，一个语义网络是在一些已定义的规则和概念的基础上建立起来的。不过，也存在一些比较强大的算法，这些算法不需要任何关于主题的预先背景知识，可以仅仅在一个调查研究文本的基础上完全自动建立起一个语义网络。,6.4数据挖掘技术的发展,2.文本挖掘,文本总结,从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释。用户不需要浏览全文就可以了解文档或文档集合的总体内容。,基于关键字的关联分析,首先收集经常一起出现的关键字或词汇，然后找出其关联或相互关系。在这类分析中，每一个文档被视为一个事务，文档中的关键字组可视为事务中的一组事务项。这样，这种基于关键字的关联分析就变成事务数据库中事务项的关联挖掘问题。,一组经常连续出现或紧密相关的关键字可形成一个词或词组。关联分析有助于找出复合关联，即领域相关的词或词组，如中国，长江，三峡。还有助于找出非复合关联，即领域不相关的词或词组，如人民币，交易，总额，证券，佣金，参股。基于这些词或词组关联的挖掘被称为“词级关联挖掘”。利用这种词和词组的识别，词级挖掘可以用于找出词或关键字之间的关联。,6.4数据挖掘技术的发展,2.文本挖掘,文档分类分析,在已有的数据基础上学会一个分类函数或构造出一个分类模型。对文档进行分类。文档的分类分析，一般是先把一组预先分类过的文档作为训练集，然后对训练集加以分析以便得出分类模式。这种分类模式一般要经过一定的测试过程，不断细化。最后用分类模式对其他文档加以分类。,常用的一种对文档分类的有效方法是基于关联的分类。这种分类方法是基于一组相关联的、经常出现的文本模式对文档加以分类。其处理过程为：首先，通过简单的信息检索技术或关联分析技术提出关键字或词汇。然后，使用已有的词类，或基于专家知识，或用关键字分类系统，生成关键字和词的概念层次。最后，使用词级关联挖掘方法发现一组关联词。这样，每一类文档相关有一组关联规则表示。这些分类规则可以基于其出现频率和识别能力，加以排序，并用于对新的文档进行分类。,6.4数据挖掘技术的发展,文档聚类分析,文档聚类是把文档集分成不同组的自动过程。没有预先定义好主题类别，它的目标是将文档集合分成若干个组，要求同一组内文档内容的相似度尽可能大，而不同组间的相似度尽可能小。当文档的内容作为聚类的基础时，不同组是对应于集合中讨论的不同主题或论题。因此，聚类是找出集合所含内容的一条途径。为帮助识别出一组主题，聚类工具可以识别出在此组文档中频繁出现的术语或词的列表。聚类也能根据文档的属性集实施，例如它们的长度、日期等进行聚类。,6.4数据挖掘技术的发展,文本挖掘的应用,利用文本挖掘构造的电子邮件路由，可以对电子邮件进行文本挖掘以后，确定由哪一个部门、哪一个人来处理这些电子邮件，并可以根据电子邮件的内容进行相关统计。,文本挖掘可以帮助组织对成千上万的文档实现有效的管理，可以使组织很快地了解到所需要查找的文档所在位置，以及其包含的主要内容。,可以利用文本挖掘建立一个客户自动问答系统，对客户所邮寄的信件、电子邮件进行文本挖掘以后，根据其反映的主要问题，能够确定客户的需求置信度后，就可以自动给客户发送合适的回信。,企业并且还可以利用联机文本挖掘系统对因特网上所出现的特定词、概念、主题进行挖掘统计，对市场进行客观的统计分析。,企业甚至可以利用一些具有文本挖掘功能的自动智能网络爬虫来收集与企业有关的市场、竞争对手和市场环境的信息，给出总结性的分析报告。,6.4数据挖掘技术的发展,6.4.2 Web挖掘技术,Web,的特点,Web,的庞大性、,Web,的动态性、,Web,的异构性、非结构化的数据结构、用户群体多种多样,2.Web,内容挖掘,基于文本信息的挖掘,和通常的平面文本挖掘比较类似。,Web,文档多为,HTML,、,XML,等语言，因此可以利用,Web,文档中的标记，如,、,等额外信息，利用这些信息来提高,Web,文本挖掘的性能。,在对,Web,文档进行分类分析中，可以基于一组预先分类好的文档，从预定义好分类目录中为每一文档赋予一个类标签。例如，,Yahoo!,的文档和其相关文档可以作为训练集，用于导出,Web,文档的分类模式，这一模式可以用于对新的,Web,文档加以分类。由于超链接包含了有关页面内容的高质量信息，因此，可以利用这些信息对,Web,文档进行分类。这种分类比基于关键字的分类方法要更准确、更完美。,6.4数据挖掘技术的发展,基于多媒体信息的挖掘,基于音频的挖掘、基于图片的静态图像的挖掘和基于视频的动态图像挖掘。,3.Web结构挖掘,从WWW的组织结构和链接关系中推导知识,有助于用户找到相关主题的权威站点，并且可以指向众多权威站点的相关主题站点。,从一个页面指向另一个页面的超链接。超链接包含了大量人类潜在的语义，它有助于自动分析出权威性语义。当一个Web页面的作者建立起指向另一页面的指针时，这就可以看作是作者对另一页面的注解，也就是对另一页面的认可。把一个页面的来自与不同作者的注解收集起来，就可以用来反映页面的重要性。,Hub页面是指一个或多个Web页面，它提供了指向权威页面的链接集合。对于一个Hub页面来说，它本身可能并不突出，但是，它却提供了指向某个话题的权威页面的链接。好的Hub是指向许多好的权威页面；好的权威页面是指有好的Hub页面指向的页面。用Hub页面和权威页面之间的这种相互作用来用于权威页面的挖掘和高质量Web结构和资源的自动发现。,6.4数据挖掘技术的发展,4.Web使用记录的挖掘,通过挖掘Web日志文件和相关数据，发现用户访问Web页面的模式。,Internet的用户一旦连接到一个在线的服务器上，就在服务器上的日志文件留下了所请求的URL，发出请求的IP地址和时间戳。这些日志纪录提供了Web数据挖掘源，可提取有关用户的知识：用户的访问行为、频度、内容，得到关于用户的行为和方式模式。改进站点的结构，或为用户提供个性化服务。,这方面的研究主要有两个方向：一般的访问模式追踪和个性化的使用纪录追踪。一般的访问模式追踪通过分析使用纪录来了解用户的访问模式和倾向，从而改进站点的组织结构。而个性化的使用纪录追踪则倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供个性化的页面，开展有针对性的服务以满足用户的需求。,6.4数据挖掘技术的发展,数据预处理阶段,包括数据清洗和事务识别两个部分,模式识别阶段,采用统计法、机器学习等技术，从Web使用记录中挖掘知识,模式分析阶段,模式分析，辅助分析人员理解,5.Web数据挖掘的应用,电子商务、网站设计和搜索引擎服务:,电子商务的应用主要有客户分类和客户聚类、寻找潜在的客户、客户的驻留。,网站设计的应用是有效地组织网站信息，把握用户的兴趣，有助于开展网站信息推送服务以及个人信息的定制服务。,搜索引擎服务：实现对网页的聚类、分类，实现网络信息的分类浏览与检索；通过用户所使用的提问式,(query),历史记录分析，提高用户的检索效果,(,查全率、查准率,),。,6.4数据挖掘技术的发展,6.4.3 可视化数据挖掘技术,1.数据的可视化,2.可视化数据挖掘技术,数据可视化,数据挖掘结果可视化,数据挖掘过程可视化,交互式可视化数据挖掘,图12.4 数据的可视化,图12.5 数据挖掘结果可视化,图12.6 数据挖掘结果的3D图形,6.4数据挖掘技术的发展,6.4.4 空间数据挖掘,1.地理信息系统,地理信息系统概念,地理信息系统的特点,2.,数据挖掘技术和地理信息系统相结合,3.,地理信息系统的数据挖掘特点,图形化数据挖掘,图形化统计查询,图形化报表输出,专业的地理分析功能,4.,空间数据挖掘,5.,空间数据挖掘用途,6.4数据挖掘技术的发展,6.4.5 分布式数据挖掘,1.分布式数据挖掘,2.适合水平式数据划分的分布式挖掘方法,SQL查询,查询结果,结果,用户查询,图6.7 PADMA体系结构,数据挖掘代理,元数据,数据挖掘代理,协调器,应用,WW用户接口,磁盘,磁盘,6.4数据挖掘技术的发展,6.4.5 分布式数据挖掘,3.适合垂直式数据划分的分布式数据挖掘方法,图6.8 CDM的体系结构,数据站点A,数据站点B,数据站点C,分布式数据挖掘代理,分布式数据挖掘代理,分布式数据挖掘代理,A局部模型,B局部模型,C局部模型,协调器,全局数据模型,