基于矩阵的频繁项集发现算法new

《基于矩阵的频繁项集发现算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第35卷第l期江汉大学学报(自然科学版)Vo1．35NO．12007年3月JournalofJianghanUniversity(NaturalSciences)M81"．．2007基于矩阵的频繁项集发现算法焦学磊，王新庄(成都理工大学信息管理学院，成都610059)摘要：A算法是关联规则的经典算法．在分析经典Apriori算法的基础上，提出了一种有效的基于矩阵的Apfiofi的改进算法．该算法应用了矩阵的思想，只需对数据库扫描一次，即可得到频繁项集，大大提高了算法的效率．关键词：

2、数据挖掘；关联规则；Apriori算法中图分类号：TP301．6文献标识码：A文章编号：1673-0143(2007)0l-0043-04O引言1一种基于矩阵的Apriori改进算法R．Agrawal等【】于1993年首先提出了挖掘顾1．1算法的几个相关概念客交易数据库中项集间的关联规则问题，关联规：{^，厶，⋯，厶)是项的集合，D：{，，则的提取主要针对大型事务数据库．由于关联规⋯，)是数据库事务集合，其中EI(，：1，2，⋯，则提取需要重复扫描数据库，因而提高算法的效P)．在矩阵中，列代表项^，厶，⋯，厶，行代表率是至关重要

3、的．挖掘关联规则问题可以分解为事务，，⋯，．以下两个子问题l2J：①找出所有频繁项集．根据定义1项的向量定义为：定义，这些项集出现的频繁性至少和预定义的最小支持计数一样．②根据定义，由频繁项集产生n：，其中：d,jEE,强关联规则必须满足最小支持度和最小置信度．．这两步中，第二步最容易，挖掘关联规则的总体也就是说，当在事务中时，矩阵的第i行第性能由第一步决定．目前大多数研究集中在第一J列的元素是1，也即：1，i：1，2，⋯，p；如个子问题上．果不包含在事务中，则：0，f：1，2，⋯，关联规则的经典算法是R．Agrawal和Sri

4、kantP，代表列向量，这样suppon_c0uIlt)：∑．于1994年提出的Apfiofi算法．Apfiofi算法使用一种称作逐层搜索的迭代方法七-项集，用于搜索+1)．项集．Apfiofi算法有一个很大的缺点，就⋯是使用了不断产生候选集并加以测试的方式来得到频繁项集．它要求多次扫描可能很大的交易数定义32-项集{，)表示为R，R向量定据库，这需要很大的I／O负载，因此产生候选集的代价是很大的．所以如何设计一个高效的算“法，以提高挖掘的计算效率，降低数据库的扫描D．J=DI八Di=^次数，是研究关联规则挖掘的重要课题．虽然现

5、●-●在对于挖掘算法Apriori不断有新的改进技术d1

6、j提出【3，但仍存在对数据库进行多次扫描、降低精确度、由候选集G产生频繁项集厶等不足．收稿日期：2006—10—20作者简介：焦学磊(1982一)，男，山东青岛人，硕士生，主要从事信息安全的计算方法研究．维普资讯http://www.cqvip.com江汉大学学报【自然科学版)总第35卷此处：l(七：l，2，⋯，P)，表示项向量中／／找数据库中除t-外的任何一项t2的元素与向量中对应的元素取交集的结果．如R=RU{t．，)；))／／连接t，，t2两项果在对应位置的元素都是

7、l，则：l，否则=)；／／自连接生成候选项集--0(七=l，2，⋯，P)．由此supportcount(RⅡ)=W=order(／／剪枝艺．f0reach∈W{／／对中每一个项检验定义4k．项集，={，厶，⋯，)表示为if，(w)-t=(2)){I．2，，，即I，2，，：{RI，2，，—I，)．I，2，，t的／／如果中的项的子集是非频繁项集向量定义为：Dl’2，，DIAD2A⋯AD(DAA=W-{w，}；／／从⋯AD)AD．也就是说∽．．表示项^，，2，⋯，L『二Lu{)；))／／将其放人中的向量中的对应元素取交集后所得的向量结

8、果．foreachw∈W{／／对中每一项定义5非频繁项集下标集定义为：由支D。=AD；／／Y~I取交集持度小于最小支持度的项集(非频繁项集)中的supportcount。)=艺；／／计算支持度项集的下标组成的集合，如supprot(R．：)

9、，13，23}．L=(；}／／最后得到频繁项集定义7集合()定义为：L()={IY∈LreturnL=uIL：}且YcW}．2实例分析1．2算法思想改进算法的思想是利用矩阵来产生频繁集根据以上改进的算法，下面通过一个^，实厶，例厶，分^，^，厶，，^，^，厶，这