《Knowledge-Based Systems》：MEU-Miner: Bitset-Guided Multi-Dimensional High-Utility Sequential Pattern Mining with Parallelism and Adaptive Top-k
编辑推荐：
本文针对多维高效用序列模式挖掘（MDHUSPM）中存在的剪枝效率低、内存开销大及缺乏并行机制等挑战，提出了MEU-Miner框架。该研究通过引入维度级效用上界（DUB）实现安全剪枝，利用位集驱动上下文匹配优化存储，并结合并行计算（PMEU-Miner）与自适应Top-k挖掘（TKMEU-Miner），在19个真实与合成数据集上验证显示，其运行速度较现有基线提升最高达66倍，内存占用降低60%以上，显著推动了多维度序列模式挖掘的实用化进程。
在当今大数据时代，从序列数据中挖掘有价值的行为模式已成为电子商务、业务流程管理等领域的核心任务。然而，传统的高效用序列模式挖掘（HUSPM）方法存在明显局限：它们往往将序列视为独立实体，忽略了用户属性、时间、地域等多维度上下文信息。这就好比在分析消费者购买行为时，只关注购买了哪些商品，却忽视了消费者年龄、设备类型、所在地区等关键背景信息。这种"维度缺失"导致挖掘出的模式缺乏针对性，难以支撑精准营销、个性化推荐等实际应用。
更严峻的是，当试图将维度信息纳入考量时，现有方法面临三重挑战：首先，维度组合的爆炸式增长使得搜索空间急剧扩大，而传统的效用上界估计松散，导致剪枝效果差，计算效率低下；其次，基于指针的列表存储结构在处理高维数据时产生巨大内存开销；第三，缺乏并行计算支持和自适应阈值机制，使得算法难以适应大规模数据场景。这些瓶颈严重制约了多维高效用序列模式挖掘（MDHUSPM）的实际应用。
为解决这些问题，青岛理工大学信息与控制工程学院的研究团队在《Knowledge-Based Systems》上发表了题为"MEU-Miner: Bitset-Guided Multi-Dimensional High-Utility Sequential Pattern Mining with Parallelism and Adaptive Top-k"的研究论文。该研究提出了一个创新的算法框架，通过维度级效用上界（DUB）、位集驱动的上下文匹配和统一搜索策略，实现了对多维高效用序列模式的高效挖掘。
研究人员开发了三个核心算法：MEU-Miner采用位集引导的上下文匹配与DUB剪枝策略；PMEU-Miner引入共享内存并行设计提升计算效率；TKMEU-Miner则提供无需预设阈值的Top-k挖掘机制。关键技术包括：基于位集的上下文匹配机制，将维度信息编码为位向量，利用位运算快速匹配；维度级效用上界（DUB）理论，保证在维度格上的反单调性，实现安全剪枝；以及并行任务调度和自适应堆结构。
在结果部分，研究团队在19个数据集上进行了系统验证：
效率对比实验显示，MEU-Miner在运行速度上较MDUS-EM、MDUS-SD等基线算法提升最高达66倍，PMEU-Miner通过多线程并行进一步获得180倍的加速效果。这证明了DUB剪枝策略和位集计算的高效性。
内存效率分析表明，MEU-Miner的向量化存储架构比传统列表结构减少60%以上的内存消耗，且在维度增加时保持稳定，解决了高维场景下的内存膨胀问题。
可扩展性验证通过改变数据集大小和维度数量证实，MEU-Miner在不同数据规模下均保持良好性能，特别是在处理400K条大型序列数据时，仍能保持合理的运行时间。
Top-k性能测试中，TKMEU-Miner在k值从5到3000的广泛范围内，均优于TKUS、TKUS-Span等基线算法10-40倍，展现了自适应阈值机制的优越性。
消融实验深入分析了各技术组件的贡献：禁用DUB会使运行时间增加1.8-2.5倍，禁用向量化计算导致性能下降1.5倍，证实了各创新点的有效性。
研究结论指出，MEU-Miner框架通过整合紧密剪枝、轻量级存储和并行计算，有效解决了MDHUSPM领域的核心挑战。其创新性在于：DUB理论为多维环境提供了严格的效用上界保证；位集驱动的存储和计算架构显著提升了内存效率和匹配速度；并行化和自适应Top-k机制则增强了算法的实用性和可扩展性。
这项研究的重要意义在于，它为处理复杂多维序列数据提供了系统解决方案，使得从海量、多源的序列数据中发现有实际价值的模式成为可能。不仅推进了序列模式挖掘的理论发展，更为电子商务分析、业务流程优化等应用场景提供了强有力的工具。未来，该框架可进一步扩展至流数据挖掘、隐私保护挖掘等方向，具有广阔的应用前景。
