论文部分内容阅读
序列模式挖掘是挖掘相对时间或其他模式出现频率高的模式。相对于正序列模式挖掘仅考虑了已发生的事件,负序列模式挖掘还考虑了缺失的（未发生的）事件,能够提供更全面的决策信息,越来越受到人们的重视。然而,现有的负序列模式挖掘算法使用了过于严格的约束条件,以至于很多有价值的信息无法被挖掘,例如,负元素约束限制负序列的最小负单位为元素即仅允许形如s1=<?（a,b）（c,d）>和s2=<（a,b）?（c,d）>的负序列,而不允许形如s3=<（?a,b）（c,?d）>（括号表示一个元素,元素里包含负项）的负序列。事实上,s3在现实生活中要比s1和s2更常见。为解决这一问题,本文取消这一限制,开始研究基于项缺失的负序列模式挖掘算法,并对由此带来的负包含定义复杂性,支持度计算花费等关键问题进行了研究。此外,本文还研究了top-k负序列模式挖掘问题,单一最小支持度对筛选模式的不公平性问题以及非频繁序列模式中隐含大量有价值的负序列模式问题。具体内容如下:1.提出了基于项缺失的负序列模式挖掘算法——NegI-NSP。首先,NegI-NSP算法提出了尽可能宽松的约束机制,即实现了基于项缺失的负序列模式挖掘。其次,NegI-NSP算法提出了一个基于项缺失的负包含定义。该定义能覆盖数据序列是否包含基于项缺失的负序列的所有情况。最后,NegI-NSP算法证明了基于项缺失的负序列支持度计算公式,使得仅通过正序列的相关信息就可以得到负序列的支持度,有效的提高了算法的时间效率。2.提出了基于项缺失的top-k负序列模式挖掘算法——TopkI-NSP。NegI-NSP算法虽然实现了挖掘基于项缺失的负序列模式,但它并没有解决用户由于专业知识的有限无法设置合理的最小支持度得到期望的模式数量问题。为了解决这一问题,我们提出了TopkI-NSP算法。首先,TopkI-NSP算法中无需用户设置最小支持度阈值且能得到期望模式数量。其次,TopkI-NSP算法中充分考虑了正序列模式对负序列模式挖掘的影响并提出了相应的策略。最后,TopkI-NSP算法提出了优化时间效率的策略,实验结果表明该策略是非常有效的。3.提出了基于两级多最小支持度的负序列模式挖掘算法——I-msNSP。NegI-NSP算法中仅从频繁序列（正序列模式）中挖掘负序列模式,而忽略掉了非频繁序列中同样包含大量有价值的负序列模式。为了解决这一问题,我们提出了I-msNSP算法。该算法中使用两级多最小支持度（2-LMMS）约束非频繁序列,即根据不同单项序列在数据库中的出现频率为每个项设置合理两个最小支持度阈值用以筛选频繁和非频繁序列。实验结果表明I-msNSP算法能够有效地挖掘非频繁序列中的负序列模式。4.提出了基于多级最小支持度的负序列模式挖掘算法——MLMS-NSP。NegI-NSP算法中仅使用单一最小支持度筛选序列模式,这对长尺寸的序列是不公平的。如果最小支持度太高,则发现的长尺寸序列很少;如果最小支持度太低,发现的短尺寸序列很多,这将会增加用户选择有用的序列模式的困难。为了解决这一问题,我们提出了MLMS-NSP算法。首先,MLMS-NSP算法能够根据序列的尺寸大小设置不同级的最小支持度阈值,用于挖掘出更多有价值的负序列模式。其次,MLMS-NSP算法通过设置最小支持度阈值,挖掘非频繁序列模式。最后,实验结果证明MLMS-NSP算法是非常有效的。