关于Top-N最频繁项集挖掘的研究

朱颢东，李红婵

(郑州轻工业学院计算机与通信工程学院 郑州 450002)

随着最频繁项集数目的增加，文本关联规则的个数及其相应的挖掘算法的时空复杂度都急剧上升，使最频繁项集的挖掘成为文本关联规则挖掘中研究的重点和难点[1-15]。在最频繁项集挖掘过程中，最小支持度阈值是一个十分关键的参数，该参数一般都是通过人工指定，但主观指定方式很难符合客观实际。参数值指定过高，导致一些有价值的规则丢失；参数值指定过低，导致规则数量剧增，生成许多无用规则，降低挖掘算法的性能。文献[1]表明：当语料库的文档为1 000篇、文本事务集的特征数目达到100个、最小支持度阈值为0.1时，其频繁项集的数目高达2 316个，产生的规则数量十分巨大，但有用的规则却很少。

为了解决上述问题，已有众多学者提出了一些相关的算法[1-15]，大都摈弃最小支持度阈值，通过指定最频繁项集的数量N控制所生成的频繁项集规模。这些算法的不足之处在于：由于没有设定最小支持度阈值，在挖掘过程中很可能对支持度较小的频繁项集也进行处理，使算法的时空复杂度较高，尤其在文档数量巨大时，时空复杂度会更高。

为了克服IntvMatrix算法的不足，本文借用文献[3]动态调整支持度阈值的思想，提出一种基于集合和倒排表的Top-N最频繁项集挖掘算法。通过实验对比，该算法优于NApriori算法和IntvMatrix算法。

1 相关知识

定义 1 把全部项集依照支持度从大到小排序，假设NS等于第N位项集的支持度，则最频繁项集：

因为支持度等于NS的项集个数可能有多个，Top-N中的最频繁项集的数目有可能多于N个。例如，如果第N+1、N+2、…、N+m个项集的支持度也是NS，则Top-N由N+m个频繁项集组成。

定义 2 把全部k-项集依照支持度从大到小排序，假设NSk等于第N位的k-项集的支持度，则最频繁k-项集：

命题 1 假设Top-N的最小支持度是NS，Top-Nk的最小支持度是NSk，则NS>=NSk。

证明 假设NS

由命题2可知，在生成Top-N的过程中，当前最小支持度阈值被逐步增大，减少了候选项集的规模，提高了算法效率。

2 本文所提推论

倒排表是一种高级索引结构，由词表和文档表两部分组成。词表由文档集中的特征词组成，对词表的任一特征词，在文档表中都有一行与包含该特征词的文档ID所对应。在IR领域，倒排表常用于文本索引，可以提高查找速度。

表1为一个文档事务数据库，表2是其相应的倒排表。

表1 文档事务数据库

表2 相应的倒排表

倒排表虽然在一定程度上提高了单一特征词的查找效率，也即1-项集的查找效率，但是对其他k-项集而言，很难获得相应的支持度，这是因为倒排表使得出现在同一事务中的各个项之间变得相互独立；并且从表2还可以看出，倒排表存在大量空元素，极大地浪费了内存空间。因此，本文对倒排表进行了改造。

(1) 在词表中，各项按其文档频从大到小的顺序排序，并用序号表明其位置。此时的词表由序号、项名、指向文本事务集合的指针3部分组成。

(2) 文档表中，每一行表示一个集合，集合元素由特征出现的文本事务号组成。此时表中各项以其所包含的元素个数降序排列。表3为改造后对应的倒排表。

根据推论2，在进行连接操作时就不需要再次扫描数据库，如连接时a与e只需对它们的指针所指的集合取交集，就能够提高算法效率。a与e连接结果如表4所示。

表3 改造表1后的倒排表

表4 a与e连接结果

推论 3 设Lk为K-频繁项集的集合，如果Lk中的项集个数不大于K，则Lk为极大频繁项集。

证明 经典Apriori算法指出，任何强项集的子集必定是强项集。因此可知，如果存在Lk+1(即K+1频繁项集的集合)，则∀lk+1∈Lk+1，lk+1一定有K+1个k-频繁子集在Lk中，因此，如果Lk的项集个数不大于K，则必定不能生成Lk+1。推论得证。

根据推论3，在产生(k+1)-项候选频繁项集之前，先统计k-项频繁集中项集的个数，如果数目<=k，则算法可以终止，也能提高算法效率。

推论 4 设∀lk∈Lk(Lk为k-频繁项集)，∀Item∈lk，如果Item在Lk中的支持数小于K，则lk不能用于生成Lk+1。

证明 经典Apriori算法指出，任何强项集的子集必定是强项集。因此可知，∀lk+1∈Lk+1，lk+1中必然存在K+1个k-频繁项集属于Lk。明显有∀Item∈lk，在lk的K+1个k-频繁项集中，Item的支持数至少为K。所以，∃Item∈lk，且Item在Lk中的支持数小于K，则lk不能用于生成Lk+1。推论得证。

根据推论4，如果某个k-项频繁项集中的一项在其中出现的次数

3 本文算法

3.1 本文算法思想

借用文献[3]中动态调整支持度阈值的思想，利用文中所给出的几个命题和结论，将倒排表和集合相结合，可以获得一个Top-N最频繁项集挖掘算法。

3.2 算法描述

输入：文本事务数据库D，最小支持数0δ(初始值为1)，频繁项集数N；

输出：Top-N最频繁项集。

步骤 1 扫描D以产生改造的倒排表W。

3.3 本文算法过程说明

Procedure Delete(Lk−1)//从Lk−1中删除包含项次数小于k−1的项集；

4 实验验证及其分析

4.1 实验验证

实验使用数据集由从新华网上下载的新闻材料组成。新闻材料的发表日期范围为2006～2008年，共1 500篇，经预处理后(忽略所有的报头)，挖掘该数据集的频繁项集并进行实验，比较本文算法与文献[3]提出的NAprioir算法和文献[5]提出的IntvMatrix算法的性能差异。

实验 1 比较3种算法在所选择数据集上挖掘出的规则数目和有效规则数，结果如表5所示。

表5 3种算法的有效规则率对比

实验 2 比较3种算法对不同规模的频繁项集进行挖掘时所消耗的时间，从实验结果选取差别较明显的实验数据作对比图，如图1所示。

图1 3种算法执行时间对比

4.2 实验分析

从表5可以看出，由于本文算法采用支持数动态自适应调整策略，所挖掘的规则有效率较高；IntvMatrix算法的规则有效率次之；Napriori算法产生了大量无意义的规则，规则有效率最低。

从图1可以看出，在频繁项集个数相同的情况下，本文算法的时间性能明显优于IntvMatrix和Napriori算法，分析其原因在于：

(1) 本文算法采用倒排索引这种数据结构组织事务集，提高了检索速度。

(2) 本文算法扫描数据库过程的步骤1中，以改造后的倒排表组织文档并对其进行扫描，这是该算法唯一一次扫描数据库，对于海量数据库来说，其时间效率的提高很明显。

(3) 本文算法中Count(Lk−1)函数用来计算Lk−1中频繁集的个数，根据推论3，如果Lk−1中频繁项集的个数小于k，则无需再生成Lk，此时算法可以结束，也提高了算法的时间效率。

(4) 根据推论4，Delete(Lk−1)函数用来从Lk−1中删除包含项次数小于k−1的项集，从而减少k-项候选集的数目，可以解决“候选项集瓶颈”问题，也提高了算法的时间效率。

(5) 本文算法中，Candidate_gen(Lk′−1)函数主要用于生成k-项候选集，它分别调用jion(l1,l2)和has_infrequent_subset(c,Lk−1)两个函数。其中jion(l1,l2)函数用于实现频繁项集的连接及求两个事务集合的交集(推论2)；has_infrequent_subset(c,Lk−1)函数用于判断一个k-项候选集的k−1子集之中是否有非频繁项集，如果有则该k-项候选集被删除，否则该k-项候选集被加入到k-项候选集集合之中(推论1)。

5 结 束 语

本文针对高维文本特征空间中仅以最小支持度阈值为约束条件产生的频繁项集规模难以确定的不足，在分析NApriori和IntvMatrix两个经典算法的基础上，提出了一种基于倒排表和集合的TOP-N最频繁项集算法。通过分析和实验表明，无论是在规则有效率方面，还是时间效率方面，本文算法都优于NApriori算法和IntvMatrix算法，使本文算法在文本关联规则挖掘中有一定的应用价值。

[1] 陈晓云. 文本挖掘若干关键技术研究[D]. 上海: 复旦大学, 2005.CHEN Xiao-Yun. Research on several key technology of text mining[D]. Shanghai: Fudan University, 2005.

[2] HAN Jia-wei, PEI Jian, YIN Yi-wen. Mining frequent patterns without candidate generation:a frequent pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004,8(1): 53-87.

[3] FU A W C, KWONG R W W , TANG J. MiningN-most interesting itemsets[C]//Proceedings of 2000 ISMIS. Berlin:Springer, 2000: 59-67.

[4] BODON F. A survey on frequent itemset mining[C]//Proceedings of the ACM SIGKDD Workshop on OSDM ’04.Chicago, USA: [s.n.], 2004: 523-531.

[5] 陈晓云, 胡运发.N个最频繁项集挖掘算法[J]. 模式识别与人工智能, 2007, 20(4): 512-518.CHEN Xiao-yun, HU Yun-fa. Mining algorithms ofN-most frequent itemsets[J]. PR & AI, 2007, 20(4): 512-518.

[6] HAJJ M E, ZAIANE O R. Inverted matrix: Efficient discovery of frequent items in large datasets in the context of interactive mining[C]//2003 Int’1 Conf on Data Mining and Knowledge Discovery (ACM SIGKDD). California,USA: [s.n.], 2003: 109-118.

[7] HAJJ M E, ZAIANE O R. Non recursive generation of frequent k-itemsets from frequent pattern tree representations[C]//Proceedings of 5th International Conference on Data Warehousing and Knowledge Discovery.Melbourne: Australia, 2003: 371-380.

[8] RACZ B. NonordFP：an FP-growth variation without rebuilding the FP-tree[C]//Proceedings of the IEEE ICDM Workshop on FIMI ’04. Brighton, UK: [s.n.], 2004:1089-1097.

[9] LIU Gui-mei, LU Hong-jun. AFOPT: an efficient implemefitation of pattern growth approach[C]//Proceedings of the IEEE ICDM Workshop on FIMI ’04. Brighton, UK:[s.n.], 2004: 2056-2067.

[10] 陈 耿, 朱玉全, 杨鹤标, 等. 关联规则挖掘中若干关键技术的研究[J]. 计算机研究与发展, 2005, 42(10):1785-1789.CHEN Geng, ZHU Yu-quan,Yang He-biao. Study of some key techniques in mining association rule[J]. Journa1 of Computer Research and Development, 2005, 42(10):1785-1789.

[11] 陈晓云, 陈 祎, 王 雷, 等．基于分类规则树的频繁模式文本分类[J]. 软件学报, 2006, 17(5): 1017-1025.CHEN Xiao-yun, CHEN Wei, WANG Lei, et a1. Text categorization based on classification rules tree by frequent patterns[J]. Journal of Software, 2006, 17(5): 1017-l025.

[12] WU Fan, CHIANG S W, LINJ R. A new approach to mine frequent patterns using item-transformation methods[J].Information Systems, 2007, 32(7): 1056-1072.

[13] 战力强, 刘大昕. 频繁项集快速挖掘算法研究[J]. 哈尔滨工程大学学报, 2008, 29(3): 266-271.ZHAN Li-qiang, LIU Da-xin. Study on fast algorithm of frequent item-set mining [J]. Journal of Harbin Engineering University, 2008, 29(3): 266-271.

[14] 田 宏, 董爱杰. 基于向量矩阵的频繁项集挖掘算法[J].大连交通大学学报, 2008, 29(3): 74-77.TIAN Hong, DONG Ai-jie. A frequent itemsets mining algorithm based on vector matrix[J]. Journal of Dalian Jiaotong University, 2008, 29(3): 74-77.

[15] 张忠平, 李 岩, 杨 静. 基于矩阵的频繁项集挖掘算法[J]. 计算机工程, 2009, 35(1): 84-86.ZHANG Zhong-ping, LI Yan, YANG Jing. Frequent itemsets mining algorithm based on matrix[J]. Computer Engineering, 2009, 35(1): 84-86.