论文导读：一个大型数据库,其各个字段之间存在着各种各样的关系,这些关系就隐含在数据库所包含的数据中,关联规则挖掘的目的是找出这些隐藏的关联。4）频繁项集：支持度不小于用户给定的最小支持度的项集。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。通过实验可以发现寻找频繁集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入hash技术来改进产生频繁2-项集的方法。的置信度最低。
关键词：关联规则,频繁集,Apriori,FP-tree,支持度,置信度
一、关联规则挖掘简介
一个大型数据库,其各个字段之间存在着各种各样的关系,这些关系就隐含在数据库所包含的数据中,关联规则挖掘的目的是找出这些隐藏的关联。
1、问题描述与基本概念
1）、问题描述
关联规则的挖掘问题可形式化描述如下：
设I={i 1 ,i 2 ,…,i m }是由m个不同的项目组成的集合,给定一个事务数据库D,其中的每一个事务T是I中一组项目的集合,即  ,T有唯一的标识符TID.一条关联规则就是一个形如  的蕴含式,其中,  。关联规则 成立的条件是：
①它具有支持度S,即事务数据库D中至少有S%的事务包含X∪Y；
②它具有置信度C，即在事务数据库D所包含X的事务中,至少有C%的事务同时也包含Y，关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的最小支持度  和最小置信度  的关联规则。
2）、基本概念：
1）项集：项的集合。
2）k项集：包含k个项的项集。
3）项集的出现频率：包含项集的事务数目。
4）频繁项集：支持度不小于用户给定的最小支持度的项集。
5）频繁k项集：支持度不小于用户给定的最小支持度的k项集。
2、关联规则分类 ： 
3、关联规则价值衡量方法
1）、主观兴趣度度量：用户决定规则的有效性、可行性，没有统一的标准。
2）、客观兴趣度度量：
①“支持度—置信度”框架:
②兴趣度：  
③IS度量： 
二、关联规则的挖掘算法
挖掘关联规则可以分解为以下两个过程：
①找出存在于事务数据库中的所有频繁项集。
②利用频繁项集生成关联规则。
（一）、Apriori算法：使用候选项集找频繁项集
Apriori性质：频繁项集的所有非空子集都必须也是频繁的。
1、Apriori算法步骤：
1)用Apriori算法产生频繁项集
①连接步：为找  ,通过  与自己连接产生k项集的集合。该候选项集的集合记作：  。论文格式。设  表示 中的项集，  表示 中的第j项，假定项集中的项按字典序排列；连接 ：  ：
②剪枝步:扫描事务集D,确定 中每个元素出现的次数，从而确定 。
2)由频繁项集产生关联规则
a、对每个频繁项集L产生其所有的非空真子集。
b、对L的每个非空真子集S计算  置信度，大于 的留下来作为挖掘到的关联规则，小于 的去掉。
2、Apriori算法的几种优化方法
1) 基于划分的方法：
①将事务集D分为n个非重叠的部分。
②找出每部分内的频繁项集（局部）。
③将所有的局部频繁项集作为整个D的候选项集，扫描D确定每个候选集的实际支持度。
1/3 1 2 3 下一页 尾页 |
