面向置换检验的冗余对比模式过滤算法

置换检验方法在进行对比模式挖掘时,返回结果中存在许多冗余对比模式。利用Charm方法挖掘样本集合中的对比模式,提出基于固定属性置换的FSPRP和FEPRP算法,依次为不同长度的对比模式构建零分布,从而过滤冗余对比模式。FSPRP算法通过生成一定数量的置换样本集合构建零分布,FEPRP算法则通过计算每个模式的对比性度量值分布合并建立零分布。实验结果表明,FSPRP和FEPRP算法相较于比较约束法能够过滤较多数量的冗余对比模式,并且FEPRP算法生成的零分布更接近精确零分布。     

面向对比序列模式发现的独立精确置换检验算法

传统的对比序列模式挖掘算法存在一定数量的假阳性对比序列模式,其提供的错误信息会干扰后续任务的决策。设计一种IEP-DSP算法过滤假阳性对比序列模式。运用spade方法和WRAcc对比性度量找到候选对比序列模式和所有置换数据集合中的对比序列模式,通过模拟置换过程,使用独立精确置换检验方法为不同长度的模式建立独立精确零分布,并计算每个候选对比序列模式的精确p-value,运用错误发现率度量将各个长度的假阳性对比序列模式数量控制在置信度为α的统计显著水平下。在真实数据集和仿真数据集上的实验结果表明,IEP-DSP算法够过滤掉大量的假阳性对比序列模式,相比基于统计显著性检验的方法能保留更多的真对比序列模式,验证了独立精确置换检验相较于标准置换检验的优越性。     

基于标准置换检验的差异序列模式挖掘算法

为了去除差异序列模式挖掘算法返回结果中的假阳性差异序列模式,提出了一个基于标准置换假设检验的算法SP-DSP。该算法首先运用GSP算法挖掘频繁序列模式,然后基于growth rate阈值生成差异序列模式候选集,并运用标准置换检验计算候选集合中每个模式的p-value,最后运用多重假设检验度量过滤假阳性差异序列模式。实验结果证明SP-DSP算法能够去除掉一定数量的假阳性模式并尽可能地保留真差异序列模式,从而促进后续分类任务正确率的提升。     

基于频繁序列树的交互式序列模式挖掘算法

为了减少在序列模式挖掘过程中由于重复运行挖掘算法而产生的时空消耗,提出了一种基于频繁序列树的交互式序列模式挖掘算法(ISPM). ISPM算法采用频繁序列树作为序列存储结构,频繁序列树中存储数据库中满足频繁序列树支持度阈值的所有序列模式及其支持度信息.当支持度发生变化时,通过减少本次挖掘所要构造投影数据库的频繁项的数量来缩减投影数据库的规模,从而减少时空消耗.实验结果表明,ISPM算法在时间性能上优于PrefixSpan算法和Inc-Span算法     

基于Bitmap的序列模式挖掘的改进算法

结合BBSP,提出了一种称做最终位置归纳序列模式挖掘（LPI-SPM）的新算法,该算法可以有效地从大型数据库中获取所有的频繁序列模式。该策略与以前工作的不同点在于：当判断一个序列是否是模式时,通过扫描数据库创建S-矩阵来实现（PrefixSpan）或者通过对候选项进行交运算（SPADE）或并运算（BBSP）统计其数量来实现。相反,在基于下列事实的基础上LPI-SPN会很容易实施这一过程,即若一个项的最终位置小于当前前缀位置,在相同的顾客序列中,该项就不会出现在当前前缀的后面。LPI-SPM在序列挖掘过程中可以大大缩减搜索空间,而且挖掘序列模式的效力可观。实验结果表明,在各种数据集合中LPI-SPM胜过BBSP三倍。     

在大型数据集上提高序列挖掘效率的统计方法

分析了在大型事务集合发现频繁模式的特点,给出了一个改进算法（称为AprioriAdjust算法）,同时,发展了两项技术：（1）提出了事务集合的压缩过程。（2）展示了一种基于统计模式的方法来评价序列的支持度,在该方法中,考虑了整个过程中每一趟的支持度均值的收敛性,以进行有效的候选频繁集的剪枝。此外,还讨论了实验结果。比较AprioriTID算法,研究展示,AprioriAdjust算法在进行大型事务集合的挖掘时更有效,可扩展性更强。     

一种新的Web频繁访问模式挖掘算法

提出了一种基于有向图的从Web日志中挖掘用户频繁访问模式的新算法,与传统使用基于关联规则挖掘的序列模式挖掘技术相比,本算法采用有向图来记录Web访问序列和它的计数,在挖掘过程中只需要扫描数据库一次,不产生数量庞大的候选模式,即可直接挖掘出所有的Web频繁访问路径,大大提高了Web访问模式的发现效率。     

基于Bitmap的序列模式挖掘的改进算法

结合BBSP,提出了一种称做最终位置归纳序列模式挖掘(LPI-SPM)的新算法,该算法可以有效地从大型数据库中获取所有的频繁序列模式。该策略与以前工作的不同点在于:当判断一个序列是否是模式时,通过扫描数据库创建S-矩阵来实现(PrefixSpan)或者通过对候选项进行交运算(SPADE)或并运算(BBSP)统计其数量来实现。相反,在基于下列事实的基础上LPI-SPN会很容易实施这一过程,即若一个项的最终位置小于当前前缀位置,在相同的顾客序列中,该项就不会出现在当前前缀的后面。LPI-SPM在序列挖掘过程中可以大大缩减搜索空间,而且挖掘序列模式的效力可观。实验结果表明,在各种数据集合中LPI-SPM胜过BBSP三倍。     

一种基于逻辑的频繁序列模式挖掘算法

传统的类Apriori频繁序列模式挖掘算法都是基于支持度框架理论,需要预先设定支持度阈值,而这通常需要较深的领域知识或大量的实践,因此目前仍没有一种很好的设定方法.同时,序列模式的挖掘结果往往数量很大且不易理解,可用性较低.针对上述问题,提出了一种基于逻辑的频繁序列模式挖掘算法即LFSPM算法,并首次在频繁序列模式挖掘算法中引入了逻辑的思想,通过逻辑规则过滤,大大优化了结果集.实验证明,该算法较好地解决了支持度设置问题及挖掘结果可理解性不高的问题.     

基于广度优先的序列模式挖掘算法

序列模式挖掘的典型算法-GSP算法及其之后的许多相关算法的重点都是放在寻找所有的序列模式上面。CloSpan算法首先提出搜索封闭集合的思想。封闭集合比全集合更精简有效,并且和全集合有着相同的表达能力。文章的ERIC算法同样用于搜索封闭集合。然而不同于之前算法多采用深度优先的策略,ERIC算法是基于广度优先的。它利用列表来保存序列的位置数据,通过利用序列的有序性,以及基于后向超模式与等位置数据的两个修剪技巧来提高算法的搜索效率。为了确保储存最终结果列表的简洁,ERIC算法对一些特殊情况进行了分析。从最终的试验结果可以看出,ERIC算法在较小支持度的情况下对中大型数据库有很好的搜索效率。     

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

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

一种挖掘压缩序列模式的有效算法

从序列数据库中挖掘频繁序列模式是数据挖掘领域的一个中心研究主题,而且该领域已经提出和研究了各种有效的序列模式挖掘算法.由于在挖掘过程中会产生大量的频繁序列模式,最近许多研究者已经不再聚焦于序列模式挖掘算法的效率,而更关注于如何让用户更容易地理解序列模式的结果集.受压缩频繁项集思想的启发,提出了一种CFSP(compressing frequent sequential patterns)算法,其可挖掘出少量有代表性的序列模式来表达全部频繁序列模式的信息,并且清除了大量的冗余序列模式.CFSP是一种two-steps的算法:在第1步,其获得了全部闭序列模式作为有代表性序列模式的候选集,与此同时还得到大多数的有代表性模式;在第2步,该算法只花费了少量的时间去发现剩余的有代表性序列模式.一个采用真实数据集与模拟数据集的实验研究也证明了CFSP算法具有高效性.     

Mining minimal distinguishing subsequence patterns with gap constraints

Discovering contrasts between collections of data is an important task in data mining. In this paper, we introduce a new type of contrast pattern, called a Minimal Distinguishing Subsequence (MDS). An MDS is a minimal subsequence that occurs frequently in one class of sequences and infrequently in sequences of another class. It is a natural way of representing strong and succinct contrast information between two sequential datasets and can be useful in applications such as protein comparison, document comparison and building sequential classification models. Mining MDS patterns is a challenging task and is significantly different from mining contrasts between relational/transactional data. One particularly important type of constraint that can be integrated into the mining process is the gap constraint. We present an efficient algorithm called ConSGapMiner (Contrast Sequences with Gap Miner), to mine all MDSs satisfying a minimum and maximum gap constraint, plus a maximum length constraint. It employs highly efficient bitset and boolean operations, for powerful gap-based pruning within a prefix growth framework. A performance evaluation with both sparse and dense datasets, demonstrates the scalability of ConSGapMiner and shows its ability to mine patterns from high dimensional datasets at low supports.     

多层次序列模式采掘算法及其在供需链管理中的应用

供需链管理中一个重要的问题是加快处理各类交易数据,由于经济的全球化趋势,一 个先进企业或商业机构会不断地获取到来自于自身以及全球供需链中其他企业的各类数据, 包括生产、供应、销售等,往往还包括竞争对手的各类数据,如何从这些海量的数据中获取 有用信息成为非常紧迫的问题,数据采掘技术的出现为有效信息获取和即时分析提供了有效 手段．本文从市场数据的多层次性上着手,提出了一种在用于发现多层次序列模式信息的有 效算法,并给出了在分析顾客基础数据上的应用案例．     

基于投影数据集的序列模式增量挖掘算法

提出一种基于投影数据集的序列增量更新算法Inc_SPM,该算法以PrefixSpan算法为基础。首先利用已有的知识得出频繁1序列,然后生成投影数据集以迭代产生频繁k序列;同时为了控制投影数据集的规模,利用等价投影数据集来改进投影终止条件。     

基于PrefixSpan的序列模式挖掘改进算法

针对序列模式挖掘算法PrefixSpan在挖掘过程中需要构造大量投影数据库的不足,提出IPMSP算法,在递归挖掘过程中,通过检查序列数据库关于前缀的前缀,避免对同一频繁前缀模式构造重复投影数据库,同时舍弃对非频繁项的存储并在投影序列数小于最小支持度时停止扫描投影数据库,从而提高PrefixSpan算法的时空性能。实验结果证明,IPMSP算法在时间和空间性能上优于PrefixSpan算法。     

数据流中基于滑动窗口的序列模式挖掘算法

序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景。针对静态数据库,序列模式挖掘已经被深入地研究,但针对基于数据流的序列模式挖掘的研究还不是十分深入。数据流有着无限性的特性,因此往往不能保存数据流中全部的数据,同时很多时候只对最近的时间段的序列模式感兴趣,提出一个有效的结合滑动窗口技术的挖掘序列模式的算法FPM-SW,算法利用到3个数据结构（PatternTable,CountTable和Ta-tree）来处理基于数据流的序列模式挖掘的复杂性问题。算法通过CountTable结构来保存以往的潜在频繁序列,考虑到在某些情况下CountTable占用内存过多,算法还结合了一种压缩CountTable技术来减少内存占用。FPM-SW的优点是可以最大限度地降低负正例的产生,实验表明FPM-SW具有较高的准确率。     

Efficient strategies for parallel mining class association rules

Mining class association rules (CARs) is an essential, but time-intensive task in Associative Classification (AC). A number of algorithms have been proposed to speed up the mining process. However, sequential algorithms are not efficient for mining CARs in large datasets while existing parallel algorithms require communication and collaboration among computing nodes which introduces the high cost of synchronization. This paper addresses these drawbacks by proposing three efficient approaches for mining CARs in large datasets relying on parallel computing. To date, this is the first study which tries to implement an algorithm for parallel mining CARs on a computer with the multi-core processor architecture. The proposed parallel algorithm is theoretically proven to be faster than existing parallel algorithms. The experimental results also show that our proposed parallel algorithm outperforms a recent sequential algorithm in mining time.     

一种基于MDL的日志序列模式挖掘算法

日志数据是互联网系统产生的过程性事件记录数据,从日志数据中挖掘出高质量序列模式可帮助工程师高效开展系统运维工作。针对传统模式挖掘算法结果冗余的问题,提出一种从时序日志序列中挖掘序列模式(DTS)的算法。DTS采用启发式思路挖掘能充分代表原序列中事件关系和时序规律的模式集合,并将最小描述长度准则应用于模式挖掘,设计一种考虑事件关系和时序关系的编码方案,以解决模式规模爆炸问题。在真实日志数据集上的实验结果表明,与SQS、CSC与ISM等序列模式挖掘算法相比,该算法能高效挖掘出含义丰富且冗余度低的序列模式。