apriori算法中频繁项集求法的改进

《apriori算法中频繁项集求法的改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Apriori算法中频繁项集求法的改进摘要：分析传统Apriori效率较低的原因，采用0-1矩阵改进数据库事务集的描述，提高Apriori中统计匹配的时间效率；分析各频繁项集的计数，改进传统Apriori算法完全从低维频繁项集产生高维频繁项集的方式，通过先求出1项频繁集和最大频繁项集，减少中间的频繁项集剪枝数量，从而达到提高算法效率的目的。　　关键词：0-1矩阵；统计匹配；剪枝　　1关联规则[1]挖掘及Apriori算法概述　　一提到关联规则挖掘就会令人联想到“尿布与啤酒”的故事，这是借助数据挖

2、掘技术对大量原始交易数据进行分析揭示的一条规律。Apriori[2]算法是由美国学者R.Agra*n矩阵的0-1矩阵，其中m为数据库事务集D的大小，即包含多少个事务，n为集合I的计数。　　采用0-1矩阵描述数据库事务集能带来如下好处：　　（1）运算简单；便于统计，横向统计“1”的个数就是事务T包含的项数，纵向统计“1”的个数就是1项集的统计数；（2）使用0-1矩阵算法，提高统计项集时候的匹配效率，传统的统计匹配效率正比于n，采用0-1矩阵匹配时间效率正比于n；（3）减少对数据库的扫描，排序后，

3、求频繁k项集的时候，统计项集时不需要扫描数据库，只需要统计包含大于等于k个项目数的事务；（4）易于对数据库事务集按事务包含的项目数大小降序排序；（5）易于求出最大频繁项集。　　2.2改进后的算法MyApriori描述　　要提高Apriori算法的效率，一般来说就是要考虑两个方面的问题：一是减少对数据库的扫描，二是在剪枝的时候减少统计项集的次数。采用0-1矩阵，并排序以后，可以减少对数据库的扫描，在求k项频繁项集时候，只需要扫描包含大于等于k个项目的项集，不需要扫描全部的数据库。传统Apriori

4、算法采用从频繁1项集开始，由频繁k-1项集产生频繁k项集，中间产生大量候选集，对这些候选集要进行统计并剪枝，运算量大；通过多次试验发现：对于1项频繁集，2项频繁集，……，m-1项频繁集，m项频繁集（m项频繁集为最大频繁项集），其数量分布有一定规律，就是两头的数量相对较少，尤其是最大频繁项集数量不多，中间频繁项集的数量较多，数量分布整体呈现为“纺锤状”。可以先通过统计的方法求出最大频繁项集，然后利用“频繁项集的所有非空子集一定也是频繁的”这一定理，再由k-1项频繁项集产生k项频繁项集时，剔除最大频

5、繁项集的子集的项集，只需要统计分析剩余的项集是否为频繁项集即可，减少了剪枝的运算量，优化算法。算法MyApriori：输入原始数据库事务集矩阵A，输出0-1矩阵FI表示的各项频繁项集。　　上述算法的优点：在减少了剪枝的运算量，减少了数据库的扫描次数；缺点是对原始数据库0-1化处理、排序和统计产生最大频繁MAXFI增加了额外开销，其中0-1化处理、排序要对数据库各扫描1次，统计产生最大频繁MAXFI也摘要：分析传统Apriori效率较低的原因，采用0-1矩阵改进数据库事务集的描述，提高Aprior

6、i中统计匹配的时间效率；分析各频繁项集的计数，改进传统Apriori算法完全从低维频繁项集产生高维频繁项集的方式，通过先求出1项频繁集和最大频繁项集，减少中间的频繁项集剪枝数量，从而达到提高算法效率的目的。　　关键词：0-1矩阵；统计匹配；剪枝　　1关联规则[1]挖掘及Apriori算法概述　　一提到关联规则挖掘就会令人联想到“尿布与啤酒”的故事，这是借助数据挖掘技术对大量原始交易数据进行分析揭示的一条规律。Apriori[2]算法是由美国学者R.Agra*n矩阵的0-1矩阵，其中m为数据库事务

7、集D的大小，即包含多少个事务，n为集合I的计数。　　采用0-1矩阵描述数据库事务集能带来如下好处：　　（1）运算简单；便于统计，横向统计“1”的个数就是事务T包含的项数，纵向统计“1”的个数就是1项集的统计数；（2）使用0-1矩阵算法，提高统计项集时候的匹配效率，传统的统计匹配效率正比于n，采用0-1矩阵匹配时间效率正比于n；（3）减少对数据库的扫描，排序后，求频繁k项集的时候，统计项集时不需要扫描数据库，只需要统计包含大于等于k个项目数的事务；（4）易于对数据库事务集按事务包含的项目数大小降

8、序排序；（5）易于求出最大频繁项集。　　2.2改进后的算法MyApriori描述　　要提高Apriori算法的效率，一般来说就是要考虑两个方面的问题：一是减少对数据库的扫描，二是在剪枝的时候减少统计项集的次数。采用0-1矩阵，并排序以后，可以减少对数据库的扫描，在求k项频繁项集时候，只需要扫描包含大于等于k个项目的项集，不需要扫描全部的数据库。传统Apriori算法采用从频繁1项集开始，由频繁k-1项集产生频繁k项集，中间产生大量候选集，对这些候选集要进行统计并剪枝，运算量大；通过多次试验发现：