信息管理系统中基于关联规则的数据挖掘算法研究

数据挖掘 (Data Mining) 是近年来随着人工智能和数据库技术的发展而出现的一门新兴技术。它是从大量的数据中筛选出隐含的、可信的、新颖的、有效的信息的高级处理过程。数据挖掘也称为数据库知识发现 (Knowledge Discovery in Database) , 已经引起了国内外学术界和工商界广泛的关注。特别是最近几年, 一些基本概念和方法趋于清晰, 它的研究正朝着更深入的方向发展[1]。

数据挖掘是数据库研究、开发和应用最活跃的分支之一。而关联规则挖掘是数据挖掘中一种重要的研究方法, 它用于发现数据库或数据仓库中潜在的、对用户感兴趣的信息[2]。目前, 关联规则的挖掘方法已经被广泛应用, 但依然有着美好而广阔的发展前景。

基于数据挖掘的发展前景, 本文在分析、归类现有数据挖掘研究成果的基础上, 对数据挖掘技术、关联规则挖掘理论进行了研究, 针对现有的增量式更新算法无法发现新增数据中的新模式这一问题, 从敏感度和时间效率出发对增量式更新算法提出了改进的思想。结果说明, 改进算法能较好地发现新增数据中的新模式, 提高了挖掘的效率, 并具有较高的敏感性[3]。

1 数据挖掘与关联规则的基本概念

1.1 数据挖掘的基本概念

数据挖掘 (Data Mining) 旨在从大量的、不完全的、有噪声的、模糊的、随机的数据中, 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识。还有很多和这一术语相近似的术语, 如从数据库中发现知识 (KDD) 、数据分析、数据融合 (Data Fusion) 以及决策支持等。

许多人把数据挖掘看作就是数据库中的知识发现 (KDD) , 而另一些人只是把数据挖掘视为数据库中知识发现过程的一个特定的步骤。关于KDD与数据挖掘的关系, 有许多不同的看法。我们可以从这些不同的观点中了解数据挖掘的含义[3~5]。

1.1.1 KDD看成数据挖掘的一个特例既然数据挖掘系统可以在关系数据库、事务数据库、数据仓库、空间数据库、文本数据以及诸如Web等多种数据组织形式中挖掘知识, 那么数据库中的知识发现只是数据挖掘的一个方面。因此, 从这个意义说, 数据挖掘就是从数据库、数据仓库以及其它数据存储方式中挖掘出有用知识的过程。

1.1.2 数据挖掘是KDD过程的一个步骤

例如, 在“1996年知识发现国际会议”上, 许多学者建议对这两个名词加以区分。核心思想是:KDD是从数据库中发现知识的全部过程, 而数据挖掘则是此全部过程的一个特定的、关键步骤。因此KDD是一个更广义的范畴, 它包括数据清洗、数据集成、数据选择、数据转换、数据挖掘、模式生成及评估等一系列步骤。这样, 我们可以把KDD看作是一些基本功能构件的系统化协同工作系统, 而数据挖掘则是这个系统中的一个关键的部分。从这种狭义的观点上, 我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程[4]。

1.1.3 KDD与数据挖掘含义相同

有些人认为, KDD与数据挖掘只是叫法不一样, 它们的含义基本相同;也有人说, KDD在人工智能界更流行, 数据挖掘在数据库界使用更多。所以, 广义的观点, 数据挖掘是从大型数据集中, 挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。

从上面的描述中可以看出, 数据挖掘概念可以在不同的技术层面上来理解, 但是其核心仍然是从数据中挖掘知识。

1.2 关联规则的基本概念

关联规则的挖掘问题可以做如下的形式化描述[6]:

设, I={i1, i2, …, im}是项的集合。任务相关的数据D是数据库事务的集合, 其中每个事务T是项的集合, 使得T∈I。每一个事务有一个标识符, 称作TID。项的集合称为项目集 (itemset) 。设A是一个项目集, 事务T包含A当且仅当A∈T。如果项目集A中包含k个项, 则称为k一项目集。关联规则是形如A=>B的蕴涵式, 其中A⊂l, Bl, 并且A∩B=φ。规则A=>B在事务集D中⊂成立并且具有支持度, 其中, 是D中事务包含A∪B (即A和B二者) 的百分比, 它是概率P (A∪B) 。如果D中包含A的事务同时也包含B的事务的百分比是c, 则规则AB在事务集D中具有置信度。它是条件概率P (B|A) 。也就是

支持度和置信度两个阈值是描述关联规则的两个重要概念, 支持度反映关联规则在数据库中的重要性, 表示规则的频度;置信度衡量关联规则的可信程度, 表示规则的强度。同时满足最小支持度阈值和最小置信度阈值的规则称为强关联规则。为了方便, 将最小支持度阐值记为m i n_s u p, 最小置信度阈值记为mni_conf。最小支持度表示项目集在统计意义上的最低重要性, 最小置信度表示规则的最低可靠性[5]。

一个项目集的出现频度是指整个交易数据集D中包含该项目集的交易记录数, 也称为是该项目集的支持度。如果项目集的出现频度大于或等于min_sup与D中事务总数的乘积, 则称项目集满足最小支持度。如果一个项目集A满足最小支持度 (support (A) min_sup) , 则称它为频繁项目集, 频繁k-项目集的集合记为L*。反之, 如果一个项目集A不满足最小支持度, 则称为非频繁项目集。

候选项目集是潜在的频繁项目集的集合, 是频繁 (k-l) -项目集的超集。含有k项的候选项目集记为Ck, 由它构成频繁k-项目集Lk。

挖掘关联规则问题可以分解为以下两个问题: (1) 找出存在于事务数据库中的所有频繁项目集。这些频繁项目集是形成关联规则的基础。 (2) 利用频繁项目集生成关联规则。[8]根据定义, 这些规则必须满足最小支持度和最小置信度。对于每个频繁项目集A, 若B∈A, B, 小, 且

则生成关联规则B= (A-B) 。

子问题 (1) 是近年来关联规则挖掘算法研究的重点。比较流行的方法是基于Agrawal等人建立的项目集格空间理论。这个理论的核心是:频繁项目集的子集是频繁项目集;非频繁项目集的超集是非频繁项目集。由于子问题 (2) 中的相应操作极为简单, 因此挖掘关联规则的总体性能由问题 (1) 决定。

2 更新算法的分析

2.1 GBARM算法

2.1.1 GBARM算法的基本思想

己知定理:如果数据库中某条记录的长度为k, 那么这条记录就不可能包含任何项数大于k的频繁项集。对这条定理的证明是显而易见的。根据这条定理, 我们在计算Ck中每一个项集的支持度时, 就可以不考虑那些长度小于k的记录, 而只考虑那些长度等于或大于k的记录。这样一来, 就可以大大减少扫描的事务集的数量。

为此, 我们将数据库中的记录按照记录的长度进行分组, 长度相同的记录将被分到同一组中。这样, 我们就可以根据k的大小, 而有选择地对数据库的事务进行扫描。

另外, 在计算Ck中各候选项集的支持度计数时, 如果减小Ck的规模, 就可以提高算法的效率, 由于我们事先对事务集进行了分组, 因此, 在每一个分组中的事务扫描结束时, 我们就可以将Ck中的那些满足最小支持度计数要求的候选项集从Ck中除去, 在下面扫描其它的分组时, 不再统计它们的支持度计数, 这样一来, 缩小了Ck的规模, 从而达到了提高算法效率的目的。

这样, 当我们需要计算Ck的支持度时, 只需从长度为k的那个记录分组开始扫描, (这样就不需要扫描长度小于k的那些记录, 减少了扫描量) 当长度为k的那些记录扫描完了之后, 如果所有的候选项集都达到了最小支持度要求, 那么就不必要接着扫描后面的分组表中的记录了;如果有一部分候选项集达到了最小支持度要求, 那么就将这些候选项集加入到频繁项集Ck中, 同时将这些候选项集从Ck中除去, 并继续扫描后面的长度为k+1的那些记录, 直到所有的候选项集都达到了最小支持度要求或者己经到达了记录长度最长的那个分组表的末尾, 算法就终止。

2.1.2 算法描述

根据上面所提出的思想, 这里给出了此算法的主要步骤。为了描述的方便, 将算法分成三个部分。

第一部分:通过扫描一遍原始数据库D, 得出频繁1~项集的集合, 并且将原始数据库按照记录的长度划分为M个组。如果交易记录的长度为k, 则将此记录划分到分组表 (k) 中。其中, k的最小值为原始数据库中记录的最小长度, k的最大值为原始数据库中记录的最大长度。

第二部分:产生候选k一项集并利用Apriori性质对候选k一项集进行剪枝, 这个算法类似于Apriori算法。

第三部分:产生频繁k一项集, 这是此算法区别于其它算法的主要部分。

首先扫描分组表 (k) , 并计算每个候选项集的支持度计数, 将那些满足最小支持度计数的候选项集加入到Lk当中, 同时将它们从Ck中除去, 如果还没有到达记录长度最长的分组表的末尾, 并且Ck不为空, 那么将继续扫描分组表 (k+1) 去计算各个候选项集的支持度计数, 并将满足条件者加入到Lk当中, 同时从C, 中除去它们。直到已经到达记录长度最长的分组表的末尾或者Ck为空, 算法终止。整个GBARM算法如图1所示。

算法如下:

算法:GBARM

输入:事务数据库D;最小支持度阈值Minsup。

输出:D中的频繁项集的集合。

方法:

3 结语

从以上分析可以看出GBARM算法比Apriori算法更优越, 主要体现在:

首先, 在数据库的压缩处理上GBARM算法对原始数据库按照记录的长度进行了分组。因此, 在计算Ck中各项集的支持度计数时, 可以只从长度为k的记录分组开始, 如果所有的项集都满足了最小支持度计数要求, 就可以不必要继续扫描后面的分组表。这样在一定程度上缩小了搜索空间, 提高了算法的效率。

其次, 在Ck的规模问题上。当一个记录分组扫描完毕时, 将已经达到最小支持度计数要求的项集从Ck中除去, 而只需再继续统计Ck中其它项集的支持度计数, 这样缩小了Ck的规模, 也提高了算法的效率, 当数据量非常大的时候, 这种效果将会非常明显, 而用于数据挖掘的事务数据库往往是非常大的, 相信该算法具有一定的理论与实用价值。

摘要：数据挖掘技术己经引起了信息产业界的广泛关注。关联规则是其中一个主要的研究方向, 有着广泛的应用价值。对数据挖掘中的关联规则挖掘算法进行了研究和探讨, 包括数据挖掘的概念、数据挖掘的理论基础、数据挖掘的主要问题和数据挖掘的分类等。Apriori算法是发现频繁项目集的经典算法, 但是该算法需反复扫描数据库, 因此效率较低。在分析分析总结了关联规则中经典的Apriori算法及其改进算法的基础上, 提出了一种挖掘算法的改进思想, 并通过一个实际例子对改进算法和原算法做了分析和比较, 以及对关联规则进行了展望。

关键词：信息管理系统,数据挖掘,关联规则,算法改进

参考文献

[1] 金胜男.基于多层关联规则的概念分层知识库中知识发现的研究[D].天津大学, 2006.

[2] David Hand, Heikki Mannila, Padhraic Smyth.数据挖掘原理[M].北京:机械工业出版社, 2004:3～5.

[3] M.Chen et al.Data mining:An over-view from a database perspective. IEEE Trans.on Knowledge and Data Engineering, 2006, Vo1.8

[4] R.Agrawal et al.Database mining: A performance perspective.IEEE Trans-actions on knowledge and Data Engineering, 2003, Vo1.5.

[5] U.Fayyad et al.Knowledge discovery and data mining towards a unifying framework.In KDD'96 Proc.2nd Int.Conf.on Knowledge Discovery&Data Mining.AAAI Press, 2006.

[6] R.Agrawal et al. Fast algorithms for mining association rules in large database.In Proc.20th Int.Conf.Very Large Databases, 1994:478～499.

[7] D.W Cheng.J.Han.V T.Ng, et al.Maintenance of discovered association rules in large database.An incremental updating technique[C].The 12th Intd conf on Data Engineering, New Orleans.Louisiana, 1996.

[8] 罗可, 贺才望.基于Apriori算法改进的关联规则提取算法[J].计算机与数字工程, 2006.

[9] 崔立新, 等.约束性关联规则发现方法及算法[J].计算机学报, 2000.

[10] 欧阳为民, 蔡庆生.在数据库中发现具有时态约束的关联规则[J].软件学报, 1999.

[11] 周欣, 沙朝锋, 朱扬勇, 等.兴趣度——关联规则的又一个阀值[J].计算机研究与发展, 2000.

[12] 朱绍文, 王泉德, 等.关联规则挖掘技术及发展动向[J].计算机工程, 2000.