关联规则挖掘研究综述

网络财富 2009年4月 26 网络财富・ Intemet fortune・Management Vision 管理视野 消耗、最少废弃”为目标，其核心思想是 “变废物为财富”，提高应急军需保障资 源的利用效率。在具体的应急军需保障过 程中，可以通过发展节约型军需保障资源 和废弃资源的回收再利用，充分挖掘应急 军需资源的可持续潜力。比如在高寒地区 处突、反恐过程中，车辆的废弃配件可以 用来制作野战炊事单元，热食制作过程中 的热能收集还可以进行热水供应，方便战 士饮用或洗澡。 参考文献 [1]胡延川.武警部队处突反恐经济准备与保障[M].北京: 人民武警出版社,2006. [2]杨雪峰.循环经济运行机制研究[M].北京:商务印书 馆,2008. 关联规则挖掘研究综述 廖伟国1，张宏书2 (1.华南农业大学珠江学院，广东 从化 510980；2.黄冈职业技术学院，湖北 黄冈 438002) 【摘要】关联规则挖掘是数据挖掘的一个重要分支，它是指在大量数据中项集之间的有趣的关联或相关联系。本文介绍了当前关联规则挖掘的研究情况，分析了传统的 关联规则挖掘算法的不足，介绍了几种优化算法。最后，展望了关联规则挖掘的研究方向。 【关键词】关联规则；Apriori；FP-tree；数据挖掘 前言 (1)数据挖掘产生背景。 数据挖掘是一门汇集统计学、机器学 习、数据库、模式识别、知识获取、专家系 统、数据可视化和高性能计算等多种学科的 新兴交叉学科，这个领域融合了多个不同学 科领域的技术和成果，使其方法表现出多种 多样的形式。为自动和智能地把海量的数据 转化为有用的信息知识提供了有力的手段， 给数据和知识之间的鸿沟架设了方便之桥。 (2)课题研究的意义和目的。 目前，数据挖掘这项新技术已经得到 社会的认同，从普通的(比如超市业务数 据、信用卡使用 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 、电话呼叫清单等) 到不太普通的(比如天体图像、分子数据 库和医疗记录)，都离不开数据挖掘技术 的支持。 国外在数据挖掘领域研究的内容十分 广泛，从挖掘的知识种类看，也取得明显 的成果，研究重点从发现方法逐步转向系 统应用。而在国内相应的理论和算法研究 上还比较薄弱，相关的 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 资料和研究成 果比较少，能为关联规则提供一些理论和 概念上的信息，并把基于关联规则的数据 挖掘方法具体应用到实际中去。对本次研 究具有十分重要的意义。 1.关联规则 1.1 关联规则的基本概念 在设I={ }1 2, ,... mi i i 是二进制文字的集合， 其中的元素称为项(item)。记D为交易 (transaction)T的集合，这里交易T是项 的集合，并且T ⊆ I。对应每一个交易有 惟一的标识，如交易号，记作TID。设X 是一个I中项的集合，如果X⊆ T，那么称 交易T包含X。一个关联规则是形如X⇒ Y的蕴涵式，这里X⊂ I，Y⊂ I，并且X∩ Y=φ 。规则X⇒ Y在交易数据库D中的支持 度(support)是交易集中包含X和Y的交易 数与所有交易数之比，记为support(X⇒ Y)，即support(X⇒ Y)=|{T：X∪Y⊆ T，T ∈D}|/|D|。 规则 X ⇒ Y 在交易集中的置信度 (confidence)是指包含X和Y的交易数与包 含X的交易数之比，记为confidence( X ⇒Y)，即confidence(X⇒Y)=|{T：X∪Y⊆ T，T∈D}|/|{T：X⊆T，T∈D}|。 项的集合称为项集(itemset)。包含 k个项的项集称为k-项集。项集的出现频 率是包含项集的事务数，简称为项集的频 率、支持度或计数。如果项集满足最小支 持度(由用户或领域专家设定)，则称它为 频繁项集。给定一个交易集D，挖掘关联 规则问题就是产生支持度和置信度分别 大于最小支持度(minsupp)和最小置信度 (minconf)的关联规则。 关联规则挖掘主要是强规则挖掘，一 般由发现大项目集和生成强规则两部分组 成。具体步骤为： (1)找出存在于事物数据库中的所有大 项目集：先计算候选1-项集(k-项集是含有k 个项目的集合)，找出频繁1-项集；根据频 繁1-项集，确定候选2-项集，找出频繁2-项 集，……依次类推，直到不再有候选项集为 止。最后得到的项集就是所求的大项集。 (2)用大项集按生成规则和置信度产 生所需要的强规则。 1.2 关联规则种类 1.2.1 按变量的类别 基于规则中处理的变量的类别，关联 规则可以分为布尔型和数值型。布尔型关 联规则处理的值都是离散的、种类化的， 它显示了这些变量之间的关系。数值型关 联规则可以和多维关联或多层关联规则结 合起来，对数值型字段进行处理，将其进 行动态的分割，或者直接对原始的数据进 行处理。 1.2.2 按数据的抽象层次 基于规则中数据的抽象层次，可以分 为单层关联规则和多层关联规则。在单层 关联规则中，所有的变量都没有考虑到现 实的数据是具有多个不同的层次的。在多 层关联规则中，对数据的多层性进行了充 分的考虑。 1.2.3 按数据的维数 基于规则中涉及到的数据的维数，关 联规则可以分为单维和多维。单维关联规 则是处理单个属性中的一些关系；多维关 联规则是处理各个属性之间的某些关系。 1.3 经典的频集算法 Agrawal等于1993年首先提出了挖掘 顾客交易数据库中项集间的关联规则[1]， 并设计了一个基本算法，其核心是基于频 集理论的递推方法，即基于两阶段频集思 想的方法，将关联规则的设计分解为两个 子问题：①发现频集。这个子问题是最重 要的，开销最大，因此，各种算法主要致 力于提高发现频集的效率。②根据所获得 的频繁项集，产生强关联规则。根据定义 这些规则必须满足信任度阈值。由于步骤 ②中的操作极为简单，因此挖掘关联规则 的整个性能就由步骤①中的操作处理所决 定。该算法利用了如下两个基本性质： 性质1：任何频集的子集必定是频 集。 性质2：任何非频繁项集的超集必定 是非频繁项集。 算法的基本思想：首先找出所有的频 集，然后由频集产生强关联规则。 Apriori核心算法分析 Apriori算法是由Agrawal等于1994年 提出的，其基本思路是重复扫描数据库。 其核心程序简要描述如下： L1={large1－itemsets}； for(k=2；Lk - 1≠φ ；k++)do begin 2009年4月 网络财富 27 Management Vision・Intemet fortune ・网络财富管理视野 Ck=apriori_gen(Lk - 1)；∥新的候选集 for all transactions t∈D do begin Ct=subset (Ck，t)；∥事务t中包含 的候选集do for all candidates c∈Ct c．count++； end Lk={c∈Ck|c.count≥ minsup}end Answer=∪k Lk ； 算法执行过程可能产生大量的候选 集，以及可能需要重复扫描数据库，这是 Apriori算法的主要缺点。 1.4 频集算法的优化 1.4.1 杂凑算法 Park等在1995年提出了一个高效地 产生频集的基于杂凑(hash)的算法—— Dynamic Hashing and Pruning(DHP)算法[3]。 通过实验可以发现寻找频集主要的计算是在 生成频繁2-项集上。DHP利用一个杂凑表在 计算频繁1-项集时先大概计算出2-项集的支 持度，从而减少了候选2-项集的数量。 1.4.2 划分 Savasere等设计了一个基于划分的算 法，这个算法把数据库从逻辑上分成几个互 不相交的块，每次单独考虑一个分块并对它 生成所有的频集，然后把产生的频集合并， 用来生成所有可能的频集，最后计算这些项 集的支持度。Partition算法很大程度上减 小了I/O负载，但在处理高项集时存在一些 问题，而且它可能导致频集的错误处理。 1.4.3 采样 Sampling算法是由Toivenen提出的。 其基本思想是对给定数据的一个子集进行挖 掘，其核心是随机从数据集D中采集样本S， 然后搜索S中的频繁项集。样本S的大小以能 够在内存中完成频繁项集的挖掘为准。因 此，整个算法只需要扫描一遍数据库，由于 搜索的是S中的频繁项集而不是D中的，可能 漏掉一些全局的频繁项集。这是一种以效率 换取准确性的方法，在对于效率要求较高的 应用场合极具意义和重要性。 1.4.4 动态项集计数 Brin等人提出了动态项集计数算法。 该算法在添加一个新的候选集之前，先估计 一下是不是它的所有子集都是频繁的。该算 法把数据库分成若干个特定大小的区间，首 先计算候选-1项目集在第一个区间上的支持 度，根据这些支持度产生候选2-项目集，并 且2-项目集的支持度和1-项目集的支持度在 剩余的区间上继续计算。算法的停止条件是 没有新的候选集产生和所有候选集都在整个 数据库上计算了支持度。该算法通过区间划 分减少了遍历数据库的次数，但是它的性能 也是和数据分布密切相关的。 1.4.5 基于栈变换的算法 惠晓滨等提出了一个基于频繁模式栈 变换的高效关联规则算法，该算法采用一 种频繁模式栈的数据结构来储存所有的频 繁模式信息，所有的栈单元都具有偏序关 系，并分成构造算法和变换算法两个子算 法，算法效率提高，且在数据集的记录数 较大时有很好的线性性和伸缩性。 综上，基于Apriori的频集方法即使 进行一些优化，但是Apriori方法一些固 有的缺陷还是无法克服：①Apriori可能 产生大量的候选集；②生成候选项目时由 于模式匹配引起巨大时空开销。 1.5 FP-tree频集算法 J Han等提出了不产生候选频繁项集的 方法：FP-树频集算法。该算法采用分而治 之的策略，在经过第一遍扫描之后，把数 据库中的频集压缩进一棵频繁模式树(FP- tree)，同时依然保留其中的关联信息，随 后再将FP-tree分化成一些条件库每个库和 一个长度为1的频集相关，然后再对这些条 件库分别进行挖掘。FP-growth只需对数据 库进行两次扫描，而且避免了产生大量候选 集的问题。实验表明：FP-growth对不同长 度的规则具有很好的适应性，同时在效率上 较之Apriori算法有很大的提高。 1.6 基于约束的关联规则 在实际应用中，用户通常对关联规 则的子感兴趣，即用户只想看到某些项目 间的关联关系。为此Srikant等提出了基 于约束的关联规则(constrain - based association rules)，其中约束用布尔表 示，例如： (夹克衫∧皮鞋)∨((descendants(衣 服)∧ancestors(旅游鞋))就表示对规则的 约束，该规则中要么包含夹克衫和皮鞋，要 么包含衣服的后代(descendants)，但不包 含旅游鞋的前辈(ancestors)。该算法没有 采取先发现所有的规则再修剪不满足约束的 规则，而是直接把约束结合到算法中去，大 大提高了规则发现的效率。 1.6.1 变支持度关联规则 上述的关联规则挖掘算法均存在两大 前提，即：①数据库中各项目有相同的性质 和作用；②数据库中各项目的分布是均匀 的。然而，实际往往并非如此，当数据库中 项目分布不均匀而出现频率相差较大时，会 导致最低支持度设高设低都存在问题：设高 了，会漏掉很多有趣的规则；设低了，会引 到大量没有意义乃至虚假的关联规则，甚至 还会导致组合爆炸。所以，在挖掘关联规则 时，如果项目之间在出现频率和重要性上存 在很大差异时，不能为所有项目设定一个统 一的支持度阈值。对此，有两种不同的解决 方式：加权支持度和多支持度。 1.6.2 加权支持度关联规则挖掘 加权支持度是指必须考虑支持度和权 重两个因素，即加权关联规则挖掘算法在计 算支持度时，既要考虑规则中所有项目在数 据库中同时出现的频率，也要考虑所有项目 的加权值。由于，一方面不能忽略低权值项 目，另一方面在加权关联规则模型中，频繁 项目集不再具有向下封闭性，因此不能采用 Apriori算法及其优化算法。文献[4]从技术 角度给出了两个加权关联规则的挖掘算法： MINWAL(O)和MINWAL(W)算法。文献[5]中提出 了一种改进的加权关联规则算法，能有效地 考虑布尔型属性的重要性和规则中所含属性 的个数。 1.6.3 多支持度关联规则挖掘 多支持度是指对每个项目都设置一个 支持度阈值，即一种多最小支持度策略。 文献[5]中给出了一种多支持度关联规则挖 掘算法——MSapiori算法，该算法是通过 对Apriori算法进行一些修改而得到的。对 于一个项目集来说，其支持度阈值为该项 目集中的项目支持度阈值的最小值，频繁 项目集就失去了向下封闭性。因此，当用 MSapriori算法得到频繁项目集以后还需要 计算频繁项目集的所有子集的支持度，这又 将带来很大的时空开销。在文献[6]中提出了 多支持度关联规则挖掘算法的改进算法—— MIS-tree算法和CFP-growth算法。 2.总结 数据挖掘技术是数据库技术发展到一 定阶段后产生的新兴技术，它的目的是采用 有效的算法，从大量现有的数据集合中发现 并找出最初未知，但最终可理解的有用知 识，并用简明的方式显示出来。挖掘关联规 则是数据挖掘的一个重要方面。本文从关联 规则的基本概念出发，介绍了经典的频集挖 掘算法，并在此基础上对五种优化的频集算 法进行了分析，同时对FP-tree频集算法和 基于约束的关联规则进行了阐述。 参考文献 [1]Han J W,Kamber M.数据挖掘:概念与技术[M].北京:机 械工业出版社,2001. [2]Agrawal R,Imielinski T,Swami A.Mining Association Rules between Sets of Items in Large Databases[C].In: Proc of the ACM SIGMOD International conference on Management of Data,Washington DC,1993:207-216. [3]刘红岩,陈剑,陈国青.数据挖掘中的数据分类算法综 述[J].清华大学学报(自然科学版),2002,42(6):727-730. [4]Srikant R,Agrawal R. Mining generalized association rules[A]. Proceedings of the 21th International Conference on Very Large Databases[C].Zurich,Switzerland,Sept,1995:407-419. [5]Srikant R,AgrawalR. Mining quantitative association rules in large relational tables [A].Proc of the 1996 ACM SIGMOD Int’l Conf on Management Of Data[M]. Montreal,Quebee,Canada:ACM Press,1996:1-12. [6]周欣,沙朝锋,朱扬勇等.兴趣度——关联规则的另一 个阈值[J].计算机研究与发展,2000,37(5):627-633.