引用本文

唐辉军, 王乐, 樊成立. 基于模式增长的高效用序列模式挖掘算法.自动化学报, 2021, 47(4): 943-954 doi: 10.16383/j.aas.c180660

Tang Hui-Jun, Wang Le, Fan Cheng-Li. A new algorithm for mining high utility sequential patterns based on pattern-growth. Acta Automatica Sinica, 2021, 47(4): 943-954 doi: 10.16383/j.aas.c180660

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180660

关键词

高效用序列模式，模式增长，闭包属性，数据挖掘 

摘要

高效用序列模式挖掘是数据挖掘领域的一项重要内容, 在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同, 高效用序列模式挖掘不仅考虑项集的内外效用, 更突出项集的时间序列含义, 计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题, 挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此, 本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求, 算法首先在去除无用项后建立全局树, 进而采用模式增长方法从全局树上获取全部高效用序列模式, 避免产生候选项集. 在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比, 实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式, 并且在计算时间和空间使用效率两方面取得了较大的提高.

文章导读

序列模式挖掘作为数据挖掘领域的一项重要研究内容, 在风险管理、生物信息学、基因分析等方面具有重要的应用[1-3].频繁序列模式挖掘作为其应用的典型代表, 突出了序列数据集中的高频模式, 传统数据集上的频繁项集闭包属性表明: 任一个频繁项集的非空子集都是频繁项集, 非频繁项集的任一个超集都不是频繁项集, 基于上述闭包属性计算原则形成了序列集频繁模式挖掘算法[4-5].然而频繁模式没有考虑序列集中各项的效用值.例如在零售业, 冰箱的销售要比牙刷卖的次数少的多, 但其利润可能比牙刷高的多, 因此在频繁序列模式的基础上, 提出了高效用序列模式挖掘, 即将内外效用值引入到序列项集中, 目前, 高效用序列模式已经成为数据挖掘领域的一个热门研究内容[6-8]. 2010年, Ahmed等[9]给出了高效用序列模式挖掘的完整定义和数学模型.其主要任务为在具有一定效用值的序列数据库中找出效用值不小于预先给定阈值的所有有序项集.在定义过程中, 一个项集X的总效用值为X在该数据集中有包含项集X的事务t上的效用值U(X,t)的总和.而在单一事务t中可能存在多个相同序列集, 文献选择其中较大效用值作为项集X在该事务中的效用.同时, 该文献还提出两种挖掘算法UtilityLevel和UtilitySpan, 其中UtilityLevel通过事务中项集按水平次序组合生成候选项集, 进而判断和识别其中高效用序列.UtilitySpan通过项集前缀垂直查找, 搜索高效用项集.相比之下, UtilitySpan的实现效率较好, 但当用户设定的阈值比较低或数据集中的不同项比较多时, 两类算法会产生众多的候选项集, 造成产生高效用序列项集的时空代价较大. 2012年, Yin等[10]在KDD会议上提出的USPAN算法, 被认为能较大地提升高效用序列模式挖掘效率.其主要基于项集树模型设计了数据库中序列模式, 所有序列模式均可从树中的结点得到, 并且基于高效用挖掘中的闭包属性原则给出了一个SWU (Sequence-weighted utilization) 模型进行剪枝操作.即一个项集的SWU值不小于用户定义的最小效用值, 该项集即为一个候选项集; 反之, 则该项集则不为高效用项集.另外, 该文还通过设置事务中的项集的Remain-utility进行深度剪枝操作, 即一个项集的现有效用加上Remain-utility如果小于最小效用值, 则停止在树中搜索该项集.USPAN的算法时空效率高于文献[9]中的算法.但其算法基于枚举而产生, 时空效率代价也相对较大. Wang等[11]考虑到在较小阈值下, SWU通常比最小效用值要大, 提出了一个不基于闭包属性原则的HUS-Span算法, 该算法主要设计了一种新的数据结构表示方法-效用链(Utility-chain), 通过添加效用链剪枝达到计算效用值的目的.不过, 该算法只在最小效用值较低或稀疏数据集时, 其性能优于USPAN. 首先采用层次方法或者一定的数据结构(树、链)找出候选项集, 然后扫描数据集计算每个候选项集的真实效用值来判断该候选项集是否为高效用序列模式是USPAN、HUS-Span等算法的核心思想, 很多算法在此基础上进行数据结构设计改进[12-14], 2017年, Zihayat等[15]在USPAN的基础上, 提出了HUSP-Miner算法, 该算法主要设计了两个新的数据结构ItemUtilLists (Item utility lists) 和HUSP-Tree (High utility sequential pattern tree), 其通过树形链式模式降低挖掘过程中的候选项个数, 在与USPAN的实验比较结果中可以看到, 算法的时空效率得到了一定的提升, 时间效率能提高到3倍. 高效用序列模式挖掘算法的时空效率有了很大的提高, 但算法的代价还比较大, 特别是挖掘时间效率的提升仍是本领域的一个挑战, 本文在基于高效用模式增长挖掘方法的基础上, 给出一个高效用序列模式新算法HUSP-FP (High utility sequential pattern based on FP-growth).该算法采用模式增长的方法来挖掘高效用序列模式, 所有的高效用序列项集均可从树上得的, 而不用再扫描原始数据集.基于模式增长的挖掘算法已经在高效用无序数据集模式挖掘上表现出了独特的优势.HUI-Miner[16]、FHM[17]、HUPM-FP[18]等算法相继提出, 在时空效率上得到了较大提升, 目前在序列数据集上开展高效用模式增长方法的研究成果还及其罕见. 本文首先给出高效用序列模式的相关数学定义; 然后, 给出HUSP-FP中的全局树建立过程, 重点突出从树中挖掘高效用序列模式的过程, 分析算法的时空效率优势; 最后, 开展相关实验, 与前述现有较好的HUSP-Miner、UPSAN和HUS-Span算法进行计算效率对比分析, 以验证新算法的优越性, 并开展总结分析提出下一步工作方向.

图 1  序列全局树构建实例

图 9  HUSP-FP和HUSP-Miner的对比评价

本文提出一种新的高效用序列模式挖掘算法HUSP-FP, 该算法基于模式增长方式可直接挖掘高效用序列模式, 而不是传统的先得到候选项集再筛选的过程, 因此算法的时空效率都得到了提升.本文采用4个典型真实数据集(包含短序列、长序列、稀疏数据集、稠密数据集)进行了静态和时间窗口动态实验验证, 实验结果也表明给出算法的时间和空间效率相比目前较好的HUSP-Miner、USPAN和HUS-Span都有较大程度的提高, 特别是时间效率得到了较大幅度的提高, 证明该方法是可行的. 同时通过实验运行, 发现HUSP-FP算法即使在最小阈值较大情况下, 在维护全局和子树环节仍然需要消耗大量时间和空间, 下一步将针对此问题进行优化.

作者简介

王乐

宁波财经学院数字技术与工程学院副教授. 2013年获得大连理工大学博士学位. 主要研究方向为数据挖掘. E-mail: wangleboro@163.com

樊成立

宁波财经学院金融与信息学院副教授. 2007年获得北京化工大学硕士学位. 主要研究方向为信息管理. E-mail: 380577275@qq.com

唐辉军

宁波财经学院金融与信息学院副教授. 2008年获得浙江工业大学硕士学位. 主要研究方向为数据挖掘技术. 本文通信作者. E-mail: totti_2018@sina.com