数据库与数据挖掘

1、第8章 数据挖掘技术概述,8.1 什么是数据挖掘？ 数据挖掘（Data Mining） ，是指从大量数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在有用信息，提取的知识一般可表示为概念（Concepts）、规则（Rules）、规律（Regularities）、模式（Patterns）等形式。,有人将数据挖掘称为数据库中的知识发现（KDD: Knowledge Discovery in Database）。 也有人将数据挖掘看成为KDD中的一个步骤。,KDD过程由以下步骤组成：,数据清理（消除噪音和不一致数据） 数据集成（多种数据源组合在一起） 数据选择（选择与分析任务相关的数据）

2、 数据变换（变换成适合挖掘的形式） 数据挖掘 模式评估（用兴趣度度量） 易于理解、新颖、潜在有用、有效 知识表示,8.2 数据挖掘产生与发展,1989年8月在美国底特律召开的第11届国际人工智能会议上首先出现“数据库中知识发现（KDD）”这个术语，随后引起了国际人工智能和数据库等领域专家的广泛关注。 1995年在加拿大蒙特利尔召开了首届KDD / 生成含有1个项目的频繁集 ( 2 ) for (k=2; Lk-1; k+) do ( 3 ) Ck=Apriori_gen(Lk-1); ( 4 ) forall transaction tD do ( 5 ) Ct=subset(Ck,t); /

3、产生包含于事务t中的k项目集Ct ( 6 ) forall Candidate cCt do ( 7 ) c.count+; ( 8 ) Lk=cCkc.countminsup ( 9 ) Answer=k Lk;,Apriori_gen(Lk-1)的算法步骤： ( 1 ) insert into Ck select p.item1，p.item2，p.itemk-1，q.itemk-1 from Lk-1.p， Lk-1.q where p.item1=q.item1，p.item2=q.item2， ，p.itemk-2=q.itemk-2，p.item k-110000 购车。 数量关联

4、规则同样要满足支持度和可信度的约束条件。 数量关联在诸如银行存款分析、股市行情分析、保险业风险分析等众多领域都有重要应用价值 。,数量关联规则挖掘的关键问题是连续属性离散化， 其实质就是将连续属性域划分为若干区间。 目前主要有三种方法： 第一种是静态离散化，就是事先确定连续属性域的分割区间。例如，根据人们的先验知识将“月收入”分为 （0，3000），（3000，5000），（5000，8000），（8000，10000）等等。 第二种是根据连续属性域的分布情况和某种原则动态地将其分割成若干区间，以满足具体挖掘要求。在挖掘过程中这些区间还可以进一步合并。Fukuda提出了对连续属性区域进行等深度

5、划分（equi-depth partitioning）算法就属于这种方法。例如，根据等深度划分思想将储户的存款额划分若干区间，使得每个区间的储户数相等。 第三种是利用聚类的方法对连续属性域进行分割。,9.6 布尔关联规则分布式挖掘,设分布式系统中有n个站点，相应的局部数据库分别为 ，且各局部数据库模式逻辑同构， 称为全局数据库。 局部数据库中生成的频繁项目集称为局部频繁项目集；全局数据库中生成的频繁项目集称为全局频繁项目集。 若X既是某站点的局部频繁项目集，又是全局频繁项目集，则X称为该站点的重频繁项目集,在分布式数据库系统中，挖掘全局关联规则可以分解为以下两个子问题： (1)找出存在于全局数

6、据库中的所有全局频繁项目集 (2)利用全局频繁项目集L生成关联规则。 其中，第个问题是挖掘全局关联规则的关键问题。,定理1 若X为某站点上的局部频繁项目集，则X的所有非空子集均为该站点上的局部频繁项目集。 推论1 若项目集X不是局部频繁项目集，则X的超集一定不是局部频繁项目集。 定理2 设分布式数据库系统中站点Si上的局部频繁项目集为Li，i=1,2，n，将所有站点上的Li合并得到集合LL，则LL一定是全局频繁项目集L的超集。,推论2 若X是某站点的重频繁项目集，则X的所有非空子集也是该站点的重频繁项目集。 定理3 若X是全局频繁项集，则至少存在一个站点Si（i=1,2，n）使得项集X在站点Si为重频繁项目集。,分布式数据挖掘系统的体系结构,挖掘全局频繁项目集的算法思想,基于Apriori算法的思想产生全局候选项集,利用局部频繁项集和全局频繁项集之间的性质,在每次循环时产生较少的候选项集, 通过重频繁项目集产生较少的候