高效用项集挖掘(High Utility Itemsets Mining,HUIM)已成为数据挖掘领域研究工作的关键。高效用项集挖掘是为了解决频繁项集挖掘只考虑出现频次的问题,高效用项集挖掘同时考虑事务数据库中项目数量和单位利润。先前大部分HUIM算法只考虑项目存在正效用的情况,然而实际应用中会存在负效用项集。根据先前高效用项集挖掘算法相关修剪策略,低效用项集的子集必是低效用项集。但是事务中存在负效用项,低效用项集的子集可能是高效用项集,因此含负效用项的高效用项集可能会被忽略。不仅如此,现有HUIM算法执行方面,阈值需要用户设定。而在实际应用中阈值的设定直接影响输出结果集的数量,从而极大地影响算法运行效率。阈值过高使得无结果产生,用户不能得到高效用项集(HUIs);阈值过低导致算法运行时间无限增长并且占用大量内存,甚至导致内存溢出。设定合适的阈值是一个困难的问题。针对上述问题本文对高效用项集挖掘算法存在负效用项和阈值设定方面进行研究,研究工作主要如下:(1)针对数据集中包含负效用项的问题,提出含负效用项的高效用项集挖掘算法EHUIN(Efficient High Utility Itemsets Mining with Navigate utility)。算法在第一次扫描数据库时使用覆盖理论指导方法,在初始化链表时对事务加权效用值相等的项集进行覆盖操作。随后在含负效用的传递分支公式tenu(transitive extension with negative utility)帮助下,将链表中项集效用与其传递分支项集效用之和与用户设定最小效用阈值比较,若小于最小效用阈值则项集的传递分支项集均为低效用项集并舍弃。在构建效用链表时使用提前过滤策略,通过计算元组中效用值来判定该效用链表是否为低效用链表,从而降低运行时间,减少内存消耗,进一步提高挖掘效率。经过近60万条数据24组实验证明在数据集稠密程度不一致的情况下,EHUIN算法效率更高,尤其是在稠密数据集上表现更佳。(2)针对最小效用阈值设定的问题,高效用项集挖掘算法通过和Top-k算法结合,将设定阈值的问题转变成设定高效用项集数量的问题。目前Top-k高效用项集挖掘算法主要研究方向是改进数据结构和优化效用链表的构建过程,但忽略效用链表构建后的内存管理。随着数据量增大,挖掘高效用项集所需构建的效用链表增多却无法管理内存资源,之前的算法运行时占用系统大量内存空间和计算开销。针对这一问题,提出新的Top-k高效用项集挖掘算法TKBPH(Top-k Buffer Pool High Utility Mining)。TKBPH算法提出数据缓冲池(DBP)结构管理内存空间,高效存储与检索缓冲池内数据,并在挖掘过程中进行内存复用。在不同类型数据集实验结果证明,TKBPH算法在挖掘过程中执行速度更快,内存消耗更少。
为了挖掘满足用户特殊需求,如含指定项目数量的高效用项集(HUI),提出一种基于长度约束的蝙蝠高效用项集挖掘算法(HUIM-LC-BA)。该算法融合蝙蝠算法(BA)和长度约束构建高效用项集挖掘(HUIM)模型,首先将数据库转换为位图矩阵,实现高效的效用计算和数据库扫描;其次,采用重新定义的事务加权效用(RTWU)策略缩减搜索空间;最后,对项集进行长度修剪,使用深度优先搜索和轮盘赌注选择法确定修剪项目。在4个数据集的仿真实验中,当最大长度为6时,与HUIM-BA相比,HUIM-LC-BA挖掘的模式数量分别减少了91%、98%、99%与97%,同时运行时间也少于HUIM-BA;且在不同长度约束条件下,与FHM+(Faster High-utility itemset Ming plus)算法相比运行时间更稳定。实验结果表明,HUIM-LC-BA能有效挖掘具有长度约束的HUI,并减少挖掘模式的数量。
针对现有的跨级高效用项集挖掘(HUIM)算法非常耗时且占用大量内存的问题,提出一种基于数据索引结构的跨级高效用项集挖掘算法(DISCH)。首先,为了高效存储和快速检索到搜索空间中的所有项集,拓展带有分类信息和索引信息的效用链表为数据索引结构(DIS);然后,为了提高内存利用率,对不满足条件的效用链表所占的内存进行回收再分配;最后,在构建效用链表时使用提前结束策略,以减少效用链表的产生。基于真实零售数据集和合成数据集进行的实验结果表明,与CLH-Miner(Cross-Level High utility itemsets Miner)算法相比,DISCH在运行时间上平均降低了77.6%,同时在内存消耗上平均降低了73.3%,可见该算法能高效完成跨级高效用项集的搜索,并且降低算法的内存消耗。
暂无评论