序列模式图及其构造算法

序列模式挖掘是数据挖掘的一个重要分支。在序列事务及有关信息处理中有着广泛的应用,目前已有许多序列模式模型及相应的挖掘算法,该文在对序列模式挖掘问题及挖掘算法进行分析的基础上。定义了一种称为序列模式图的序列模式框架。用于表示序列模式挖掘过程发现的所有序列模式,序列模式图是由离散状态的序列集到统一的图结构的桥梁,可以将序列模式挖掘结果统一到序列模式图中来,基于序列模式图进行研究可发现某些结构化的新知识,称之为后序列模式挖掘,文中还给出了序列模式图的有关性质及构造算法。     

基于H-tree的多维序列模式挖掘算法

提出了一种基于H-tree的多维序列模式挖掘算法,首先在序列信息中挖掘序列模式,然后针对每个序列模式,根据包含此模式的所有元组中的多维信息构造H-tree树,挖掘出相应的多维模式,从而得到了多维序列模式。该算法将多维分析方法与序列模式挖掘算法有效地结合在一起,当维度较高时具有较高的性能。     

带通配符和One-Off条件的序列模式挖掘

很多应用领域产生大量的序列数据。如何从这些序列数据中挖掘具有重要价值的模式,已成为序列模式挖掘研究的主要任务。研究这样一个问题：给定序列S、支持度阈值和间隔约束,从序列S中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束。设计了一种有效的带有通配符的模式挖掘算法One-Off Mining,模式在序列中的出现满足One-Off条件,即模式的任意两次出现都不共享序列中同一位置的字符。在生物DNA序列上的实验结果表明,One-Off Mining比相关的序列模式挖掘算法具有更好的时间性能和完备性。     

网络入侵检测中序列模式挖掘技术研究

面向入侵检测的数据挖掘是目前国际上网络安全和数据库、信息决策领域的最前沿的研究方向之一。入侵检测中进行序列模式挖掘时,由于频繁网络模式和频繁系统活动模式只能在网络或操作系统的单个审计数据流中获得,因而传统从事件流数据中获取单序列模式的算法,以及从不同多数据序列中获取多个序列模式的算法都不再适用。本文研究了入侵数据的特性,提出了网络入侵检测中序列模式挖掘框架和实时序列模式挖掘模型,并设计了一种新的面向入侵检测．基于轴属性、参考属性、相关支持度的序列模式挖掘算法SPM—ID(Sequential Patterns Mining for Intrusion Detection)。最后在KDD Cup99数据集的基础上实现算法及分析算法的性能。     

去冗余Top-k对比序列模式挖掘

对比序列模式可以用来表征不同类别数据集之间的差异。在生物信息、物流管理、电子商务等领域,对比序列模式有着广泛的应用。Top-k对比序列模式挖掘的目标是发现数据集中对比度最高的前k个序列模式。在Top-k对比序列模式挖掘中,可能挖掘出冗余的序列模式。目前,虽然有Top-k对比序列模式发现算法被提出,但这些算法并未考虑冗余序列模式的问题。为此,本文提出了基于广度优先生成树的去冗余Top-k对比序列模式挖掘算法BFM（breadth-first miner）。使用BFM算法可以有效地解决冗余问题,得到去冗余的Top-k对比序列模式。在BFM算法的基础上,提出了性能更好的算法PBFM（pruning breadth-first miner）。通过在真实数据集上的实验分析与对比 ,验证了本文算法的有效性。     

基于密度感知模式的生物序列分类算法

针对现有的基于模式的序列分类算法对于生物序列存在分类精度不理想、模型训练时间长的问题,提出密度感知模式,并设计了基于密度感知模式的生物序列分类算法——BSC。首先,在生物序列中挖掘具有"密度感知"的频繁序列模式;然后,对挖掘出的频繁序列模式进行筛选、排序制定成分类规则;最后,通过分类规则对没有分类的序列进行分类预测。在4组真实生物序列中进行实验,分析了BSC算法参数对结果的影响并提供了推荐参数设置;同时分类结果表明,相比其他四种基于模式的分类算法,BSC算法在实验数据集上的准确率至少提高了2.03个百分点。结果表明,BSC算法有较高的生物序列分类精度和执行效率。     

考虑价格的跨种类模糊序列模式挖掘算法*

消费者对不同种类的产品具有不同的价格偏好,而传统的序列模式挖掘算法仅考虑序列中不同项目的出现顺序,使得挖掘到的序列模式没有包含产品价格以及种类等重要信息。为了克服传统算法的这一缺陷,在序列模式中体现更多的用户行为信息,本文基于模糊集理论,提出了一种在产品种类维度上进行的跨种类模糊价格序列模式挖掘算法。实验结果表明,与传统序列模式挖掘算法相比,该算法可以有效解决序列数据的稀疏性问题,能够挖掘得到更多个性化的序列模式。     

基于不定长系统调用序列模式的入侵检测方法

提出了一种不定长序列模式的寻找算法,目标是从训练序列中找出一组基本的、相对独立的不定长序列模式。并在模式集的更新过程中自动定义了模式间的前后次序关系,以此构建了一个描述进程执行模式的DFA。针对已有基于不定长序列模式的模式匹配算法需要向前预测若干个系统调用号的缺点,文章设计了一个更好的模式匹配算法。实验结果表明,算法在模式寻找过程中是稳定的,并在保持一组规模很小的模式集的情况下,取得了很低的误报率和漏报率。     

基于Spark的Top-k对比序列模式挖掘

对比序列模式(distinguishing sequential pattern, DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如：构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSP-Miner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.     

并发序列模式挖掘方法研究

提出并发关系的概念,在此基础上给出并发度的概念,进而提出并发序列模式的概念。给出了用于挖掘并发序列模式的方法——基于支持向量的并发序列模式挖掘方法。该方法通过产生序列模式的支持向量求得2-分支并发序列模式及其支持向量;然后通过（k-1）-分支并发序列模式的支持向量和序列模式的支持向量产生k-分支并发序列模式及其支持向量,进而求得所有k分支并发序列模式。实验中采用IBM数据生成器产生的合成数据源对算法进行了验证实现,实验表明算法是有效和可行的,在不同的支持度和最小并发度下,挖掘得到并发序列模式总数随最小并发度的增大呈指数递减。     

序列模式挖掘研究

为了更好地分析购物篮数据,挖掘出潜在客户,序列模式挖掘应运而生。序列模式挖掘是数据挖掘一个重要研究内容,近年来在很多领域得到广泛运用。概述序列模式挖掘的发展现状,研究基本挖掘框架的经典挖掘算法与扩展模型挖掘算法,特别针对近年来出现的新数据形式序列模式挖掘,以及基于零压缩二叉决策图(ZBDD)结构的挖掘算法做了阐述,最后对序列模式挖掘发展趋势进行了展望。     

基于序列模式挖掘的入侵检测系统的研究

对入侵检测和数据挖掘从定义和分类等各方面等进行了基本介绍,提出了一个基于数据挖掘的入侵检测系统的总体框架,其整个系统分为训练阶段和测试阶段,对其中各个模块进行基本的功能分析。为了提高数据挖掘的效率,可以将序列模式挖掘引入该入侵检测系统中。将关联规则算法和序列模式挖掘算法同时使用,增加挖掘的粒度。对序列模式挖掘的算法进行了具体分析,并通过具体的实例来说明引入序列模式挖掘能更好地提高数据挖掘的效率。     

基于模糊序列模式挖掘的网络异常检测

序列模式挖掘技术在网络入侵检测中极具应用潜力。该文将模糊序列模式挖掘引入网络异常检测,构建了基于模糊序列模式挖掘的网络异常检测模型,介绍了模型中的主要工作流程。     

OSAF-tree--可迭代的移动序列模式挖掘及增量更新方法

移动通信技术和无限定位技术的发展积累了海量的、动态增长的时空数据．利用数据挖掘技术从移动用户的时空行为轨迹当中挖掘用户移动序列模式,在移动通信、交通管理、基于位置服务等领域有着广泛的应用前景．由于移动环境网络资源珍贵、数据量大的特点,传统的序列模式挖掘方法在效率上很难满足需求．OSAF-tree算法基于投影的概念,只需要对数据库进行一遍扫描,就可以很好地处理移动序列模式的挖掘及其增量更新和迭代挖掘问题,这是一个非常高效的算法．与已有的方法相比,OSAF-tree算法在性能和I/O代价等方面都具有明显的优势．     

Constraint-based sequential pattern mining: the pattern-growth methods

Constraints are essential for many sequential pattern mining applications. However, there is no systematic study on constraint-based sequential pattern mining. In this paper, we investigate this issue and point out that the framework developed for constrained frequent-pattern mining does not fit our mission well. An extended framework is developed based on a sequential pattern growth methodology. Our study shows that constraints can be effectively and efficiently pushed deep into the sequential pattern mining under this new framework. Moreover, this framework can be extended to constraint-based structured pattern mining as well. This research is supported in part by NSERC Grant 312194-05, NSF Grants IIS-0308001, IIS-0513678, BDI-0515813 and National Science Foundation of China (NSFC) grants No. 60303008 and 69933010. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.     

基于深度优先序列模式挖掘的预取模型

序列模式挖掘能够发现隐含在Web日志中的用户的访问规律,可以被用来在Web预取模型中预测即将访问的Web对象。目前大多数序列模式挖掘是基于Apriori的宽度优先算法。提出了基于位图深度优先挖掘算法,采用基于字典树数据结构的深度优先策略,同时采用位图保存和计算各序列的支持度,能够较迅速地挖掘出频繁序列。将该序列模式挖掘算法应用于Web预取模型中,在预取缓存一体化的条件下实验表明具有较好的性能。     

序列模式挖掘研究与发展

序列模式挖掘是数据挖掘的一个重要研究课题,它在很多领域中都有着广泛的应用.首先讨论了序列模式挖掘的相关背景,然后对序列模式挖掘进行分类,并在此基础上对每一类序列模式挖掘算法的特点进行了介绍和比较;最后,对序列模式挖掘未来的研究重点进行展望,以便研究者对序列模式挖掘做进一步的研究.     

流数据中一种高效剪枝的频繁序列挖掘算法

序列模式挖掘就是在时序数据库中挖掘相对时间或其他模式出现频率高的模式.序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景.针对静态数据库,序列模式挖掘已经被深入的研究.近年来,出现了一种新的数据形式:数据流.针对基于数据流的序列模式挖掘的研究还不是十分深入.提出一个有效的基于数据流的挖掘频繁序列模式的算法SSPM,利用到2个数据结构(F-list和Tatree)来处理基于数据流的序列模式挖掘的复杂性问题.SSPM的优点是可以最大限度地降低负正例的产生,实验表明SSPM具有较高的准确率.     

基于闭合序列模式的减量挖掘算法

针对数据库减量时不断重复挖掘的问题,在已有闭合序列模式算法PosD*的基础上,提出一种减量挖掘算法 DePosD*。通过移动频繁和非频繁闭合序列集合之间的数据,在原有挖掘结果上直接进行更新,减少挖掘的时间。实验结果证明,在减量过程中该算法的时间效率与PosD*相比有所提高。