毕业设计（论文）基于SQL的关系数据库关联规则数据挖掘.doc

一、 数据挖掘的概念：数据挖掘，又称为数据采掘、数据开采等。一般认为数据挖掘是数据库中知识发现(Knowledge Discovery in Database,简记KDD)的一个环节，是KDD中采用具体的数据挖掘算法从数据中自动高效地提取有用模式的最重要的步骤19。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。它是一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学等相关技术15。数据挖掘是一门交叉性学科，有很多不同的术语名称。其中，最常用的是"知识发现"和"数据挖掘"。相对来讲，数据挖掘主要流行于统计界（最早出现于统计文献中）、数据分析、数据库和管理信息系统界；而知识发现则主要流行于人工智能和机器学习界。数据挖掘可粗略地理解为三部曲：数据准备（data preparation）、数据挖掘以及结果的解释评估（interpretation and evaluation）。  根据数据挖掘的任务分，有如下几种：分类或预测模型数据挖掘、数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。根据数据挖掘的对象分，有如下若干种数据源：关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗产（legacy）数据库、Web数据源。根据数据挖掘的方法分，可粗分为：统计方法、机器学习方法、神经网络方法和数据库方法。统计方法中，可细分为：回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）、以及模糊集、粗糙集、支持向量机等。机器学习中，可细分为：归纳学习方法（决策树、规则归纳等）、基于范例的推理CBR、遗传算法、贝叶斯信念网络等。神经网络方法，可细分为：前向神经网络（BP算法等）、自组织神经网络（自组织特征映射、竞争学习等）等。数据库方法主要是基于可视化的多维数据分析或OLAP方法，另外还有面向属性的归纳方法。数据库能有效地存储数据和查询数据， 但不能有效地分析数据。数据挖掘不但分析数据，而且帮助用户得知原因，并预测未来。因此，数据挖掘被普遍认为是非常有效的数据分析工具，被信息产业界认为是数据库系统最重要的前沿技术之一，是信息产业最有前途的交叉学科。数据挖掘的过程：1）了解应用领域，掌握相关先验知识以及应用的目标。2）收集并集成数据。3）对数据进行清洁和预处理。4）对数据进行归约和投影（发现有用特征，降维和变量约简）。5）确定适当的数据挖掘功能（总结、分类、回归、关联、聚类）。6）确定数据挖掘算法，并进行数据挖掘。7）对挖掘结果进行评估。8）对挖掘结果进行解释：分析结果。9）应用发现的知识。数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般分两类：1）描述式数据挖掘：刻划DB中数据的一般特性。2）预测式数据挖掘：在当前数据上进行推断，以进行预测。数据挖掘的方法包括：1) 统计分析方法：对关系表的各属性进行统计分析，找到它们之间存在的关系。2) 决策树：决策树可用于分类。3) 人工神经网络：人工神经网络用于分类、聚类、特征挖掘、预测和模式识别。4) 遗传算法（Genetic Algorithm）：遗传算法用于分类、关系型规则挖掘等。5) 粗糙集：粗糙集用于数据简化、数据意义评估、对象相似性或共性分析、因果关系及范式挖掘等。6) 联机分析处理技术。基于关系数据库的多维关联规则数据挖掘这一节主要介绍系统中使用的基于关系数据库的多维关联规则数据挖掘方面的技术。一、 关联规则数据挖掘关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众多知识类型中最为典型的一种。目前关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、可视化及信息科学等诸多领域的广大学者和研究机构的高度重视，取得了许多研究成果。由于关联规则形式简洁、易于解释和理解并可以有效地捕捉数据间的重要关系，因此从大型数据库中挖掘关联规则问题已成为数据挖掘中最成熟、最重要、最活跃的研究内容。关联规则挖掘最早是由Agrawal等人提出的。最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作涉及到关联规则的挖掘理论的探索、原有的算法的改进和新算法的设计、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等问题。在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力。一个事务数据库中的关联规则挖掘可以描述如下：设I= i1，i2，Im 是一个项目集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。设i1I，项目集i1在D上的支持度（support）是包含i1的事务在D中所占的百分比，即support（i1）= | t D | i1t| / | D|。一个定义在I和D上的形如i1=> i2的关联规则通过满足一定的可信度（confidence）来给出。所谓规则的可信度是指包含i1和i2的事务数与包含i1的事务数之比，即confidence（i1=> i2）= support（i1U i2）/ support（i1），其中i1，i2I，i1i2=。给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度（minsupport）和最小可信度（minconfidence）来寻找合适关联规则的过程。一般地，关联规则挖掘问题可以划分成两个子问题：（1）发现频繁项目集通过用户给定的minsupport，寻找所有频繁项目集（Frequent Itemset），即满足support不小于minsupport的项目集。事实上，这些频繁项目集可能具有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频繁大项集（Frequent Large Itemset）的集合。这些频繁大项集是形成关联规则基础。（2）生成关联规则通过用户给定的minconfidence，在每个最大频繁项目项目集中，寻找confidence不小于minconfidence的关联规则。子问题（1）是近年来关联规则挖掘算法研究的重点。比较流行的方法是基于Agrawal等人建立的项目集格空间理论。这个理论的核心是这样的原理：频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。对于子问题（2）而言，在每个频繁大项集中逐一匹配规则并进行confidence（i1=> i2）minconfidence的测试是必需的，因此这部分工作相对比较成熟。关联规则按不同的情况进行分类：1. 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。2. 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。3. 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。二、 关联规则挖掘算法l Apriori的关联规则挖掘算法15Apriori算法的有效性,在于它利用了一个非常重要的原理,即Apriori性质：如果一个项集是频繁的，则这个项集的任意一个非空子集都是频繁的。该性质属于一种特殊的分类，也称作反单调性。算法2-1 Apriori-发现频繁项目集(1) L1 = large 1-itemsets;(2) for (k=2; Lk-1¹F; k+) do begin(3) Ck=apriori-gen(Lk-1); /新的候选集(4) for all transactions tÎD do begin(5) Ct=subset(Ck,t); /事务t中包含的候选集(6) for all candidates cÎ Ct do(7) c.count+;(8) end(9) Lk=cÎ Ck |c.count³minsup(10) end(11)    Answer=kLk;首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁项集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频繁项集的候选集，最后的频繁项集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk。算法2-1中调用了apriori-gen(Lk-1)，是为了通过k-1频繁项集产生K候选集。算法2-2描述了apriori-gen过程。算法2-2 apriori-gen(Lk-1)-候选集产生：(1) FOR all itemset pÎ Lk-1 DO BEGIN(2) FOR all itemset qÎ Lk-1 DO BEGIN(3) IF p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1 THEN BEGIN(4) c= pq;/把q的第k-1个元素连到p后(5) IF has_infrequent_subset(c, Lk-1) THEN(6) delete c;/删除含有非频繁项目子集的候选元素(7) ELSE add c to Ck;(8) END(9) Return Ck;算法2-2中调用了has_infrequent_subset(c, Lk-1)，是为了判断c是否需要加入到k候选集中。按Agrarwal的项目集格空间理论，含有非频繁项目子集的元素不可能是频繁项目集，因此应该裁减掉，以提高效率。例如，如果L2=AB，AD，AC，BD，对于新产生的元素ABC不需要加入到C3 中，因为它的子集BC不在L2中；而ABD应该加入到C3 中，因为它的所有2-项子集都在L2中。算法2-3描述了这个过程。算法2-3 has_infrequent_subset(c, Lk-1)- 判断候选集的元素：(1) FOR all (k-1)-subset s of c DO (2) IF sÎLk-1 THEN(3) Return TURE;(4) ELSE Return FALSE;(5) ENDApriori算法是通过项目集元素数目不断增长来逐步完成频繁项目集发现的。首先产生1-频繁项集L1，然后是2-频繁项集L2，直到不再能扩展频繁项集的元素数目而算法停止。在第k次循环中，过程先产生k-候选项集的集合Ck，然后通过扫描数据库生成支持度并测试产生k-频繁项集Lk。Apriori算法的性能瓶颈问题：很显然，Apriori算法有两个致命的性能瓶颈：1. 多次扫描事务数据库，需要很大的I/O负载。对每次k循环，候选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项集包含10个项的话，那么就至少需要扫描事务数据库10遍。 2. 可能产生庞大的候选集。由Lk-1 产生k-候选集Ck 是指数增长的，如此大的候选集对时间和主存空间都是一种挑战。 正因为如此，包括Agrawal在内的许多学者提出了Apriori算法的改进方法。l FP- Tree的算法152000，Han等提出了一个称为FP- Tree的算法。这个算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。我们简单地描述利用FP- Tree算法构造频繁模式树的过程如下：1) 按Apriori算法，扫描数据库一次生成1-频繁集，并把它们按降序排列，放入L表中；2) 创建根节点，并标志为NULL，扫描数据库一次，当得到数据库的一个项目集（即一个元组）时，就把它中的元素按L表的次序排列，然后递归调用FP_Growth来实现FP_ Tree增长。下面的算法2-4给出了递归过程FP-Growth (Tree,)的较为正式描述。算法2-4 Procedure FP-Growth (Tree,)- 频繁模式树的生成（1） IF Tree contains a single path P THEN （2） FOR all combination (denoted as ) to the nodes in the path P DO （3） generate patter with support=minsupport of nodes in ;（4） ELSE FOR all i in the header of Tree DO BEGIN（5） generate patter =i with support=i.support;（6） construct conditional pattern base and generate Tree;（7） IF Tree THEN CALL FP-Growth (Tree, );（8） END；FP-Tree算法只有两次数据库扫描，的确在减少挖掘所需的I/O代价方面进行了有益的探索。而且它不会有庞大的候选集产生，减少了内存临时空间的占用。但是，它的问题是随着频繁模式树的增长可能使效率变得很差。l AprioriTid算法15AprioriTid算法对Apriori算法做了调整，它的特点是在第一次遍历数据库D之后，就不再使用数据库来计算支持度，而是用集合Ck来完成。集合Ck每个成员的形式为（TID, Xk），其中每个Xk都是一个潜在的大型k项集，在标识符为TID的事务中。对于k=1，C1对应与数据库D，虽然在概念上每个项目i由项目集l代替。对于k>1，有算法产生Ck（步骤（10）。与事务t相应的Ck的成员是（t.TID,cCk|t中包含的c）。若某个事务不包含任何候选k项目集，那么Ck对于这个事务就没有条目（Entry）。这样，Ck中条目数量比数据库中的事务数量少，尤其对于大值的k而言。另外，对于大值的k，每个条目比相应的事务要小，这是因为几乎没有什么候选能包含在此事务中。但是，对于小值的k，每个条目比相应的事务要大，因为Ck中的一个条目包括了此事务中的所有候选k项目集。算法步骤如下： （1）       L1=large l-itemsets（2）       C1=数据库D;（3）       For (k=2; Lk-1ø k+) do begin（4）       Ck = apriori-gen(Lk-1); /新的候选集（5）       Ck= ø（6）       for 所有条目tCk-1do begin（7）       /确定事务t。TID中包含的候选Ct= cCk |(c-ck) t.项目集的集合（c-ck-1）t.项目集的集合；（8）       for 所有候选cCt do （9）       c.count +;（10）   if(Ctø) then Ck+=<t.TID, Ct>（11）   end（12）   Lk=cCk |c.countmin.supp（13）   end三、 多维关联规则挖掘方法单维关联规则通常由事务数据库挖掘，如果使用的不是事务数据库，而是关系数据库或数据仓库，则数据和相关信息是以多维形式定义存储的。如关系数据库除记录销售事务中购买的商品外，还记录与商品有关的其它属性：购买数量、价格、销售分店的地址等。将数据库的每个属性或数据仓库的每个维看作一个谓词，这样就能挖掘多维关联规则。根据有没有重复的谓词分为：维间关联规则和混合关联规则。数据库中属性可能是分类的或是量化的（符号属性和量化属性）。其中量化属性的处理分为3种基本方法：使用预定义的概念分层对数值属性离散化；根据数据的分布，将数值属性离散化到箱(bins)，即用柱状图方法离散化；数值属性离散化，以紧扣区间数据的语义。在多维关联规则挖掘中是搜索频繁谓词集（k-谓词集）。1. 使用量化属性的静态离散化挖掘多维关联规则此时，数值属性在挖掘前就使用预定义的概念分层离散化，将属性的值用区间替代。例如，对于零件的价格可以用区间值，如“010$” 、“1120$” 、“2130$”等替代原来属性的值。而对符号属性，可根据需要概化到较高的概念层。若任务相关数据存放在关系表中，则Apriori算法等方法只要稍加修改，就可找出所有的频繁谓词。我们可以利用数据立方体来挖掘多维关联规则，我们必须先建立一个数据立方体，然后采用类似于Apriori所用的策略来寻找频繁谓词集，基于先验知识：频繁谓词集的每个子集也必须是频繁的。但是在没有挖掘任务的相关数据立方体存在时，必须创建。我们可以修改那些创建和计算数据立方体的算法，在数据立方体构造的时候搜索频繁谓词集。如图2-1 3-D数据立方体：（）(price)(producer)(material)(material,producer)(price,producer)(material,price,producer)(material,price)图2-1 3-D数据立方体2. 挖掘量化关联规则这里介绍基于图像处理基本思想的关联规则聚类方法（简称ARCS），其思想源于图像处理。本质上，该方法将数值属性对映射到满足给定符号属性条件的2-D删格上，然后搜索删格点的聚类，由此产生关联规则。下面是ARCS的步骤：（1） 分箱我们将量化属性的范围划分为区间，这些区间是动态的，在挖掘期间可以进一步合并。这种划分过程称作分箱，即区间被看着“箱”。三种常用的分箱策略是：l 等宽分箱：每个箱的区间长度相同。l 等深分箱：每个箱赋予大致相同个数的元组。l 基于同质的分箱：箱的大小这样确定，使得每个箱里面的元组一致分布。ARCS方法中，若使用等宽分箱，每个量化属性的箱尺寸由用户输入。对于涉及两个量化属性的每种可能的箱组合，创建一个2-D数组。每个数组单元存放规则右部分类属性每个可能类的对应的计数分布。通过创建这种数据结构，任务相关数据只需扫描一次。利用同样的2-D数组，还可以基于相同的两个量化属性产生分类属性的任何值的规则。（2） 找频繁谓词集一旦包含每个分类计数分布的2-D数组设置好，就可以扫描它，以找出那些满足最小支持度和最小置信度的频繁谓词集。然后使用前面介绍的规则产生算法，由这些谓词集产生关联规则。（3） 关联规则聚类将上一步骤得到的强关联规则映射到2-D栅格上，如图2-2表示材料元组的2-D栅格。26-30$16-20$11-15$6-10$0-5$21-25$属性produce-time属性price05.0605.0705.0805.0905.10图2-2 表示材料元组的2-D栅格图中的四个“X” 分别对应以下规则：price(X,”1115$”)produce-time(X,”05.08”)material(X,”铜制”)price(X,”1620$”)produce-time(X,”05.08”)material(X,”铜制”)price(X,”1115$”)produce-time(X,”05.09”)material(X,”铜制”)price(X,”1620$”)produce-time(X,”05.09”)material(X,”铜制”)我们可以找到一个更简单的规则替换上面四个规则：price(X,”1120$”)produce-time(X,”05.0905.08”)material(X,”铜制”)ARCS使用聚类算法来把上面四个规则汇总在一起，该算法扫描栅格，搜索规则的矩形聚类。用这种方法，出现在规则聚类中的量化属性的箱可能进一步合并，从而对量化属性动态地离散化。3. 挖掘基于距离的关联规则关联规则的一个不足是它不允许使用属性的近似值，这导致基于距离的关联规则挖掘，以便能比较准确地把握区间数据的语义，并允许数据值的近似。有一个两遍算法用于挖掘基于距离的关联规则：1) 第一遍使用聚类找出区间或簇设SX是N 个元组t1 ， t2 ， tn投影到属性集X的集合。定义一个直径度量，评估元组的接近性。SX的直径是投影到X的元组两两距离的平均值。距离度量可以使用欧氏距离或Manhattan距离。SX的直径越小，其元组投影到X上时越接近。因此直径度量评估簇的稠密性。簇Cx是定义在属性集X上的元组集合，其中的元组满足密度阈值和频率阈值。频率阈值限定聚类中元组的最少个数。聚类方法可以修改，用于挖掘过程的第一遍。2) 第二遍将簇组合，形成基于距离的关联规则一个简单的基于距离的关联规则为：Cx Cy，设X是属性集age ，Y是属性集income，要确保age的簇Cx和income的簇Cy之间的强关联关系，这就要求当age簇的元组投影到属性income上时，它们对应的值落在income簇之内，或接近它。若簇Cx在属性集Y上的投影记作Cx Y，那么Cx Y和Cy Y之间的距离必须很小。这一距离代表了Cx和Cy之间的关联程度。关联程度可以用标准统计度量定义。如:簇间的平均距离，中心的Manhattan距离(一个簇的中心为其“平均”元组）。通常可以组合簇，产生基于距离的关联规则。形式如下：其中Xi和Yj是两两不相交的属性集，并满足以下三个条件：1) 规则前提条件中的每个簇与结论中的每个簇是强关联的。2) 规则前提条件中的簇一起出现。3) 规则结论中的簇一起出现。 在此，关联程度取代了非基于距离的关联规则框架下的置信度，而密度阈值取代了支持度。关系数据库中关联规则应用的实现关联规则挖掘的最初目标是面向事务数据库，布尔关联规则挖掘技术也只是从事务数据库中挖掘出布尔型关联规则。为使关联规则挖掘技术应用更为广泛，让更多的决策者从中受益，就必需使关联规则挖掘技术能面向更为庞大和多样化的数据存储。近年来，随着关系数据库技术的迅速发展和不断完善，许多行业和部门的大量生产、管理及科研信息都采用关系数据库来存储和管理，存储体异常庞大，而其中必然蕴含了丰富的、人们感兴趣的知识。因此，积极研究在关系数据库中挖掘关联规则的有效技术具有极为广阔的发展前景14。在我的这个系统中就是研究关联规则挖掘在关系数据库中的应用。在这个系统中用户在XML文件里面定义好每个数据表采用的最小置信度（minconfidence）和最小支持度（minsupport），然后系统根据定义好的最小置信度和最小支持度，针对每个数据表如果是n维，那么找出所有的2k(k<=n)频繁谓词，从而产生2k维关联规则。这样在插入数据的时候则搜索关联规则库，并调用相匹配的规则。比如存在这么一个5维关联规则：X(2)Y(5)Z(7)A(12)B(9),那么我们在编辑的时候当字段X、Y、Z的值分别为2、5、7，那么双击字段A和字段B的编辑框则弹出一个子窗口（如下面图4-2 子窗口示意图）分别显示12、9，如果还存在规则：X(2)Y(5)Z(7)A(6)B(8)，那么字段A、B的编辑框双击事件弹出子窗口分别显示为12、9/6、8（自动在子窗口的列表中增加一条），选中子窗口中一个元素双击则自动在编辑框里填充该值。并且字段A选择12的时候字段B的那个子窗口里面的6还存在，字段A选择6的时候字段B的那个子窗口里面的8还存在（参见下面的推理1）。推理1：如果规则1：A1A2AiAi+1A i+2Aj,那么规则2：A1A2Ai-1AiAi+1Aj也成立。证明如下：假设规则1的支持度和置信度分别为support1和confidence1，规则2的支持度和置信度分别为support2和confidence2，根据前面支持度的定义可以证明support2=support1，根据前面置信度的定义：confidence（i1=> i2）= support（i1U i2）/ support（i1），从规则1到规则2分子不变但是分母变小了或者不变，从而confidence2confidence1，推得规则1成立的情况下规则2肯定成立。1 关系数据库中的关联规则关系数据库是依照关系模型建立起来的数据组织和存储体，而数据表是关系数据库最基本的组成单元。因此，在关系数据库中挖掘关联规则是从一个或多个关系数据库的一个或多个表中发现强规则的过程。在关系数据库中各个字段的类型可能会包括很多种不同的类型。1. 关系数据库中关联规则的相关定义：关系表S也可以用四元组来表示为S= (E, A, V, F)。其中E是记录号即元组标识的集合；A是表中属性的集合，如图4-4中A= 設備，部門，設備；V是各属性值域的并集，即V= U (VAi)，其中VAi表示S中属性Ai的值域;F是S中每个元组在不同属性上的从V中的取值关系。对应于事务数据库的关联规则的定义，在描述关系数据库中的关联规则时可将关系数据库看作是事务数据库的特例:设关系数据表S= (E, A, V, F)中与挖掘任务相关的属性有n个，即A= A1，A2,.，An;V是n个属性值域所构成的集合，即V=U (VAi)。1）关系表中的每一个元组Ei都可以看作是事务数据库中的一条事务。2）一个属性一一值对称为关系项目，记为(Ai ：VAj,)，表示S中某元组Ej的属性Ai取值是VAj。关系项目集I是关系表中所有与挖掘任务相关的属性的值域的并，即I=V=U(VAi)。3）元组也是项的集合，项集T构成某一元组，具有如下性质。 TI 所有T都具有相同的项数n 构成T的元素t1, t2, . , tn分别取值自VA1, VA2, . , VAn4）关联规则是形如A=>B的蕴含式。5）对于用户指定的最小支持度阂值(min_sup)和最小置信度阂值(min_ conf)，若有support (A=>B)>=min_sup，且confidence (A=>B) >=min_ conf，则AUB称为频繁项集，规则A=>B称为强规则。2. 关系数据库中关联规则的一般特征关系数据库中关系表的存储结构决定了从中获取的关联规则往往会带有以下明显特征:1）关联规则的多维性：根据关系数据库中关联规则定义的扩展描述，可以看到，关系数据库中的关联规则揭示了关系表中属性之间取值的内存联系。参照多维关联规则的定义描述，关系表的每个属性即是一个维，因此关系数据库中蕴含的不同属性取值之间的关联规则是多维型关联规则，关系数据库中的关联规则挖掘问题是一个多维型关联规则的挖掘问题。2）关联规则的多值性：由于关系数据库中属性的取值类型具有多样性，数据库的属性可能是分类的或量化的。分类属性又叫做标称属性，它具有有限个不同值，值之间无序；量化属性是数值型的，而且在值之间具有大小顺序。因此在关系数据库中发现的关联规则是多值性的关联规则，这样就要求挖掘算法不仅能发现布尔型关联规则，而且对数值型关联规则的挖掘也应具有一定的适应性和较高的效率。3）关联规则的多层性：因为关系数据库中的每个属性即可看作是一个维，而在多维数据库中许多维的取值在实际意义中是具有概念分层的，所以关系数据库中的关联规则往往会涵盖不同属性的多个概念层，属于多层型关联规则。关系数据库中关联规则挖掘的两种思路：在关系数据库中挖掘多值、多维、多概念层关联规则也是一个两步过程，即：搜索关系数据库中的频繁项目集，这里的频繁项目集是指频繁谓词集即不同属性之间取相同值的频繁性；根据所有频繁谓词集产生强关联规则。第一步工作仍然是整个挖掘算法的核心，目前从关系数据库中产生频繁谓词集的方法主要有两种思路：一是基于布尔型转换；二是基于SQL的集合操作。下面对两种思路进行简单的剖析。 1.基于布尔型转换的关系数据库中关联规则挖掘思想布尔型关联规则挖掘技术的研究已经取得了巨大的成功它是关联规则挖掘问题的起源，但该技术只能从事务数据库中进行关联规则的挖掘。在研究如何从不仅包含了二值属性，而且也包含了大量的类别属性和值属性的关系数据库中挖掘关联规则时，自然地有许多人想到了将关系数据库中的类别和数值等属性映射成布尔型属性，把关系数据表转换成事务数据库的形式，然后再利用已有的布尔型关联规则技术进行挖掘。类别和数值等属性进行布尔型映射的方法主要是：对取值较少的类别属性(包括布尔型等二值属性)，每一个类别值映射为一个项目；对取值较多的类别属性，根据概念分层等原则将属性值划分为多个子集，每个属性子集产生一个项目；对数值属性，根据某种分箱方法，将数值离散化为多个子区间，每个子区间便为对应一个项目。事务数据库是关系数据库的特例，它包含的项目都只来自同一个维，从这种意义上讲关系数据库是事务数据库在维数上扩充的一种更为广泛的概念。因此，可以认为关系数据库中关联规则的挖掘技术是包含事务数据库中布尔型关联规则挖掘技术的更广泛、更一般的关联规则挖掘技术。这种基于布尔转换的关系数据库中关联规则的挖掘技术虽然可以获得正确的强规则，但是多值分类属性和数值等类型属性的离散化处理加大了整个挖掘过程中数据预处理的时间开销，而且经过转换后的关系数据库所占的存储空间大大增加了。因此可以说基于布尔型转换的关系数据库中关联规则的挖掘方法是以牺牲整个挖掘过程的运行时间为代价的。2.基于SQL语言集合操作技术的关系数据库关联规则挖掘算法关系数据库之所以成为社会各行各业对生产、管理和科研等重要信息进行管理与存储的重要形式，一方面因为关系数据模型具有简单、直观、易于理解；另一方面因为关系数据库管理系统具有功能强大、操作简便、运行速度快等特点。关系数据库管理系统的成功，在很大程度上应归功于SQL语言。SQL是一种介于关系代数与关系演算之间的结构化查询语言，它之所以能够为用户和业界接受并成为国际标准，主要因为它是一个综合的、具有超强功能的、而且又简捷易懂的语言。SQL语言集数据查询(DataQuery)、数据操纵(Data Manipulation)、数据定义(Data Definition)和数据控制(Data Control)功能于一体，具有如下主要特征：综合统一，指其数据定义语言DDL、数据操纵语言DML和数据控制语言DCL的语言风格统一和数据操作符统一；高度非过程化，即在进行数据操作时，只需提出“做什么”，而不必指明“如何做” ；面向集合的操作方式，不仅操作对象、查找结果可以是元组的集合，而且一次插入、删除、更新操作的对象也可以是元组的集合；以同一种语法结构提供自含式和嵌入式两种使用方式，即SQL语言既能够在数据库管理系统中独立地用于联机交互操作，又能够嵌入到高级语言程序中；语言简捷，易学易用，它的核心功能只用SELECT、CREATE、INSERT等9个动词就可以完成，而且其语言接近英语口语，易于理解。由于关系数据库和SQI的上述特点，在研究如何从关系数据库中挖掘关联规则时，许多人想到了利用SQL来实现，更具体地说主要是利用SQL语言中提供的分组聚集语句来实现频繁项集的计数与筛选。4.3.2 基于SQL的关联规则挖掘算法在分析了关系数据库中关联规则的特点和目前在关系数据库中挖掘关联规则的两种基本思路后，借鉴Apriori算法的思想，通过产生数据规模比挖掘源表小的搜索替换表过程，利用产生属性组合以支持在搜索替换表中执行聚集操作和频繁关系项目表之间的连接查询等关键技术，提出了一种高效的关系数据库中关联规则挖掘算法（见图4-3 算法的流程图）。（其中RDB代表关系数据库、min_sup代表最小支持度、 min_conf代表最小置信度、相关属性代表所有参与数据挖掘任务的属性。）RDB 、min_sup、 min_conf以RDB的相关的属性为属性列表和分组条件进行聚集查询，生成用于关系项目集支持度计数统计的新基表。聚集查询，生成用于关系项目集支持度计数统计的新基表生成RDB中相关属性的k组合表Ck以Ck中的每一条记录所示的属性组合为属性列表和分组条件进行聚集查询，以min_sup为查询条件搜索频繁关系项目集L1-Lm (m<=n)件进行聚集查询，结果存入关系项目集支持度计数统计表Skk<n?利用频繁关系项目集L1-Lm，产生强规则输出规则k=k+1图4-3 算法的流程图算法也是分为两大部分：频繁谓词集的搜索和关联规则的生成。其中频繁谓词集的搜索是整个过程的核心，这里是利用SQL语句中的聚集查询来进行频繁谓词集的搜索。下面说明一下算法中几个主要步骤：l 比如在一个关系数据库中A1,A2,.,An为所有参与数据挖掘任务的属性，则利用下面的SQL语句：SELECT A1,A2,.,An,COUNT(*) AS sup_Temp FROM RDB GROUP BY A1,A2,.,An INTO TABLE RDB_TEMP 就生成用于关系项目集支持度计数统计的新基表。这样做的目的是降低算法的执行时间，新生成的基表会比原始的数据表规模小很多，在计算