从序列数据库中挖掘具有高平均效用且不重叠的模式

《ACM Transactions on Intelligent Systems and Technology》：Mining high average utility nonoverlapping patterns from sequential database

针对高平均效用序列模式挖掘中忽略重复出现的模式问题，提出HUP-Miner算法。采用位置字典减少数据库重复扫描，结合模式合并策略和四类剪枝方法降低计算复杂度，并设计SPC算法高效计算模式效用。实验表明，该算法在14个数据集上优于12种现有方法，且基于信息增益的效用指标能提升聚类性能。

　　

摘要

作为数据挖掘中的一个关键方面，高平均效用序列模式挖掘（SPM）旨在发现序列数据中的低频高平均效用模式（子序列）。大多数现有的高平均效用SPM方法忽略了每个序列中模式的重复出现，导致一些重要模式被忽略。为了解决这个问题，我们专注于从序列数据库中挖掘高平均效用非重叠模式（HUPs）的问题，并提出了一种HUP-Miner算法。为了减少对原始数据库的重复扫描需求，我们使用了一个位置字典来记录每个元素的出现信息。为了减少生成的候选模式数量，我们采用了模式连接策略并探索了四种剪枝策略。为了高效计算模式的平均效用，我们提出了一种利用子模式出现位置的SPC算法。与12种竞争算法相比，在14个数据库上的实验结果表明，HUP-Miner取得了更好的性能。此外，我们使用信息增益作为每个元素的效用，并发现通过这种方式发现的HUPs可以通过聚类分析产生更好的性能。这里使用的所有算法和数据库都可以从https://github.com/wuc567/Pattern-Mining/tree/master/HUP-Miner获取。