才能：针对性挖掘非重叠的序列模式

《ACM Transactions on Management Information Systems》：TALENT: Targeted Mining of Non-overlapping Sequential Patterns

靶向非重叠序列模式挖掘算法TALENT设计与优化

　　

摘要

随着序列模式挖掘（SPM）算法的广泛应用，允许存在间隙约束的序列模式对于从生物数据（如DNA和蛋白质序列）以及某些非生物数据中发现知识具有重要意义。这种方法在连续约束SPM和传统SPM之间取得了平衡，能够在满足用户定义的间隙需求的同时，发现更广泛的模式。在所有类型的带间隙约束的挖掘方法中，非重叠SPM能够发现互不重叠的有趣模式，同时满足抗单调性属性（即Apriori属性，即一个模式的支持度不会大于其子模式的支持度）。然而，现有算法并未针对目标序列模式进行搜索，从而导致不必要的重复模式生成。目标模式挖掘是一种用于发现与用户感兴趣的项目直接相关的项集或序列模式的技术。在本文中，我们定义并形式化了目标非重叠SPM的问题，并提出了一种名为TALENT（TArgeted mining of SequentiaL PattErN with ConsTraints）的算法。我们设计了两种搜索方法（广度优先搜索和深度优先搜索）来生成模式，并提出了几种剪枝策略以减少数据中序列和项目的读取量并终止冗余模式的扩展。最后，我们进行了广泛的实验，将TALENT算法与现有的非重叠序列模式挖掘算法进行了比较。实验结果表明，TALENT具有出色的挖掘效率，并能有效地处理不同的查询设置。在最佳情况下，与基线算法NOSEP相比，TALENT的时间复杂度降低了三个数量级，内存消耗仅占原来的20%。