基于质数理论的最大频繁项集挖掘研究

【摘   要】   利用质数的特性，采用质数积代替事务将事务数据库转换成质数积数据集，采用数据集二维数组保存质数积之间的整除关系和最大公约数信息。PNMax算法利用数据集二维数组可以快速地挖掘出最大频繁项集，并且数据集二维数组在挖掘过程中将持续减少所占的空间。最后通过实验验证了算法的可行性和优越性。

【关键词】   质数;质数积;最大频繁项集;PNMax

Research on Mining Maximum Frequent Itemsets Based

on Prime Number Theory

Wang Lijun

（Department of Information Engineering， Anhui Institute of Economics Management， Hefei 230031， Anhui）

Abstract：Using the characteristics of prime number， the transaction database is transformed into a data set of prime product by using the product of prime number instead of transaction， and the two-dimensional array of data set is used to save the integer division relationship and the greatest common divisor information between the products of prime number. PNMax algorithm can quickly mine the maximum frequent itemsets by using this array， and this array will continue to reduce the space occupied in the mining process. Finally， the feasibility and superiority of the algorithm are verified by experiments.

Key words： prime number; product of prime numbers; maximum frequent itemsets;PNMax

〔中图分类号〕  TP301.6   〔文獻标识码〕  A             〔文章编号〕 1674 - 3229（2021）03- 0000 - 00

0     引言

挖掘最大频繁模式的经典算法有FP-Max[1]、DMFIA[2]、MaxMiner[3]和MAFIA[4]等。FP-Max算法相当于FP-growth[5]算法的扩展，生成初始FP-Tree[5]会需要长期存放，依旧采用递归方式进行挖掘，需要产生大量的条件模式树消耗大量的时空资源，并采用最大频繁项目树MFI-Tree[1]来保存最大频繁项目集。DMFIA算法依旧采用FP-Tree树存放事务信息，但该算法会产生过多冗余的候选项目集影响算法的执行效率。每种经典的算法都有各自的优势，但仍存在改进的空间。因此可以从优化存储事务信息的存储结构;减少产生条件存储结构的数量和规模;减少挖掘事务项的数量等策略来提高挖掘最大频繁模式算法的时空效率。

许多学者提出了一些新的改进方案，比如PFPMax算法[6]、NCFP-Max算法[7]等，PFPMax算法是基于压缩FP-树和数组技术的最大频繁模式挖掘算法，压缩FP-树是对FP-Tree进行改进，使得项头表的数目有所减少，从而达到减少递归调用的次数，并结合数组技术实现挖掘最大频繁模式;NCFP-Max算法可以实现不产生条件模式树，采用类似二维表格的项目表格进行位运算来获取最大频繁项集。

笔者将提出一种基于质数理论的最大频繁项集挖掘算法PNMax，该算法可以在不需要创建FP-Tree树结构的情况下，利用质数积二维数组进行数值运算来挖掘最大频繁项集。最后以实验方式验证了算法的可行性和优越性。

1     相关理论和研究

1.1   质数

质数（Prime Number）是一个大于1的自然数，而且除了1和本身外，不存在其他因数的数称为质数，也叫素数。

所有大于1的自然数，要么其本身就是质数，否则就可以分解成几个质数之积，并且这种分解是唯一的。

素数在数论中有着很重要的地位。质数具有很多性质：

（1）质数的因数只有1和本身;

（2）质数的个数有无限个;

（3）所有大于10 的质数的个位数都是1，3，7，9;

（4）大于3的素数只有6n-1和6n+1两种形式（n为大于等于1的整数），但符合这两种形式的数不一定是质数，如25不是质数;

质数常被应用到密码学、生物科学和军事领域。

1.2   定义与性质

频繁事务项与质数映射方法：设定最小支持度计数为min_sup，扫描一次事务数据库D后删除事务中的非频繁事务项，并将事务中的事务项根据事务项支持度计数大小进行降序，排序后得到的预处理事务数据库D， 获得项头表L，将支持度计数最大的频繁事务项映射为质数2，第二大的事务项映射为质数3，以此类推。举例设置最小支持度计数为4，预事务数据库D如表1所示，得到的项头表L如表2所示。

定义1：质数序列--将预处理事务数据库D中的事务根据频繁事务项与质数的映射关系进行相应的转换而得到的序列。如TID为1的事务{c，d，f，g}转换为质数序列{2，3，7，11}。

定义2：质数积--将质数序列中的所有质数相乘得到的数值。如质数序列{2，3，7，11}的质数积为462。

定义3：质数积数据集—将预处理事务数据库D中的所有事务都转换成质数序列，并计算出相应的质数积，并统计质数积相同的个数，按照质数积的大小进行降序排序，由质数积和统计计数形成的数据集。如表1预处理数据库D对应的质数积数据集表3所示

性质1：若两个事务的质数积数值相等，则这两个事务包含的事务项完全相同。

证：根据预处理事务数据库的特点，每个事务中包含的事务项最多出现一次，根据频繁事务项与质数的映射关系，则每一个质数序列中包含的质数最多也出现一次，另外质数只存在1和本身的因子，不存在其他的因子，故质数积相等的两个事务包含的事务项也相同

性质2：若两个事务的质数积不相同，且存在整除关系，则质数积大对应的事务包含的项集是质数积小的事务对应项集的超集。

证：设事务T1对应的项集为{d1，d2，d3，…，dk}，对应的质数序列为{p1，p2，p3，…，pk}，则该事务的质数积TV1= p1*p2*p3*…*pk，若事务T2的质数积TV2不等于TV1，且可以整除TV1，则TV2=（ p1*p2*p3*…*pk）*TVother，根据频繁事务项与质数的映射关系，TV2对应的事务T2中必包含p1、p2、p3、…、pk所对应的事务项d1、d2、d3、…、dk，因此T2是T1的超集，T1是T2的真子集。

举例说明：质数积462可以整除质数积42，462的质数序列为{2，3，7，11}，对应的事务为{c，d，f，g}，质数积42的质数序列为{2，3，7}，对应的事务为{c，d，f}，则{c，d，f，g}是{c，d，f}的超集。

性质3：若两个事务的质数积存在最大公约数g，且g不为1，则这两个事务存在若干个相同的事务项。g也可以表示为一个质数或质数的乘积，g所对应的项集即为这两个事务最大的共同事务项的集合。

证：设两个事务T1和T2，对应的质数积为TV1和TV2，TV1和TV2的最大公约数为g，则TV1=g*TVother1，TV2=g*TVother2，根据质数积的产生方式和质数的特性，可知g也可以表示一个质数或质数的乘积，g所对应的项集必是T1和T2最大的共同事务项的集合。

举例说明：质数积462与质数积330的最大公约数为66，则66对应的质数序列为{2，3，11}，对应的项集为{c，d，g}是462对应的事务{c，d，f，g}和330对应的事务{c，d，e，g}的最大共同事务项组成的项集。

2     挖掘算法研究

本论文主要研究如何快速地挖掘最大频繁模式，通过频繁事务项与质数的映射转换后，预处理事务数据库转换成了质数积数据集，挖掘最大频繁模式的计算变成数值运算。每一个事务都是用质数积代替，另外，笔者将引用二维数组来存储质数积之间的整除关系和最大公约数信息，有了该二维数组的协助，我们不需要再建立FP-tree树结构和条件子FP-tree树结构，更不会采用递归挖掘方式挖掘最大频繁模式。

定义4：质数积二维数组--若质数积数据集包含m条记录，则需要创建一个规模为m*（m-1）/2的二维动态数组，该质数积二维数组有两个方面的功能，功能一存储质数积之间的整除关系和相关的计数信息;功能二是在功能一完成后才能使用的，用于存储质数积之间的最大公约数和相关的计数信息。

质数积二维数组的初始化：数组的对角线的元素值为相应质数积的质数积计数，其他元素值初始值为0，再根据质数积之间的整除关系将相应的元素值改为1（如462与42是整除关系，则将462与42交叠的元素值改为1），完成整除关系的元素值的修改后形成的初始质数积二维数组。

利用质数积二维数组挖掘最大频繁模式算法需要运用挖掘方法一和挖掘方法二两种方法，才可以提取出全部的最大频繁模式。

挖掘方法一：利用质数积的整除关系获取部分最大频繁项集;

具体描述：从最大的质数积开始向右运算，可通过质数积整除关系数组的非对角线元素值来判断质数积与其他质数积是否存在整除关系，若两个质数积对应的元素值为1，则表示这两个数存在整除关系，若存在整除关系则将除数的所在列的对角线元素的计数加上被除数的质数积计数（如462与42存在整除关系，则对角线元素值加1），以此类推，最终得到的质数积二维数组如图1所示。质数积整除关系数组的对角线元素值大于等于最小支持度计数的质数积所对应的项集将作为候选最大频繁项集，本例中42、15、14和10符合要求，由于42與14存在整除关系，因存在整除关系即项集之间就存在包含关系，根据最大频繁项集的真子集都不是最大频繁项集，故14舍弃。则最大频繁质数积项集为{42：4，15：5，10：5}

挖掘方法二：利用质数积的最大公约数获取剩余最大频繁项集

删除质数积整除关系数组中候选质数积所在列，本例中即删除42、15、14和10所在的列，将最大质数积所在列的对角线元素值初始化为该质数积计数，剩下所有列的元素值对挖掘最大频繁项集无影响，故不做清零操作，从剩下的最大质数积开始向右分别与其他质数积求最大公约数，并将最大公约数存放在两个质数积数交叠的元素位置上，并将这大质数积所在列的对角线元素值加上小质数积的质数积计数并将结果存放在较小的质数积所在列的对角线元素位置上，若该相加的值大于等于最小支持度计数则将该最大公约数作为候选最大频繁项集;完成第一遍最大公约数的计算后，继续向上开始第二遍向右分别求最大公约数，以此类推，若最左侧的最大公约数已经是质数则停止运算，以质数积462为例，其演算过程如下图：

运算完462的最大公约数计算后，继续运算330的最大公约数直到倒数第二个质数积即110。利用质数的最大公约数的求解方法得到候选最大频繁项集为{6：4，22：4}，因6是42的因子故舍弃，将{22：4}加入最大频繁质数积项集后，最终的最大频繁质数积项集为{42：4，15：5，10：5，22：4}。

利用解码器将各个质数积还原成项集得到的最大频繁项集为{{c，d，f：4}，{d，e：5}，{c，e：5}，{c，g：4}}

上述最大频繁模式挖掘过程需要充分的利用质数积二维数组，这两个挖掘方法中描述的运算都是简单的数值运算，且该数组也是数值型数组即可，存储空间较小，且挖掘过程中不需要创建树结构，也不存在递归调用。

3     伪算法描述

笔者将基于质数理论的最大频繁项集挖掘算法为PNMax的伪算法为：

定义函数 PNMaxFunction （）

形参：初始质数积二维数组PNArray，最小支持度计数min_sup

输出：最大频繁项集集合max_fi

PNMaxFunction （PNArray， min_sup）{

max_fi= ?;   //定义并初始化最大频繁项集集合max_fi

PN_max_fi= ?;   //定义并初始化最大频繁质数积项集集合PN_max_fi

获取PNArray的行数m;

FC1（）;  //调用FC1（）方法，执行挖掘方法一

FC2（）;  //调用FC1（）方法，执行挖掘方法二

FC3（）;  //调用FC3（）方法，删除非最大频繁质数积项集并转换成最大频繁项集

FC1（）{  //定义挖掘方法一的功能

For（i=m-1;i>=1;i- -）{  //从最后一行即行标为m-1开始遍历

For（j=1;j<=m-1;j++）{

If（PNArray[i][j]==1）{

PNArray[m-1-j][0]+=PNList[j][1];// 包含统计计数加上被除数的质数积计数

}

}

}

For（k=m-1;k>=0;k- -）{

If（PNArray[k][0]>=min_sup）{

PNList[m-1-k][0]加入PN_max_fi;

删除PNList中行号为m-1-k的行;

}

}

}

FC2（）{  //定义挖掘方法二的功能

获取PN_max_fi中元素的个数n;

删除加入PN_max_fi的质数积的PNArray相关元素空间;

For（p=m-n-1;p>=1;p- -）

PNArray[p][0]= PNList[m-n-1-p][1];   //初始化正在运算的质数积的统计值

For（q= m-n-1;q>=1;q--）{

For（r=1;r<=q;r++）{

If（q= =p{

PNArray[q][r]=GCD（PNList[m-n-1-p][0]， PNList[（m-n-1-p）++][0]）;

}else{

PNArray[q][r]=GCD（PNArray[q+1][1]， PNArray[q+1][ ++r]）;

}

PNArray[q--][0]= PNArray[q [0]+ PNList[（m-n-1-p）++][1];//统计最大公约数包含个数

If（PNArray[q--][0]>= min_sup）{

将PNArray[q][r]加入PN_max_fi;

}

}

}

FC3（）{

删除PN_max_fi中可以作为其他质数积除数的质数积;

将PN_max_fi剩下的质数积转换成相应的最大频繁项集

}

}

4     实验验证

采用PNMax、FP-Max和DMFIA三种不同的算法对相同数据库集进行挖掘比较，三种算法挖掘出的最大频繁项集结果一致，从而验证了PNMax的可行性，通过图表的方式显示挖掘的执行时间和内存消耗情况分别如图3和图4所示，分析图表验证PNMax算法的优越性。

PNMax算法在两种类型的数据集上都具有较好的执行效率，PNMax算法的时间效率明显优于FP-Max和DMFIA算法，随着支持度阈值减少，PNMax算法的优越性越来越明显，因此PNMax算法更加优越。

5      結论与展望

PNMax算法在质数积二维数组的协助下可以通过数值运算即可快速地挖掘出最大频繁项集，即不需要创建FP-Tree树结构也不要递归调用，大大提高了执行效果和减少系统资源的浪费。下一步工作希望能将该算法运用到SPARK平台上实现分布式运算。

参考文献：

[1] Grahne G，Zhu J. High Performance Mining of Maximal Frequent Itemsets[EB/OL]. 2003-06-05/2014-07-06

[2] 宋余庆，朱玉全，孙志挥等.基于FP-Tree的最大频繁项目集挖掘算法[J].软件学报，2003，14（9）：1586-1592

[3] R J Bayardo.Efficiently mining long patterns from databases[C] .ACM SIGMOD Record：ACM，1998：85-93

[4]Burdick D，Calimlim M，Gehrke J.Mafia：A Maximal Frequent Itemset Algorithm for Transactional Database[A].In：Stuart Feldman ed，Proceeding of the 17th International Conference on Data Engineering[C].Washington：IEEE Computer Society Press，2001：443-452

[5]Han J，Pei J，Yin Y.Ming frequent patterns without candidate generation[C].ACM SIGMOD Record：ACM，2000：29（2）：1-12

[6] 马达，王佳强.一种基于压缩FP-树的最大频繁项集挖掘算法[J].长春理工大学学报（自然科学版），2009，32（3）：457-461

[7] 赵志刚，王芳，万.基于OWSFP_tree的最大频繁项目集挖掘算法 [J]. 计算机工程与设计，2013，34（5）：1687-1690

[收稿日期]   2020-03-16

[基金项目]   安徽省高校自然科学重点项目“基于spark分布式计算平台的高校教学大数据分析方法研究”（KJ2019A0965）;安徽经济管理学院教学研究项目 “基于SPOC平台的“五位一体”的高职教学模式推进研究”（yjjyxm201903）。

[作者简介]   王利军，（1983- ），男，硕士，安徽经济管理学院信息工程系讲师，研究方向：为数据挖掘、计算机应用。