现代数据挖掘技术与发展.ppt

第6章现代数据挖掘技术与发展,本章学习目标： (1) 通过知识挖掘系统的体系结构的学习掌握知识发现的定义和知识发现系统的结构 。 (2) 通过现代挖掘技术及应用的学习掌握规则型、神经网络型、遗传算法型、粗糙集型和决策树型现代挖掘技术。 (3) 通过知识发现工具与应用的学习掌握知识挖掘工具的系统结构、运用中的问题和知识挖掘的价值。 (4) 经过数据挖掘技术的发展的学习了解文本挖掘、Web挖掘、可视化数据挖掘、空间数据挖掘和分布式数据挖掘。,现代数据挖掘技术与发展,6.1知识挖掘系统的体系结构 6.2现代挖掘技术及应用 6.3知识发现工具与应用 6.4数据挖掘技术的发展 练 习,6.1知识挖掘系统的体系结构,6.1.1知识发现的定义 知识发现是用一种简洁的方式从大量数据中抽取信息的一种技术，所抽取的信息是隐含的、未知的，并且具有潜在应用价值。 知识发现可看成是一种有价值信息的搜寻过程，它不必预先假设或提出问题，仍然能够找到那些非预期的令人关注的信息，这些信息表示了不同研究对象之间的关系和模式。它还能通过全面的信息发现与分析，找到有价值的商业规则。 知识发现意味着在数据仓库或数据集市的几千兆、几万兆字节数据中寻找预先未知的商业模式与事实。 6.1.2 知识发现系统的结构 知识发现系统的结构由知识发现系统管理器、知识库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价和知识发现描述等部分组成（图6.1）。,1.知识发现系统管理器 控制并管理整个知识发现过程 2.知识库和商业分析员 知识库包含了源于各方面的知识。商业分析员要按一种有效的方式指导关注信息的发现。 3.数据仓库的数据库接口 知识发现系统的数据库接口可以直接与数据仓库通信。 4.数据选择 确定从数据仓库中需要抽取的数据及数据结构 5.知识发现引擎 将知识库中的抽取算法提供给数据选择构件抽取的数据 6.发现评价 有助于商业分析员筛选模式，选出那些关注性的信息 7.发现描述 发现、评价并辅助商业分析员在知识库中保存关注性发现结果以备将来引用,并保持知识发现与管理人员的通信。,6.2现代挖掘技术及应用,6.2.1 规则型现代挖掘技术及应用 1.关联规则的基本概念,buys(x,“computer”)=buys(x,“finacial_management_software”) age(“3040”)income(“4200050000”)=buys(x,“high_resolution_TV”) 布尔关联规则 量化关联规则 单维规则 多维关联 多层关联规则 单层关联规则 age(“3040”)=buys(x,“IBM computer”) (6.3) age(“3040”)=buys(x,“computer”) (6.4),2.关联规则的应用目标 置信度或正确率可以定义为： (6.5) 覆盖率可以定义为 “兴趣度”为目标的关联规则,3.关联规则的算法 Apriori算法 1找出所有支持度大于最小支持度的项集，这些项集称为频集，包含k个项的频集称为k-项集。 2使用第1步找到的频集产生所期望的规则。 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步算法较为简单。如果只考虑规则的右边只有一项的情况，给定一个频集Y=I1,I2,I3,Ik,k2,IjI，那么只有包含集合 I1,I2,I3,Ik中的项的规则最多有k条。这种规则形如I1,I2,I3,Ii-1,Ii+1,IkIi,。这些规则置信度必须大于用户给定的最小置信度。,由L2产生C3 L3,4.关联规则的应用,前件和后件规则中的正确率和覆盖率 规划覆盖率和正确率的平衡,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.神经网络的应用,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的一个实数，也是每一组解(ai,bi,ci)的适应度的度量，算法的目标是找一个(ao ,bo ,co)，使F=f(ao ,bo ,co)取最大值。 （2）计算当前基因群体中所有个体的环境适合度 （3）用适应函数评价每一个体对环境的适应度 （4）选择适应度好的生物个体进行复制 （5）选择适应度好的生物个体进行复制交叉配对繁殖 （6）新生代的变异操作,6.2.3 遗传算法型现代挖掘技术,6.2.3 遗传算法型现代挖掘技术,3.遗传算法的应用 用四个染色体来定义客户类型： 基因1：客户的年龄下限 基因2：客户的年龄上限 基因3：客户的收入水平 基因4：客户的人口状况（人口状况可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三种状况）,6.2.3 遗传算法型现代挖掘技术,所有的生物个体按顺序排放在一张二维表格上，使每个生物体的上、下、左、右都与其它生物体相邻接。 （1）竞争复制 （2）杂交繁殖 （3）异变处理,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已经流失，而客户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.决策树的应用,6.2.5 决策树型现代挖掘技术,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.文本分析和语义网络 文本分析 语义网络 2.文本挖掘 文本总结 基于关键字的关联分析 文档分类分析 文档聚类分析 文本挖掘的应用,6.4数据挖掘技术的发展,6.4.2 Web挖掘技术 1. Web的特点 2. Web内容挖掘 基于文本信息的挖掘 基于多媒体信息的挖掘 3.Web结构挖掘 4. Web使用记录的挖掘 数据预处理阶段 模式识别阶段 模式分析阶段 5.Web数据挖掘的应用,6.4数据挖掘技术的发展,6.4.3 可视化数据挖掘技术 1.数据的可视化 2.可视化数据挖掘技术 数据可视化 数据挖掘结果可视化 数据挖掘过程可视化 交互式可视化数据挖掘,6.4数据挖掘技术的发展,6.4.