关联规则挖掘算法

胡霁芳+邵明月

摘 要 本文介绍了关联规则挖掘算法的基本原理，并按照挖掘中涉及到的变量数目、数据的抽象层次和处理变量的类型，依次对关联规则挖掘算法的研究进行综述，并对一些典型的算法进行分析和比较，最后展望了关联规则挖掘算法的研究方向。

关键词 数据挖掘 关联规则 算法

中图分类号：TP311 文献标识码：A

0引言

数据挖掘是从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物，是国际上数据库和信息决策系统最前沿的研究方向之一。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。关联规则是数据挖掘领域中一个非常重要的研究课题，广泛用于各个领域，既可以检验行业内长期形成的知识模式，也能够发现隐藏的新规律。有效地发现、理解、运用关联规则是完成数据挖掘任务的重要手段，因此对关联规则的研究具有重要的理论价值和现实意义。

1关联规则基本原理

关联规则挖掘问题就是在事务数据库D中找出具有用户给定的最小支持度minsup和最小置信度minconf的关联规则。关联规则挖掘问题可以分解为以下两个子问题。

（1）找出存在与事务数据库中所有强相集X的支持度support（X）不小于用户给定的最小支持度minsup，则X为强项集。

（2）利用强项集生成关联规则。对于每个强项集A，若B€H袮，B≠，且support（A）/support（B）minconf，则有关联规则。B€H！（AB）。

2关联规则算法概述及典型算法分析

R.Agrawal等提出了关联规则挖掘问题以后，一批有效的挖掘关联规则的算法在过去几年中得到了长足的发展。到目前为止，其主要研究方向有：基于规则中涉及到的数据维数的挖掘算法，基于规则中处理变量类别的挖掘算法，其他关联算法等。

2.1单维关联规则

基于约束的规则挖掘约束的内容可以是：（1）数据约束：用户可以指定对哪些数据进行挖掘，而不一定时全部的数据。（2）指定挖掘的维和层次：用户可以指定对数据哪些维以及这些维上的哪些层次进行挖掘。（3）规则约束：可以指定哪些类型的规则是所需要的，引入一个模板的概念，用户使用它来确定哪些规则令人感兴趣的：如果一条规则匹配一个包含的模板，则是令人感兴趣的，然而如果一条规则匹配一个限制的模板，则被认为是缺乏兴趣的。

2.2多维关联规则挖掘

它指关联规则涉及2个或2个以上变量，根据是否允许同一维重复出现，多维关联规则又可以分为维间关联规则和混合维关联规则。维间关联规则和混合维关联规则还要考虑不同的字段种类，即类别数据与数值数据。对于类别资料，一般关联规则算法都可以处理，而对数值资料，就需要将这些资料转化成类别资料才可以处理。

3总结

目前，数据库关联规则挖掘已经取得了令人瞩目的成绩，但对下列问题进行研究时具有挑战性的工作。

3.1开发更有效的挖掘算法

随着数据库的尺寸不断增大，不仅增大了挖掘算法的搜索空间，而且也增加了盲目发现的可能性。因此必须利用领域知识去提取与发现任务有关的数据，删除无用的数据，有效地降低问题的维数，设计出更加有效地挖掘算法。在这一方面，基于约束的关联规则挖掘具有广阔的前途。

3.2可视化挖掘

设计一个灵活方便的用户界面，允许用户与挖掘系统进行互换，并对所挖掘的结果进行很好的可视化表示，使非领域专家也能进行挖掘。

3.3各种非结构化数据的挖掘

目前大多数关联规则挖掘大多是基于关系数据库或事务数据库的算法，设计应用于其他类型数据库（如面向对象数据库、数据仓库、文本数据、图形图像数据、多媒体数据等）关联规则挖掘算法也将是十分有意义的工作。

3.4并行关联规则数据挖掘

随着数据挖掘中数据量的高速增加以及大规模并行计算在数据挖掘中的应用，由于挖掘系统本身的原因，并行数据挖掘过程更加趋向粗粒度的挖掘，无法实现任意程度的并行。目前在并行数据挖掘中尚有一些问题需要解决：数据量的不断增加，维数越来越高，数据定位问题，数据的不对称，动态负载平衡，多表数据库的数据分布和索引方案，增量的方法，并行的数据库管理系统和文件系统。

3.5制定更加合理的關联规则衡量评价标准

目前的关联规则衡量标准可能会发现一些冗余的、虚假的和非挖掘者关心的关联规则，因而有必要制定一些新的衡量标准，用来衡量关联规则挖掘算法的优劣，但这些标准的制定可能要具体问题具体分析。

3.6与其他系统的集成

这里的集成包括与其他挖掘方法的集成和与其他系统的集成。

3.7研究在网络环境下的关联规则挖掘技术

特别是在Internet上建立DM服务器，与数据库服务器配合，实现数据挖掘。

参考文献

[1] Agrawal R， Srkant R. Mining association rules between sets of items in large databases[A].ProcACM SIGMOD Int1 Conf Management of data [C]. Washington DC，May 1993.207-216.

[2] 尹阿东，高学东，武森等，基于数值属性的关联规则挖掘算法[J]. 微机发展，2003，（04）：67-70.

[3] 齐雁，李石君，薛海峰。对演变数据进行关联规则挖掘的新方法[J].计算机工程，2002（11）：126-128.

[4] 罗可，吴杰.关联规则衡量标准的研究[J]. 控制与决策，2003（08）：419-424.

[5] 杨建林，邓三鸿，苏新宁.关联规则兴趣度的衡量[J]. 情报学报，2003（08）：277-281.endprint