基于提高频繁项集挖掘效率算法在市场分析中的探讨

摘要：频繁模式是频繁地出现在数据集中的模式（如项集、子序列或子结构）。如频繁地同时出现在交易数据集中的商品的集合是频繁项集，利用高效率的频繁项集挖掘算法来发现频繁项集，通过分析这些频繁项集来预测商品的销售情况。

关键词：关联规则；Apriori算法；频繁项集；商品

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）04-0661-03

Based on the Improvement of Frequent Itemsets Mining Efficiency Algorithm in Market Analysis of Discuss

CHEN Wei

（Huainan Union University， Huainan 232038， China）

Abstract： Frequent pattern is frequently seen in the data concentration mode （such as itemsets， sequences or structures）.As frequently appear in both the transaction data concentrated merchandise collection is frequent itemset， Using of efficient algorithm for mining frequent itemsets to find frequent itemsets， through the analysis of the frequent itemsets to predict the commodity the sales situation.

Key words： association rule； Apriori algorithm； frequent itemsets； commodity

随着大量数据不停地收集和存储，从数据库中挖掘频繁模式引起各行各业人士的兴趣。许多商务决策的制定，如交叉销售、顾客购买习惯分析等，都可以从大量事务记录中寻找一些有趣的相关联系。如今的超级市场作为一种新的销售形式，因为其商品价格低、品种多和商品直接面向顾客等优势得到了广大顾客的青睐。但是，随着超市规模的不断增大，商品种类和交易量也日益庞大起来，自然所积累的商业数据也越来越多。在这种情况下，面临如何以最少的资金组织最快的商品流动、如何根据顾客的需求对商品进行合理的布局和搭配、如何根据目前的销售信息去预测未来的销售情况等等一系列问题都是商家特别关心的。

1 频繁项集挖掘方法概述

购物篮分析是频繁项集挖掘的一个典型例子，它是根据购买者购买的商品来分析该顾客的购物习惯，比如典型的“啤酒和尿布”例子，超市经过对购物信息的挖掘，改变货物在货架上的摆放位置，从而调高了销售额。

除了购物篮分析以外，还有许多种频繁模式、关联规则和相关联系。频繁模式挖掘有多种方法：

1）根据所处理的值类型分为：布尔关联规则和量化关联规则。

2）根据涉及的数据维分为：单维关联规则和多维关联规则。

3）根据所涉及的抽象层分为：单层关联规则和多层关联规则。

目前已经开发了许多有效的、可伸缩的频繁项集挖掘算法，由它们可以导出关联规则。这些算法分成三类：1）类Apriori算法，2）基于频繁模式增长算法，如FP增长，3）使用垂直数据格式的算法。

关联规则挖掘中最简单形式的挖掘是单维、单层和布尔关联规则，其中用一种称为逐层搜索的迭代方法来找出所有的频繁项集的Apriori算法是最著名、最有影响的关联规则挖掘算法。它的建立也是基于频繁项集性质的基础。

2 提高频繁项集挖掘效率算法

在寻找频繁项集的Apriori算法中需要频繁进行这样两个操作：判断两个k-项集中是否满足前k-l项相同且最后一项不同，即连接步；判断一个项集是否为另一个项集的子集，即剪枝步。假设事务数据库中各记录的项目均已排序，可以利用这一特点，从减少算法中这两个操作的执行次数的方法来达到优化算法的目的。

1）减少连接步骤的执行次数具体实现方法：

由于我们已经设定各事务项目按字典排序，所以其中的任一个k-项集L，有L[l]

2）减少剪枝步骤的执行次数具体实现方法：

对于一个k-项候选集的一个子集（k-1）-项集La和一个（k-l）-项频繁集Lb，若La[i]< Lb[i]，则La与Lb后的所有（k-l）-项频繁集都不会相同。所以只要La[i]< Lb[i]，就不需要再判断La是否与Lb后的（k-1）-项集相同。则判定La不是频繁项集。由频繁项集的所有非空子集都必须是频繁的Apriori算法性质，所以该k-项候选集不是频繁项集，从而删除它。该步操作中大大减少了判断候选项集的任一子集是否是频繁项集的执行次数。

从Apriori算法中由k频繁项集生成k+1频繁项集时，要首先生成候选项目集Ck+1。在扫描数据库时，要记录下该函数生成的许多候选项目集的出现次数，但这些候选项目集并不都是要找的频繁项集。假如数据库中的事务数很大，k频繁项集数就多，导致侯选项目集的元素个数也会很多。例如1000个频繁1-项集，就生成1000*999/2=499500个候选2-项集。统计如此巨大数量的候选项目集的出现次数开销非常大，这是整个算法性能好坏的关键。

Apriori算法是从TID项集格式的事务集中挖掘频繁项集，这里的TID是事务标识符，而item是TID中购买的商品集，这种数据格式称为水平数据格式。如果数据用项-TID集格式表示，其中item是项的名称，TID_set是包含item的事务标识符的集合，这种格式称为垂直数据格式。

所以在探讨过程中准备使用垂直数据格式挖掘频繁项集，这是对频繁项集挖掘效率的进一步改进。然后再利用改进的方法重新对数据进行分析应用。

首先在求频繁1项集的同时把数据转化为垂直格式，即记录下在数据库中每个项集出现时的该条数据的TID号，那么项集的支持度计数就是项集的TID集的长度。从k=2开始，用Apriori算法通过取频繁k项集的TID集的交计算对应的k+1项集的TID集，若该TID集的长度大于最小支持度计数，则该记录为频繁项集。重复该过程，k值增加1，直到不能再找到频繁项集或候选项集[1-2]。

3 算法应用探讨

实验方案：

1）首先利用Visualfoxpro6.0中提供的导入向导功能将顾客信息和商品销售信息的数据文件导入到Visualfoxpro6.0中，建立相应的数据库文件；

2）针对现有数据进行数据预处理，包括二个步骤：数据清理和数据变换。

数据清理：消除一些冗余数据，消除噪声数据，消除重复记录。

数据变换：将数据转换成适合于挖掘的形式。假设一段小数据量的交易如下：

其中表格中的数值代表顾客购买商品的数量。对数据进行预处理后其中1代表购买，0代表没有购买：

3）用优化的算法求解频繁项集：根据超市的商品销售量、顾客购买情况等信息，设定最小支持度，求解频繁项目集。设酸奶为A、香肠B、面包C、啤酒D、果汁E：

①建立一个数据表，表中有1个字段，数据类型为字符型用于存放每种商品的表达值，该表中每条记录代表一种表达值，记录数就是表达值形式的数目。表中的记录按升序排列。

②建立二个空数据表，分别用来存放1、2频繁项集和它们的支持度计数。其中一个表中有2个字段，另一个表中有3个字段。

4）从已经产生的频繁项集中找出它们的子集，然后根据关联规则的挖掘算法原理，设定最小置信度，由实验得出关联规则[3-6]。

从得出的规则中可以看出买酸奶的顾客就一定会同时购买面包，反之亦然；买酸奶的顾客一定会同时购买香肠，买面包一定会同时购买香肠，但反过来不一定等等购买信息。

4 总结

关联规则的应用广泛，而其中耗时最多的工作就是它的经典算法 Apriori算法中的频繁项集的求解，因此提高了频繁项集的求解速度，自然也就加快了关联规则的求解速度。在原算法的基础上一步步改进其效率是本应用的一个主要亮点，并把这些改进的过程一一运用在具体的数据中是另一亮点。但在文章中由于数据量小，说明问题的力度不够大，需要采集大容量数据。

近年来超市发展迅速，成为我国商品流通领域中非常重要的一种形式。超级市场的数据不仅十分庞大、复杂，而且包含着许多有用的信息，我们利用上述算法可以从这庞大的数据中发现一些潜在的、有用的、有价值的信息来应用于超市的经营。利用提高挖掘效率的过程对顾客消费模式、商品销售、营销情况进行分析，可以帮助许多商务决策的制定。同样利用该算法我们可以把它应用于银行、股市等等其他行业，应用前景广泛。

参考文献：

[1] 陈文伟，黄金才.数据仓库与数据挖掘[M].北京：人民邮电出版社，2004.

[2] 陈伟.数据挖掘技术在学生成绩管理中的应用[D].合肥：安徽大学，2008.

[3] 戴智杰，袁卫，谢邦昌.超市里的数据挖掘[J].中国统计，2008（5）：42-43.

[4] Agrawal R，Imielinski T，Swami A. Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIGMOD Conference on Management of data（ACM SIGMOD’93），Washington.USA，1993：20-216.

[5] 洪晶，柳炳祥，程功勋.一种基于Apriori算法的彩票数字组合数据挖掘[J].福建电脑，2005（9）：92-92.

[6] 陈伟.关联规则在学生CET4成绩中的应用[J].信息化纵横（原微型机与应用），2009，28（5）：10-12.