Corresponding author: LIN Shu-kuan, E-mail: linshukuan@ise.neu.edu.cn
频繁项集挖掘是数据挖掘领域的研究热点，在顾客购买行为分析[1, 2]、网络入侵检测[3, 4]等许多领域有着广泛的应用.传统的频繁项集挖掘[5, 6, 7, 8]只依据项集出现的次数决定其频繁性，没有考虑项集的重要程度.近年来，高效用项集挖掘越来越受到关注[9, 10, 11, 12, 13]，这里，效用是综合考虑项集出现次数和重要程度(对应单价或权重)的衡量指标.给定最低效用阈值，效用高于该阈值的项集称为高效用项集.然而，在实际挖掘过程中，指定大小合适的效用阈值并不容易，给定的阈值过大或过小，都会影响高效用项集挖掘的效果.为此，本文对Top-k 高效用项集挖掘方法进行研究，用户无需指定效用阈值，Top-k 高效用项集挖掘将给出效用最高的前k个项集.然而，Top-k 高效用项集挖掘失去了向下封闭性，使挖掘中的剪枝过程面临挑战.已有的Top-k 高效用项集挖掘方法[14]为了保持向下封闭性，用项集所在的事务效用代替其真实效用对候选项集进行剪枝，使得项集的效用被估计得过高，剪枝效果不明显，导致挖掘效率低.针对这一问题，本文提出了基于索引效用的Top-k高效用项集挖掘方法，基于所提出的索引效用建立索引并进行剪枝，提高了Top-k 高效用项集挖掘的效率.
1 问题定义本文挖掘的数据对象为效用事务数据库，表 1是效用事务数据库的一个例子.
 | 表 1 效用事务数据库D Table 1 A utility transaction database D |
表 1所示的效用事务数据库共包括6个事务T1~T6及7个项A~G，每个事务T中包含的项i描述为一个三元组：(i,count(i,T),w(i,T))，其中，i为项的名称，count(i,T)为项i在事务T中的发生计数，w(i,T)为项i在T中的权重(即重要程度).在实际应用中，同一个项在不同的事务中可能具有不同的权重，本文充分考虑这种情况，项目的权重不是固定的，是与事务相关的可变量.
在高效用项集挖掘中，由项构成的集合称为项集，项集包含的项数称为项集的长度，长度为l的项集称为l-项集.
定义1 (项在事务中的效用)项i在事务T中的效用uoi(i,T)定义为项i在事务T中出现的次数count(i,T)与项i在T中的权重w(i,T)的乘积，即
定义2 (项集在事务中的效用)项集S在事务T中的效用uois(S,T)定义为项集S包含的所有项在事务T中的效用之和，即
定义3 (项集的效用)项集S的效用uois(S)即为S在整个效用事务数据库D中的效用，定义为S在所有包含S的事务中的效用之和，
Top-k高效用项集挖掘就是在效用事务数据库中挖掘出效用最高的前k个项集.
定义4 (边界阈值)在Top-k高效用项集挖掘的过程中，设当前的Top-k高效用项集为K={S1,S2,…,Sk}，则对于1≤p≤k，min(uois(Sp))称为当前的边界阈值.
初始的边界阈值设为0，随着Top-k高效用项集挖掘的进行，边界阈值将被不断提高.
定义5 (项集的事务效用)若将一事务T中包含的所有项在该事务中的效用之和称为该事务的效用，表示为uot(T)，则对于一项集S，包含S的所有事务的效用之和称为项集S的事务效用tuos(S)，即
已有Top-k高效用项集挖掘方法利用项集事务效用的向下封闭性，对候选项集进行剪枝[14].项集的事务效用将项集的真实效用扩大化，基于此进行剪枝效果不明显，导致挖掘效率低.针对这一问题，本文提出了基于索引效用和效用矩阵的Top-k高效用项集挖掘方法，一方面，通过建立效用矩阵，可对项集的效用进行快速计算，避免了已有挖掘方法中对效用事务数据库的多次扫描，提高了挖掘的效率；另一方面，引入索引效用的概念，并基于此建立索引及对索引进行剪枝，进一步提高了挖掘的效率.
2 效用矩阵的建立本文基于效用矩阵实现项集效用的快速计算.对于具有n个项i1,i2,…,in和m个事务T1,T2,…,Tm的效用事务数据库D，效用矩阵M是一个(m+1)行、(n+2)列的矩阵，1~m行分别对应D中的每一个事务，1~n列分别对应1~n项.对于m≥p≥1，n≥q≥1，元素Mpq为项iq在事务Tp中的效用uoi(iq,Tp)，第(m+1)行第q列的元素为1-项集iq的效用uois(iq)，第p行第(n+1)列的元素为事务Tp的效用uot(Tp)，第p行第(n+2)列的元素为事务Tp所包含的项数.
效用矩阵中的1~n列确定了效用事务数据库中各项之间的一种顺序，本文称为矩阵列序，表示为∠.为方便起见，本文约定所有项集中各项均按照矩阵列序排列.
通过一次扫描效用事务数据库，可生成效用矩阵以及各项所在的事务编号集合和最长事务长度.具体生成过程见算法1.
算法1 效用矩阵生成
输入：效用事务数据库D.
输出：效用矩阵M，各项所在的事务编号集合I，最长事务长度maxLength.
1) 矩阵M的每一元素初始化为0;
2) I=Φ; maxLength=0;
3) for q=1 to n,Iq=Φ;
4) for D中每个事务Tp
5) for Tp中的每一项iq
6) Mpq=uoi(iq,Tp);
7) Iq=Iq∪{p};
8) Mp(n+1)=Mp(n+1)+Mpq;
9) Mp(n+2)=Mp(n+2)+1;
10) if Mp(n+2)>maxLength then
maxLength=Mp(n+2);11) for q=1 to n
12) 计算M(m+1)q;
13) I=I∪Iq;
对于具有n个项i1,i2,…,in和m个事务T1,T2,…,Tm的效用事务数据库D，建立效用矩阵后，可以得到(n+m)个效用值，包括n个1-项集的效用u1=M(m+1)1,u2=M(m+1)2,…,un=M(m+1)n，以及m个项集在相应事务中的效用un+1=M1(n+1),un+2=M2(n+1),…,un+m=Mm(n+1)，将这(n+m)个效用和相应的项集按照降序进行排列，截取前k个项集可得到当前的Top-k高效用项集以及当前的边界阈值.
3 建立索引本文建立两级索引并提出索引效用的概念，在此基础上，对索引进行剪枝，从而减少项集效用的计算量，提高挖掘效率.
定义6 (项集在事务中的尾超集)对于项集S=i1i2…ir和事务T，若S⊆T，令S1={i|ir∠i且i∈T}，S’=S∪S1，则S’称为项集S在事务T中的尾超集，表示为Esuper(S,T).
定义7 (索引效用)对于项集S，其索引效用uoin(S)定义为S在所有包含它的事务中的尾超集的效用之和，即
按照定义7，借助于算法1生成的效用矩阵和各个项所在的事务编号集合，可快速计算所有1-项集和2-项集的索引效用，为建立两级索引提供支持.
本文所建的两级索引结构如图 1所示，其中，一级索引对应1-项集，二级索引对应以1-项集为首项的2-项集(是以1-项集为起始的超集).一级索引节点的指针P指向以相应的1-项集为首项的二级索引节点，二级索引节点的指针指向以相应的2-项集为起始的l-项集(l≥2，l-项集是以2-项集为起始的超集)链成的链表.索引节点和链表节点分别随着挖掘过程中的剪枝和迭代发生变化.索引效用uoin是相应索引项集的索引效用.flag是为了减少项集效用计算量而设置的一个标志变量，其值可根据索引项集的索引效用设为0或1，若flag=0，表明该索引节点指向的所有项集，其效用均无需进行计算，从而提高挖掘效率.
 | 图 1 两级索引结构 Fig. 1 The structure of the two-level index |
定理1 对于任一项集S和以S为起始的任一超集Super(S)，Super(S)的效用uois(Super(S))不超过S的索引效用uoin(S)，即uois(Super(S))≤uoin(S)
证明 略
由定理1，若项集S的索引效用不超过边界阈值，则以S为起始的所有超集均不可能成为Top-k高效用项集.本文将依据定理1构建两级索引，并在Top-k高效用项集挖掘的过程中，安全地对索引进行剪枝，从而提高挖掘效率.以定理1为依据，可按以下规则建立索引.
规则1 若一级索引项集的索引效用小于边界阈值，则不建立该一级索引节点.
规则2 若一级索引项集的索引效用不小于边界阈值，但其所有二级索引效用均小于边界阈值，则置该一级索引节点中的标志变量flag为0，表示以该一级索引为起始的所有项集均无需计算效用.
规则3 若二级索引项集的索引效用为0，则无需建立该二级索引节点.
规则4 若二级索引项集的索引效用大于0而小于边界阈值，则置该二级索引节点中的标志变量flag为0，表明该二级索引节点指向的链表中的所有项集效用均无需计算.
4 Top-k高效用项集挖掘本文在建立效用矩阵和两级索引的基础上，对Top-k高效用项集进行挖掘，具体过程如算法2所示.
算法2 Top-k高效用项集挖掘
输入：效用矩阵M，最长项集长度maxLength，两级索引，初始的Top-k高效用项集集合.
输出：最终的Top-k高效用项集.
1) cLength=maxLength;
2) while (cLength>1) do{
3) 查找效用矩阵第(n+2)列，得到cLength-项集及其所在的事务编号集合;
4) 将cLength-项集连同所在的事务编号集合按照索引插入相应链表;
5) 对于flag标志为1的索引节点，利用效用矩阵计算该节点指向的所有项集的效用;
6) 根据计算所得的项集效用提高边界阈值，并修改Top-k高效用项集集合;
7) 利用新的边界阈值对索引进行剪枝;
8) 将cLength-项集分裂为(cLength-1)-项集，并将cLength-项集从索引中删除;
9) cLength--;
10) }
从算法2可以发现，与已有的同类算法不同，算法2从高阶项集不断向低阶项集分裂，固定经过(maxLength-1)次循环，其中，maxLength为效用事务数据库中最长的项集长度.每次循环中，对于当前长度为cLength的项集，都要经过项集按索引插入链表、项集效用计算、根据新的项集效用提高边界阈值并对索引进行剪枝的过程，最终得到全部的Top-k高效用项集.与已有的Top-k高效用项集挖掘方法相比，算法2的高效性体现在：① 迭代过程从长项集向短项集分裂，可尽早获得较大边界阈值，剪枝效果更好；② 效用矩阵的建立，减少了对效用事务数据库的扫描次数，并可支持项集效用的快速计算；③ 基于项集的索引效用对索引剪枝的过程大大减少了需计算效用的项集数量.
5 实验及其评价为验证所提出的Top-k高效用项集挖掘方法的性能，本文在两个不同类型的数据集上进行了实验.一个是模拟生成的数据集TL10，事务的最大长度较小，是一个相对稀疏的数据集；另一个是真实数据集Mushroom，事务的最大长度较大，是一个较稠密的数据集.本文方法(index and matrix based Top-k utility,IMTKU)将与文献[14]中的方法(up-growth Top-k utility,UTKU)进行比较.
图 2给出了两种方法在数据集TL10上的挖掘时间比较(实验中k的取值分别为1,10,100,500,1 000).可以看出，IMTKU的挖掘效率优于UTKU，且随着k值的增大，优势越来越明显.这是因为，IMTKU在挖掘过程中不断利用项集的索引效用对索引进行剪枝，使得需要计算效用的项集数量大为减少，同时，借助于效用矩阵加快了项集效用的计算时间.而UTKU在挖掘过程中产生大量的候选项集，且利用项集的事务效用剪枝效果不明显，因此，需要计算效用的项集数量比较多.当k值较大时，UTKU方法中上述问题更加突出，使得两种方法的差距更加明显.
 | 图 2 两种方法在数据集TL10上的挖掘效率比较 Fig. 2 The mining efficiency comparison of the two methods on TL10 |
图 3给出了两种方法在数据集Mushroom上的挖掘时间比较(实验中k的取值分别为1,10,100,500,1 000).可以看出，当k值较大时，IMTKU具有明显的优势.这是因为数据集Mushroom中最长事务长度较大，导致IMTKU在挖掘过程中迭代次数较多，当k值较小时，IMTKU的挖掘效率较低.但是，UTKU用项集的事务效用估计项集的真实效用，剪枝效果不明显，当k值较大时，需要计算效用的候选项集数量大量增加，因此，UTKU的挖掘时间迅速增加，超过IMTKU所需要的时间.
 | 图 3 两种方法在数据集Mushroom上的挖掘效率比较 Fig. 3 The mining efficiency comparison of the two methods on Mushroom |
图 4给出了在数据集TL10上两种挖掘方法的扩展性实验结果.从图 4可以看出，随着效用事务数据库中事务数量的增多，两种方法的挖掘时间均随之增大，并呈线性增长，均具有较好的扩展性.但由于建立了效用矩阵和索引并基于索引效用进行剪枝，IMTKU的挖掘效率一直高于UTKU，且数据库中的事务数量越多，优势越明显.
 | 图 4 两种方法的扩展性 Fig. 4 The scalabilities of the two methods |
1) 本文对Top-k高效用项集挖掘方法进行研究，针对已有方法利用项集的事务效用进行剪枝效率较低的问题，提出了索引效用的概念，在此基础上，建立两级索引并基于索引效用进行索引剪枝，大大减少了需计算效用的项集数量，提高了Top-k高效用项集挖掘的效率.
2) 本文通过建立效用矩阵，支持对项集效用的快速计算，同时只需对效用事务数据库进行一次扫描，进一步提高了挖掘效率.
3) 不同类型数据集上的实验表明，本文所提出的Top-k高效用项集挖掘方法对于事务长度较短的数据集和较大的k值具有非常明显的优势，并具有良好的扩展性.
| [1] | Han J, Kamber M, Pei J.Data mining:concept and technique[M].3rd ed.Beijing:China Machine Press, 2012.( 1) |
| [2] | Brin S, Motwani R, Ullman J D, et al.Dynamic itemset counting and implication rules for market basket data[C]// Proceedings of ACM SIGMOD Conference on Management of Data.Tucson, 1997:255-264.(1) |
| [3] | 毛国君, 宗东军.基于多维数据流挖掘技术的入侵检测模型与算法[J].计算机研究与发展, 2009, 46(4):602-609. (Mao Guo-jun, Zong Dong-jun.An intrusion detection model based on mining multi-dimension data stream[J].Journal of Computer Research and Development, 2009, 46(4):602-609.)(1) |
| [4] | 杨欢, 张玉清, 胡予濮, 等.基于权限频繁模式挖掘算法的Android 恶意应用检测方法[J].通信学报, 2013, 34(Z1):106-115. (Yang Huan, Zhang Yu-qing, Hu Yu-pu, et al.Android malware detection method based on permission sequential pattern mining algorithm[J].Journal on Communications, 2013, 34(Z1):106-115.)(1) |
| [5] | Agrawal R, Srikant R.Fast algorithms for mining association rules[C]// Proceedings of the 20th VLDB Conference.Santiago de Chile, 1994:487-499.(1) |
| [6] | Agrawal R, Imielinski T, Swami A.Mining association rules between sets of items in large databases[C]// Proceedings of the ACM SIGMOD Conference on Management of Data.New York:ACM Press, 1993:207-216.(1) |
| [7] | Pei J, Han J, Lu H, et al.H-Mine:hyper-structure mining of frequent patterns in large databases[C]// IEEE International Conference on Data Mining.Piscataway, 2001:441-448.(1) |
| [8] | Han J, Pei J.Mining frequent patterns without candidate generation:a frequent-pattern tree approach[J].Data Mining and Knowledge Discovery, 2004, 8(1):53-87.(1) |
| [9] | Yao H, Hamilton H J, Geng L.A unified framework for utility-based measures for mining itemsets[C]// Proceedings of ACM SIGKDD 2nd Workshop on Utility-Based Data Mining.Philadelphia, 2006:28-37.(1) |
| [10] | Tseng V, Wu C W, Shie B E, et al.UP-growth:an efficient algorithm for high utility itemset mining[C]// Proceedings of KDD’10.Washington DC, 2010:253-263.(1) |
| [11] | Song W, Liu Y, Li J H.Vertical mining for high utility itemsets[C]// Proceedings of IEEE International Conference on Granular Computing.Hangzhou, 2012:429-434.(1) |
| [12] | Liu J, Wang K, Fung B.Direct discovery of high utility itemsets without candidate generation[C]// Proceedings of ICDM’12.Brussels, 2012:984-989.(1) |
| [13] | Lin C W, Hong T P, Lan G C, et al.Incrementally mining high utility patterns based on pre-large concept[J].Applied Intelligence, 2014, 40(2):343-357.(1) |
| [14] | Wu C W, Shie B E.Mining top-k high utility itemsets[C]// Proceedings of KDD’12.Beijing, 2012:78-86.(3) |