现代数据挖掘技术与发展

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章,现代数据挖掘技术与发展,本章学习目标：,(1)通过知识挖掘系统的体系结构的学习掌握知识发现的定义和知识发现系统的结构。,(2)通过现代挖掘技术及应用的学习掌握规则型、神经网络型、遗传算法型、粗糙集型和决策树型现代挖掘技术。,(3)通过知识发现工具与应用的学习掌握知识挖掘工具的系统结构、运用中的问题和知识挖掘的价值。,(4)经过数据挖掘技术的发展的学习了解文本挖掘、Web挖掘、可视化数据挖掘、空间数据挖掘和分布式数据挖掘。,现代数据挖掘技术与发展,6.1,知识挖掘系统的体系结构,6.2,现代挖掘技术及应用,6.3,知识发现工具与应用,6.4,数据挖掘技术的发展,练 习,6.1,知识挖掘系统的体系结构,知识发现的定义,知识发现是用一种简洁的方式从大量数据中抽取信息的一种技术，所抽取的信息是隐含的、未知的，并且具有潜在应用价值。,知识发现可看成是一种有价值信息的搜寻过程，它不必预先假设或提出问题，仍然能够找到那些非预期的令人关注的信息，这些信息表示了不同研究对象之间的关系和模式。它还能通过全面的信息发现与分析，找到有价值的商业规则。,知识发现意味着在数据仓库或数据集市的几千兆、几万兆字节数据中寻找预先未知的商业模式与事实。,知识发现系统的结构,知识发现系统的结构由知识发现系统管理器、知识库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价和知识发现描述等部分组成（图,6.1,）。,数据仓库,知识库,数据库接口,数据选择,知识发现引擎,知识发现评价,知识发现描述,知识发现管理器,商业分析员,图6.1 知识发现系统结构,1.知识发现系统管理器,控制并管理整个知识发现过程,2.,知识库和商业分析员,知识库包含了源于各方面的知识。商业分析员要按一种有效的方式指导关注信息的发现,。,3.,数据仓库的数据库接口,知识发现系统的数据库接口可以直接与数据仓库通信。,4.,数据选择,确定从数据仓库中需要抽取的数据及数据结构,5.,知识发现引擎,将知识库中的抽取算法提供给数据选择构件抽取的数据,6.,发现评价,有助于商业分析员筛选模式，选出那些关注性的信息,7.,发现描述,发现、评价并辅助商业分析员在知识库中保存关注性发现结果以备将来引用,并保持知识发现与管理人员的通信。,6.2,现代挖掘技术及应用,6.2.1,规则型现代挖掘技术及应用,1.,关联规则的基本概念,buys(x,“puter”)=buys(x,“finacial_management_software”),age(“30.40”)ine(“42000.50000”)=buys(x,“high_resolution_TV”),布尔关联规则,量化关联规则,单维规则,多维关联,多层关联规则,单层关联规则,age(“30.40”)=buys(x,“IBM puter”)(6.3),age(“30.40”)=buys(x,“puter”)(6.4),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),F,R,(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,就是边界实例，即它们不能根据有效知识进行适当的分类。余下的客户,9