第6章现代数据挖掘技术与发ppt课件

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

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

3、库、商业分析员、数据仓库的数据库接口、数据选择、知识发现引擎、知识发现评价和知识发现描述等部分组成（图6.1）。 数据仓库知识库数 据库 接口数据选择知识发现引擎知识发现评价知识发现描述知识发现管理器商业分析员图6.1 知识发现系统结构1.1.知识发现系统管理器知识发现系统管理器 控制并管理整个知识发现过程控制并管理整个知识发现过程 2.知识库和商业分析员知识库和商业分析员知识库包含了源于各方面的知识。商业分析员要按一种有知识库包含了源于各方面的知识。商业分析员要按一种有效的方式指导关注信息的发现效的方式指导关注信息的发现。3.数据仓库的数据库接口数据仓库的数据库接口知识发现系统的数据库接口可

4、以直接与数据仓库通信。知识发现系统的数据库接口可以直接与数据仓库通信。 4.数据选择数据选择确定从数据仓库中需要抽取的数据及数据结构确定从数据仓库中需要抽取的数据及数据结构 5.知识发现引擎知识发现引擎将知识库中的抽取算法提供给数据选择构件抽取的数据将知识库中的抽取算法提供给数据选择构件抽取的数据 6.发现评价发现评价有助于商业分析员筛选模式，选出那些关注性的信息有助于商业分析员筛选模式，选出那些关注性的信息 7.发现描述发现描述发现、评价并辅助商业分析员在知识库中保存关注性发现发现、评价并辅助商业分析员在知识库中保存关注性发现结果以备将来引用结果以备将来引用, ,并保持知识发现与管理人员的通

5、信。并保持知识发现与管理人员的通信。 6.26.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,“ibm computer”) (6.3)age(“30.

6、40”)=buys(x,“computer”) (6.4) 2.关联规则的应用目标关联规则的应用目标置信度或正确率可以定义为：置信度或正确率可以定义为： (6.5) (6.5)覆盖率可以定义为覆盖率可以定义为 “兴趣度兴趣度”为目标的关联规则为目标的关联规则的元组数包含的元组数和包含置信度ababa)(元组总数的元组数和包含覆盖率baba)( 3.关联规则的算法关联规则的算法aprioriapriori算法算法 1 1找出所有支持度大于最小支持度的项集，这些项集称为频集，包含找出所有支持度大于最小支持度的项集，这些项集称为频集，包含k k个项的频集个项的频集称为称为k-k-项集。项集。2 2使

7、用第使用第1 1步找到的频集产生所期望的规则。步找到的频集产生所期望的规则。aprioriapriori算法的第算法的第1 1步采用了递归方法，算法表示为步采用了递归方法，算法表示为l l1 1=large 1-itemsets;/=large 1-itemsets;/产生频繁产生频繁1 1项集项集l l1 1for (k=2;lfor (k=2;lk-1k-1;k+) do /;k+) do /循环产生频繁循环产生频繁2 2项集项集l l2 2直到某个直到某个r r使使l lr r为空为空beginbegin c ck k=apriori-gen(l=apriori-gen(lk-1k-1)

8、;/);/产生产生k-k-项集的候选集项集的候选集 for all transactions tfor all transactions td dod do begin beginc ct t=subset(c=subset(ck k,t);/,t);/事务事务t t中包含的候选集中包含的候选集for all candidates cfor all candidates cc ct t do do c.count+; c.count+; end endl lk k=c=cc ck k|c.count|c.countminsupminsupendendanswer=uanswer=uk kl l

9、k k第第2 2步算法较为简单。如果只考虑规则的右边只有一项的情况，给定一个频步算法较为简单。如果只考虑规则的右边只有一项的情况，给定一个频集集y=iy=i1 1,i,i2 2,i,i3 3, ,i,ik k,k,k2,i2,ij ji i，那么只有包含集合，那么只有包含集合 i i1 1,i,i2 2,i,i3 3, ,i,ik k 中中的项的规则最多有的项的规则最多有k k条。这种规则形如条。这种规则形如i i1 1,i,i2 2,i,i3 3, ,i ii-1i-1,i,ii+1i+1,i,ik ki ii i, ,。这。这些规则置信度必须大于用户给定的最小置信度。些规则置信度必须大于用

10、户给定的最小置信度。数据库d事务标识a1a2a3a4项集1,3,42,3,51,2,3,52,5扫 描 数据库d项集12345c1支持度23313比较支持度项集1235l1 支持度2333由l1产生c2 项集1,21,31,52,32,53,5扫 描 数据库d项集1,21,31,52,32,53,5 c2 支持度121232比较支持度项集1,22,32,53,5 l2 支持度2232项集扫描数据库d项集支持度2,3,52,3,52由l2产生c3 l34.关联规则的应用关联规则的应用前件和后件规则中的正确率和覆盖率 规划覆盖率和正确率的平衡 前件后件正确率覆盖率百吉饼奶油干酪80%5%百吉饼橙汁

11、40%3%百吉饼咖啡40%2%百吉饼鸡蛋25%2%面包牛奶35%30%黄油牛奶65%20%鸡蛋牛奶35%15%奶酪牛奶40%8%规划覆盖率正确率低正确率高覆盖率高规划很少是正确的，但可以使用规划多数情况下是正确的，而且可以经常使用覆盖率低规划很少是正确的，一般不被使用规划多数情况下是正确的，但很少被使用6.2.2 神经网络型现代挖掘技术神经网络型现代挖掘技术 1.神经网络及其学习方法神经网络及其学习方法神经网络的工作过程主要分两个阶段：学习阶段和工作阶段。神经网络的工作过程主要分两个阶段：学习阶段和工作阶段。学习方式则有三种：有教师（监督）学习、无教师（监督）学学习方式则有三种：有教师（监督）

12、学习、无教师（监督）学习和强化学习。习和强化学习。 6.2.2 神经网络型现代挖掘技术神经网络型现代挖掘技术 2.基于神经网络的数据挖掘基于神经网络的数据挖掘（1 1）基于自组织神经网络的数据挖掘技术）基于自组织神经网络的数据挖掘技术一种无教师学习过程一种无教师学习过程 、可以提取一组数据中的重要特征或某可以提取一组数据中的重要特征或某种内在知识种内在知识 （2 2）模糊神经网络类型数据挖掘技术）模糊神经网络类型数据挖掘技术模糊模糊bpbp网络、模糊网络、模糊kohonenkohonen聚类网络、模糊推理网络、模糊聚类网络、模糊推理网络、模糊artart模型等模型等 模糊模糊bpbp网络中，样

13、本的希望输出值改为样本相对各类的希望隶网络中，样本的希望输出值改为样本相对各类的希望隶属度属度 输出表达方面实现了模糊化，而且将样本的隶属度引入了权系输出表达方面实现了模糊化，而且将样本的隶属度引入了权系数的修正规则中，使权系数的修正规则也实现了模糊化。数的修正规则中，使权系数的修正规则也实现了模糊化。 6.2.2 神经网络型现代挖掘技术神经网络型现代挖掘技术 3.后向传播模型（后向传播模型（bp,back propagation）及其算法）及其算法具体过程如下：具体过程如下：选定选定p p个样本；个样本；权值初始化（随机生成）；权值初始化（随机生成）；依次输入样本；依次输入样本；依次计算各层

14、的输出；依次计算各层的输出；求各层的反传误差；求各层的反传误差；按权值调整公式修正各权值和阀值；按权值调整公式修正各权值和阀值；按新权值计算各层的输出，直到误差小于事先设定阀值；按新权值计算各层的输出，直到误差小于事先设定阀值；变换函数可以采用这样几种：变换函数可以采用这样几种：阶跃函数、阶跃函数、s s型函数、型函数、比例函数、比例函数、符号函数、符号函数、饱和饱和函数函数 、双曲函数双曲函数 6.2.2 神经网络型现代挖掘技术神经网络型现代挖掘技术 4.神经网络的应用神经网络的应用47岁收入6500元节点借贷拖欠？连接0.470.650.39weight=0.7weight=0.1年龄收入

15、0.47（0.7）+0.65（0.1）0.396.2.3 遗传算法型现代挖掘技术遗传算法型现代挖掘技术 1.遗传算法的基本原理遗传算法的基本原理达尔文的达尔文的“适者生存适者生存”理论、继承的信息由基因携带理论、继承的信息由基因携带 、多个、多个基因组成了染色体基因组成了染色体 、基因座、等位基因、基因座、等位基因 、基因型和表现、基因型和表现型型 染色体对应的是一系列符号序列，通常用染色体对应的是一系列符号序列，通常用0 0、1 1的位串表示的位串表示进行生物的遗传进化。在这一过程中包括三种演化操作：在父进行生物的遗传进化。在这一过程中包括三种演化操作：在父代基因群中的双亲选择操作、两个父代

16、双亲产生子代基因代基因群中的双亲选择操作、两个父代双亲产生子代基因的交叉操作和在子代基因群体中的变异操作。的交叉操作和在子代基因群体中的变异操作。 两种数据转换：从表现型到基因型的转换，另一种是从基因型两种数据转换：从表现型到基因型的转换，另一种是从基因型到表现型的转换到表现型的转换遗传算法实质上是一种繁衍、检测和评价的迭代算法遗传算法实质上是一种繁衍、检测和评价的迭代算法 最大优点是问题的最优解与初始条件无关，而且搜索最优解的最大优点是问题的最优解与初始条件无关，而且搜索最优解的能力极强能力极强 6.2.3 遗传算法型现代挖掘技术遗传算法型现代挖掘技术 2.遗传算法的处理过程遗传算法的处理过

17、程 （1 1）编码并生成祖先群体）编码并生成祖先群体要用遗传算法解决问题，首先要定义有待解决的问题：要用遗传算法解决问题，首先要定义有待解决的问题：f=f(a,b,c),ff=f(a,b,c),fr ,(a,b,c)r ,(a,b,c) f=f(a,b,c)f=f(a,b,c)是属于实数域是属于实数域r r的一个实数，也是每一组解的一个实数，也是每一组解(a(ai i,b,bi i,c,ci i) )的适应度的度量，算法的目标是找一个的适应度的度量，算法的目标是找一个(a(ao o ,b,bo o ,c,co o) )，使使f=f(af=f(ao o ,b,bo o ,c,co o) )取最大

18、值。取最大值。（2 2）计算当前基因群体中所有个体的环境适合度）计算当前基因群体中所有个体的环境适合度（3 3）用适应函数评价每一个体对环境的适应度）用适应函数评价每一个体对环境的适应度（4 4）选择适应度好的生物个体进行复制）选择适应度好的生物个体进行复制（5 5）选择适应度好的生物个体进行复制交叉配对繁殖）选择适应度好的生物个体进行复制交叉配对繁殖（6 6）新生代的变异操作）新生代的变异操作6.2.3 遗传算法型现代挖掘技术遗传算法型现代挖掘技术 编码并生成祖先群体计算当前基因群体中所有个体的适合度是否满足最优解条件？选择群体中适应值高的个体进行复制交叉操作变异操作终止6.2.3 遗传算法

19、型现代挖掘技术遗传算法型现代挖掘技术 3.遗传算法的应用遗传算法的应用用四个染色体来定义客户类型：用四个染色体来定义客户类型：基因基因1 1：客户的年龄下限：客户的年龄下限基因基因2 2：客户的年龄上限：客户的年龄上限基因基因3 3：客户的收入水平：客户的收入水平基因基因4 4：客户的人口状况（人口状况可以分成：少（：客户的人口状况（人口状况可以分成：少（1 1至至2 2人）、一般（人）、一般（3 3至至4 4人）和多（人）和多（5 5人以上）三种状况）人以上）三种状况）客户id年龄累计购买金额收入家庭人口性别1098546 1843 中等4女1859549 0 中等2男4738261 362

20、8低5男7491236 18463高6女9562329 8463高3男8552632 274中等2男5875352 1846低2女6495748 0中等3女7695727 21634高5男6583945 842低1女6.2.3 遗传算法型现代挖掘技术遗传算法型现代挖掘技术 所有的生物个体按顺序排放在一张二维表格上，使每个生物体所有的生物个体按顺序排放在一张二维表格上，使每个生物体的上、下、左、右都与其它生物体相邻接。的上、下、左、右都与其它生物体相邻接。 （1 1）竞争复制）竞争复制（2 2）杂交繁殖）杂交繁殖（3 3）异变处理）异变处理 年龄下限年龄上限高收入中等收入低收入人口少人口一般人口

21、多客户群13864是是否否是是客户群22650是否是是否是客户群32040否是是是否否6.2.4 粗糙集型现代挖掘技术粗糙集型现代挖掘技术1粗糙集技术粗糙集技术2.粗糙集的应用粗糙集的应用表中的表中的970230970230、980304980304、990211990211客户的客户的“赞扬竞争对手的产品赞扬竞争对手的产品”属性是相属性是相似的；似的；980304980304、990327990327客户的客户的“挑选产品时间很长挑选产品时间很长”和和“客户流失客户流失”属性是相似的；属性是相似的；970230970230、990211990211客户的客户的“赞扬竞争对手的产品赞扬竞争对手

22、的产品”、“ “ 挑选产品时间很长挑选产品时间很长”和和“距最后一次销售时间距最后一次销售时间”属性是相似的；属性是相似的；这样，围绕这样，围绕“赞扬竞争对手的产品赞扬竞争对手的产品”属性就可以产生两个初等集合：属性就可以产生两个初等集合：970230970230、980304980304、990211990211和和970102970102、980625980625、990327990327；而；而“赞扬赞扬竞争对手的产品竞争对手的产品”和和“挑选产品时间很长挑选产品时间很长”属性可以生成三个初等集属性可以生成三个初等集合：合：970102970102、980625980625、990327

23、990327、970230970230、990211990211和和980304980304。 客户编号赞扬竞争对手的产品否挑选产品时间很长距最后一次销售时间客户流失否970102否是长是970230是否长是980304是是很长是980625否是正常否990211是否长否990327否是很长是6.2.4 粗糙集型现代挖掘技术粗糙集型现代挖掘技术因为客户因为客户970230970230已经流失，而客户已经流失，而客户990211990211没有流失，由于属性没有流失，由于属性“赞扬竞争对手的产品赞扬竞争对手的产品”、“ 挑选产品时间很长挑选产品时间很长”和和“距最后一次销售时间距最后一次销售时间

24、”是相似的。因此，客户流失不能是相似的。因此，客户流失不能以属性以属性“赞扬竞争对手的产品赞扬竞争对手的产品”、“ 挑选产品时间很长挑选产品时间很长”和和“距最后一次销售时间距最后一次销售时间”作为特征进行描述。作为特征进行描述。而而970230970230、990211990211就是边界实例，即它们不能根据有效知识进就是边界实例，即它们不能根据有效知识进行适当的分类。余下的客户行适当的分类。余下的客户970102970102、980304980304和和990327990327所显所显示的特征，可以将他们确定为已经流失的客户。当然，也示的特征，可以将他们确定为已经流失的客户。当然，也不能排

25、除不能排除970230970230和和990211990211已经流失，而已经流失，而980625980625毫无疑问没毫无疑问没有流失。有流失。所以客户集合中所以客户集合中“流失流失”的下近似集合是的下近似集合是970102970102、980304980304、990327990327，上近似集合是，上近似集合是970102970102、970230970230、980304980304、990211990211、990327990327。同样，同样，980625980625没有流失，但是不能排除没有流失，但是不能排除970230970230和和990211990211流失。流失。因此，客

26、户因此，客户“没有流失没有流失”概念的下近似是概念的下近似是980625980625，上近，上近似是似是970230970230、980625980625、990211990211。6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术1决策树技术决策树技术id3id3，该算法建立在推理系统和概念学习系统的基础之上，基，该算法建立在推理系统和概念学习系统的基础之上，基本步骤是。本步骤是。（1 1）创建一个节点。如果样本都在同一类，则算法停止，把）创建一个节点。如果样本都在同一类，则算法停止，把该节点改成树叶节点，并用该类标记。该节点改成树叶节点，并用该类标记。（2 2）否则，选择一个能够最好的将

27、训练集分类的属性，该属）否则，选择一个能够最好的将训练集分类的属性，该属性作为该节点的测试属性。性作为该节点的测试属性。（3 3）对测试属性中的每一个值，创建相应的一个分支，并据）对测试属性中的每一个值，创建相应的一个分支，并据此划分样本。此划分样本。 （4 4）使用同样的过程自顶向下的递归，直到满足下面的三个）使用同样的过程自顶向下的递归，直到满足下面的三个条件中的一个时，就停止递归。条件中的一个时，就停止递归。(a)(a)给定节点的所有样本都属于同一类。给定节点的所有样本都属于同一类。(b)(b)没有剩余的属性可以用来进一步划分。没有剩余的属性可以用来进一步划分。(c)(c)继续划分得到的

28、改进不明显。继续划分得到的改进不明显。6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术1决策树技术决策树技术信息增益被定义为原始分割的熵与划分以后各分割的熵信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。累加得到的总熵之间的差。信息增益是指划分前后进行正确预测所需的信息量之差。信息增益是指划分前后进行正确预测所需的信息量之差。选择具有最高信息增益的属性作为当前节点的测试属性。选择具有最高信息增益的属性作为当前节点的测试属性。一个给定的样本分类所需要的期望信息为一个给定的样本分类所需要的期望信息为由由a划分成子集的熵或期望信息是划分成子集的熵或期望信息是 miiimp

29、psssi1221log,vjmjjmjjssisssae111)()(6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术1决策树技术决策树技术为第为第j个子集的权，等于子集（个子集的权，等于子集（a值为值为aj）中的）中的样本数除以样本数除以s中的样本数。对于给定的子集中的样本数。对于给定的子集sj， i(s1j,s2j,smj)可用下式计算 是sj中的样本属于类ci的概率 由a划分的信息增益是gain(a)=i(s1,s2,sm)-e(a) sssmjj1miijijmjjjppsssi1221)(log),(jijijssp6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术2.决策树

30、的应用决策树的应用年龄学生信誉等级会购买不会购买会购买会购买不会购买30314040否是一般良好6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术编号年龄学生信誉等级类别标号1=30是良好会购买240否一般会购买440否良好不会购买540否一般会购买63140是一般会购买740是一般会购买940否良好不会购买11=30否一般不会购买123140是一般会购买133140否一般会购买143140是良好会购买6.2.5 决策树型现代挖掘技术决策树型现代挖掘技术“年龄”在各个属性中具有最大的信息增益，所以选择“年龄”属性作为第一个测试属性，创建一个节点，用“年龄”标记。计算剩余各个属性的相应的信息增

31、益，选择信息增益最大的属性作为测试属性，这时信息增益最大的是“学生”属性，创建一个节点，用“学生”标记 。6.3知识发现工具与应用知识发现工具与应用6.3.1 知识挖掘工具的系统结构知识挖掘工具的系统结构1.无耦合（无耦合（no coupling）dm系统不利用系统不利用db或或dw系统的任何功能系统的任何功能 2.松散耦合（松散耦合（loose coupling）dm系统将使用系统将使用db/dw的某些工具的某些工具 3.半紧密耦合（半紧密耦合（semitight coupling）dm系统连接到一个系统连接到一个db/dw系统，一些基本数据挖掘原语系统，一些基本数据挖掘原语可以在可以在db

32、/dw系统中实现。系统中实现。 4.紧密耦合（紧密耦合（tight coupling）dm系统被平滑地集成到系统被平滑地集成到db/dw系统中系统中 6.3知识发现工具与应用知识发现工具与应用6.3.2 知识挖掘工具运用中的问题知识挖掘工具运用中的问题1.数据挖掘技术应用中的共性问题数据挖掘技术应用中的共性问题(1)数据质量数据质量(2)数据可视化数据可视化(3)极大数据库极大数据库(vldb)的问题的问题(4)性能和成本性能和成本(5)商业分折员的技能商业分折员的技能(6)处理噪声和不完全数据处理噪声和不完全数据(7)模式评估模式评估兴趣度问题兴趣度问题6.3知识发现工具与应用知识发现工具与

33、应用6.3.2 知识挖掘工具运用中的问题知识挖掘工具运用中的问题2.数据挖掘技术应用中的个性问题数据挖掘技术应用中的个性问题(1)规则归纳应用中的问题规则归纳应用中的问题主要用于显式描述数据抽取的规则主要用于显式描述数据抽取的规则 、找到所有的规则，工作量是巨大的 (2)神经网络应用中的问题神经网络应用中的问题受训练过度的影响受训练过度的影响 、神经网络的训练速度问题 (3)遗传算法应用中的问题遗传算法应用中的问题6.3知识发现工具与应用知识发现工具与应用6.3.3 知识挖掘的价值知识挖掘的价值1.了解商业活动了解商业活动2.发现商业异常发现商业异常3.预测模型预测模型6.3.4 现代数据挖掘

34、工具简介现代数据挖掘工具简介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