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

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

一般间隙与One-Off条件的序列模式匹配

带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.

带有间隔约束的多序列模式挖掘

研究这样一个问题:给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off条件。在解决该问题上,已有算法M-OneOffMine在计算模式的支持度时,只考虑模式的每个字符在序列中的首次出现,导致计算的模式支持度远小于其真实支持度,以致许多频繁的模式没有被挖掘出来。为此,设计了一个有效的带有间隔约束的多序列模式挖掘算法——MMSP算法:首先,通过采用二维表保存模式的候选位置;然后,根据候选位置采用最左最优的思想选择匹配位置。通过生物DNA序列进行实验,多序列中元素序列数目不变而序列长度变化时,MMSP挖掘出的频繁模式总数是同类算法M-OneOffMine的3.23倍;在元素序列个数变化时,MMSP挖掘出的频繁模式个数平均是M-OneOffMine的4.11倍;这两种情况下MMSP都有更好的时间性能。在模式长度变化时,MMSP挖掘出的频繁模式个数分别平均是M-OneOffMine的2.21倍和MPP的5.24倍。同时还验证了M-OneOffMine挖掘到的模式是MMSP挖掘到的频繁的子集。实验结果表明,MMSP算法不仅可以挖掘到更多的频繁模式,而且时间花费更少,更适合于实际的应用。

求解PMWOC问题的位并行算法

带有灵活通配符和One-Off条件的模式匹配问题(pattern matching with flexible wildcards and One-Off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即One-Off条件。提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描。通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响。

带通配符的多序列模式挖掘

带有通配符的多序列模式挖掘在文本检索、网络安全、生物科学等领域中具有很重要的作用.通过挖掘多序列模式,能够透彻的了解序列之间的联系,在各个领域中具有重要的现实意义.在已有的工作中,随着多序列集长度的增大,挖掘的规模呈现指数级增长.研究这样一个问题:给定多条序列s1,…,sn,支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一个有效的算法M-OneOffMine,模式在序列中的出现满足one-off条件.在生物DNA序列上的实验结果表明,M-OneOffMine算法比相关的序列模式挖掘算法具有更好的时间性能.

水质时间序列模式挖掘

对水质时间序列进行数据挖掘,找出其蕴含的模式,对于水资源的改善有重要的现实意义。针对带间隔约束的有序时间序列的模式挖掘,现有算法多按左优先匹配以完备性为代价加快效率或枚举可能位置损失效率提高完备性。为了提高模式挖掘的效率同时保证一定的完备性,提出一种满足One-Off条件的带有间隔约束的单序列模式挖掘算法FOFM(fast one-offing mining)。算法首先扫描序列获得长度为1的模式,再通过将当前长度的所有频繁模式进行两两比较,而后连接可连接的模式以形成新的模式,在模式连接的过程中记录候选模式最后事件的可能位置并通过回溯位置序列的方法检查模式的支持度,直至无法生成新的模式。实验结果表明,FOFM算法在水质时间序列上相较于相关序列模式挖掘算法拥有较高的效率和一定的完备性。