多种关联规则挖掘算法的研究与分析_王金甫

多种关联规则挖掘算法的研究与分析

王金甫觹

摘

要：本文首先介绍关联规则的基本概念，对关联规则算法进行了详细地分析和研究，就目前针对提高该算法效率的各种优

化技术也进行了详细地描述与分析，并说明各改进算法在各商业领域中的应用。

关键词：数据挖掘；关联规则；遗传算法

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

WangJinfu

文章编号：1002－2422（2011）01－0004－02

ResearchandAnalysisofAVarietyofAssociationRuleMiningAlgorithm

Abstract:

Thepaperfirstintroducesthebasicconceptsofassociationrules,Associationrulesalgorithmfordetailedanalysisa－ndresearch．Thealgorithmforimprovingthecurrentefficiencyofvariousoptimizationtechniqueshavealsobeende－scribedandanalyzedindetail,anddescribestheimprovedalgorithminallareasofbusiness．

Keywords:DataMining;AssociationRule;GeneticAlgorithm

1传统的关联规则挖掘算法

1．1Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度再使用第1步找到的频集产生期望的规则，和最小可信度。

产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。

Apriori算法的缺点是扫描事务数据库次数过多、在频繁项长度变大的情况下，运算时间显著增加、不能直接用于关系数据库的关联规则挖掘、不适于海量数据环境下的关联规则挖掘。1．2基于划分的算法

此类算法包括A．Savasere等人的Partition算法[14]，S．Brin等人的DIC算法[19]等。这些算法将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访问外存的I／O开销。Partition算法只需要对整个数据集进行两次扫描，DIC算法在数据块划分恰当时可以通过两次扫描数据集找出所有的频繁项目集。

数据集划分算法的候选项目集的数量一般比Apriori算法的候选项目集的数量大，数据集划分算法是各种并行关联规则挖掘算法和分布式关联规则挖掘算法的基础。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k－项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。

1．3FP－树频集算法

频繁项集挖掘算法FP－growth通过对数据库的两次扫无描，将数据信息存到一种压缩的数据结构（FP－tree）里，须生成候选项目集，显著地缩小了搜索空间，极大地减少了数据模式匹配的开销，有效地避免了产生“知识的组合爆，因此挖掘效率有了很大提高。但是此算法没有充分考炸”

虑层次数据的自身特点，在频繁项集查找过程中，仍然包含了大量无用项集的计算。无法根据层次数据的特点来进行关联规则的去冗余，造成了大量的冗余关联规则的产生。

2几种关联规则挖掘算法的改进

基于FP－树频集算法的改进算法，利用层次结构数据去冗余的多层关联规则挖掘方法，的内在特征，采取高效、将是一件非常有意义的工作。采用聚类的方法，对已有的评增加价关联规则的两个常用客观性指标－支持度和可信度，一个相关的业务参数，达到对树的进一步划分，使得频繁项集挖掘时须扫描的数据库变得越来越小，以此提高挖掘效率，以便挖掘出收益较高、值得关注的业务。

基于哈希（hash）表技术，利用hash表技术可以帮助有（k＞1）所占用的空间。例如:在扫描效减少候选k－项集Ck

交易数据库以便从候选1－项集C1中产生频繁1－项集L1时，就可以为每个交易记录产生所有的2－项集并将哈希（hash）到hash表的不同栏目中，增加相应栏目的技术。如果hash表中一个存放2－项集的出现频率低于最小支持度，则表示相应2－项集为非频繁项集而被移出候选集。利用hash表技术可以帮助有效减少需要检查的候选项集数目。

应用遗传算法的思想改进Apriori算法只需扫描一次数据库，通过一次扫描数据库，给定一个映射，把数据库映射成一个矩阵M，以下所有对数据库D的扫描均可在M上运算完成。把求解关联规则最长频繁项集的问题转化到某生物种群对环境的适应性，将优化变量对应生物种群的个

收稿日期：2010－12－23

*王金甫长春理工大学光电信息学院信息工程分院讲师（吉林，长春130022）。

·4·

利用OFFSET、COUNTA、COUNT和SERIES

函数实现股票研究图表的自动更新

陈一匡觹

摘

要：采用MicrosoftExcel软件可以非常方便的制作股票研究图表，但是当图表源数据发生变化的时候，必须手动更改图表。

本文介绍一种简单实用的方法，可以实现股票研究图表的自动更新。

关键词：图表；自动更新；Excel中图分类号：TP311．5

文献标识码：A文章编号：1002－2422（2011）01－0005－03

UsingOFFSET,COUNTA,COUNTandSERIESFunctions

toAuto－updateStockStudyCharts

ChenYikuang

Abstract:ItisconvenienttocreatestockstudychartsinExcelwhichisdevelopedbyMicrosoft．Butthereisalimitation．Thechartswon＇tupdateaccordingtothechangesoftheirbasicdata．Thepaperintroducesasimplewhileutilitymethodtoauto－updatestockcharts．

Keywords:Charts;Auto－update;Excel

．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．

体，将所发展的求解优化问题的算法与生物种群的进化过程类比。

改进算法的基本思想:首先要对实际问题进行编码，编定码方法可以是二进制编码，也可以是十进制编码。然后，义遗传算法的适应度函数，根据适应度函数求出频繁1－项变异运算对该组项集进行进化，再利用选择集，应用交叉、运算产生下一代频繁项集，这样经过若干次迭代后，遗传算法满足终止条件，从而得到一组最长频繁项集。

越小，以此达到提高生成频繁项集和关联规则的效率。因此该算法适用于大型的金融交易中，比如银行交易，大型企业交易等。

3．2应用遗传算法的思想改进Apriori算法

此算法对其进行求解，设交叉概率为0．8，变异概率为0．01，初始化种群规模为100，迭代次数为50。最小支持度为0．3，算法中还随机产生了一组数据，共有2100个事务，30个项。表1显示了在不同支持度下所得到的最大频繁项集的个数、所用时间和循环次数。相对于原始的Apriori算法改进后的算法节省了时间，提高了效率。

表1实验运行结果

最小支持度最大频繁集个数

0．230．320．45

时间（s）迭代次数T

30．134059．1260168．55110

3改进算法分析

3．1基于FP－树频集算法的改进算法

以大型的商业交易为例，每次商业交易都有层次结构树的特征，对整个交易树利用特定的业务参数进行分类，采取自顶向下方式，依次对各层子树进行分类，其中下层分类是在上层分类结果基础上进行的。整个分类过程分为以下几个主要步骤。

步骤1：针对交易树的第i层，考察i－1层的每个分类交易子树如果是第2层，则考察整个交易子树。

步骤2：对于第i－1层中1－项集不是频繁项集的子树，将其从交易数据库中删除且不纳入后续分类。

步骤3：针对第i－1层每棵待分类的每个交易子树，计算所有子树两两之间的业务参数。由于包含这两棵交易子树的2－项集表示的是这两类交易在事务数据库中同时出现的频率，值越大，则这两类交易子树参数相关性程度可能会越高，按每一层上交易子树之间的业务参数相关程度，根据层次连接聚类算法的方法，就可以得到该层上各交易子树之间相互独立的分类，然后依此对上层交易数据库进一步进行划分，使得生成k－项集时须扫描的数据库变得越来

4实验结论

根据理论以及实验结果分析，改进算法调高了效率，且节省了时间，在实际应用中有一定的可行性，根据不同算法的不同特点，可以应用到相应的领域中去。

参考文献

[1]冯洁，陶宏才．典型关联规则挖掘算法的分析与比较[J]．西安：

计算机技术与发展，2007，17（3）:121－124．

[2]陈沛玲．决策树分类算法研究[D]．长沙：中南大学，2007．[3]PernerP．Recentadvancesindatamining[J]．EngineeringAp－

pli－cationsofArtificialIntelligence，2006，19（4）:361－362．[4]刘建．商务智能中关联规则挖掘算法的研究及应用．长春：长

春理工大学，2009．

收稿日期：2010－12－18

*陈一匡广东省韩山师范学院物理与电子工程系讲师（广东，潮洲521041）。

·5·

本文来源：https://www.bwwdw.com/article/9su4.html