文档介绍：父联规则挖掘Apriori算法的研究与改进
 
 
 
 
 
   
 
 
 
王铮 周国光
重庆大学计算机学院重庆400044
摘要：本文采用一种基于布尔矩阵的频繁集挖掘算法。该算法直   
 
   
父联规则挖掘Apriori算法的研究与改进
 
 
 
 
 
   
 
 
 
王铮 周国光
重庆大学计算机学院重庆400044
摘要：本文采用一种基于布尔矩阵的频繁集挖掘算法。该算法直接通过支持矩阵行向量的按位与运算来找出频繁集，而不需要Apriori算法的连接和剪枝，通过不断压缩支持矩阵，不仅节约了存储空间，还提高了算法的效率。
关键词：数据挖掘；关联规则；Apriori算法；频繁项集
0 引言
为了方便快速的从事务数据库中挖掘出频繁项集，本文依据Apriori算法的思路加以改进，将事务数据库转换成O-l矩阵，通过0-1矩阵可很快计算出各个候选集的支持度计数，省去了Apriori算法中的连接步骤和删除步骤这样避免了传统Apriori算法频繁扫描数据库的操作，从而提高了算法的效率。
1 关联规则Apriori算法
Apriori算法是R[].。Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集，找每个L3需要一次数据库扫描。为提高频繁项集逐层产生的效率，
Apriori算法利用了一个性质用于压缩搜索空间。Apriori性质：频繁项集的所有非空子集也必须是频繁的Apriori性质在挖掘频繁项集中的应用可以用Lk-1，产生Lk为例来说明，用Lk-1产生Lk包含两步，即连接步和剪枝步。
(1)连接步：由Apriori性质，[]频繁项集的子集一定频繁。Lk的任一项集一定是Lk-1某项集的超集。通过Lk-1内部项集间的连接，生成候选k一项集记作Ck。如果两个项集有(k-2)个相同的项，Lk-1，的元素是可连接的。
(2)剪枝步：由Apriori性质：任何非频繁的（k一1）项集都不是频繁k项集的子集。因此如果候选k项集的(k-1)项子集不在Lk-1中，则改候选也不可能是频繁的，从而从Ck中删除。
2 改进算法
Apriori算法缺陷
Apriori算法作为关联规则挖掘的经典算法，能够比较有效的产生频繁项集，但也存在几个缺陷：
(1)扫描数据库的次数太多，每次寻找k频繁项目集时都需要扫描数据库来获得候选集的支持度，共需扫描n次，如果数据库很大则算法效率太低。
(2)利用k频繁项集连接产生(k+1)候选项集，判断连接条件时重复次数太多。
Apriori算法改进
针对以上情况，产生了一种基于矩阵的改进Apriori算法。它将矩阵的思想应用到Apriori算法中，将数据库表示成矩阵的形式。改进算法思想可描述为：成员表示行向量，事务表示列向量，若第
i