Abstract: Mininng High Utility Itemsets (HUI) with negative items is one of the emerging itemsets mining tasks. In order to mine the result set of HUI with negative items meeting the user needs, a Top-k High utility itemsets with Negative items (THN) mining algorithm was proposed. In order to improve the temporal and spatial performance of the THN algorithm, a strategy to automatically increase the minimum utility threshold was proposed, and the pattern growth method was used for depth-first search; the search space was pruned by using the redefined subtree utility and the redefined local utility; the transaction merging technology and dataset projection technology were employed to solve the problem of scanning the database for multiple times; in order to increase the utility counting speed, the utility array counting technology was used to calculate the utility of the itemset. Experimental results show that the memory usage of THN algorithm is about 1/60 of that of the HUINIV (High Utility Itemsets with Negative Item Values)-Mine algorithm, and is about 1/2 of that of the FHN (Faster High utility itemset miner with Negative unit profits) algorithm; the THN algorithm takes 1/10 runtime of that of the FHN algorithm; and the THN algorithm achieves better performance on dense datasets.

Key words: itemset mining, high utility itemset, top-k itemset, negative item, positive item

摘要： 含负项高效用项集（HUI）挖掘是新兴的数据挖掘任务之一。为了挖掘满足用户需求的含负项HUI结果集，提出了含负项top-k高效用项集（THN）挖掘算法。为了提升THN算法的时空性能，提出了自动提升最小效用阈值的策略，并采用模式增长方法进行深度优先搜索；使用重新定义的子树效用和重新定义的本地效用修剪搜索空间；使用事务合并技术和数据集投影技术解决多次扫描数据库的问题；为了提高效用计数的速度，使用效用数组计数技术计算项集的效用。实验结果表明，THN算法的内存消耗约为HUINIV-Mine算法的1/60，约为FHN算法的1/2；THN算法的执行时间是FHN算法的1/10；而且该算法在密集数据集上的性能更好。

关键词: 项集挖掘, 高效用项集, top-k项集, 负项, 正项