关联规则数据挖掘算法浅析.doc

关联规则数据挖掘算法浅析2009年08月24日 星期一 03:23文章编号：（）190206-03 收稿日期：摘 要：简要介绍了关联规则的概念及其基本思想，重点分析和讨论了两个挖掘关联规则的经典算法，即算法和分段算法。关键词：关联规则；数据挖掘；频繁项集中图分类号：TP274 文献标识码：随着现代科学技术和数据库技术的迅速发展，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。为此，人们需要有新的、更为有效的手段对各种信息资源进行挖掘以发挥其应用潜能。数据挖掘正是在这样的应用需求背景下产生并迅速发展起来的一门技术。所谓数据挖掘（ ，简称）是从大量数据中鉴别出有效模式（）的非平凡过程。该模式是新的，可能有用的和最终可理解的，又可称为数据采掘。的定义还有一些不同的表达形式，但其本质都是一样的，即从数据库中提出隐含的、高水平的模式，其目的是为数据库理解与应用提供自动化、智能化的手段。关联规则是数据挖掘的一个重要课题，目前已受到越来越多研究者的关注。 关联规则及其基本思想关联规则是数据挖掘过程中所能挖掘的一类重要的模式或知识，可以用来描述事物之间在特定条件下存在的某种强度的联系。例如，在购买铁锤的顾客当中，有的人同时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些规则更好地进行规划，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。关联规则的基本思想：一是找到所有支持度大于最小支持度的频繁项集，即频集。二是使用第一步找到的频集产生期望的规则。其核心方法是基于频集理论的递推方法。 挖掘关联规则的基本算法挖掘关联规则，就是在大型数据库中发现所有可能有用的或者用户感兴趣的强关联规则的过程。按照它的基本思想，挖掘关联规则一般可以分为以下两个步骤。（）求出支持度项集的集合（ ），即找出目标数据库中包含的所有频度项集。（）使用各频度项集生成相应的强关联规则。不难看出，在上述两步中，第二步的工作是比较简单直接的。具体来说，若已知所有频度项集的集合为，为中的任一频度项集，设项集真包含于，测试（）是否大于设定的最小置信度门限，若是，则规则是强关联规则。按此方法即能将中所能构造的所有强关联规则找出来。因此，挖掘关联规则算法的主要工作应集中在第一步，即设法高效地发现目标数据库中包含的所有频度项集。为了测试某些特定项集是否是频度项集，不可避免地需要扫描整个数据库。如果目标数据库很大，应设法尽可能减少扫描数据库的次数。考虑一种极端的情况：只需扫描数据库一次，但要检测的所有子集（若中包含个项，则共有个子集）。显然，这种指数级数数据检测方法是不可行的，除非的值很小。支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。支持度和置信度均高的关联规则才是有用的关联规则。 挖掘关联规则的经典算法 算法算法基于这样的一个原则：如果某一项不是频度集，那么它的所有超集也都不可能是频度集。反过来说，就是任一频度集的所有子集一定都是频度集。算法采用逐维扩展（ ）的方法，从求维频度集的集合开始，依次生成维频度集的集合、维频度集的集合，直到所有维的频度项集都生成为止。具体算法如下：输入：，的值，目标数据库，的大小。输出：上的所有频度项集。 算法流程： （） /算法中的表示维的所有频度项集组成的集合 / 表示维的所有候选项集组成的集合 （；（）；） （）；/利用（）生成 （K，）；/找出中包含于的所有项集 ； / 算法首先计算单元素项集的支持度，生成所有维频度项集构成的集合，然后，利用构造维候选项集的集合，再去扫描数据库，并根据设定的最小支持度门限值筛选出维频度集的集合，之后，按照类似的方法，在维频度集的集合基础上构造维候选项集的聚合，再去扫描数据库，生成维频度集的集合，直到再也构造不出任何候选项集为止。这种生成的所有维的频度项集即是所求的最终结果。算法中根据已求出的维频度集构造维候选项集的原则是下面的等式：k且的任一维子集都包含于集合k。在实际构造候选项集的时候（算法中的（），可使用下述方法：先求出kkk，k，显然，k包含k。然后，在k，的基础上根据式中k的条件构造k。（k，）的功能是筛选出k中所有包含于当前记录的项集。该算法针对每一维度集都要扫描数据库一次。假如频度集的最大维数是，则算法需要扫描数据库或次。由此我们可看出，该算法的效率与目标数据库的数据特征密切相关。这种挖掘关联规则算法的特点，即都需要对整个数据库进行多次扫描，然而，当数据库的容量很大时，多次扫描数据库所需的磁盘/开销是非常惊人的。上述算法在数据库不太大时的效率还行，但在数据库比较大时却较难取得令人满意的挖掘效率。这种算法缺乏必要的人机交互，是将所有可能的关联规则全挖掘出来，然而，这里面有用的或用户感兴趣的规则也许只占很小部分，故冗余规则的挖掘降低了挖掘效率。这两个问题可通过下面讨论的改进算法（分段算法）来有效解决。 分段算法通过前面对基本算法的讨论，可以看到一般的挖掘关联规则的算法都需要对整个数据库进行多次扫描，对大型数据库来说，算法的/开销较大。因而，/开销问题常常成为挖掘算法效率提高的一个瓶颈。不过，若能有效地减少数据库的扫描次数，则能较好地解决该问题。在关联规则的挖掘中融入分段思想就是一个比较好的解决方法。下面详细讨论该方法。 关联规则挖掘中的分段思想采用分段（）的思想挖掘关联规则，只需扫描数据库两次。该思想是将原来很大的数据库分成若干小的、适宜于内存中处理的子数据库，然后按常规算法（如算法）挖掘出各个子数据库上局部支持度集（因为各分段足够小，挖掘过程中的所有操作都在内存中进行，故各分段只需读取一次），最后把各个子数据库上的挖掘结果归并，再次扫描数据库，筛选出最终的关联规则集。如下所示的算法即是该思想的体现。算法输入：目标数据库，的大小，分段数，最小支持度门限。算法输出：所有支持度集的集合。 ； / 的个分段； （） L（） ，L / / 包含于 / ； （） 该算法的执行大体分两个大的阶段：第一阶段（行），将大的目标数据库逻辑上分成个互不相交的分段，对每一分段进行局部挖掘（）的过程可采用前面介绍的任一挖掘关联规则的算法进行），然后将每个分段上挖掘的结果，即各个段上的支持度集的集合（）进行合并，生成一个全局候选项集的集合（）。第二步（行），再次扫描全局数据库，筛选出全局数据库上的支持度集的集合（）。由于分段算法只需扫描数据库两次，与前面讨论的几种挖掘关联规则的算法相比大大减少了磁盘的/的开销，其性能的优越是无可非议的。分段思想之所以能用于挖掘关联规则是基于这样一个论断：全局数据库的任一支持度集应至少出现一个局部数据库的支持度集的集合。 分段算法的性能分析为了更清楚地看到分段算法在处理大数据库上的优越性，下面用一组实验数据来说明分段算法与算法的性能比较。实验的硬件条件： 的P ， 内存；目标数据取自于数据表，表长 个元组，包含个属性。通过实验结果，可以发现，分段算法能够获得稳定的较佳性能。不过，我们还应该看到，在支持度门限较大时，还是算法的性能要好一些。 分段大小的选取由上面的讨论不难看出，分段算法的效率确实较高，但在具体实现时却存在一个难点，即如何选取合适的分段大小。一般来说，为了算法的效率最优，对每个分段的处理最好都在主存中进行。所有分段大小的选取就要基于这个原则，结合具体的实现环境，选择合适的分段大小，使数据闪入闪出的操作最少。如果目标数据库较小，只需将其作为一个单独的分段来处理即可；若目标数据库较大，可采用试探法（）来解决分段大小选取的问题，即首先根据实际系统的可用容量估算一个段的大小，然后再按照实际运行使闪入闪出的次数以及主存的利用率来动态调整分段的大小，直至获得一个最合适的分段大小。这样，以后各分段的大小即按此选取。使用这种方法，前面若干段上的挖掘也许并不能获得最佳效率，但后面按最佳分段大小选取的段却能获得较高的挖掘效率。 分段算法的局限及改进由前面的讨论我们可看到，使用分段算法挖掘关联规则可获得较好的性能。不过，这只是就某些情况而言，其性能的好坏其实是与目标数据库中数据分布的情况密切相关的。当目标数据库中的数据分布比较均匀时，上述算法确实能获得较好的性能，但当目标数据库中的数据分布比较凌乱时，上述算法的性能却要大打折扣。究其原因，是因为上述算法采用的是连续分段，当数据分布不规则时，各分段上挖掘出的结果集差异性会很大，从而造成太多冗余项集的检测，使算法性能下降。比如，目标数据库的某些属性在某个分段上出现的频率很高，由这些属性构成的项集很可能就是该分段上的支持度集。然而，这些属性在其他分段上出现的频率却很低，也就是说，由这些属性构成的项集在那些段上可能就是非支持度集，综合起来，这些项集在全局数据库上很可能也是非支持度集。那么，这些项集显然就是冗余项集了。当数据分布不均时，这些冗余项集产生的概率还是很大的。那么如何有效减少类似的冗余项集呢？一种较好的策略是随机采样分段，即每个段中的元组并非来自于目标数据库中的连续的元组，而是从目标数据库中随机采样而得。当然，所谓的“随机”只是相对的，必须保证满足条件：，且。这样，可以大大减少因数据分布不均带来的数据冗余增长，从而使分段算法的优越性能得以稳定发挥。 结论数据挖掘技术，由于其诱人的实用前景，引起了众多研究者的浓厚兴趣。目前，国外有关数据挖掘技术的研究正方兴未艾，而国内该领域的研究也正在崛起。本文对数据挖掘技术中的一个重要分子关联规则作了比较深入的研究，侧重于分析挖掘规则的算法。算法需多次扫描数据库，使得算法的效率在数据库比较大时受到很大的制约。不过，算法在目标数据库不是很大时仍不失为一个好的挖掘关联规则算法。分段算法在算法的基础上，先将目标数据库分而挖掘之，然后再根据各部分的挖掘结果整体校验筛选出最后的结果。它只需扫描目标数据库两次。该算法通