数据库关联规则挖掘算法研究

刘晓慧

摘要：该文介绍了数据挖掘、关联规则相关概念，分析了经典的挖掘布尔关联规则频繁项集的算法-Apriori算法，阐述了关联规则的生成过程，并通过实例进行验证。针对Apriori算法的缺陷进行了分析并列举了几种算法优化方法。

关键词：数据挖掘；关联规则；Apriori算法；阈值

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3721-03

Abstract： This article describes the conception of data mining and association rules， Analyzes apriori algorithm，Its the classic algorithm in frequent itemsets mining base on boolean association rules， Describes the generation process of association rules and verified by examples. Analysis of the defects of apriori algorithm and several improved algorithms.

Key words： data mining； association rules； Apriori algorithm； threshold

1 数据挖掘

随着计算机、网络和信息技术的发展，采集和保存数据的能力也大大提高，信息大量涌现，如何从海量信息中找出所需的、有用的知识，成为了一个重要研究课题。数据挖掘一般是指从大量的实际数据中，通过算法搜索提取隐藏于其中的、有用的信息和知识的过程，同时通过分析大量数据来揭示有意义的新的关系和趋势。数据挖掘融合了人工智能、机器学习、模式识别、统计学、数据库、可视化技术等多个领域的理论和技术，是数据库研究中的一个很重要且有应用价值的领域。

2 关联规则

数据关联是数据库中存在的可被发现的知识，若多个变量的取值存在某种规律性，就称为关联。关联分析在数据挖掘中用于揭示数据项集之间的相互关系，生成关联规则，形如[X?Y]的蕴含式。关联规则挖掘要先从数据集合中找出所有的频繁项目组（Frequent Itemsets），然后从频繁项目组中产生强关联规则（Association Rules）。具体描述如下：

假设[I={i1，i2，…，im}]是一个项目集合。给定一个事务数据库[D={t1，t2，…，tn}]，其中每个事务[ti（i=1，2，…，n）]具有唯一标识TID，且都对应I上的一个非空子集。设[X?I]，项目集[X]在数据库D上的支持度（support）指包含[X]的事务在D中的百分比，即：

[support（X）={t∈D|X∈I}D] （1）

对于项目集I和事务数据库D，I中所有满足用户指定的最小支持度min_sup的项目集，称为频繁项目集。在频繁项目集中选出所有不被其他元素包含的项目集称为最大频繁项目集。

如果有[X?I，Y?I，X?Y=φ]，则一个定义在I和D上的关联规则形如“[X?Y]”，其置信度（Confidence）指包含[X]和[Y]的事务数与包含[X]的事务数的比值，即：

[Confidence（X?Y）=support（X?Y）support（X）] （2）

关联规则挖掘就是用户根据需要设定最小支持度和最小置信度min_conf阈值，搜索满足这两个阈值的关联规则的过程，满足条件的关联规则称为强关联规则。

根据规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的是离散的、种类化的值，揭示这些变量之间的关系；数值型关联规则对数值型字段进行处理，可以将其进行动态分割，或直接对原始数据进行处理。

3 Apriori算法

3.1 算法描述

关联规则由Agrawal等人于1993年首次提出之后，研究人员对数据库关联规则挖掘方法进行了大量研究，提出了多种算法，如Apriori算法、基于划分的算法、FP-树频集算法等，其中最有影响的是Apriori算法。

Apriori算法是挖掘布尔关联规则频繁项集的经典算法，该算法首先使用逐层搜索的迭代法，根据最小支持度阈值，找出所有的频繁项集。然后由频繁项集产生强关联规则：给出最小置信度阈值，针对每个频繁项集，生成其所有非空子集，计算每个非空子集的置信度，置信度满足最小置信度阈值，则相应关联规则成立。算法核心思想描述如下：

1） [L1=find_frequent_1_itemsets（D）；]

2） [for（k=2；Lk-1≠φ；k++）{]

3） [Ck=apriori_gen（Lk-1，min_sup）；]

4） [foreachtransactiont∈D{//scanDforcounts]

5） [Ct=subset（Ck，t）；//getthesubsetsoftthatarecandidates]

6） [foreachcandidatec∈Ct]

7） [c.count++；]

8） [}]

9） [Lk={c∈Ck|c.count≥min_sup}]

10）[}]

11）[returnL=UkLk；]

利用该算法挖掘布尔关联规则频繁项集时，首先找出频繁1-项集[L1]，然后用[L1]找到频繁2-项集[L2]，依此类推，直到找不到频繁k-项集[Lk]为止。算法中找每个频繁项集时需要扫描一次数据库。endprint

该算法由连接和剪枝两个步骤组成，为了找到[Lk]，通过[Lk-1]与自身连接产生候选k-项集的集合，该候选项集的集合记作[Ck]； [Ck]是[Lk]的超集，它的成员不一定都是频繁项集，但所有频繁k-项集都在[Ck]中，通过计算每个k-项集的支持度来得到[Lk]。

3.2 算法举例

例：以下关系（credit_bill）是模拟银行对某单位年度个人信用卡账单的统计数据：

关系中“Sex”、“Wedded” 和“Title”字段是布尔型，“Age”、“Income”和“Bill”字段是数值型，使用Apriori算法对关系中布尔型数据集进行关联规则挖掘，先对相应属性值时行离散化处理，将“Sex”属性的两种取值“男”和“女”离散化为属性s1和s2，“Wedded”属性取值“已婚”和“未婚”离散化为属性w1和w2，“Title”属性取值“高级”、“中级”和“初级”离散化为属性t1、t2和t3。设最小支持度和最小置信度阈值均为50%，则挖掘过程如图1所示。

通过上述搜索过程得到频繁项集[L2]，其中支持度由公式（1）计算得出，由频繁项集生成的关联规则及由公式（2）计算得出的规则置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

规则置信度大于最小置信度阈值，说明所得规则有效。此规则说明关系所列数据中信用卡持有者男性过半数，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均为70%。

3.3 算法优化

Apriori算法虽然经典，但有两个性能上的瓶颈：在搜索k-频繁项集时，侯选集[Ck]中每个元素都必须通过扫描数据库来确认其是否放入频繁项集中，因此需要对数据库进行k次扫描，数据库中数据量越大，搜索效率越低；由[Lk-1]生成k-侯选项集[Ck]时，[Ck]中元素个数是指数增长的，因此数据量越大，生成的侯选集也就越庞大，既耗费时间，也需要大量的存储空间。

针对Apriori算法中的缺陷，不同学者提出了多种不同的改进方法，如Park等人提出的引入散列技术改进产生频繁2-项集的方法，或高效产生频繁项目集的基于杂凑的算法；Agrawal等人提出的压缩进一步迭代扫描的事务数的方法；Savasere等人提出的基于划分的方法；Mannila等人提出的通过对数据库采样发现规则的方法；Brin等人提出的动态项集计数方法等。这些方法虽然对Apriori算法进行了优化，但没能克服Apriori算法中的固有缺陷：可以产生庞大的侯选集；最小支持度阈值设定值较低时，算法执行效率会降低，而阈值设定较高时，会影响规则产生。

针对上述算法缺陷中的前一种情况，[4]提出采用FP-growth方法，第一次扫描数据库后，将得到的频繁项集放进一棵频繁模式树FP-tree，再将这棵树分解成多个条件库，对这些条件库分别进行挖掘，该方法能适应不同长度的规则，而且执行效率也大大提高。

4 结束语

对于数据库关联规则挖掘方法，该文只针对布尔型值进行了介绍，分析了经典的Apriori算法挖掘布尔关联规则频繁项集的过程及关联规则的得出，并针对Apriori算法的缺陷进行了分析，对多种优化算法进行了阐述。对于数据库来说，数值型字段也是其主要组成部分，而关联规则挖掘也同样可以针对数据值字段，并和多层关联规则结合，或同模糊理论相联系，分析并找出数据间联系，具有重要现实意义。

参考文献：

[1] 杜玉兰.基于模糊理论的关联规则挖掘算法研究[D].保定：华北电力大学，2008.

[2] 梁循. 数据挖掘算法与应用[M].北京：北京大学出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint

该算法由连接和剪枝两个步骤组成，为了找到[Lk]，通过[Lk-1]与自身连接产生候选k-项集的集合，该候选项集的集合记作[Ck]； [Ck]是[Lk]的超集，它的成员不一定都是频繁项集，但所有频繁k-项集都在[Ck]中，通过计算每个k-项集的支持度来得到[Lk]。

3.2 算法举例

例：以下关系（credit_bill）是模拟银行对某单位年度个人信用卡账单的统计数据：

关系中“Sex”、“Wedded” 和“Title”字段是布尔型，“Age”、“Income”和“Bill”字段是数值型，使用Apriori算法对关系中布尔型数据集进行关联规则挖掘，先对相应属性值时行离散化处理，将“Sex”属性的两种取值“男”和“女”离散化为属性s1和s2，“Wedded”属性取值“已婚”和“未婚”离散化为属性w1和w2，“Title”属性取值“高级”、“中级”和“初级”离散化为属性t1、t2和t3。设最小支持度和最小置信度阈值均为50%，则挖掘过程如图1所示。

通过上述搜索过程得到频繁项集[L2]，其中支持度由公式（1）计算得出，由频繁项集生成的关联规则及由公式（2）计算得出的规则置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

规则置信度大于最小置信度阈值，说明所得规则有效。此规则说明关系所列数据中信用卡持有者男性过半数，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均为70%。

3.3 算法优化

Apriori算法虽然经典，但有两个性能上的瓶颈：在搜索k-频繁项集时，侯选集[Ck]中每个元素都必须通过扫描数据库来确认其是否放入频繁项集中，因此需要对数据库进行k次扫描，数据库中数据量越大，搜索效率越低；由[Lk-1]生成k-侯选项集[Ck]时，[Ck]中元素个数是指数增长的，因此数据量越大，生成的侯选集也就越庞大，既耗费时间，也需要大量的存储空间。

针对Apriori算法中的缺陷，不同学者提出了多种不同的改进方法，如Park等人提出的引入散列技术改进产生频繁2-项集的方法，或高效产生频繁项目集的基于杂凑的算法；Agrawal等人提出的压缩进一步迭代扫描的事务数的方法；Savasere等人提出的基于划分的方法；Mannila等人提出的通过对数据库采样发现规则的方法；Brin等人提出的动态项集计数方法等。这些方法虽然对Apriori算法进行了优化，但没能克服Apriori算法中的固有缺陷：可以产生庞大的侯选集；最小支持度阈值设定值较低时，算法执行效率会降低，而阈值设定较高时，会影响规则产生。

针对上述算法缺陷中的前一种情况，[4]提出采用FP-growth方法，第一次扫描数据库后，将得到的频繁项集放进一棵频繁模式树FP-tree，再将这棵树分解成多个条件库，对这些条件库分别进行挖掘，该方法能适应不同长度的规则，而且执行效率也大大提高。

4 结束语

对于数据库关联规则挖掘方法，该文只针对布尔型值进行了介绍，分析了经典的Apriori算法挖掘布尔关联规则频繁项集的过程及关联规则的得出，并针对Apriori算法的缺陷进行了分析，对多种优化算法进行了阐述。对于数据库来说，数值型字段也是其主要组成部分，而关联规则挖掘也同样可以针对数据值字段，并和多层关联规则结合，或同模糊理论相联系，分析并找出数据间联系，具有重要现实意义。

参考文献：

[1] 杜玉兰.基于模糊理论的关联规则挖掘算法研究[D].保定：华北电力大学，2008.

[2] 梁循. 数据挖掘算法与应用[M].北京：北京大学出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint

该算法由连接和剪枝两个步骤组成，为了找到[Lk]，通过[Lk-1]与自身连接产生候选k-项集的集合，该候选项集的集合记作[Ck]； [Ck]是[Lk]的超集，它的成员不一定都是频繁项集，但所有频繁k-项集都在[Ck]中，通过计算每个k-项集的支持度来得到[Lk]。

3.2 算法举例

例：以下关系（credit_bill）是模拟银行对某单位年度个人信用卡账单的统计数据：

关系中“Sex”、“Wedded” 和“Title”字段是布尔型，“Age”、“Income”和“Bill”字段是数值型，使用Apriori算法对关系中布尔型数据集进行关联规则挖掘，先对相应属性值时行离散化处理，将“Sex”属性的两种取值“男”和“女”离散化为属性s1和s2，“Wedded”属性取值“已婚”和“未婚”离散化为属性w1和w2，“Title”属性取值“高级”、“中级”和“初级”离散化为属性t1、t2和t3。设最小支持度和最小置信度阈值均为50%，则挖掘过程如图1所示。

通过上述搜索过程得到频繁项集[L2]，其中支持度由公式（1）计算得出，由频繁项集生成的关联规则及由公式（2）计算得出的规则置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

规则置信度大于最小置信度阈值，说明所得规则有效。此规则说明关系所列数据中信用卡持有者男性过半数，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均为70%。

3.3 算法优化

Apriori算法虽然经典，但有两个性能上的瓶颈：在搜索k-频繁项集时，侯选集[Ck]中每个元素都必须通过扫描数据库来确认其是否放入频繁项集中，因此需要对数据库进行k次扫描，数据库中数据量越大，搜索效率越低；由[Lk-1]生成k-侯选项集[Ck]时，[Ck]中元素个数是指数增长的，因此数据量越大，生成的侯选集也就越庞大，既耗费时间，也需要大量的存储空间。

针对Apriori算法中的缺陷，不同学者提出了多种不同的改进方法，如Park等人提出的引入散列技术改进产生频繁2-项集的方法，或高效产生频繁项目集的基于杂凑的算法；Agrawal等人提出的压缩进一步迭代扫描的事务数的方法；Savasere等人提出的基于划分的方法；Mannila等人提出的通过对数据库采样发现规则的方法；Brin等人提出的动态项集计数方法等。这些方法虽然对Apriori算法进行了优化，但没能克服Apriori算法中的固有缺陷：可以产生庞大的侯选集；最小支持度阈值设定值较低时，算法执行效率会降低，而阈值设定较高时，会影响规则产生。

针对上述算法缺陷中的前一种情况，[4]提出采用FP-growth方法，第一次扫描数据库后，将得到的频繁项集放进一棵频繁模式树FP-tree，再将这棵树分解成多个条件库，对这些条件库分别进行挖掘，该方法能适应不同长度的规则，而且执行效率也大大提高。

4 结束语

对于数据库关联规则挖掘方法，该文只针对布尔型值进行了介绍，分析了经典的Apriori算法挖掘布尔关联规则频繁项集的过程及关联规则的得出，并针对Apriori算法的缺陷进行了分析，对多种优化算法进行了阐述。对于数据库来说，数值型字段也是其主要组成部分，而关联规则挖掘也同样可以针对数据值字段，并和多层关联规则结合，或同模糊理论相联系，分析并找出数据间联系，具有重要现实意义。

参考文献：

[1] 杜玉兰.基于模糊理论的关联规则挖掘算法研究[D].保定：华北电力大学，2008.

[2] 梁循. 数据挖掘算法与应用[M].北京：北京大学出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint