数据挖掘中关联规则挖掘算法比较研究

第 26卷 VO1．26 第5期 NO．5 计算机 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 Computer Engineering and Design 2005年 5月 M ay．2005 数据挖掘中关联规则挖掘算法比较研究 何小东 ， 刘卫国 (1．湖南经济管理干部学院计算机系，湖南长沙410004；2．中南大学信息科学与X--程学院，湖南 长沙410008) 摘 要： 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 数据挖掘中关联规则挖掘算法的研究现状，提出关联规则新的价值衡量方法和关联规则挖掘今后进一步 的研究方向。以核心Apriori算法为基点，运用文献查询和比较分析方法对典型的关联规则挖掘算法进行了综合研究： ①Apriori方法即使进行了优化，一些固有的缺陷仍然无法克服，还需进一步研究；②今后的研究方向将是提高处理极 大量数据和非结构化数据算法的效率、与OLAP相结合以及生成结果的可视化 。 关键词：数据挖掘；关联规则；算法；频集 中图法分类号：TP3l1．13 文献标识码：A 文章编号：l000—7024(2005)05—1265—04 Comparison of association rules mining methods in data mining HE Xiao—dong ． LIU Wei—guo (1．Department of Computer,Hunan College of Economic Management，Changsha 4 1 0004，China；2．College of Engineering and Information Science，Central South University,Changsha 4 1 0008，China) Abstract：By analyzing the research actuality ofin data mining，a new association rules value measuring methods an d the further research direction of association rules in the future is provided．Literature query and comparison analysis methods are applied in beating typical association rules mining methods for integrate research based on kernel Apriofi arithmetic．~Even if apriori algorithm is optimized， some connatural bug cannot be overcome，and the further research iS also needed in the future．②The future research direction to enhalice algorithm efficiency of dealing with the maximum data an d non—structure data and combine with OLAP as well as the inspection of growing results． Key words：data mining； association rules；algorithm ；frequent set 1 引 言 2 关联规则的基本概念 数据挖掘(DataMining，DM)是近年来数据库研究界最热 的研究方向，其中关联规则 (Association Rules)的挖掘是数据 挖掘的重要功能之 。 所谓关联规则挖掘是从大量的、有噪声的、模糊的、随机 的实际数据中，抽取隐含在其中的、人们事先不知道的、但又 是潜在有用的关联信息和知识的过程。自从Agrawal等“ 于 1993年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题以来，很多研究人员对关联规则的挖掘问题进行了研究， 从不同角度提出了数十种关联规则挖掘算法，主要有Apfiofi、 AIS、SETM、PARTITION、ML T2L1等数据挖掘算法，而其中以 Agrawal等人提出的Apriori算法“ 最为著名，其后的数据挖掘 算法大多建立在Apriori算法基础之上，或改进，或衍生变种。 如 Apriori—Tid算法和 Park等人提出的 DHP算法等。还有一 些独立于 Agrawal的频集方法的研究工作 ，以避免频集方法 的一些缺陷。文中对数据挖掘中一些典型的关联规则算法做 了比较分析与研究。 2．1 基本概念 设／--{il,i：，⋯，f )是二进制文字的集合，其中的元素称为项 (item)。记 D为交易(transaction)T的集合，这里交易 是项的 集合，并且Tc_l。对应每一个交易有惟一的标识，如交易号， 记作TID。设 是一个，中项的集合，如果 T，那么称交易 包含 一 个关联规则是形如X=Y的蕴涵式 ，这里XCI,YCI，并且 xn 。规则 y在交易数据库 D中的支持度(support)是交 易集中包含 和Y的交易数与所有交易数之比，记为support y)，即 support(X=Y)=l(T：XUy D)lliDl 规则 y在交易集中的可信度(confidence)是指包含 卿 】，的交易数与包含 的交易数之比，记为confidence(X= ，即 confidence(X=y)=l(T：XOYGT， D)l／l( D)l 给定一个交易集D，挖掘关联规则问题就是产生支持度和 可信度分别大于用户给定的最小支持度(min—supp)即阈值和最 收稿日期：2004．12—07。 作者简介：何小东 (1962一)，男，湖南郴州人，副教授，硕士，研究方向为计算机网络和数据库技术： 刘卫国 (1963．)，男，湖南祁阳人，教 授，研究方向为软件工程和网络信息系统。 一 l265— 维普资讯 http://www.cqvip.com 小可信度(min．conf)即阈值的关联规则。 2．2 关联规则的种类 关联规则可按不同的情况进行分类。 (1)基于规则中处理的变量的类别，关联规则可以分为布 尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示 了这些变量之间的关系；而数值型关联规则可以和多维关联 或多层关联规则结合起来，对数值型字段进行处理，将其进行 动态的分割，或者直接对原始的数据进行处理，当然数值型关 联规则中也可以包含种类变量。 例如：性别=“男”=>职业=“经理”，是布尔型关联规则；性 别．‘‘男”= (收入)=3000，涉及的收入是数值类型，所以是 一 个数值型关联规则。 (2)基于规则中数据的抽象层次，可以分为单层关联规则 和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的 数据是具有多个不同的层次的；而在多层的关联规则中，对数 据的多层己进行了充分的考虑。例如：HP台式机=>Canon打 印机，是一个细节数据上的单层关联规则：台式机=>Canon打 印机，是一个较高层次和细节层次之间的多层关联规则。 (3)基于规则中涉及到的数据的维数，关联规则可以分为 单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用 户购买的物品，而在多维的关联规则中，要处理的数据将会涉 及多个维。 换句话说，单维关联规则是处理单个属性中的一些关系， 多维关联规则是处理各个属性之间的某些关系。如啤酒=>尿 布，这条规则只涉及到用户购买的物品；性别=“男”=>职业= “经理”，这条规则就涉及到两个字段的信息，是两个维上的一 条关联规则。 3 关联规则挖掘的算法 3．1 经典频集方法 Agrawal等“ 于 1993年首先提出了挖掘顾客交易数据库 中项集间的关联规则问题，其核心方法是基于频集理论的递 推方法。以后许多研究人员对原有的算法进行优化，如引入 随机采样、并行的思想等，以提高算法挖掘规则的效率；提 出各种变体，如泛化的关联规则，对关联规则的应用进行推 广 。 3．1．1 核心算法 Agrawal等“ 在 1993年设计了一个基本算法，提出了挖掘 关联规则的一个重要方法，这是一个基于两阶段频集思想的 方法，将关联规则挖掘算法的设计分解为两个子问题： (1)找到所有支持度大于最小支持度的项集(Itemset)，这 些项集称为频集(Frequent Itemset)。 (2)使用第 l步找到的频集产生期望的规则。 这里的第2步相对简单一点。如给定了一个频集Y=I。 ⋯ ，七 2， ∈，，产生只包含集合( ，⋯， )中的项的所有规则 (最多k条)，其中每一条规则的右部只有一项，(即形如[y- ] 、 Vl fs 。一旦这些规则被生成，那么只有那些大于用户给 一 1266一 定的最小可信度的规则才被留下来。为了生成所有频集，使 用了递推的方法。其核心思想为： 首先产生频繁 l一项集厶，然后是频繁2一项集厶，直到有某 个r值使得厶为空，这时算法停止。这里在第k次循环中，过程 先产生候选k一项集的集合 ，G中的每一个项集是对两个只 有一个项不同的属于厶 。的频集做一个 一2)一连接来产生的。 G中的项集是用来产生频集的候选集，最后的频集厶必须是G 的一个子集。G中的每个元素需在交易数据库中进行验证来 决定其是否加入厶，这里的验证过程是算法性能的一个瓶颈。 这个方法要求多次扫描可能很大的交易数据库，这将增加很 大的I／O负载。 Agrawal等后来引入了修剪技术(Pruning)来减小候选集 C 的大小，这样，可以显著地改进生成所有频集算法的性能。 算法中引入的修剪策略基于这样一个性质：一个项集是频集 当且仅当它的所有子集都是频集。那么，如果G中某个候选 项集有一个(k-1)-子集不属于厶．．，则这个项集可以被修剪掉 不再被考虑，这个修剪过程可以降低计算所有的候选集的支 持度的代价。 3．1．2 频集算法的几种优化方法 虽然Apriori算法 自身已经进行了一定的优化，但是在实 际的应用中还是存在不足，于是人们相继提出了以下一些优 化的方法： (1)基于栈变换的算法：惠晓滨等“ 提出了一个基于频繁 模式栈变换的高效关联规则算法FPST，该算法采用一种频繁 模式栈的数据结构来储存所有的频繁模式信息，所有的栈单 元都具有偏序关系，并分成构造算法和变换算法两个子算法， 算法效率提高，且在数据集的 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 数较大时有很好的线性性 和伸缩性。 (2)基于划分的方法：Savasere等 设计了一个基于划分 (partition)的算法，这个算法先把数据库从逻辑上分成几个互 不相交的块，每次单独考虑一个分块并对它生成所有的频集， 然后把产生的频集合并，用来生成所有可能的频集，最后计算 这些项集的支持度。这里分块的大小选择要使得每个分块可 以被放入主存，每个阶段只需被扫描一次。而算法的正确性 是由每一个可能的频集至少在某一个分块中是频集保证的。 这个算法是可以高度并行的，可以把每一分块分别分配给某 一 个处理器生成频集 产生频集的每一个循环结束后，处理 器之间进行通信来产生全局的候选k一项集。 (3)减少冗余规则的算法：吴伟平等 提出了一种无冗余 快速关联规则发现算法，该算法基本原理与Apriori算法相似， 但采取了不同的计算候选项集支持度的方法。首先通过对数 据库的一次搜索得到高频 l一项集，然后使用一个链表得到其 他频繁项集。规则生成的方法也与Apriori算法不同。该算法 首先以最大频繁项集中的某一项 目为前件生成规则，再讨论 前件中包含该项 目的子规则。所以，该算法所需的I／O次数较 少且内存开销适中，消除了简单和严格冗余规则，减少了发现 的规则数量，同时提高了规则发现的速度。 (4)基于采样的方法：基于前一遍扫描得到的信息，对此 仔细地作组合分析，可以得到一个改进的算法，Mannila等” 先 考虑了这一点，他们认为采样是发现规则的一个有效途径。随 维普资讯 http://www.cqvip.com 后又由Toivonen 进一步发展了这个思想，先使用从数据库中 抽取出来的采样得到一些在整个数据库中可能成立的规则， 然后对数据库的剩余部分验证这个结果。Toivonen的算法相 当简单并显著地减少了I／O代价，但此法有一个很大的缺点就 是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分 布在同一页面上的数据时常是高度相关的，可能不能表示整 个数据库中模式的分布，由此，导致采样 5％的交易数据所花 费的代价可能同扫描一遍数据库相近。 Brin等 提出的算法使用比传统算法少的扫描遍数来发 现频集，同时比基于采样的方法使用更少的候选集，这些都改 进了算法在低层的效率。具体的作法是，在计算k一项集时，一 旦认为某个(抖1)一项集可能是频集时，就并行地计算这个 ( 1)一项集的支持度，算法需要的总的扫描次数通常少于最 大的频集的项数。 (5)基于Hash的方法。基于哈希(Hash)的算法由Park等 提出来。通过实验他们发现寻找频集主要的计算是在生成频 繁2．项集厶上，于是 Park等人利用这个性质引入哈希技术来 改进产生频繁 2-项集的方法 3．2 其它频集挖掘方法 以上都是基于 Apriori算法的频集方法。即使进行了优 化，但Apriori方法一些固有的缺陷仍然无法克服。 (1)可能产生大量的候选集：当长度为 l的频集有 10000 个的时候，长度为2的候选集个数将会超过 10M。还有就是 如果要生成一个很长的规则的时候，要产生的中间元素也是 巨大量的。 (2)无法对稀有信息进行分析：由于频集使用了参数min— sup，所以就无法对小于minsup的事件进行分析；而如果将min- sup设成一个很低的值，那么，算法的效率就成了一个很难处 理的问题。 为此，国内外研究人员经过大量、深入的研究，最近又提 出了一些新的算法。 文献[1l】提出了解决第 1个问题的一种采用FP—growth的 方法，即实施分而治之的策略：在经过了第 1次的扫描之后， 把数据库中的频集压缩进一棵频繁模式树 (FP—tree)，同时依 然保留其中的关联信息。随后我们再将FP．tree分化成一些条 件库，每个库和一个长度为 l的频集相关，然后再对这些条件 库分别进行挖掘。当原始数据量很大的时候，也可以结合划 分的方法，使得一个 FP—tree可以放入主存中。实验表明，FP— growth对不同长度的规则都有很好的适应性，并在效率上较 之Apriori算法有很大提高。 在Apriori算法中，起决定作用的是支持度，但如果把可 信度放在第 l位，可能挖掘一些具有非常高可信度的规则。文 献[12]中介绍了解决第2个问题的一种方法，即为数据库中每 个项 目设定一个最小支持度 MIS。 使用最小项 目支持使我们可以对只包含频繁项目的规则 设置较高的最小支持度，对包含稀有项目的规则设置较低的 最小支持度。确定个项目支持度的方法是依据项目在数据中 的实际频率来分配项目的MIS值。该种多支持度挖掘算法效 率较高。 从前面的讨论我们知道，传统的Apriofi算法具有重复扫 描数据库的弊端，文献[13】中则提出了一种新的算法：构造元 向量，通过向量的逻辑与运算，寻找频繁元向量集，继而根据 有关阈值挑选有趣有效的强关联规则输出。使用该算法，各 相关元向量在数据库扫描时一次性全部构造，并驻留内存，保 证了后续挖掘工作不再重复扫描整个数据库，挖掘效率高。 FP．树算法虽然也只需要扫描数据库一次，但它需要建FP-树 和项头表，挖掘过程需对树进行遍历，其递归算法设计复杂， 运行效率低。 该向量算法以一致的办法处理量化属性、分类属性和谓 词，在元向量确定后，可以统一的算法处理任何层任何维的关 联规则问题。 马廷淮等“ 提出了一种带结论域的关联规则的挖掘算法， 这种算法以rough set为基础，将粗糙集方法与关联规则挖掘 方法相结合，通过设定“结论域”，快速地实现关联挖掘，得出 各种条件属性极其组合对结论属性的影响，使关联规则挖掘 的时间和空间复杂度大为减少，提高了数据挖掘的效率和针 对性。而李乃乾等 则提出了一种新的普遍化关联规则挖掘 算法GARL，该算法基于支持格，采用完全不同于算法 Cumu． 1ate的算法结构，使得整个挖掘过程对数据库扫描减少到不超 过两遍，并允许用户以交互方式对最小支持率进行调整，能连 续处理事务序列，比较适合于网上在线进行数据挖掘。 3I3 多层关联规则的挖掘算法 随着数据仓库和 OLAP技术的研究发展，大量的数据将 经过整合、预处理，而存入数据仓库之中。目前，大多数的数 据仓库的应用都是进行统计、建立多维以及OLAP的分析工 作。 基于OLAP的挖掘就可以提供在不同数据集、不同的细 节上的挖掘，可以进行切片、切块、展开、过滤等各种对规则的 操作，然后再加上一些可视化的工具，就能大大地提高数据挖 掘的能力和灵活性。 多层关联规则：对于很多的应用来说，由于数据分布的分 散性，很难在数据最细节的层次上发现一些强关联规则。当 我们引入概念层次后，就可以在较高的层次上进行挖掘。虽 然较高层次上得出的规则对于一个用户来说可能更普通的信 息，但对于另一个用户却未必如此。所以，DM(数据挖掘)应 该提供一种在多个层次上进行挖掘的功能。多层关联规则可 分为同层关联规则和层间关联规则。 同层关联规则可采用以下两种支持度策略： (1)统一的最小支持度：对于不同的层次，都使用同一个 最小支持度，这样对于用户和算法实现来说都比较容易，但是 弊端也是显然的。 (2)递减的最小支持度：每个层次都有不同的最小支持度， 较低层次的最小支持度相对较小，同时还可以利用上层挖掘 得到的信息进行一些过滤的工作。 层间关联规则考虑最小支持度的时候，应该根据较低层 次的最小支持度来定。 关于多层关联规则挖掘的研究近几年非常热烈 除了 ML — T2Ll等算法外，如任家东等“ 就提出了一种分布式多层 关联规则挖掘的算法。该算法在每一层使用不同的支持度。 由于分布式系统自身的特点，现有的多层关联规则挖掘算法 · — — 1267·—— 维普资讯 http://www.cqvip.com 不能直接应用于分布式系统之中。 该DMARM算法使用轮询方法处理分布式系统中各个节 点间的通信问题，在每个节点上利用集合“或”和“与”运算，在 求候选频繁模式的同时求出了模式的支持度，减少了数据库 的扫描次数。 4 衡量关联规则价值的方法 当我们用数据挖掘的算法得出了一些结果之后，数据挖 掘系统如何知道哪些规则对于用户来说是有用的?哪些规则 是有价值的呢?需考虑系统和用户两个方面。 4．1 系统方面 很多的算法都使用“支持度．可信度”的框架，这样的结构 有时会产生一些错误的结果。有时某条规则的支持度和可信 度都比另一条蕴涵正向关联的规则低，但是它可能更精确。如 果我们把支持度和可信度设得足够低，那么我们将得到两条 矛盾的规则。另一方面，如果我们把那些参数设得足够高，我 们只能得到不精确的规则。 总之，没有一对支持度和可信度的组合可以产生完全正 确的关联。 人们经过研究发现引入兴趣度，可用来修剪无趣的规则。 一 股情况下，一条规则的兴趣度是在基于统计独立性假设下 真正的强度与期望的强度之比。然而在许多应用中已发现， 只要人们仍把支持度作为最初的项集产生的主要决定因素。 那么，要么把支持度设得足够低，以使得不丢失任何有意义的 规则，或者冒丢失一些重要规则的风险；对前一种情形计算效 率可能不高，而后一种情形则有可能丢失从用户观点来看是 有意义的规则。 4．2 用户方面 上面的讨论只是基于系统方面的考虑，而一个规则的有 用与否应最终取决于用户的感觉。只有用户可以决定规则的 有效性和可行性。实际中我们应将用户的需求和系统相结合。 可以采用一种基于约束(consraint．based)的挖掘。具体约 束的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 可以有： (I)数据约束：用户可以指定对哪些数据进行挖掘，而不一 定是全部的数据。 (2)指定挖掘的维和层次：用户可以指定对数据哪些维以 及这些维上的哪些层次进行挖掘。 (3)规则约束：可以指定哪些类型的规则是我们所需要的。 引入一个模板(template)的概念，用户使用它来确定哪些规则 是令人感兴趣的，而哪些则不然：如果一条规则匹配一个包含 的模板，则是令人感兴趣的，然而如果一条规则匹配一个限制 的模板，则被认为是缺乏兴趣的。 其中有些条件可以和算法紧密结合，提高效率，同时又使 挖掘的目的更加明确化。 5 结束语 目前，数据挖掘中产生关联规则的方法以及它的应用已 渐渐成熟，一些研究成果已被集成在一些系统中，如IBM的 Quest项目、SimonFarse大学的DBMiner等。关联规则挖掘算 法可归纳为两大类，一是产生频繁项集候选项的算法，二是不 一 l268一 产生候选项的算法。综上所述在今后几年内，就关联规则的 挖掘可以在下面一些问题上做进一步的研究：①将 OLAP和 关联规则相结合的问题：②在处理极大量的数据时，如何提高 算法效率的问题；③生成结果的可视化及对非结构化数据的 挖掘。 参考文献： [1] Agrawal R，Imielinski L Swami A．Mining association roles bet· ween sets of items in large databases[C]．Proceedings of the ACM SIGMOD conference on management ofdata，l993 207- 2l6． [2] Han J。Pei J。Yin Mining frequent pattems without candidate generation[C]．Proc 2000 ACM·SIGMOD Int Conf Manage- ment of Data(SIGMOD’oo)，Dalas，TX，2000． 【3】 HAN Jia-wei，Micheline Kamber．数据挖掘概念与技术【M]．北 京：机械工业出版社，2001． 惠晓滨，张凤呜，虞健飞 一种基于栈变换的高效关联规则算 法[J]．计算机研究与发展，2003，40(2)：330．335 [5] Savasere A，Omiecinski E，Navathe S．An efficient algorithm for mining association roles in large databases[C]．Proceedings of the 2 l st Intemational Conference on Very large Database， l995． [6] 吴伟平，林馥，贺贵明．一种无冗余的快速关联规则发现算法 [J]．计算机工程，2003，29(8)：90．9 1． [7] Mannila H，Toivonen H，Verkamo A．Efficient algorithm for dis- covering association roles[C]．AAAI Workshop on Knowledge Discovery in Databases，1994．I8I-192． [8] Toivonen H．Sampling large databases for association roles[C]． Bombay，India：Proceedings of the 22nd Intemational Confe卜 ence on Very Large Database，l 996． [9] Brin S，Motwani R，Silverstein C．Beyond market baskets：Gen． erlizing association roles to correlations[C]．Proceedings of the ACM SIGM0D．1996．255-276． [10]Park J S，ChenM S，Yu P S．An effective hash-based algorithm for mining association roles[C]．San Jose，CA：Proceedings of ACM SIGMOD Intemational Conference on Management of Data，1995．175-186． [11]Ng R，Lakshm anan L V S，Han J．Exploratory mining and pm- ning optimizations of constrained associations roles[C]，Seattle， Washington：Proceedings ofACM SIGMOD Intemational Con- ference on M anagement ofData，1998．13-24． [12]李铭．关联规则的多支持度挖掘在销售数据中的应用[J]_计算 机工程，2003，29(8)：92．93． [13]李哲，杨兆中，庞炳章．大型数据库中关联规则的向量法挖掘 [J]．计算机工程，2003，29(8)：97．99． [14]马廷淮，张海盛，曾振柄．带结论域的关联规则的挖掘[J]．计算 机工程，2003，29(5)：l6一l7． [15]李乃乾，沈钧毅，田絮资．一种新的普遍化关联规则挖掘算法 [J]．计算机工程，2003，29(7)：4—6 [16]任家东，任东英，高伟．分布式多层关联规则挖掘[J】．计算机工 程．2003，29(5)：96．98． 维普资讯 http://www.cqvip.com