基于兴趣度的序列模式挖掘算法的研究外文翻译资料

英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

TKS：Top-K序列模式的高效挖掘

{philippe.fournier-viger，etg8697，eem7706}@umoncton.ca,

rinc_thomas@rediffmail.com，agomariz@um.es

摘要:序列模式挖掘是一种应用广泛的数据挖掘任务。但是，对序列模式挖掘算法的参数进行微调以生成足够的模式是困难和耗时的。为了解决此问题，已经定义了top-k序列模式挖掘的任务，其中k是要查找的序列模式的数目，并且由用户设置。本文提出了一种有效的算法来解决这个问题，即TKS（top-K序列模式挖掘）。TKS使用一个垂直位图数据库表示，一个名为PMAP的新的数据结构(优先级图)和几个有效的策略，用来修剪搜索空间。对实际数据集进行的大量实验研究表明，TKS的性能优于目前最先进的top-k序列模式挖掘算法TSP，并且TSK在执行时间和内存方面都超过TSP一个数量级。

关键词:top-k，序列模式，序列数据库，模式挖掘

1 介绍

目前已经提出了各种方法来挖掘序列数据库中的时间模式，例如挖掘重复模式，趋势和顺序模式[8]。其中，序列模式挖掘可能是最流行的一套技术。给定一个用户定义的阈值和一组序列，它包括发现所有超过序列的共同子序列[1]。它是一个经过深入研究的数据挖掘问题，具有广泛的应用，如分析网络点击流，程序执行，医学数据，生物数据和电子学习数据[5,8]。尽管在设计序列模式挖掘算法方面已经做了很多研究[1,2,3,8]，但一个重要的问题是用户应该如何选择阈值来生成所需数量的模式。这个问题很重要，因为在实践中，用户拥有有限的资源（时间和存储空间）来分析结果，因此往往只对参数感兴趣，这是耗时的。根据阈值的选择，算法可能会变得非常缓慢并产生大量的结果，或者不会产生或不产生太多结果，从而忽略有价值的信息。为了解决这个问题，有人提出将挖掘序列模式的问题重新定义为挖掘top-k序列模式的问题，其中k是要找到的序列模式的数量，并且由用户设置。当前解决这个问题最好的算法是TSP[4]。然而，在我们的实验研究中（参见第4节），我们发现它在密集数据集上表现不佳。因此，一个重要的研究问题是我们能否开发一种比TSP更有效的top-k序列模式挖掘算法。在本文中，我们通过提出一种名为TKS（Top-K序列模式挖掘）的新算法来解决这个研究问题。TKS是一种有效的top-k序列模式挖掘算法。它使用与SPAM相同的垂直数据库表示和基本候选序列生成过程[3]。此外，TKS结合了几种有效的策略来修剪搜索空间，并依靠了一种名为PMAP（优先映射）的新型数据结构来避免代价高昂的位向量交集操作。对五个真实数据集进行的广泛实验研究表明：（1）TKS在执行时间和内存使用方面比现有算法（TSP）高出一个数量级以上。此外，我们发现TKS在密集数据集上表现出色。

本文的其余部分安排如下。第2节正式定义了序列模式挖掘和top-k序列模式挖掘的问题，并提出了相关工作。第3节描述了TKS算法。第4节介绍了实验研究。最后，第5节提出了结论并讨论了未来的工作。

2 问题定义和相关工作

序列模式挖掘问题由Agrawal和Srikant[1]提出，定义如下。序列数据库SDB是出现在这些序列中的一组序列和一组项目。一个项目是一个象征性的价值。项目集是一组不同项目的无序集合。例如，项目集{a，b，c}表示项目集合a，b和c。序列是项集的有序列表，使得对于所有1le;kle;n。例如，考虑图1.a中描述的序列数据库SDB。它包含分别具有序列ids（SIDs）1，2，3和4的四个序列。在该示例中，每个单个字母表示一个项目。大括号之间的项表示项目集。例如，第一个序列lt;{a，b}，{c}，{f}，{g}，{e}gt;表示项目a和b同时发生，接着是c，f，g最后e。一个序列被认为包含在另一个序列当且仅当存在整数使得（表示为）。在序列数据库中对子序列的支持被定义为序列的数目，使得并且由表示。在序列数据库中挖掘序列模式的问题是要找到所有频繁的序列模式，即每个子序列使得对于由用户设置的阈值，ge;。例如，图1.b显示了图1.a的数据库中满足 = 2的29个序列模式中的6个序列模式。针对这个问题，已经提出了几种算法，比如：PrefixSpan[2]，SPAM[3]，GSP和SPADE[9]。

问题定义。为了解决设置的困难，序列模式挖掘问题被重新定义为top-k序列模式挖掘问题[4]。在序列数据库中发现包含k个序列模式的集合L，使得对于每个属于L的模式，不存在序列模式。例如，对于图1.a和k=10的数据库，top-k个序列模式是lt;{g}gt;，lt;{a}，{f}gt;，lt;{a}gt;，lt;{b}，{e}gt;，lt;{b}，{g}gt;，lt;{a}，{e}gt;和lt;{e}gt;，支持度为3；并且lt;{b}，{f}gt;，lt;{b}gt;和lt;{e}gt;，支持度为4。这个问题的定义类似于模式挖掘领域的其他top-k问题的定义，例如top-k频繁项集挖掘[1]，top -k关联规则挖掘[6]和top-k连续规则挖掘。

当前最先进的top-k序列模式挖掘算法是TSP[4]。已经提出了两种TSP版本分别用于挖掘（1）top-k序列模式和（2）top-k封闭序列模式。在本文中，我们正在处理第一个案例。将我们的算法扩展到第二种情况将在未来的工作中考虑。TSP算法基于PrefixSpan[2]。TSP首先生成包含单个项目的频繁序列模式。然后递归地扩展每个模式s（1）通过s投影数据库，（2）扫描结果投影数据库以识别在s之后出现超过次数的项目，以及（3）将这些项目附加到s。这种基于投影的方法的主要优点是它只考虑出现在数据库中的模式，而不像“生成和测试”算法[1，4]。然而，这种方法的不足之处在于重复投影/扫描数据库的成本很高，并且对于需要执行多重投影的密集数据库来说成本变得很大（参见第4节中的实验性研究）。鉴于此限制，一个重要的研究挑战是定义一种比TSP更高效并且在密集数据集上表现良好的算法。

Fig.1 序列数据库（上）和一些序列模式（下）

3 TKS算法

我们通过提出一种名为TKS的新算法来解决这一研究挑战。TKS采用了SPAM的垂直数据库表示和基本候选生成过程[2]。此外，它还包括几种有效的策略来有效地发现top-k序列模式。下一小节回顾了SPAM算法的重要概念。然后，下面的小节介绍TKS算法。

3.1 数据库表示和候选生成程序

TKS中使用的垂直数据库表示[3]定义如下。设为包含q个项目和m个序列的序列数据库，其中size（i）表示的第i个序列中的项目集数量。SDB的垂直数据库表示V（）被定义为大小为的一组q个比特向量，使得每个项目x具有对应的比特向量。对于每个位矢量，第j位代表的第t个序列的第p个项集，使得并且。一个位矢的每一位被设置为1当且仅当x出现在由该位表示的项目集中，否则它被设置为0。例如，表1的左边部分示出构造的位矢量对应于图1的数据库中的每个项目。

表1 垂直表示（上）和PMAP数据结构（下）

候选生成过程[3]如图2所示。它以参数序列数据库和阈值为参数。它首先扫描一次来构建V（）。与此同时，它还计入每个单一项目的支持度。然后，对于每个频繁项目s，它调用程序“SEARCH”。此过程输出模式lt;{s}gt;并递归探索以前缀lt;{s}gt;开头的候选模式。搜索过程（参见图3）将参数作为序列模式，并将两组项目附加到以生成候选项。第一组表示通过s-扩展追加到的项目。序列模式对项x的s-扩展的结果是[3]。第二组代表通过i-扩展追加到pat的项目。一个序列模式对一个项目x的-扩展的结果是[3]。对于通过扩展生成的每个候选，SPAM通过执行与和附加项相关的位向量的修改后的逻辑“与”（详见[3]）来计算候选者的位向量。通过计算[3]中设置为1的不同序列的位数来计算候选者的支持度，而不是扫描。如果模式频繁，那么它将用于递归调用SEARCH以生成以前缀开头的模式。请注意，在递归调用中，只有通过扩展导致频繁模式的项才会被考虑用于扩展（见[3]的对齐）。此外，请注意，由于Apriori属性，不频繁的模式不会被SEARCH过程扩展（任何不频繁的序列模式都不能被扩展以形成频繁模式）[3]。候选生成过程在密集数据集中是非常有效的，因为执行“与”操作来计算支持度不需要扫描原始数据库，这与TSP的基于投影的方法不同，后者在最坏的情况下对每个附加到模式的项目执行数据库投影。但是，SPAM的候选生成过程存在潜在的不利之处，就是它可以生成不在数据库中的候选人。因此，建立基于这个过程的top-k算法会产生一个有效的算法并不是显而易见的。

SPAM（，）

1. 扫描以创建V（）并标识频繁项目列表。
2. FOR 每个项目

3. 搜索（lt;sgt;，，一系列来自的并在这在词汇上大于s，的项目）。

Fig.2 SPAM 算法

SEARCH（pat，，，）

1. 输出模式pat。
2. 。
3. FOR每个项目

4.

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[22136]，资料为PDF文档或Word文档，PDF文档可免费转换为Word