论文（设计）题目

基于FP-tree算法的小型超市购物序列分析

学科分类（二级）

520.1040

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

a

该选题研究的意义和应用价值

伴随着超市信息化建设和应用进程的加快，大量信息技术如条码技术、电子收款机、POS系统，数据库技术在超市中的普遍应用，超市积累的客户交易数据越来越大，但是数据利用率却很低，如何从收集到得大量数据中分析出那些商品好卖、哪些商品不好卖、那些客户群需要哪些商品、商品与商品之间如何搭配等这些对企业有价值的信息和知识，哪些商品同时被顾客频繁购买，解决其所面临的数据爆炸而知识贫乏的困境，一种新的信息技术——数据挖掘技术开始应用于超市管理，利用分析决定未来，从大量的商务事务记录中发现有趣的相关联系，可以帮助许多商务决策的制定，如分类设计、交叉销售和顾客购买习惯分析，使超市信息化管理逐步开始迈向知识管理。这种信息可以帮助商家做选择性销售和安排货架空间，从而增加商品销售量和商品的利润。利用数据挖掘，每个超市对供货商的信誉管理模式可以从定型化逐步走向定量化，通过科学的强化对供应商的信息评估，风险度测量管理，有效地防范和控制超市经营风险；同时利用数据挖掘技术，能够从超市各种应用系统中提取各种基础绩效指标和关键绩效指标。 

研究的主要内容：

jiawei Han在2000年文献中提出了一个称为FP-tree的算法如下[3]:

这个算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库生成一个频繁模式树，最后通过这棵树生成关联规则。

用FP-tree挖掘频繁集的基本思想是分而治之的，即使用FP-tree递归增长频繁集的方法：

(1)对事物数据库中的每个项，生成它的条件模式库，然后是它的条件FP-tree；

(2)对每个新生成的条件FP-tree，重复这个步骤；

(3)直到结果FP-tree为空，或只含唯一的一个路径(此路径的每个子路径对应的项目集都是频繁集)。

挖掘FP-tree的主要步骤可以归纳如下：

(1)为FP-tree中的每个结点生成条件模式库，即从FP-tree的头开始；按照每个频繁项的连接遍历FP-tree，列出能够到达此项的所有前缀路径，得到条件模式库；

(2)有条件模式库构造对应的条件FP-tree，即对每个模式库，计算库中每个项的支持度，并用模式库中的频繁项建立FP-tree；

(3)递归构造条件FP-tree同时增长其包含的频繁集，这一步中，为了正确地挖掘条件模式树以生成频繁模式，需要对下面两种情况加以讨论，首先，是单FP-tree路径生成，二是，FP-tree中的唯一前缀路径；

(4)如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。