含负项top-k高效用项集挖掘算法

孙 蕊，韩 萌，张春砚，申明尧，杜诗语

（北方民族大学计算机科学与工程学院，银川 750021）

0 引言

近年来，数据挖掘技术引起了信息产业的极大关注。其中，频繁项集挖掘是数据挖掘的重要组成部分之一。频繁项集［1］的目标是发现满足最小支持度阈值的所有项集。但是，在实际应用中，频繁项集挖掘算法具有一定的局限性。它假定所有项具有相等的价值，并且每个项在每次事务中出现的次数不超过一次。但是，这两个假设在现实生活中不是普遍存在的。例如，客户购买6袋面包和1台电脑，客户购买多个相同的商品非常普遍，而出售面包和电脑的利润却有所不同。为了解决这一问题，研究人员提出了高效用项集挖掘算法。高效用项集（High Utility Iteme，HUI）［2］挖掘算法的主要目标是通过考虑用户的偏好（例如利润、数量和成本）来挖掘效用值高的项集。高效用项集挖掘算法克服了频繁项集挖掘算法带来的限制，在挖掘过程中，项的数量可能出现多次，并且每个项都有不同的价值。由于高效用项集挖掘算法缺乏向下闭合属性，因此搜索空间很难缩小。随后，Liu等［2］提出了一种Two-Phase算法，该算法使用向下闭合属性来减小搜索空间，并有效地找到高效用项集。随后，研究人员提出了IHUP（Incremental High Utility Pattern）［3］、TWU（Transaction Weighted Utility）-Mining［4］、IIDS（Isolated Items Discarding Strategy）［5］、UP-Growth（Utility Pattern Growth）［6］、UP-Growth+［7］算法。但是，以上提出的算法在挖掘过程中会生成大量的候选项集，这导致了算法执行时间长和内存消耗大的问题。Liu等［8］提出了一阶段HUI-Miner（High Utility Itemset Miner）算法，该算法依赖效用列表结构，可以有效地修剪大部分搜索空间。……