论文部分内容阅读
频繁场景挖掘是一种对序列模式挖掘的扩展，它特指从一条单一的事件序列中识别频繁出现的有序的事件集合。频繁场景挖掘技术已经得到广泛的研究，并在多个应用领域取得了良好的效果。 现存的频繁场景挖掘算法主要可以分为确定算法和近似算法两大类。其中，确定算法旨在识别出给定序列中所有的频繁场景，这种算法时间复杂度通常较高且对内存消耗大。此类算法计算复杂的原因主要有两点:(1)检验一个场景在序列中是否存在是一个NP-完全问题，因此目前现存的算法多以枚举算法为主。(2)在频繁场景挖掘问题中，频繁度量不一定具有反单调性，因此基于反单调性的剪枝技术不能用于提升算法效率。无法在算法模式上解决枚举算法的瓶颈，同时在某些场合又无法使用剪枝技术，这使得频繁场景挖掘算法在过去二十年的发展历程中始终停留在一种低效的离线分析模式。此外，现存的频繁场景挖掘算法研究将主要注意力放在如何快速找出序列中的频繁场景，而并不是特别关注如何使用这些场景。通常情况下，我们在使用这些频繁场景时，需要将频繁场景转化成场景规则。在当前的频繁场景挖掘框架中，对于场景规则，我们仅知道构成整条规则的事件序列从起始到结束在一个用户给定的阈值范围内。在某些需要知道结果的确切发生时间并作出自动响应的应用中，这些规则会变得无用。 在当前大数据时代的背景下，数据更新迅速，离线的频繁场景挖掘不再适应当前的需求，需要设计新的算法模式以及在线挖掘算法进行频繁场景挖掘。此外，诸多实际应用对场景规则的使用提出更高要求，需要跨越场景规则和实际应用之间的鸿沟，将场景规则变得更加实用，成为一种可执行场景规则，可服务于自动响应应用系统之中。因此，本文围绕上述两个问题对频繁场景挖掘算法及其应用展开研究。从四个方面由浅及深，先后提出了一种场景挖掘算法的新模式、一种在线频繁场景挖掘新算法，一种可执行场景规则的挖掘框架算法以及这些算法在金融领域和文本分析领域的创新应用。取得主要成果如下: (1)提出一种直推式频繁2-场景挖掘算法 为了解决传统频繁场景挖掘算法“连接-扫描”的模式带来的效率瓶颈，研究形式最简单的仅包含两个事件的场景（称为2-场景），提出事件的最后发生概念，并且通过基于此概念设计的一种高效数据结构—最后发生链表，提出了一种可以直接发现场景最小发生的高效频繁2-场景挖掘算法MEELO。基于最后发生链表实现的MEELO算法可以通过对序列的两边扫描以直推的方式找到所有的频繁2-场景。它是一种直推式挖掘算法，采用“扫描-生成”的模式，在不产生候选场景的基础上，尽可能减少序列扫描的次数。 (2)提出一种在线频繁场景挖掘算法 在线频繁场景挖掘问题中，事件序列总是在连续增长。此问题中，老旧的场景可能会变得不再重要，而新产生的场景可能会变得更有价值。更重要地，对于一些对响应时间要求非常高的应用，需要一种高效算法从不断增长的序列中发现近期的频繁场景。因此，我们提出了一种在线频繁场景挖掘算法。通过定义场景的最后发生概念，使得所提出的算法可以直接且快速地基于所有最近的频繁场景去发现新的场景。另外，还设计了一种紧凑的基于Trie的数据结构存储场景。同时，我们严格证明了算法的正确性和完整性。 (3)提出一种可执行场景规则挖掘方法 传统的通过分割频繁场景生成的频繁场景规则在实际应用中并不实用。为了解决这个问题，我们定义了可执行场景规则挖掘问题。一条场景规则如果是可执行的，那么其后件中每一个事件的确切发生时间应该报告给用户。通过可执行场景概念，可将一条可执行场景规则划分为两个不同的部分，其中传统的场景作为前件，而可执行场景作为后件。然后，我们提出了生成可执行场景规则的解决框架MAER，并提出了若干高效算法分别获得规则的候选前件以及候选后件。 (4)频繁场景挖掘算法在股票投资交易和发现轰动新闻场景中的应用 将可执行场景规则挖掘框架以及算法应用到股票投资交易中，基于可执行场景规则完成自动化交易决策。在2011年至2014年的中国股市数据上取得了良好的预测效果和收益。在文本挖掘领域，提出了发现轰动新闻场景的新应用及其解决框架。框架主要分为:(1)新闻事件提取;(2)频繁2-场景挖掘;(3)排序学习新闻场景轰动效应。将MEELO算法用于框架的第二步，并在第三步提出了一种排序学习的方法从大量频繁新闻场景中发现具有轰动效应的那些新闻场景。在一个采自Twitter的新闻数据集上取得了良好的效果。