基于Close算法的小型超市购物序列分析

论文（设计）题目

基于Close算法的小型超市购物序列分析

学科分类（二级）

520.1040

题目来源（a.教师拟题；b.学生自拟；c.教师科研课题；d.其他）

a

本选题的依据：1）说明本选题的研究意义和应用价值

2）简述本选题的研究现状和自己的见解

1本课题的研究意义和应用价值

随着科学技术的不断发展，在各个行业中积累了大量的数据，但是，我们面对如此庞大的数据的时候，经常会感到迷茫，不能够从这些数据中提取出对我们有用的知识，造成“数据丰富，信息贫乏”这种现状。在这种情况下，数据挖掘技术应运而生，它能够帮助我们从大量数据中提取出有价值的知识模式，被认为是最具发展前景的一项关键技术。

数据挖掘技术在零售业方面是研究的重点领域，因为，在日常的零售业过程中积累了大量的数据，例如货物进出记录，购买记录，消费记录等，随着时间的推移，这些数据会不断增大，如何从这些大量数据中提取出隐含的规则模式，分析顾客购买行为模式，协助货架的布置等是数据挖掘研究的重点内容，如果能对这些大量数据进行很好的分析就能够帮助零售业提高销售额度。

基于闭合项目空间的理论，Pasquier等提出了Close算法，加速了频繁项目集的生成，减少了数据库的扫描次数。本课题主要通过应用Close算法来分析某小型超市的购物序列，从而得到更有效的决策方法。

2本课题研究现状

目前，关于频繁模式挖掘的研究主要集中在算法的执行效率上，大致有以下几类：

(1)以Apriori算法为代表的基于Apriori性质的广度优先逐层挖掘频繁模式的方法，也即在候选k-项集的基础上广度优先挖掘（k+1）-项集。

(2)以FP-Growth算法为代表的采用一种高度压缩的树结构(FP-Tree)“分治"的深度挖掘频繁模式的方法。

    1999年，Pasquire等人提出闭合项目集挖掘原理，并给出了基于这种理论的Close算法。他们给出了闭合项目集的概念，并讨论了这个闭合集格空间上的基本操作算子。实验证明，Close算法对特殊数据是可以减少数据库扫描次数的。

3个人见解

随着科学技术的迅猛发展和计算机技术的普及，社会的各个领域都积累了大量的数据，如银行每天的巨额交易数据和人类对科学知识的不断探索等等。显然这些数据中蕴藏着丰富的对人类有益的信息，那么怎样挖掘这些信息就成为我们所必须面对的问题。数据库技术的发展使得处理数据成为可能，但面对不断增加的海量数据，人们不再满足于数据库的统计和查询功能，从而提出了更深层次的问题，就是能否从数据中提取信息或知识为决策服务。这对于数据库技术而言就有些捉襟见肘了，因此我们急需寻求～种新的技术来处理这些如潮水般涌来的数据。于是，人们将数据库、机器学习和统计学等技术相结合，提出了数据挖掘的概念来解决这个难题。

研究的主要内容：

1 关联规则

关联规则是基于数据项目的同时出现特征，不是基于数据自身的固有属性(例如函数依赖关系)，不能通过数据库的逻辑操作(如表的联接)或统计的方法得出。

关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则反映顾客购买行为模式，如购买了某一商品的影响。发现这样的规则可以应用于顾客购物分析、目录设计、商品广告邮寄分析、追加销售、商品货架设计、仓储规划、网络故障分析以及根据购买模式对用户进行分析。刚亮泽的数据挖掘在商业领域的成功应用，使它成为数据挖掘中最熟悉、最主要、最活跃的研究内容。

1.1 Close算法

频繁项目集挖掘是序列模式挖掘和关联规则挖掘的关键部分，自从1994年Agrawal等人提出Apriori算法以来，国内外诸多学者对频繁项目集挖掘问题进行了大量的研究。但是挖掘频繁项目集需要考虑太多的候选频繁项目集，所以近些年来很多人开始去挖掘频繁闭项目集和最大频繁项目集。频繁闭项目集和最大频繁项目集隐含了所有频繁项目集的信息，而且集数量要远远小于频繁项目集的数量。

1.2 Close算法的思想

Close算法是基于这样原理的:一个频繁闭合项目集的所有闭合子集一定是频繁的，一个非频繁闭合项目集的所以闭合超集一定是非频繁的。因此，可以在闭合项目集空间格上讨论项目集的频繁问题。实验证明，它对特殊数据是可以减少数据库扫描次数的。

Close算法是对Apriori的改进算法。在Close算法中，也使用了迭代的方法；利用频繁闭合i-项目集记为FCi ，生成频繁闭合（i+1）-项目集，记为FCi+1  （i>=1）。首先找出候选1-项目集，记为FCC1 ，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不笑于最小支持度，则加入到频繁闭合项目集FC1中。再将它与自身连接，以得到候选频繁闭合2-项目集FCC2，再经过修剪得出FC2，再用FC2推出FC3，如此继续下去，直到有值r使得候选频繁闭合r-项目集FCCr为空，这时算法结束。

1.3 Close算法中用到的函数及算法的实现过程

在Close算法中调用了三个关键函数：Gen-Closure（FCCi），Gen-Generator（FCi）和Deriving frequent itemsets。

函数Gen-Closure（FCCi）产生候选的闭合项目集，以用于频繁项目集的生成。查找闭合的方法是（设要查找FCC1的闭合）：取出数据库的一项，记为t。如果FCCi的某一项对应的产生式p是t的子集而且它的闭合为空，则把T的闭合记为p的闭合。如果不为空，则把它的闭合与t的交集作为它的闭合。在此过程中也计算了产生式的支持度。最后将闭合为空的产生式从FCCk中删除。

在Gen-Generator（FCi）算法中，也使用了Apriori算法的连个重要步骤：连接和修剪。在由FCCi生成FCCi+1时，前面的连接和删除非频繁子集与Apriori算法虽然是相同的，但是它增加了一个新的步骤，就是对于FCCi+1的每个产生式p，将FCi的产生式中是p的子集的产生式放到sp中（因为这时已经进行了非频繁子集的修剪，所以p的所以i项子集都都存在于FCi中）。

Close算法最终需要通过频繁闭合项目集得到频繁项目集。

2 现有算法总结

关联规则挖掘算法中比较典型的算法有Apriori、基于划分的算法、DHP和增量式更新算法等，后面三种算法都是在Apriori算法的基础上改进的算法。

Apriori算法是最早提出的关联规则挖掘算法，它的实现过程比较简单。但是每次生成含有不同项目数的候选集时都要扫描数据库，当候选集规模较大时，该算法在时间上的开销就会比较大。另外由于事务数据库中的数据在不断地增加，每次增加数据后Apriori算法计算频繁项目集和生成关联规则这两项工作必须针对新数据增加后的数据库重新做起，这意味着以前生成的频繁项目集和关联规则都被白白浪费了，显然不利于快速高效地发现关联规则。还有当数据库的规模超出主存的容量时，该挖掘算法就无法使用，相对于以后的各种算法而言，其效率最低。

基于闭合模式的思想，1999年，Pasquier提出了基于Apriori算法的Close算法。Close算法借鉴了Apriori算法的设计思想，采用自底向上广度优先的搜索策略。长度为k十l的频繁产生模式是从长度为k的频繁产生模式进行连接得到的长度为斛l的候选集中得到的。Close算法在生成长度为k的频繁产生集之后就扫描数据集求得它们的闭包，从而得到对应的闭合模式。由于引入了产生集，Close算法扫描数据集的次数和候选集中模式的个数一般要少于Apdori算法。

2.1 Close算法的研究现状

目前，关于频繁模式挖掘的研究主要集中在算法的执行效率上，大致有以下几类：

(1)以Apriori算法为代表的基于Apriori性质的广度优先逐层挖掘频繁模式的方法，也即在候选k-项集的基础上广度优先挖掘（k+1）-项集。

(2)以FP-Growth算法为代表的采用一种高度压缩的树结构(FP-Tree)“分治”的深度挖掘频繁模式的方法。

频繁模式挖掘虽然利用剪枝等策略会降低频繁模式的产生数量，但是随着支持度等度量的降低依然会产尘大量的频繁模式。自Pasquier 93年首次提出挖掘频繁闭项集(frequent closed itemset)概念。并提出了以Apriori算法为基础，采取自顶向下、广度优先的搜索策略，逐层求出所有的频繁闭项集的A-Close算法后，频繁闭项集的研究成为人们关注的热点。

主要研究方法：  

调查法：对于特殊物品的消费的特征需要进行跟踪调查才能获得其数据。

观察法：观察超市货物的摆放情况，然后比对销售情况，发现其中的联系。

文献研究法：检索网上的资料，从中了解前人的研究情况和方法。

测验法：对于获得的数据和分析出的结果，需要进行测验。

信息研究方法：根据信息论、系统论、控制论的原理，通过对信息的收集、传递、加工和整理获得知识，并应用于实践，以实现新的目标。

验证法：用C语言编程实现挖掘算法，对于程序的正确性需要进行多方验证。

研究进度计划：

2011年12月   完成开题报告和文献综述。

2012年1月    熟悉数据挖掘的过程和掌握Close算法的实现。

2012年2月    锁定一家小型超市并进行原始数据的收集。

2012年3月    对数据进行调研，建立事物数据库。

2012年4月    用Close算法进行设计，对所选的超市购物序列进行分析实现，得到决策方法。

2012年5月    毕业设计结题

主要参考资料：

[1] 胡冰.繁闭项集的挖掘算法及内容分析[D].河南：河南大学，2009.

[2] 陈俊波.频繁闭合项集挖掘算法及应用研究[D].浙江：浙江大学，2009.

[3] 许娅.关联规则更新算法研究与应用[D].合肥：合肥工业大学，2009.

[4] Usama Fayyad，Gregory Piatetsky-Shapiro，Padhraic Smyth．From data mining to knowledge discovery in databases[J]. AI Magzine，1996，1 7(3)：37-54．

[5] 刘必红.购物篮分析中若干问题的研究[D].浙江：浙江大学，2006.

[6] 李洋.闭合序列模式挖掘模型与算法的研究[D].合肥：合肥工业大学，2007.

[7] 毛国君，段立娟，王实，石云.数据挖掘原理与算法[M].北京:清华大学出版社,2005,74～79.

[8] 徐利军. 基于数据流的频繁集挖掘研究[D].上海：上海交通大学，2006.

[9] argarent H.Dunham.数据挖掘教程[M].郭崇慧,凤占等译,北京:清华大学出版社, 2005,88～91.

[10] 张亮．频繁项目集挖掘算法研究[D]．辽宁：辽宁师范大学，2009.

[11] 唐微波，唐宇剑.数据挖掘技术在零售业中的应用[J]. 合肥学院学报(自然科学版),2007,17(2)：80～82.

[12] 赵松.priori算法的改进及应用[D]. 哈尔滨：哈尔滨理工大学，2006.

[13] Jiawei Han  Micheline Kamber.数据挖掘概念与技术[M]．范明，孟小峰  译,北京：机械工业出版社,2007，67～71.

指导教师意见（含选题的科学性、可行性、应用价值、结合本专业知识的情况以及具体指导意见等）：

指导教师签名：

年    月    日

开题会议纪要

时间

地点

开题小组成员

姓名

职称

姓名

职称

姓名

职称

开题小组意见（含开题基本情况及结论）：

组长签名：

年    月     日

学院意见：

分管领导签名：

年     月     日