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

1 一、数据挖掘的概念： 数据挖掘，又称为数据采掘、数据开采等。一般认为数据挖掘是数据库中 知识发现(knowledge discovery in database,简记 kdd)的一个环节，是 k dd 中采用具体的数据挖掘算法从数据中自动高效地提取有用模式的最重要的 步骤19。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识 别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。它是 一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据库、 模式识别、粗糙集、模糊数学等相关技术15。 数据挖掘是一门交叉性学科，有很多不同的术语名称。其中，最常用的是 “知识发现“和“数据挖掘“。相对来讲，数据挖掘主要流行于统计界（最早出现 于统计文献中） 、数据分析、数据库和管理信息系统界；而知识发现则主要流 行于人工智能和机器学习界。 数据挖掘可粗略地理解为三部曲：数据准备（data preparation） 、数据 挖掘以及结果的解释评估（interpretation and evaluation） 。 根据数据挖掘的任务分，有如下几种：分类或预测模型数据挖掘、数据总 结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异 常和趋势发现等等。 根据数据挖掘的对象分，有如下若干种数据源：关系数据库、面向对象数 据库、空间数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗 产（legacy）数据库、web 数据源。 根据数据挖掘的方法分，可粗分为：统计方法、机器学习方法、神经网络 方法和数据库方法。统计方法中，可细分为：回归分析（多元回归、自回归等 ） 、判别分析（贝叶斯判别、费歇尔判别、非参数判别等） 、聚类分析（系统聚 类、动态聚类等） 、探索性分析（主元分析法、相关分析法等） 、以及模糊集、 粗糙集、支持向量机等。机器学习中，可细分为：归纳学习方法（决策树、规 则归纳等） 、基于范例的推理 cbr、遗传算法、贝叶斯信念网络等。神经网络 方法，可细分为：前向神经网络（bp 算法等） 、自组织神经网络（自组织特征 映射、竞争学习等）等。数据库方法主要是基于可视化的多维数据分析或 ola p 方法，另外还有面向属性的归纳方法。 2 数据库能有效地存储数据和查询数据， 但不能有效地分析数据。数据挖 掘不但分析数据，而且帮助用户得知原因，并预测未来。因此，数据挖掘被普 遍认为是非常有效的数据分析工具，被信息产业界认为是数据库系统最重要的 前沿技术之一，是信息产业最有前途的交叉学科。 数据挖掘的过程： 1）了解应用领域，掌握相关先验知识以及应用的目标。 2）收集并集成数据。 3）对数据进行清洁和预处理。 4）对数据进行归约和投影（发现有用特征，降维和变量约简） 。 5）确定适当的数据挖掘功能（总结、分类、回归、关联、聚类） 。 6）确定数据挖掘算法，并进行数据挖掘。 7）对挖掘结果进行评估。 8）对挖掘结果进行解释：分析结果。 9）应用发现的知识。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。 数据挖掘任务一般分两类： 1）描述式数据挖掘：刻划 db 中数据的一般特性。 2）预测式数据挖掘：在当前数据上进行推断，以进行预测。 数据挖掘的方法包括： 1)统计分析方法：对关系表的各属性进行统计分析，找到它们之间存在 的关系。 2)决策树：决策树可用于分类。 3)人工神经网络：人工神经网络用于分类、聚类、特征挖掘、预测和模 式识别。 4)遗传算法（genetic algorithm）：遗传算法用于分类、关系型规则挖掘 等。 5)粗糙集：粗糙集用于数据简化、数据意义评估、对象相似性或共性分 析、因果关系及范式挖掘等。 6)联机分析处理技术。 3 基于关系数据库的多维关联规则数据挖掘基于关系数据库的多维关联规则数据挖掘 这一节主要介绍系统中使用的基于关系数据库的多维关联规则数据挖掘方 面的技术。 一、关联规则数据挖掘 关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众 多知识类型中最为典型的一种。目前关联规则挖掘问题已经引起了数据库、人 工智能、统计学、信息检索、可视化及信息科学等诸多领域的广大学者和研究 机构的高度重视，取得了许多研究成果。由于关联规则形式简洁、易于解释和 理解并可以有效地捕捉数据间的重要关系，因此从大型数据库中挖掘关联规则 问题已成为数据挖掘中最成熟、最重要、最活跃的研究内容。 关联规则挖掘最早是由 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）来寻找合适关联规则的过程。 4 一般地，关联规则挖掘问题可以划分成两个子问题： （1）发现频繁项目集 通过用户给定的 minsupport，寻找所有频繁项目集（frequent itemset） ， 即满足 support 不小于 minsupport 的项目集。事实上，这些频繁项目集可能 具有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频 繁大项集（frequent large itemset）的集合。这些频繁大项集是形成关联规 则基础。 （2）生成关联规则 通过用户给定的 minconfidence，在每个最大频繁项目项目集中，寻找 confidence 不小于 minconfidence 的关联规则。 子问题（1）是近年来关联规则挖掘算法研究的重点。比较流行的方法是 基于 agrawal 等人建立的项目集格空间理论。这个理论的核心是这样的原理： 频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。 对于子问题（2）而言，在每个频繁大项集中逐一匹配规则并进行 confidence（i1= i2）minconfidence 的测试是必需的，因此这部分工作相对 比较成熟。 关联规则按不同的情况进行分类： 1.基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间 的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值 型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当 然数值型关联规则中也可以包含种类变量。 例如：性别=“女”=职业=“秘书” ，是布尔型关联规则；性别=“女 ”=avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规 则。 2.基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不 同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑 。 5 例如：ibm 台式机=sony 打印机，是一个细节数据上的单层关联规则； 台式机=sony 打印机，是一个较高层次和细节层次之间的多层关联规则。 3.基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维 关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的 某些关系。 例如：啤酒=尿布，这条规则只涉及到用户的购买的物品；性别=“女”= 职业=“秘书” ，这条规则就涉及到两个字段的信息，是两个维上的一条关联 规则。 二、关联规则挖掘算法 apriori 的关联规则挖掘算法15 apriori 算法的有效性,在于它利用了一个非常重要的原理,即 apriori 性 质：如果一个项集是频繁的，则这个项集的任意一个非空子集都是频繁的。该 性质属于一种特殊的分类，也称作反单调性。 算法 2-1 apriori-发现频繁项目集 (1) l1 = large 1-itemsets; (2) for (k=2; lk-1; k+) do beginbegin (3) ck=apriori-gen(lk-1); /新的候选集 (4) for all transactions td do beginbegin (5) ct=subset(ck,t); /事务 t 中包含的候选集 (6) for all candidates c ct do (7) c.count+; (8) endend (9) lk=c ck |c.countminsup (10) endend (11) answer=klk; 首先产生频繁 1-项集 l1，然后是频繁 2-项集 l2，直到有某个 r 值使得 lr 为空，这时算法停止。这里在第 k 次循环中，过程先产生候选 k-项集的集合 ck，ck中的每一个项集是对两个只有一个项不同的属于 lk-1的频繁项集做一 6 个(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 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+=; （11） end （12） lk=cck |c.countmin.supp （13） end 9 三、多维关联规则挖掘方法 单维关联规则通常由事务数据库挖掘，如果使用的不是事务数据库，而是 关系数据库或数据仓库，则数据和相关信息是以多维形式定义存储的。如关系 数据库除记录销售事务中购买的商品外，还记录与商品有关的其它属性：购买 数量、价格、销售分店的地址等。将数据库的每个属性或数据仓库的每个维看 作一个谓词，这样就能挖掘多维关联规则。 根据有没有重复的谓词分为：维间关联规则和混合关联规则。 数据库中属性可能是分类的或是量化的（符号属性和量化属性） 。其中量 化属性的处理分为 3 种基本方法：使用预定义的概念分层对数值属性离散化； 根据数据的分布，将数值属性离散化到箱(bins)，即用柱状图方法离散化；数 值属性离散化，以紧扣区间数据的语义。在多维关联规则挖掘中是搜索频繁谓 词集（k-谓词集） 。 1.使用量化属性的静态离散化挖掘多维关联规则 此时，数值属性在挖掘前就使用预定义的概念分层离散化，将属性的值用 区间替代。例如，对于零件的价格可以用区间值，如“010$” 、 “1120$ ” 、 “2130$”等替代原来属性的值。而对符号属性，可根据需要概化到较 高的概念层。若任务相关数据存放在关系表中，则 apriori 算法等方法只要稍 加修改，就可找出所有的频繁谓词。 我们可以利用数据立方体来挖掘多维关联规则，我们必须先建立一个数据 立方体，然后采用类似于 apriori 所用的策略来寻找频繁谓词集，基于先验知 识：频繁谓词集的每个子集也必须是频繁的。但是在没有挖掘任务的相关数据 立方体存在时，必须创建。我们可以修改那些创建和计算数据立方体的算法， 在数据立方体构造的时候搜索频繁谓词集。如图 2-1 3-d 数据立方体： 10 （） (price) (producer) (material) (material,producer)(price,producer) (material,price,producer) (material,price) 图 2-1 3-d 数据立方体 2.挖掘量化关联规则 这里介绍基于图像处理基本思想的关联规则聚类方法（简称 arcsarcs） ，其 思想源于图像处理。本质上，该方法将数值属性对映射到满足给定符号属性条 件的 2-d 删格上，然后搜索删格点的聚类，由此产生关联规则。下面是 arcsarcs 的步骤： （1） 分箱 我们将量化属性的范围划分为区间，这些区间是动态的，在挖掘期间可以 进一步合并。这种划分过程称作分箱，即区间被看着“箱” 。三种常用的分箱 策略是： 等宽分箱：每个箱的区间长度相同。 等深分箱：每个箱赋予大致相同个数的元组。 基于同质的分箱：箱的大小这样确定，使得每个箱里面的元组一致分 布。 arcs 方法中，若使用等宽分箱，每个量化属性的箱尺寸由用户输入。对 于涉及两个量化属性的每种可能的箱组合，创建一个 2-d 数组。每个数组单元 存放规则右部分类属性每个可能类的对应的计数分布。通过创建这种数据结构 ，任务相关数据只需扫描一次。利用同样的 2-d 数组，还可以基于相同的两个 量化属性产生分类属性的任何值的规则。 （2） 找频繁谓词集 11 一旦包含每个分类计数分布的 2-d 数组设置好，就可以扫描它，以找出那 些满足最小支持度和最小置信度的频繁谓词集。然后使用前面介绍的规则产生 算法，由这些谓词集产生关联规则。 （3） 关联规则聚类 将上一步骤得到的强关联规则映射到 2-d 栅格上，如图 2-2 表示材料元组 的 2-d 栅格。 26-3026-30$ $ 16-2016-20$ $ 11-1511-15$ $ 6-106-10$ $ 0-50-5$ $ 21-2521-25$ $ 属性属性 produce-timeproduce-time 属性属性 priceprice 05.0605.06 05.0705.07 05.0805.0805.0905.09 05.1005.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.挖掘基于距离的关联规则 关联规则的一个不足是它不允许使用属性的近似值，这导致基于距离的关 12 联规则挖掘，以便能比较准确地把握区间数据的语义，并允许数据值的近似。 有一个两遍算法用于挖掘基于距离的关联规则： 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)规则结论中的簇一起出现。 在此，关联程度取代了非基于距离的关联规则框架下的置信度，而密度 阈值取代了支持度。 yx yyyxxx cccccc, 2121 13 关系数据库中关联规则应用的实现 关联规则挖掘的最初目标是面向事务数据库，布尔关联规则挖掘技术也只 是从事务数据库中挖掘出布尔型关联规则。为使关联规则挖掘技术应用更为广 泛，让更多的决策者从中受益，就必需使关联规则挖掘技术能面向更为庞大和 多样化的数据存储。近年来，随着关系数据库技术的迅速发展和不断完善，许 多行业和部门的大量生产、管理及科研信息都采用关系数据库来存储和管理， 存储体异常庞大，而其中必然蕴含了丰富的、人们感兴趣的知识。因此，积极 研究在关系数据库中挖掘关联规则的有效技术具有极为广阔的发展前景14。在 我的这个系统中就是研究关联规则挖掘在关系数据库中的应用。 在这个系统中用户在 xml 文件里面定义好每个数据表采用的最小置信度 （minconfidence）和最小支持度（minsupport） ，然后系统根据定义好的最 小置信度和最小支持度，针对每个数据表如果是 n 维，那么找出所有的 2k(k i2）= support（i1u i2）/ support（i1）， 从规则 1 到规则 2 分子不变但是分母变小了或者不变，从而 confidence2confidence1，推得规则 1 成立的情况下规则 2 肯定成立。 14 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, . , van 4）关联规则是形如 a=b 的蕴含式。 5）对于用户指定的最小支持度阂值(min_sup)和最小置信度阂值(min_ conf)，若有 support (a=b)=min_sup，且 confidence (a=b) =min_ conf，则 aub 称为频繁项集，规则 a=b 称为强规则。 2.关系数据库中关联规则的一般特征 关系数据库中关系表的存储结构决定了从中获取的关联规则往往会带有以 15 下明显特征: 1）关联规则的多维性：根据关系数据库中关联规则定义的扩展描述，可 以看到，关系数据库中的关联规则揭示了关系表中属性之间取值的内存联系。 参照多维关联规则的定义描述，关系表的每个属性即是一个维，因此关系数据 库中蕴含的不同属性取值之间的关联规则是多维型关联规则，关系数据库中的 关联规则挖掘问题是一个多维型关联规则的挖掘问题。 2）关联规则的多值性：由于关系数据库中属性的取值类型具有多样性， 数据库的属性可能是分类的或量化的。分类属性又叫做标称属性，它具有有限 个不同值，值之间无序；量化属性是数值型的，而且在值之间具有大小顺序。 因此在关系数据库中发现的关联规则是多值性的关联规则，这样就要求挖掘算 法不仅能发现布尔型关联规则，而且对数值型关联规则的挖掘也应具有一定的 适应性和较高的效率。 3）关联规则的多层性：因为关系数据库中的每个属性即可看作是一个维， 而在多维数据库中许多维的取值在实际意义中是具有概念分层的，所以关系数 据库中的关联规则往往会涵盖不同属性的多个概念层，属于多层型关联规则。 关系数据库中关联规则挖掘的两种思路： 在关系数据库中挖掘多值、多维、多概念层关联规则也是一个两步过程， 即：搜索关系数据库中的频繁项目集，这里的频繁项目集是指频繁谓词集即 不同属性之间取相同值的频繁性；根据所有频繁谓词集产生强关联规则。第 一步工作仍然是整个挖掘算法的核心，目前从关系数据库中产生频繁谓词集的 方法主要有两种思路：一是基于布尔型转换；二是基于 sql 的集合操作。下 面对两种思路进行简单的剖析。 1.基于布尔型转换的关系数据库中关联规则挖掘思想 布尔型关联规则挖掘技术的研究已经取得了巨大的成功它是关联规则挖掘 问题的起源，但该技术只能从事务数据库中进行关联规则的挖掘。在研究如何 从不仅包含了二值属性，而且也包含了大量的类别属性和值属性的关系数据库 中挖掘关联规则时，自然地有许多人想到了将关系数据库中的类别和数值等属 性映射成布尔型属性，把关系数据表转换成事务数据库的形式，然后再利用已 有的布尔型关联规则技术进行挖掘。类别和数值等属性进行布尔型映射的方法 主要是：对取值较少的类别属性(包括布尔型等二值属性)，每一个类别值映 射为一个项目；对取值较多的类别属性，根据概念分层等原则将属性值划分 16 为多个子集，每个属性子集产生一个项目；对数值属性，根据某种分箱方法 ，将数值离散化为多个子区间，每个子区间便为对应一个项目。事务数据库是 关系数据库的特例，它包含的项目都只来自同一个维，从这种意义上讲关系数 据库是事务数据库在维数上扩充的一种更为广泛的概念。因此，可以认为关系 数据库中关联规则的挖掘技术是包含事务数据库中布尔型关联规则挖掘技术的 更广泛、更一般的关联规则挖掘技术。这种基于布尔转换的关系数据库中关联 规则的挖掘技术虽然可以获得正确的强规则，但是多值分类属性和数值等类型 属性的离散化处理加大了整个挖掘过程中数据预处理的时间开销，而且经过转 换后的关系数据库所占的存储空间大大增加了。因此可以说基于布尔型转换的 关系数据库中关联规则的挖掘方法是以牺牲整个挖掘过程的运行时间为代价的 。 2.基于 sql 语言集合操作技术的关系数据库关联规则挖掘算法 关系数据库之所以成为社会各行各业对生产、管理和科研等重要信息进行 管理与存储的重要形式，一方面因为关系数据模型具有简单、直观、易于理 解；另一方面因为关系数据库管理系统具有功能强大、操作简便、运行速度快 等特点。关系数据库管理系统的成功，在很大程度上应归功于 sql 语言。 sql 是一种介于关系代数与关系演算之间的结构化查询语言，它之所以能够为 用户和业界接受并成为国际标准，主要因为它是一个综合的、具有超强功能的、 而且又简捷易懂的语言。sql 语言集数据查询(dataquery)、数据操纵(data manipulation)、数据定义(data definition)和数据控制(data control)功能于 一体，具有如下主要特征：综合统一，指其数据定义语言 ddl、数据操纵语 言 dml 和数据控制语言 dcl 的语言风格统一和数据操作符统一；高度非 过程化，即在进行数据操作时，只需提出“做什么” ，而不必指明“如何做” ；面向集合的操作方式，不仅操作对象、查找结果可以是元组的集合，而且 一次插入、删除、更新操作的对象也可以是元组的集合；以同一种语法结构 提供自含式和嵌入式两种使用方式，即 sql 语言既能够在数据库管理系统中 独立地用于联机交互操作，又能够嵌入到高级语言程序中；语言简捷，易学 易用，它的核心功能只用 select、create、insert 等 9 个动词就可以 完成，而且其语言接近英语口语，易于理解。由于关系数据库和 sqi 的上述特 点，在研究如何从关系数据库中挖掘关联规则时，许多人想到了利用 sql 来 实现，更具体地说主要是利用 sql 语言中提供的分组聚集语句来实现频繁项 17 集的计数与筛选。 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 =min_sup 就可以得到一个长度为3的关系项目集支持度计数，遍历 c3中所有记录运行聚集查询的结果的并集，同理可以完成所有长度 19 为k（12“ dmrc = gfunexecsql(csql, conn, record, comm, 1) next 根据前一步产生的频繁关系项目集，采用连接查询的方法就可以产 生规则。 这里用到的新基表 rdb_temp 是一个临时表，这个表的作用是用来降低 20 数据库的规模，相关属性的 k 组合 c1-ck是存放在 k 个临时表 c1_tempck_temp 里面，频繁关系项目集也是放在临时表中，最后根据 前面的连接查询产生关联规则放到一个规则表 rule_left 和 rule_right 中，从 而形成规则库。 如果根据频繁关系项目集把所有符合条件的规则都输出到规则库中，规则 库可能会变得非常庞大，影响了软件的性能。系统中处理的过程是我们在需要 使用到这条规则的时候先到规则库中搜索，如果规则库里没有对应的规则那么 就根据频繁关系项目集挖掘相应的规则；如果存在，那么输出到规则库中去并 调用相应的规则。所以规则库在初始阶段是空的，它的规模随着软件不断被使 用而慢慢增长的，当规则库的规模达到某一个限度的时候，利用随机算法删除 其中的某些规则，使规则库的规模降低到原来的 2/3 再重复前面的过程。 新基表为表 4-1 新基表所示： 表4-1 新基表 其中 c3表里的如表 4-2 属性 3 组合表所示： 表4-2 属性3组合表 根据表 4-1 新基表产生如表 4-3 频繁关系项目集表所示的频繁关系项目集 ： 表4-3 频繁关系项目集表 21 我们看其中的属性组合（bumon_cd，machine_cd，machine_grp_cd） 可以发现 bumon_cd（12） ，machine_cd（13） ，machine_grp_cd（2）和 bumon_cd（52） ，machine_cd（14） ，machine_grp_cd（2）的支持度计数 分别为 12 和 5，大于最小支持度（min_sup）2。 我们根据上面 c3 中（bumon_cd, machine_cd, machine_grp_cd）频繁 关系项目集，取最小置信度为 50%，进行连接查询可以得到关联规则，其中两 条强规则如下：bumon_cd（12）machine_cd（13） machine_grp_cd（2）和 bumon_cd（52）machine_cd（14） machine_grp_cd（2） （置信度分别都为 92.3和 100%） 。 我们把得到的规则存储到表 rule_left 和 rule_right 中形成规则库，这里 rule_left 表的结构是（id,a1,a2an,support,confidence） ，rule_right 表的 22 结构是（id, a1,a2an,support,confidence） ，这两个表中的字段 id 是对应 于同一条规则是相同的并且是唯一的。例如上面这两条规 则：bumon_cd（12）machine_cd（13）machine_grp_cd（2）和 bumon_cd（52）machine_cd（14）machine_grp_cd（2）在规则库分 别存放在表 rule_left 和 rule_right 中，如下所示，id 分别对应为 6 和 35： 表4-4 rule_left表 23 表4-5 rule_right表 表 rule_left 存储规则的左边部分，rule_right 存储规则的右边部分， support 和 confidence 分别存储规则的支持度和置信度，这两个表之间通过字 段 id 相关联，这里 id 的值代表了这条规则的编号。当字段 bumon_cd、machine_cd 的值分别为 12、13 的时候就自动触发这条规则。对 应的 sql 语句是：select rule_right.* from rule_left,rule_right where rule_left. bumon_cd =12 and rule_left. machine_cd =13and rule_left.id= rule_ right.id ,把从 rule_right 中检索到的结果中不为 null 的 字段抽取出来就是规则的右边部分。 4.3.3 关联规则的维护 前面讨论的是在初始状态下根据数据库里的数据进行分析得到的关联规则 ，在 db 编辑界面自动生成的研究中，会有很多的对数据库进行更新的操作， 包括删除、插入、更新记录等，正是因为数据库里的记录的变化使得我们已经 挖掘的关联规则可能不够准确，这就要求我们根据数据库里面记录的变动相应 24 地刷新规则库里面的内容，如图 4-5 关联规则维护示意图。 编辑数据库 规则 kb 系统 db 基于关系数据库进行多维 关联规则数据挖掘 插入数据 删除数据 更新数据 图 4-5 关联规则维护示意图 对于数据库的修改分为三种情况，下面我们来分别说明对应于每种情况的 处理方法： 删除数据 删除一条数据则搜索规则库，如果存在与删除的数据相关的规则，则修改 这条规则对应的支持度（support）和置信度（confidence） ，同时与最小支持 度和最小置信度比较，如果不满足则把这条规则从规则库里删除。 例如表 4-4 和表 4-5 显示一条 id 为 6 的规则，如果删除一条数据对应的 bumon_cd、machine_cd 和 machine_grp_cd 对应的值分别为“12” 、 “13” 和“2” ，则表 4-4 和表 4-5 里面对应的 id 为 6 那条记录的 support 和 confidence 分别修改为 11 和 92%，如果这两个值不符和最小支持度和最小置 信度，则从表 4-4 和表 4-5 中删除这条 id 为 6 的规则。 插入数据 插入一条新的记录则先搜索规则库，如果规则库里存在与新插入的记录相 关的规则，则修改对应规则的支持度（support）和置信度（confidence） ，如 果对应的属性组合在规则库里没有，则按照前面讨论的方法来生成频繁关系集 和关联规则，修改规则库里面的记录。 如果插入一条数据对应的 bumon_cd、machine_cd 和 machine_grp_cd 对应的值分别为“52” 、 “14”和“2” ，参照上面表 4-4 和表 4-5 中 id 为 35 的 规则，则表 4-4 和表 4-5 里面对应的 id 为 35 那条记录的 support 和 25 confidence 分别修改为 6 和 100%。如果在规则库里面不存在对应的规则，那 么则参照上一节 4.3.2 基于关系数据库进行连接查询，如果发现新的规则那么 添加到规则库。 更新数据 更新数据可以看作是删除数据和插入数据两个过程的总和，则按照前面的 介绍分别按照删除数据和插入数据进行处理，修改规则库里面的记录。 26 27 第第 5 章章 总结和展望总结和展望 5.1 总结 在本文中主要研究了数据库的编辑界面的自动生成，主要处理了三个方面 的约束条件：数据库本身可以定义的、用户自己定义的、从数据库中已有的数 据里发现的潜在的规则。 对于数据库本身可以定义的那部分的处理相对比较容易，数据库本身可以 定义的内容很有限（例如字段类型前端检查、 check 约束、foreign k ey 约束、unique 约束、not null 约束和 primary key 约束等） ，只要在自动生成的过程中针对每一种情况都对应相应的处理函数，同时界面 上还会给出一些提示信息方便用户操作（例如在鼠标移动到输入框的时候自动 显示对于字段要求的数据类型等） ，这样在用户编辑数据的时候就检查输入的 数据是否满足相应的约束条件，虽然数据库管理系统本身会做这样的检查，这 里我们把这个检查放在前端来做。 对于用户自己定义的那部分则是预先给用户一个手册，用户按照这个手册 定义自己想要定义的信息（这里只能处理一些相对简单、常用的定义） ，在界 面的自动生成过程中会去解析这些定义的信息，从而在用户编辑数据库的时候 检查输入的数据是否符合这些约束。 本文主要介绍了基于关系数据库的关联规则的数据挖掘，数据库中已经存 在的数据可能预示着很多很有价值的信息，关联规则的发现和应用就是其中很 重要的一个方面，这里在数据库服务器上建立一个规则库用来存储发现的规则 ，然后在编辑数据库的时候应用这些规则来指导用户，同时在用户对数据库进 行编辑以后刷新规则库，进一步指导用户进行数据库的编辑。 另外在自动生成的编辑界面中还支持不同类型的数据库连接，对于查询得 到的结果可以按照任意字段进行排序，查询界面支持查询条件的各种组合等。 28 5.2 展望 这个系统还有很多需要扩充的地方，从以下几个方面分别阐述： 数据挖掘算法的改进 怎么改进多维关联规则产生的算法的性能也是一个很值得研究的方向，因 为在数据量很大的情况下算法的性能显得非常重要，这方面的研究关系到整个 计算机行业的发展，算法是计算机科学的精髓。 文档数据库的处理 随着应用领域的不断拓展和多媒体技术广泛应用, 人们发现关系数据库的 许多限制和不足，因而数据库技术进入了“后关系数据库时代”。文档数据库 由此应运而生。 文档数据库区别于传统的其它数据库，它是用来管理文档。在传统的数据 库中,信息被分割成离散的数据段，而在文档数据库中，文档是处理信息的基本 单位。一文档可以很长、很复杂、可以无结构，与字处理文档类似。 本文研究的是基于关系数据库的编辑界面的自动生成，随着文档数据库的 出现我们可以进行基于文档数据库的编辑界面的自动生成方面的研究。 29 参考文献参考文献 1gregory piatetsky-shapiro, knowledge discovery in databases: 10 years after, sigkdd explorations, volume1, issue 2, pp. 59-61, 2000. 2r. j. torres. practitioners handbook for user interface design and development. pears on education,2002:3 -130. 3社孝平，罗宪，唐世渭.频繁项集挖掘中的两种哈希树构建方法.计算机科学 29(12). 4chad creighton, samir hanash. mining gene expression databases for association rules, bioinformatics, vol.19 no. 1, pp. 79-86, 2003. 5ronny kohavi, mehran sahami, kdd-99 panel report: data ming into vertical solutions, sigkdd explorations, volume1, issue 2, pp.55-57, 2000. 6ka yee yeung, david r. haynor, walter l. ruzzo. validating clustering for gene expression data, bioinformatics, vol.17 pp.309-318, 2001. 7andrea califano. advances in sequence analysis, current opinion in structural biology 2001, 11, pp. 330-333, 2001. 8崔立新，苑森森，赵春喜. 2000.约束性相联规则发现方法及算法.计算机学报. 9elizabeth pennisi. whats next for the genome centers. science 2001 february 16, 291, pp. 1204-1207, 2001. 10 eisen mb, spellman pt, brown po et al.cluster analysis and display of genome-wide expression patterns, proc. nat1 acad. sci. usa, 95(25), pp. 1486314868, 1998. 11 carol ezzell. hooking up biologists: consortia are forming to sort out a common cyberlanguage for life science, scientific american, nov. 2000. 12 周宇，叶庆卫.多表关联的关联规则提取 sql 实现.计算机应用研究，2002(8). 13 r. s .michalski,1 .brakto,and m .kubat.machine learning and datamining: methods and applications.new york: johnwiley&sons,1998:23-56. 14 m.j.zaki, srini