基于关联矩阵频繁项集挖掘算法-
最后更新时间：2024-01-28
作者：用户投稿
本站原创
点赞:6318
浏览:22221
本站原创
点赞:6318
浏览:22221
论文导读：
摘要: 根据经典Apriori性质和算法思想，提出了一种基于关联矩阵的挖掘频繁项集的算法.应用实例分析表明，该算法在挖掘过程中，只需扫描一次数据库，有效地减少了扫描数据库的次数，提高了算法的效率.
关键词: Apriori算法；关联矩阵；频繁项集
:A文章编号:1672-8513(2012)02-0138-03
An Algorithm for Mining Frequent Itemsets Based on Associated Matrix
ZHANG Yafen,WANG Xin
(School of Mathematics and Computer Science, Yunnan University of Nationalities, Kunming 650500, China)
Abstract: According to the ideas and properties of the classical Apriori algorithm, a new algorithm for mining frequent itemsets is proposed, which is based on the associated matrix. Through the analysis of the example, it has been found that this algorithm scans the database only for one time and reduces the number of scanning during the mining process, and improves the efficiency of the algorithm.
Key words: Apriori algorithm; associated matrix; frequent itemsets
关联规则挖掘是指从海量的数据库中挖掘项集之间有趣的模式或者是相关关系.此概念以及经典的Apriori算法最初是由Agrawal等［1-2］提出的，该问题主要包括频繁项集的产生和由频繁项集得到的关联规则的产生［3-4］，而其核心问题是频繁项集的挖掘.因此对于该问题的研究是至关重要的，目前许多相关研究人员对该问题进行大量的研究和探讨，主要的算法都是基于对经典Apriori算法和FP-Growth算法［5］的改进.本文通过介绍图的关联矩阵概念，然后对其作相关定义上的修改,从而运用到频繁项集的挖掘算法中，提出了一种新的基于关联矩阵的频繁项集挖掘算法（Frequent Itemsets Mining Algorithm Based on Associated Matrix, AMFM）.并且通过应用实例说明该算法较Apriori算法是有效的，在挖掘过程中，只需扫描一次数据库，从一定意义上降低了时间复杂度，提高了算法的效率.
1 基本概念
设I={i1,i2,…,im}是项的集合，设任务相关的数据D={T1,T2,…,Tn}是事务数据库的集合，其中每个事务T是项的集合，使得TI.每个事务都有一个标识符，记为TID.
定义1 （项集、k项集、频繁项集）如果AT，则称A是一个项集，并且定义包含k个项的项集称为k项集.对于一个项集A，如果其支持度大于等于用户给定的最小支持度阈值min_sup，则A为频繁项集.
关联规则发现的任务是指挖掘出同时满足最小支持度（min_sup）和最小置信度（min_conf）阈值的规则［6］.因此在挖掘过程中对于频繁项集的计数从而计算其支持度是最关键的.
定义2 （图的关联矩阵）［7-8］设G=为无向图，且V={v1,v2,…,vn}表示顶点的集合，E={e1,e2,…,em}表示边的集合，则图G=的关联矩阵M=(mij)为n×m阶矩阵.其中
mij=1,若vi关联ej,0,若vi不关联ej .
基于上述图的关联矩阵的定义，显然这是1个布尔矩阵，而事务数据库的数据是满足布尔矩阵的特征的，因而可以类似地定义项集的关联矩阵.
定义3 （项集的关联矩阵）设I={i1,i2,…,im}是项的集合， D={T1,T2,…,Tn}是事务数据库的集
2 基于关联矩阵的频繁项集挖掘算法
该算法中的（1）~（7）部分是关联矩阵的生成过程；步骤（8）是利用关联矩阵的相关性质寻找所有的1-频繁项集；（9）~（23）部分是整个算法的核心，包括候选项集的产生和计数，在进行候选项集产生的过程中主要利用了Apriori算法的性质和先验知识：任何非频繁的（k-1）项集源于：7彩论文网党校毕业论文www.7ctime.com
都不是频繁k项集的子集，基于此对产生的候选项集进行连接和剪枝；步骤（24）利用关联矩阵的k-项集的支持度计数方法进行计数，并论文导读：CDF};③计算3-候选项集{ABC}的支持度计数如下：sup_count{ABC}=(s110∧s210)∧s310=(1100000001)∧(0101100111)=(0100000001)=2.同理可计算出其余3-项集的支持度计数并且满足sup_count>=2的所有3-频繁项集L3={ABC:2,ABD:3,BCD:3,BCF:2,BDF:2}.5)连接C4=L3×L3=
且与给定的最小支持度计数阈值进行比较；步骤（26）得到的是支持度计数不小于最小支持度计数阈值的所有频繁项集.
3 应用实例分析
下面给出如表1所示的小型事务数据库［9~10］，它包含了10条交易数据记录和6个项.其中T1~T10表示每条交易的标识符号，字母A~F表示每条交易所包含的对象.若以购物篮分析为例，字母A~F可以具体地表示为顾客所购买的商品名称.将本文算法应用于该数据库的频繁项集挖掘，具体过程如下所示.其中给定最小支持度阈值min_count=2.
2） 根据所得关联矩阵（1）的性质，并且满足sup_count>=2,得到各1-频繁项集如下：L1={A:5,B:7,C:6,D:6,E:3,F:5}.
3) 基于Apriori算法由L1产生2-候选项集C2={AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF}.
根据定义5可得例如2-项集{AB}的支持度计数如下所示：
sup_count{AB}=s110∧s210=(1100000001)=3.
同理可计算出其余2-项集的支持度计数并且满足sup_count>=2的所有2-频繁项集L2={AB:3,AC:3,AD:3,AE:2,AF:2,BC:4,BD:6,BF:3,CD:3,CE:2,CF:3,DF:2}.
4) 根据算法步骤（12）~（17）连接和剪枝得到3-频繁项集，具体过程如下：
①连接C3=L2×L2={ABC,ABD,ABE,ABF,BCD,BCF,BDF,CDE,CDF,CEF};
②剪枝：由Apriori的基本性质得，如果候选k项集的k-1项集子集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除.因而得到
C3={ABC,ABD,ABF,BCD,BCF,BDF,CDF};
③计算3-候选项集{ABC}的支持度计数如下：
sup_count{ABC}=(s110∧s210)∧s310=(1100000001)∧(0101100111)=(0100000001)=2.同理可计算出其余3-项集的支持度计数并且满足sup_count>=2的所有3-频繁项集L3={ABC:2,ABD:3,BCD:3,BCF:2,BDF:2}.
5) 连接C4=L3×L3={ABCD,BCDF},由于{CDF}L3，故将其直接从C4中删除.故得到C4={ABCD},通过计算得到
sup_count{ABCD}=((s110∧s210)∧s310)∧s410=
4 结语
本文提出的算法是基于Apriori算法的思想，通过引入关联矩阵的概念对算法进行了改进，并且通过应用实例进行分析，在分析过程中可以发现本文提出的AMFM只需扫描1次数据库，转换成关联矩阵，之后只需运用本文定义的支持度定义进行判断是否频繁，无须重复扫描数据库，进而提高了算法的效率，从一定程度上降低了时间复杂度.然后对于关联规则算法的研究目前已经比较成熟，本文所提出的算法还有待改进的地方以及提高，比如能否对此算法再次进行改进，从而不需要产生候选项集，直接应用该关联矩阵挖掘出所有的频繁项集，这将在后期的工作中加以研究.
(下转第144页)
摘要: 根据经典Apriori性质和算法思想，提出了一种基于关联矩阵的挖掘频繁项集的算法.应用实例分析表明，该算法在挖掘过程中，只需扫描一次数据库，有效地减少了扫描数据库的次数，提高了算法的效率.
关键词: Apriori算法；关联矩阵；频繁项集
:A文章编号:1672-8513(2012)02-0138-03
An Algorithm for Mining Frequent Itemsets Based on Associated Matrix
ZHANG Yafen,WANG Xin
(School of Mathematics and Computer Science, Yunnan University of Nationalities, Kunming 650500, China)
Abstract: According to the ideas and properties of the classical Apriori algorithm, a new algorithm for mining frequent itemsets is proposed, which is based on the associated matrix. Through the analysis of the example, it has been found that this algorithm scans the database only for one time and reduces the number of scanning during the mining process, and improves the efficiency of the algorithm.
Key words: Apriori algorithm; associated matrix; frequent itemsets
关联规则挖掘是指从海量的数据库中挖掘项集之间有趣的模式或者是相关关系.此概念以及经典的Apriori算法最初是由Agrawal等［1-2］提出的，该问题主要包括频繁项集的产生和由频繁项集得到的关联规则的产生［3-4］，而其核心问题是频繁项集的挖掘.因此对于该问题的研究是至关重要的，目前许多相关研究人员对该问题进行大量的研究和探讨，主要的算法都是基于对经典Apriori算法和FP-Growth算法［5］的改进.本文通过介绍图的关联矩阵概念，然后对其作相关定义上的修改,从而运用到频繁项集的挖掘算法中，提出了一种新的基于关联矩阵的频繁项集挖掘算法（Frequent Itemsets Mining Algorithm Based on Associated Matrix, AMFM）.并且通过应用实例说明该算法较Apriori算法是有效的，在挖掘过程中，只需扫描一次数据库，从一定意义上降低了时间复杂度，提高了算法的效率.
1 基本概念
设I={i1,i2,…,im}是项的集合，设任务相关的数据D={T1,T2,…,Tn}是事务数据库的集合，其中每个事务T是项的集合，使得TI.每个事务都有一个标识符，记为TID.
定义1 （项集、k项集、频繁项集）如果AT，则称A是一个项集，并且定义包含k个项的项集称为k项集.对于一个项集A，如果其支持度大于等于用户给定的最小支持度阈值min_sup，则A为频繁项集.
关联规则发现的任务是指挖掘出同时满足最小支持度（min_sup）和最小置信度（min_conf）阈值的规则［6］.因此在挖掘过程中对于频繁项集的计数从而计算其支持度是最关键的.
定义2 （图的关联矩阵）［7-8］设G=为无向图，且V={v1,v2,…,vn}表示顶点的集合，E={e1,e2,…,em}表示边的集合，则图G=的关联矩阵M=(mij)为n×m阶矩阵.其中
mij=1,若vi关联ej,0,若vi不关联ej .
基于上述图的关联矩阵的定义，显然这是1个布尔矩阵，而事务数据库的数据是满足布尔矩阵的特征的，因而可以类似地定义项集的关联矩阵.
定义3 （项集的关联矩阵）设I={i1,i2,…,im}是项的集合， D={T1,T2,…,Tn}是事务数据库的集
2 基于关联矩阵的频繁项集挖掘算法
2.1 AMFM算法基本思想
本文所提出的AMFM算法是基于经典的Apriori算法思想，即采用的是一种宽度优先搜索方法，通过连接（k-1）频繁项集产生k候选项集和利用Apriori性质对所产生的候选项集进行压缩和剪枝.Apriori算法在寻找每个k频繁项集的过程中需要扫描一次数据库，也就是说对于一个简单的事务数据库,如果包含10个项集，则采用Apriori算法产生所有的频繁项集需要扫描10次数据库，耗时较多.为避免多次扫描数据库，本文提出了基于关联矩阵的概念，将其应用于频繁项集挖掘中，从而使得在挖掘过程中只要扫描一次数据库，将其转换为关联矩阵，然后通过本文定义的支持度计数方法进行计数，每次只需要计算相应的“与”计算即可判断是否满足支持度阈值，从而确定频繁项集，大大减少了数据库扫描的次数，提高了算法的效率.该算法中的（1）~（7）部分是关联矩阵的生成过程；步骤（8）是利用关联矩阵的相关性质寻找所有的1-频繁项集；（9）~（23）部分是整个算法的核心，包括候选项集的产生和计数，在进行候选项集产生的过程中主要利用了Apriori算法的性质和先验知识：任何非频繁的（k-1）项集源于：7彩论文网党校毕业论文www.7ctime.com
都不是频繁k项集的子集，基于此对产生的候选项集进行连接和剪枝；步骤（24）利用关联矩阵的k-项集的支持度计数方法进行计数，并论文导读：CDF};③计算3-候选项集{ABC}的支持度计数如下：sup_count{ABC}=(s110∧s210)∧s310=(1100000001)∧(0101100111)=(0100000001)=2.同理可计算出其余3-项集的支持度计数并且满足sup_count>=2的所有3-频繁项集L3={ABC:2,ABD:3,BCD:3,BCF:2,BDF:2}.5)连接C4=L3×L3=
且与给定的最小支持度计数阈值进行比较；步骤（26）得到的是支持度计数不小于最小支持度计数阈值的所有频繁项集.
3 应用实例分析
下面给出如表1所示的小型事务数据库［9~10］，它包含了10条交易数据记录和6个项.其中T1~T10表示每条交易的标识符号，字母A~F表示每条交易所包含的对象.若以购物篮分析为例，字母A~F可以具体地表示为顾客所购买的商品名称.将本文算法应用于该数据库的频繁项集挖掘，具体过程如下所示.其中给定最小支持度阈值min_count=2.
2） 根据所得关联矩阵（1）的性质，并且满足sup_count>=2,得到各1-频繁项集如下：L1={A:5,B:7,C:6,D:6,E:3,F:5}.
3) 基于Apriori算法由L1产生2-候选项集C2={AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF}.
根据定义5可得例如2-项集{AB}的支持度计数如下所示：
sup_count{AB}=s110∧s210=(1100000001)=3.
同理可计算出其余2-项集的支持度计数并且满足sup_count>=2的所有2-频繁项集L2={AB:3,AC:3,AD:3,AE:2,AF:2,BC:4,BD:6,BF:3,CD:3,CE:2,CF:3,DF:2}.
4) 根据算法步骤（12）~（17）连接和剪枝得到3-频繁项集，具体过程如下：
①连接C3=L2×L2={ABC,ABD,ABE,ABF,BCD,BCF,BDF,CDE,CDF,CEF};
②剪枝：由Apriori的基本性质得，如果候选k项集的k-1项集子集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除.因而得到
C3={ABC,ABD,ABF,BCD,BCF,BDF,CDF};
③计算3-候选项集{ABC}的支持度计数如下：
sup_count{ABC}=(s110∧s210)∧s310=(1100000001)∧(0101100111)=(0100000001)=2.同理可计算出其余3-项集的支持度计数并且满足sup_count>=2的所有3-频繁项集L3={ABC:2,ABD:3,BCD:3,BCF:2,BDF:2}.
5) 连接C4=L3×L3={ABCD,BCDF},由于{CDF}L3，故将其直接从C4中删除.故得到C4={ABCD},通过计算得到
sup_count{ABCD}=((s110∧s210)∧s310)∧s410=
2.故得到L4={ABCD：2} .
6） 连接C5=L4×L4=φ,到此整个算法结束.故最后得到所有的频繁项集记为：L=L1∪L2∪L3∪L4 .4 结语
本文提出的算法是基于Apriori算法的思想，通过引入关联矩阵的概念对算法进行了改进，并且通过应用实例进行分析，在分析过程中可以发现本文提出的AMFM只需扫描1次数据库，转换成关联矩阵，之后只需运用本文定义的支持度定义进行判断是否频繁，无须重复扫描数据库，进而提高了算法的效率，从一定程度上降低了时间复杂度.然后对于关联规则算法的研究目前已经比较成熟，本文所提出的算法还有待改进的地方以及提高，比如能否对此算法再次进行改进，从而不需要产生候选项集，直接应用该关联矩阵挖掘出所有的频繁项集，这将在后期的工作中加以研究.
(下转第144页)