衍生高效用模式挖掘算法综述.pdf

第 48 卷 第 2 期燕山大学学报Vol.48 No.22024 年 3 月Journal of Yanshan UniversityMar.2024 文章编号:1007-791X(2024)02-0138-19衍生高效用模式挖掘算法综述刘淑娟,韩 萌,高智慧,穆栋梁,李 昂(北方民族大学 计算机科学与工程学院,宁夏 银川 750021)收稿日期:2022-09-05 责任编辑:温茂森基金项目:国家自然科学基金资助项目(62062004);宁夏自然科学基金资助项目(2022AAC03279)作者简介:刘淑娟(1998-),女,河南新乡人,硕士研究生,主要研究方向为模式挖掘;通信作者:韩萌(1982-),女,河南商丘人,博士,教授,主要研究方向为大数据挖掘,Email:2003051 。摘 要:在数据挖掘领域中,高效用模式挖掘任务具有较高的理论研究价值和广泛的实际应用场景。针对多变的应用场合,提出了一系列衍生高效用模式。首先从关键技术的角度对高平均效用模式挖掘算法进行了分类论述,主要包括基于先验、基于树、基于列表、基于投影和基于数据格式的方法。其次,分析讨论了基于全集、精简集以及融合模式的含有负效用的高效用模式挖掘算法。再次,从模糊高效用模式、相关高效用模式和其他新兴高效用模式三个方面概述和总结了扩展高效用模式算法。最后,针对现阶段研究方向的不足,给出下一步的研究方向。关键词:衍生高效用模式;高平均效用模式;负效用;模糊高效用模式;相关高效用模式;综述中图分类号:TP311.13 文献标识码:A DOI:10.3969/j.issn.1007-791X.2024.02.0050 引言频繁模式挖掘1(Frequent Pattern Mining,FPM)假设数据库中所有项目具有相同的重要性,主要通过其二进制属性(该项目是否在事务中出现)从数据库中寻找频繁发生的项集。然而,现实生活中,特别是在市场数据库中,每条事务都包含了项目的内在价值,因此仅考虑项集的频率对于找出高利润的项集意义不大。例如,香烟,红酒是一个频繁项集,这仅体现了香烟常与红酒同时销售,并未体现其数量和价值信息。为解决其局限性,提 出 了 高 效 用 模 式 挖 掘2(High Utility Pattern Mining,HUPM),通过定义项目的单位利润和数量来发现具有高效用(如产生高利润)的项集。例如,香烟:2,红酒:1,纸巾:1表示顾客购买 2 包香烟、1 瓶红酒和 1 包纸巾,以上单件商品利润分别为 25 元、200 元和 1 元。经计算,此项集产生 251 元的利润,销售者可根据自身制定的标准来判断此项集是否为一个高效用项集(High Utility Itemsets,HUIs)。在购物篮数据分析中,这能有效帮助决策者制定营销计划。尽管 HUPM 通过考虑效用度量揭示了有意义的高效用模式,由于实际应用的多变性,面对复杂的需求,传统的 HUPM 无法普遍适用于多元化的生活场景。针对特定某一类问题,研究者们提出了更加精确的解决方案。于是,以高效用模式为基础,衍 生 出 一 系 列 较 为 复 杂 的 模 式。传 统HUPM 忽略了项集长度对效用值的影响3-4,因此会产生大量无意义的长模式,即长项集中可能会包含大量低于效用平均值的项。例如,销售者将利润高于 200 元的商品称为 HUIs,由于红酒利润较高,故其与任意商品组合均为 HUIs,如红酒,纸巾、红酒,纸巾,尿布,口香糖,等,即使HUIs 中存在如纸巾这样的低利润项,但项集的利润随着物品组合数的增加而增加,此时,效用度量更偏向于长项集。为解决此问题,TPAU3-4算法引入平均效用度量以挖掘高平均效用项集(High Average Utility Itemsets,HAUIs),即单位效用较高的项集,首次提出高平均效用模式挖掘(High Average Utility Pattern Mining,HAUPM)方法删除大量长度较长但含有低利润项的 HUIs。由于其具有两阶段算法5的局限性,随后 PBAU6算法采用第 2 期刘淑娟 等 衍生高效用模式挖掘算法综述139 投影技术缩小数据库规模。HAUP-growth7算法通过树结构存储信息减少数据库扫描次数。HAUI-Miner8算法设计紧凑的垂直列表结构高效挖掘 HAUIs。为提高挖掘效率,MHAI9算法和FHAUI10等算法通过设计紧凑上界来减少候选项集数量,进一步丰富该模式领域。此外,HUPM 的局限性还在于未考虑项效用为负的情况11。实际上,负项存在于生活的方方面面,如商家的销售亏损和消费者的欠费行为等,例如,香烟降价促销,出现亏本的情况,其利润为-1 元,即亏损 1 元处理,但商家可通过将香烟红酒捆绑销售的策略保证收益为正。由于 HUPM 的方法仅考虑了项效用为正的情况,则无法直接应用于负项存在的场景。HUINIV-Mine12算法首次引入了负效用的概念并挖掘含有负项的高效用模式,克服了 HUPM 仅适用于正项的局限。随后,人们还研究了其它问题,如基于 Top-k 的 TopHUI13算法、增量数据库上的 HUPM 算法 ITPAU14、数据流上的 HUPM 算法 HND 以及不确定数据库上的HUPNU16算法等,使得模式挖掘的任务进一步广泛应用。近年来,学者们仍致力于对高效用模式的创新研究工作。一些新兴的衍生 HUPM 方法逐渐出现在大众视线,如模糊高效用模式17、相关高效用模式18、占用高效用模式19和跨层级的高效用模式20等。针对传统高效用模式在定量数据库上挖掘会产生大量冗余项集的缺陷,HUFI-Miner17算法首次提出模糊高效用模式挖掘方法,引入模糊集概念,将难以表达的数量或利润关系转化为易于理解的语言表达。相关高效用模式挖掘任务解决了高效用模式挖掘结果中项集之间相关性较低的问题。Fournier-Viger 等人18首次引入相关度量,同最小效用阈值共同约束挖掘过程,删减了大量项之间相关性较弱的模式。为进一步挖掘有用高效的模式,文献19结合效用和占用率概念,提出了占用高效用模式挖掘(High Utility Occupancy Pattern Mining,HUOPM)方法。通过比较模式和包含该模式的事务效用占比情况,判断该模式的重要程度以提取出更具代表性的有趣模式。此外,传统的高效用模式忽略了项目的分类信息,从而丢失了部分有意义信息,故跨层级的高效用模式20引入分类法概念,为模式中的每个项目设置相对应的类别。这种结合分类信息的模式发现为分析用户行为提供了新思路。以上模式均衍生自高效用模式,故命名为衍生高效用模式;不同点在于针对特定问题提出的衍生高效用模式各有特点。此外,有学者研究了这些模式的融合以处理较复杂的问题。例如,红酒和纸巾的购买组合并不常见,故项目之间的相关性较弱,这种购买关系的推荐是无意义的。结合模式长度的影响,挖掘出单位利润较高的商品组合,Sethi 等人提出 CoHAI-Miner21算法挖掘相关高平均效用模式。此外,为克服现有 HAUPM方法只能处理正效用的问题和在含负效用的数据库中模式发现不完全的局限,提出融合模式算法MHAUIPNU22挖掘含负效用的高平均效用模式。现阶段仍不断产生较为复杂的衍生高效用模式以处理传统高效用模式中存在的不足,模式之间可根据需求彼此结合更加精准地提供解决方案。为便于后续进一步研究和丰富内容,现总结分析衍生高效用模式挖掘的算法是必要且有意义的。本文将对以上模式的算法进行全面综述。在现有的相关综述中,Singh 等人23从数据结构的角度总结了带负项的高效用挖掘问题。随后,又从静态、动态和序列数据方面阐述并分析了HAUPM24算法的最新信息。张妮等人25首次从正负效用划分角度总结了 HUPM 算法。Almoqbily等人26根据时间顺序和算法采用的度量类型总结了相关高效用模式挖掘算法。以上文献仅对一类高效用模式算法进行介绍,此外,只简单涉及其余新兴高效用模式。李慕航等人27首次从高效用融合模式和衍生模式角度阐述归纳算法,但主要分析融合模式,仅涉及四种衍生模式,并未对近期新出现的高效用模式进行总结分析。因此,本文从不同的角度切入,对多种衍生高效用模式进行全面分析总结并进行优缺点对比。衍生高效用模式分类框架如图 1 所示。本文贡献如下:1)全面总结了多种衍生高效用模式,包括高平均效用模式、含有负效用的高效用模式和最近提出的新兴高效用模式。2)首次从关键技术的角度对 HAUPM 算法进行分类总结和优缺点对比;从全集、精简集以及融合模式的角度对含有负效用模式进行分类总结和140 燕山大学学报2024优缺点对比;最后,对扩展高效用模式挖掘算法进行分析归纳。3)根据目前研究不足,给出下一步研究方向,包括智能优化算法在衍生高效用模式挖掘中应用、结合项目分类法的跨层级模式挖掘和并行分布式挖掘等。图 1 衍生高效用模式分类框架Fig.1 Derived high utility patterns classification framework1 相关概念和定义为了清楚地描述部分衍生模式挖掘问题,给出一个事务数据库和一个效用表,如表 1 和表 2所示。事务数据库是一组事务的集合,定义为 D=T1,T2,Tn,I=i1,i2,im为一组项的集合,其中对于每个事务 TC,TCI 且具有唯一的标识 TID。每一个项目 i 均有一个购买数量 in(i,TC)(内部效用)和效用表(其中存储了项目到单位利润的映射)中项 i 的单位利润 ex(i)(外部效用),即表 1 和表 2 中数字。表 1 事务数据库Tab.1 Transaction databaseTIDABCDET111410T201030T320010T400100T512013T611111 定义 1(事务中的项/项集的效用)2 项 i 在事务 TC中的效用记为 u(i,TC),定义为 u(i,TC)=in(i,TC)ex(i)。项集 X 在事务 TC中效用记为 u(X,TC),定义为 u(X,TC)=iXXTCu(i,TC)。例:项 A 在事务 T1中的效用为 u(A,T1)=in(A,T1)ex(A)=13=3。项集AB在事务 T1中的效用为 u(AB,T1)=u(A,T1)+u(B,T1)=13。表 2 效用表Tab.2 Profit table项ABCDE利润3101-15 定义 2(数据库中项集的效用)2 项集 X 的效用记为 u(X),定义为 u(X)=TCg(X)u(X,TC),其中,g(X)表示包含 X 的事务集。例:项集AB的效用为 u(AB)=u(AB,T1)+u(AB,T5)+u(AB,T6)=13+23+13=49。定义 3(事务效用)2事务 TC的事务效用表示事务 TC中的每一项的效用之和,记为 tu(TC),定义为 tu(TC)=iTCu(i,TC)。例:事 务 T2的 效 用 tu(T2)=1 10+3(-1)=7。定义 4(数据库效用)2数据库的效用为事务效用之和,记为 TU,定义为 TU=TCDtu(TC)。例:数据库中有 6 条事务,TU=tu(T1)+tu(T2)+tu(T3)+tu(T4)+tu(T5)+tu(T6)=84。定义 5(最小平均效用阈值)20,1,最小平均效用阈值定义为 minutil=TU。例:=0.7,minutil=0.784=58.8。定义 6(事务中项/项集的平均效用)4项 i在事务 TC中的平均效用记为 au(i,TC),定义为au(i,TC)=u(i,TC)。项集 X 在事务 TC中的平均效用 au(X,TC)=u(X,TC)X。例:项集AC 在事务 T6中的平均效用为au(AC,T6)=2。定义 7(数据库中项集的平均效用)4项集X 在数据库中的平均效用记为 au(X),定义为au(X)=TCg(X)au(X,TC),其中 g(X)是包含 X 的事务集。第 2 期刘淑娟 等 衍生高效用模式挖掘算法综述141 定义 8(事务最大效用)4事务 TC的最大效用记为 tmu(TC),定义为 tmu(TC)=maxu(i,TC)|iTC。例:tmu(T2)=maxu(A,T2),u(B,T2),u(C,T2),u(D,T2),u(E,T2)=max0,10,0,-3,0=10。定义 9(平均效用上界)4项集 X 的平均效用上 界 记 为 auub(X),定 义 为 auub(X)=TCg(X)tmu(TC),其中 g(X)是包含 X 的事务集。定义 10(高平均效用上限项集)4如果auub(X)minutil,项集 X 为高平均效用上限项集,记为 HAUUBI。定义 11(高平均效用项集)4如果 au(X)minutil,项集 X 为高平均效用项集,记为 HAUI。例:设最小效用阈值 minutil=10,auub(AC)=tmu(T1)+tmu(T6)=10+10=20,au(AC)=au(AC,T1)+au(AC,T6)=5.5,auub(AE)=tmu(T5)+tmu(T6)=20+10=30,au(AE)=au(AE,T5)+au(AE,T6)=13。由定义 10,项集AC和AE均为 HAUUBI。由定义 11,项集AC不是 HAUI,AE是 HAUI。定义 12(重定义事务效用)28事务 TC中所有外部效用为正的项效用之和,记为 RTU(TC),定义为 RTU(TC)=iTCex(i)0u(i,TC)。定义 13(重定义事务加权效用)29项集 X的重定义事务加权效用记为 RTWU(X),定义为RTWU(X)=XTCTCDRTU(TC)。例:RTWU(AE)=RTU(T5)+RTU(T6)=57。2 高平均效用模式由于项集的效用是项的效用之和,长项集会产生很高的利润,因此,传统 HUPM 倾向于寻找更长的项集,故在相同的阈值下,短模式不易被发现,其效用度量无法保证公平性。为解决 HUPM的不足,HAUPM 算法通过长度规范了项集的效用来发现单位效用较高的项集,因此删除了大量无意义的包含低效用项的高效用长模式。本节从关键技术对高平均效用模式挖掘的算法进行总结,包括基于先验、基于树、基于列表、基于投影和基于数据格式的方法。2.1 基于先验的方法Apriori 算法30是最早出现在关联规则挖掘中的算法,通过逐层水平迭代搜索的方式生成候选项集进而形成规则。其原理是利用 Apriori 性质,又称向下闭包属性(Downward Closure,DC),来限制候选项集产生来发现频繁项集,即若某个项集是频繁的,其所有的子集都是频繁的;若某个项集不是频繁的,其所有的超集也是非频繁的。随着用于克服 FPM 局限性的 HUPM 出现,Apriori 性质也被用于效用挖掘中,如 Two-phase 算法5结合TWU 模型和 Apriori 性质在两个阶段内挖掘 HUIs。然而,在效用挖掘中,项集的实际效用随着项数量的增加而增加。Hong 等人首次在 HUPM 中引入平均效用概念并提出了一个两阶段挖掘算法TPAU3-4,算法利用 auub 度量高估项集的平均效用,筛选出 auub 值大于 minutil 的候选项集,通过再次扫描数据库计算候选项集的实际平均效用找到 HAUIs。针对算法仅考虑单一最小效用阈值的局限性,HAUIM-MMAU31算法可为每个项目指定不同阈值,为挖掘具有多个最小效用阈值的HAUIs 提供了一个基础框架,引入最小平均效用(Least Minimum Average Utility,LMAU)解决 auub属性无法直接应用该框架的问题,并设计改进的估计效用共现剪枝(Improved Estimated Utility Co-occurrence Pruning,IEUCP)策略和计算前剪枝策略(Pruning Before Calculation Strategy,PBCS)来尽早剪枝无希望的项集,从而加快 HAUIs 的发现。当前的大部分 HUPM 或 HAUPM 算法均基于静态数据库,故不适用于动态数据的处理。随后,ITPAU14算法引入快速更新(Fast Update,FUP)概念以处理增量数据挖掘的复杂情况,将新事务中挖掘出的新结果与原事务库中挖掘出的信息结合,通过重用部分有效信息来加速挖掘过程。但在某些情况下,该算法仍需重新扫描数据库来获取新的信息,知识维护的效率低下。Wu 等人引入预大的概念来设置 Sl和 Su两个阈值以用于知识维护工作,并进一步提出 APHAUIM32算法。该算法为避免多次扫描数据库,在缓存区内存储预大平均效用上限项集,因此节约了大量时间成本。2.2 基于树的方法由于基于先验的算法需多次扫描数据库生成142 燕山大学学报2024候选项集并验证,因此花费高昂的时空成本。故研究者们提出了基于树的挖掘算法,即通过数据库扫描构建存储项集相关内容信息的树33,随后挖掘过程中只需迭代遍历树而无需扫描数据库。本小节将基于树的方法分为在静态数据上和在动态数据(增量数据、数据流)上的挖掘算法。在静 态 数 据 上,Lin 等 人 提 出 的 HAUP-growth7算法中设计了新颖的压缩树结构 HAUP-tree,树路径末端的每个节点存储项的 auub 以及路径中前项的数量,该结构结合模式增长方法导出模式。姜玫等人提出了一种不需要产生候选项集 HAUI-Mine34算法,树中尾节点存有路径中的最大效用、路径中条件模式基的效用以及路径的效用列表。算法依据 HAUI-Tree 中的项,通过产生的条件模式基依次递归构建条件模式树以挖掘HAUIs。该算法的对比实验表明,在稀疏数据集上优于 HAUP-growth 算法。Lu 等人35设计类似于索引表的项集结构以快速计算该项集的 au 和auub,并采用新的数据结构 HAUI-Tree 存储。该结构可根据项集属性直接计算出下一阶段中项集的效用值,提高了算法执行效率。以上算法均基于静态数据库,由于现实应用程序中,数据往往以流的形式产生,数据库会随着事务的增加或删除而发生变化,此时,静态数据的挖掘方法将无法满足应用需求33。下面将总结动态数据上基于树的挖掘方法。在增量数据库上,Kim 等人提出 IMHAUI36算法和新的数据结构 IHAUI-Tree,IHAUI-tree 上的每个结点 N 存储从根到 N 的路径重叠事务信息,通过结点的共享效应维护增量数据库的信息。Lin等人提出基于改进 FUP 概念的 IHAUPM37算法以处理有事务插入的增量数据库,采用 HAUP-Tree结构保存来自原始数据库的必要信息,将原始数据库和新添加的事务划分为四种情况进行维护。此外,该算法仅关注增量部分,利用部分内存就可以快速实现对 HAUIs 的更新。在数据流上,姜玫等人提出一种不产生候选项集的挖掘算法 ITR-Mine34,设计 ITR-Tree 结构维护窗口内数据信息,依次更新当前窗口内的数据并递归构建条件模式基和条件模式树,实现在数据流上的挖掘任务。SHAU38算法提出 SHAU-Tree 结构,其中每个结点用批量列表保存最近流数据中的平均效用信息以此挖掘最新的重要模式。此外,通过平均效用上界最小化剪枝策略提高算法的性能。由于最新数据可能比旧数据具有更高的影响,Yun 等人首次应用平均效用因子和数据流衰减概念以处理敏感数据流上的事务,提出了基于阻尼窗口的 MPM39算法,通过设计阻尼平均效用树(Damped Average utility Tree,DAT)维持事务的阻尼平均效用,为管理事务效用信息并确定无效事务,通过事务效用列表(Transaction Utility List,TUL)信息判断下一步候选验证。HAOP-Miner40算法将 HAUPM 方法同一次性序列模式结合,采用反向填充策略计算支持度避免冗余节点的创建,此外,为解决枚举树生成大量候选模式,提出支持度下界方法并结合模式连接策略剪枝候选模式,从而实现了模式的高效剪枝。HANP-Miner41算法将 HAUPM 方法与非重叠序列模式挖掘结合,采用了基于简化 Nettree 结构的深度优先搜索和回溯策略计算模式的支持度,结合基于平均效用上限的模式连接策略减少候选模式的生成。2.3 基于列表的方法由于先前已有的算法均需要大量计算来找到符合条件的项集。为此,研究人员还积极探索了基于列表的方法。效用列表结构内存占用较小且无需重复数据库扫描,此外,项集间的连接操作方便,k-项集(k1)的列表结构可通过其子集的(k-1)列表结构连接操作构造。因此,受效用列表启发,HAUI-Miner8算 法 提 出 了 平 均 效 用 列 表(Average Utility List,AU-List)结构。与效用列表结构不同在于,三元组中剩余效用被替换为事务最大效用。该算法利用项集的平均效用与事务最大效用之和及早识别无希望项集。为加快算法执行速度,解决上界松散问题,Yun 等人提出 MHAI9算法和新的数据结构 HAI-List。在此基础上,设计了基于最大平均概念的预剪枝技术。FHAUI10算法提出了新颖列表结构IAU-List,该算法在首次数据库扫描后重新计算项集的 tmu 值以得到更加紧凑的平均效用上界。此外,引入估计平均效用共现剪枝结构(Estimated Average Utility Co-occurrence Structure,EAUCS)减少项集间的比较连接次数。FHAUPM42算法提出第 2 期刘淑娟 等 衍生高效用模式挖掘算法综述143 一个较为松散的上界 lubau,该上界在早期阶段有效淘汰候选项集,但当项集不相关时,性能提高不明显,随后,还引入更严格的上界 tubau 以缩小搜索空间。EHAUPM43算法开发了新的效用列表MAU-List 结构,包含四元组(tid,iutil,rmu,remu),其中 rmu 为修正事务的最大效用,remu 为事务剩余最大效用。在此基础上,引入 lub 和 rtub 两个更紧凑的上界。TUB-HAUPM44算法应用两个新的更严格上界 mfuub 和 krtmuub,同时对传统的全局事务上界进行改进,比较事务的两个上界值,选择较 小 值 作 为 该 事 务 上 界 实 现 快 速 紧 化。LMHAUP45算法提出 TA-List 结构,其中,具有相同事务标识的元组在构造过程中相互链接以减少列表连接成本。此外,提出两个新的紧凑上界tmaub 和 mrau。由于单一的最小阈值可能会导致项集过少或冗余的状况,且存在不公平因素,因此 MEMU46算法利用多个最小效用阈值挖掘。为解决 HAUIM-MMAU 使用生成测试方式耗时的问题,该算法采用紧凑效用列表 CAU-List 和表示搜索空间的排序树挖掘 HAUIs,根据列表中存储的 rmu 可快速得到 rtub 紧凑上界值。上述基于多最小阈值的算法均是按照最小平均效用阈值的升序处理项目以保留 auub 的 DC 特性,而传统 HAUPM 算法均是基于 auub 升序,因此不能直接采用 HAUIM-MMAU和 MEMU 框架。针对此问题,GHAIM47算法引入后缀 最 小 平 均 效 用(Suffix Minimum Average Utility,SMAU)概念保持 auub 模型的 DC 特性和几种剪枝方法,使得所有修剪方法通用并且独立于项集的排序。在增量数据库中,基于 AU-List 结构和 FUP概念,Wu 等人提出在事务插入更新时挖掘 HAUIs的方法48,将原数据库和新事务中的 HAUUBIs 分为四种情况,更新数据集和 AU-List,同时删除 AU-List 中 的 非 HAUUBIs,从 而 有 效 维 护 HAUIs。FUP-HAUIMI49算法维护事务插入情况下的数据库,FUP-HAUIMD50是一种通过事务删除来更新发现的 HAUP 的算法。两者均引入改进版的 FUP概念减少增量挖掘中候选模式数量,仅在特定情况下进行原始数据库扫描。随着研究的不断深入,HAUPM 方法也同其它模式融合。Sethi 等人将相关性度量引入 HAUPM中,提出 CoHAI-Miner21算法,使用垂直的列表结构保存效用和相关信息。通过与 EHAUPM 算法的实验分析对比,该算法能发现更多有意义的模式。MHAUIPNU22算法为挖掘具有正负效用的HAUIs,提出新颖数据结构 TUBPNUL,引入严格上界 tubpn 并提出三种剪枝策略。2.4 基于投影的方法在 HAUPM 中,投影技术和索引机制可加快算法执行速度,投影相关子数据库能有效缩小原始数据库的大小,从而只保留在挖掘过程中必要的项集信息,避免不必要的检查从而降低挖掘过程中的内存需求。为了提高 HAUPM 的效率,Lan 等人提出了PBAU6算法,该算法利用索引表结构模拟投影技术,投影当前前缀所需要的事务数据。随后,PAI51算法利用前缀映射方法,据项集持续变化更新 投 影 事 务 的 最 大 效 用 值 以 紧 化 上 界。FIMHAUI52算法结合数据库投影和事务合并技术高效发现 HAUIs,提出 IHAUI-Tree 结构的改进版本,仅在叶子结点中存储事务信息,用该结构来获取有希望项集的投影数据库,而无需生成条件模式基和局部树。Thilagu 等人提出一种基于平均效用的 Web遍历模式挖掘算法53,该算法利用投影序列计算模式的事务加权效用,无需考虑整个序列中项的效用,这极大地减少了候选模式的数量。在不确定数据库中,李霆提出 PrefixMUHAUSP54算法挖掘出高平均效用序列模式,通过投影数据库的方法,缩小数据库规模并生成更少的候选序列。2.5 基于数据格式的方法为解决算法性能的不足,研究人员们提出了基于垂直数据结构和基于索引结构的挖掘算法。由于基于水平数据结构的挖掘方法需要额外的数据库扫描,HAUI-Miner 算法设计了一种垂直表结构存储项集的效用信息,通过递归生成扩展项集的效用列表来提高挖掘速度。随后,在 AU-list 的基础上,许多算法引入更为紧凑的上界模型和剪枝策略,但仍花费大量时间成本浪费在评估不必要的模式上。通常,研究者认为基于垂直表示法的上界与水平表示法(如 auub 和 lub)相比表现良好。为解决144 燕山大学学报2024上述问题,有算法引入基于垂直数据集表示来挖掘完整的 HAUIs 集合。dHAUIM55算法提出 aub1、aub、iaub 和 laub 四个紧凑上界,并在此基础上开发三种剪枝策略。通过开发树结构 IDUL 来垂直计算列效用向量以得到项集的平均效用和上界,该算法为评估上界剪枝效果提供了一个通用框架,并在大量实验中证明了优于几种最先进的算法,但不足在于上界仍较为松散不能有效地减少搜索空间消耗时空成本。随后,VMHAUI56算法提出了四种新型的垂直弱上界 vmsub1、vmsub、vmaub 和 vtopmaub,还开发了两种基于上界的剪枝和收紧策略以尽早消除无希望的候选项集,该算法在上界紧凑性和搜索空间修剪能力方面性能表现优异。此外,基于索引结构的算法也可在一定程度上提高算法执行效率。类似于 PBAU 算法中使用的索引表,HAUI-Tree35算法中使用了一种特殊的项目结构快速计算项集效用,从而优化内存使用。EHAUI-Tree57算法利用索引表快速计算项集的平均效用上界,引入位数组结构保存项集信息,从而最大限度地减少内存的使用并提高计算效率。2.6 小结本节首次将高平均效用模式挖掘方法按关键技术角度分类总结,分别为基于先验、基于树、基于列表、基于投影和基于数据格式的算法。如表 3 所示,从关键技术角度总结并对比了 HAUPM 算法。本小结采用定量分析的方法在同一数据集上进行算法的时空消耗对比,并分析了此类方法的共同特点和仍普遍存在的缺陷。此外,对部分HAUPM 算法的时间复杂度进行了分析比较。以TPAU3-4算法为代表,基于先验的算法采用生成和测试的方法挖掘,虽然剪枝策略能减少比较连接的次数和平均效用的计算成本,但仍需进行多次数据库扫描并在内存中生成大量候选项集,这极大影响了算法的时空效率;基于树的方法通过构建树结构存储原始数据库信息,在一定程度上克服了多次扫描数据库的弊端。在相同的最小阈值下,基于树的 HAUP-growth7算法比 TPAU 算法快近一倍,但该算法内存消耗较大且随着树的高度的增长大大增加。此外,这类算法普遍存在的问题在于树的结构较为复杂且不利于算法扩展;基于列表的算法使用垂直压缩结构保留挖掘过程中所需信息,结构简单易实现。在 Mushroom 数据集上,当 minutil 为 4%时,HAUP-Growth 算法的执行时间为 233.7 s,而基于列表结构的 HAUI-Miner8算法仅需1.3 s,比 HAUP-Growth 算法快12 个数量级,此外,在内存消耗方面同样优于 HAUP-Growth 算法,但这类算法的缺陷在于昂贵的列表比较和连接操作;基于投影的算法通过缩小原数据库规模减少扫描数据库的成本,例如 PAI51算法,在 BMS-POS 和 Chess 数据集上,其生成的候选项数量远小于 TPAU 生成的,且运行速度比 TPAU算法快得多。但其依赖于投影机制,在内存消耗方面不如 HAUI-Miner 算法。这类算法仍未克服生成大量候选项集的局限性;基于数据格式的算法主要指基于垂直数据结构的或者索引结构的挖掘方法,基于垂直数据库表示的算法在运行速度和列表连接次数方面性能较优,基于索引的方法在一定程度上提高了计算效率。在实验中,基于垂直挖掘的 dHAUIM55算法比 HAUI-Miner 等算法快 12 个数量级,在 Chess 数据集上的实验结果显示,随着 minutil 的不断调整,该算法速度为HAUI-Miner 算法的 32239 倍。由于算法设计的上界比 HAUI-Miner 使用的传统 auub 上界模型更加严格,因此可在早期删除大量无希望的候选项来降低列表的连接次数。此外,对部分 HAUPM 算法的时间复杂度进行了分析比较。ITPAU14算法是两阶段的算法,时间主要消耗在候选项集的生成和测试阶段,设Lk为生成 k-项集的数量,kCi为 i 个元素组中 k 个元素的组合数,数据集中项的数量为 n,则生成项集数为nC1+nC2+nCn=2n-1,故时间复杂度为O(2n)。基于树的 IMHAUI36算法主要分为扫描数据库、插入新事务更新 IHAUI-Tree、重构 IHAUI-Tree、递归挖掘局部树等阶段。其中,设 n 是在新事务(n/2 个不同项)插入之后,增量数据库具有的不同项数量。故扫描数据库以及更新树的时间复杂度为 O(3n/2),该算法在挖掘过程中需按auub 降序重构树,在使用冒泡排序调整路径的情况下,最坏时间复杂度为 O(n2)。为 n 个结点构建局部条件树的时间复杂度为 O(2np),其中 p 为参与构建局部条件树的结点个数,令 Tz是 z 的局部树的递归模式增长操作时间。故整个挖掘过程第 2 期刘淑娟 等 衍生高效用模式挖掘算法综述145 所需 O n2+2np+nz=1Tz(),即 O(n2)。对于基于列表的 MHAI9算法,设 m 为事务数,n 为每个事务中的项目数,在最坏情况下,数据库排序时间复杂度为 O(mn log2n),故构建列表需 O(2mn+mn log2n),最坏情况下,每个列表中含有项的条目数为 m,列表之间的比较连接次数为 2n-1,则递归构建 HAI-Lists 挖掘所有项集的时间复杂度为O(m(2n-1-n),总的时间复杂度两者相加之和,即 O(m2n)。3 含有负效用的高效用模式传统高效用项集挖掘中,默认项的效用值为正。但在应用场合下,存在效用值为负的情况。例如,超市临期处理商品时,往往降价促销,存在亏本的情况。超市决策者可以通过指定捆绑销售措施来稍微挽回损失,故需要提出能同时处理正负效用的 HUPM 方法。有研究者提出含有负效用的高效用模式挖掘方法。本节根据模式划分方法进行分类总结,包括基于全集、精简和融合的模式。3.1 全集模式全集模式是指传统意义上的高效用模式挖掘结果,即找到所有满足效用值大于等于最小效用阈值的所有项集。Chu 等人首次提出基于两阶段的含有负效用的模式挖掘算法 HUINIV-Mine12,算法利用重定义事务加权效用上界高估含有负效用的项集效用,保证项集中最少含有一个外部效用为正的项,并通过再次数据库扫描验证,故存在一定时空局限性。3.1.1 基于模式增长的方法为解决基于候选生成-测试方法的局限性且避免生成数据集中实际不存在的候选项集提出了基于模式增长的方法。UP-GNIV11算法仅需两次数据库扫描,引入两种过滤策略删除负项效用(Removing Negative item Utilities,RNU)和剪枝负项集(Pruning Negative Itemsets,PNI)以去除含有负效用的项来提高挖掘效率。实验结果表明,该算法在执行时间和扩展性方面优于算法 HUINIV-Mine12。EHIN29算法为减少内存消耗,采用事务库投影和事务合并技术,另外引入效用数组来计算重定义的本地效用(Redefined Local Utility,RLU)和重定义的子树效用(Redefined Subtree Utility,RSU)的新上界。基于此,运用 RLU-Prune和 RSU-Prune 策略剪枝搜索空间。为挖掘出数量较少且更有意义的模式。EHNL58算法引入长度约束的概念,利用最小长度约束删除大量短项目集,最大长度约束来限制过长的项集,从而使得生成的关联规则更具代表性,此外,结合事务合并技术降低算法计算成本。在动态数据库上,Li 等人提出了两种基于滑动窗口的挖掘含有负效用的高效用项集算法,即MHUI-BIT-NIP59和 MHUI-TID-NIP59,两者分别采用了 BITvector 和 TIDlist 的项目表示法以加快当前滑动窗口内项集的挖掘速度,同时,开发 LexTree-2HTU 结构维护窗口内 2-项集的高事务加权效用。3.1.2 基于列表的方法单阶段算法 FHN60是 FHM2算法的一种扩展,开发新的列表结构 PNU-List 应对负项的出现,且项的正负效用值采用单独的列表结构存储。此外,应用基于估计效用共现剪枝结构(Estimated Utility Co-occurrence Structure,EUCS)的剪枝策略和剩余效用剪枝策略。经实验证明,该算法在时空效率上均优于 HUINIV-Mine12。随后,在 FHN的扩展版本28中添加 LA-Prune 剪枝策略再次缩小搜索空间。GHUM61算法开发了一个简化效用列表结构,同时,基于项集效用反单调特性提出了A-Prune 和 N-Prune 剪枝策略来降低列表连接成本。陈丽娟提出 EHINM62 算法,该算法应用了改进的列表结构,包含三元组(tid,rutil,rpnu),其中rpnu 为重新定义的剩余效用值。考虑到负效用在项集扩展时对事务效用的影响,引入 RPNU 和RTWU 两种紧凑上界并提出三种剪枝策略。面对不确定事务数据库,HUPNU16算法采用新的垂直列表结构PU-list 存储正负项并提出六种修剪策略提前修剪无希望的项。此外,张妮等人首次提出在数据流中挖掘含有负项的 HUPM 算法 HND15。受 ULB-Miner 算法启发,开发出新的列表索引结构(List Index Structure,LIS)。不同于传统效用列表,此结构通过内存重用策略降低内存消耗成本,大大提升了挖掘性能。146 燕山大学学报2024表 3 高平均效用模式挖掘算法Tab.3 High average utility pattern mining algorithms算法技术数据集数据结构剪枝策略对比算法优点缺点TPAU3-4先验静态无auubTwo-phase引入平均效用度量减少候选项集数量重复扫描数据库并产生大量候选项集ITPAU14先验增量无auubTPAU实现增量挖掘产生大量候选项集HAUIM-MMAU31先验静态无IEUCP/PBCSHAUI-MMAUIEUCPHAUI-MMAUPBCS考虑多个最小阈值挖掘问题多次数据库扫描大量候选项生成APHAUIM