机场航站楼内员工的频繁路径挖掘技术研究

门禁管理系统在机场航站楼内的推广应用会产生海量的员工路径数据。为了挖掘员工的频繁路径,提出一种基于路径编码的改进Prefix Span算法。在递归挖掘过程中,只检查投影序列关于前缀的最近后缀,避免产生非法的投影数据库,在投影序列数小于最小支持数时停止扫描。实验结果表明,该算法在时间和空间上比Prefix Span算法优越,能合理有效地挖掘出员工的频繁路径。     

一种基于序列末项位置信息的序列模式挖掘算法

针对PrefixSpan算法中反复扫描投影数据库寻找局部频繁项并重复构造挖掘大量重复投影数据库的不足,提出一种基于序列末项位置信息的序列模式挖掘算法SPM-LIPT。通过连接2-序列位置信息表(LIPT)找到序列模式的下一项,实现序列模式增长,避免对投影数据库反复扫描;同时通过检查相同末项序列首位置信息表(SLIFPT)进行前向剪枝;消除大量重复投影的构建。最后通过实验证明了算法的有效性。     

基于位置信息的序列模式挖掘算法*

PrefixSpan算法在产生频繁序列模式时会产生大量的投影数据库,其中很多投影数据库是相同的。提出了基于位置信息的序列模式挖掘算法——PVS,该方法通过记录每个已产生投影数据库的位置信息,避免了重复产生相同的投影数据库,从而提高了算法的运行效率。通过实验证明,该算法在处理相似度很高的序列数据时比PrefixSpan算法有效。     

一种改进的LIPI数据挖掘算法的仿真分析

在传统LIPI数据挖掘算法中,需要反复扫描投影数据库寻找局部频繁项并重复构造大量重复投影,造成数据挖掘耗时,效率低下的不足.为了提高算法的计算速度,提出改进的LIPI数据挖掘算法.算法借助连接2-序列位置信息表(LIPI)找到序列模式的下一项,完成K-1序列位置信息与2-序列位置信息的连接,实现序列模式放缩式增长,得出K-序列与K-序列相应的位置信息数据,避免对投影数据库反复扫描;引入了BIDE算法的前后向剪枝策略,检查相同末项序列位置信息表进行前向剪枝,消除大量重复投影的构建,提高挖掘算法的效率.实验结果表明,改进后的算法能快速的寻找到局部频繁项,有效提高了数据挖掘的效率.     

无重复投影数据库扫描的序列模式挖掘算法

序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan.     

基于序列前缀技术的XML频繁路径挖掘算法

XML文档是半结构化数据,对其进行频繁路径挖掘可以分为两步：XML文档序列化和序列挖掘阶段. 现有的序列化方式将XML文档表示为Xpath路径集合,其中有大量的节点冗余;序列挖掘阶段采用的类Apriori算法需要多次扫描数据库并产生大量的候选集,采用的PrefixSpan算法会产生大量的投影数据库,占用较大的内存. 针对以往XML频繁路径挖掘算法存在的不足,本文提出一种高效的挖掘算法——基于序列前缀技术的XML频繁路径挖掘算法（PXFP,Prefix-based XML Frequent Path Mining Algorithm）. PXFP算法以广度优先方式遍历XML文档树并将每个节点表示为“节点：父节点”的形式,这种序列化的方式减少了节点冗余. 在序列挖掘阶段借鉴PrefixSpan 算法中前缀的概念,但不产生投影数据库,仅得到直接后缀（即前缀的子节点）,通过记录频繁子路径的位置信息逐渐扩大频繁模式的长度,位置信息的引入减少了对数据库的扫描. 实验结果表明,PXFP算法取得了比PrefixSpan算法更高的时间和空间效率.     

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

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

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

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

一种有效的序列模式增量式更新方法

针对序列模式增量式更新挖掘算法产生大量候选项集以及多次扫描数据库的问题,提出了一种有效的增量式更新算法ESPIA,该算法利用基于2-序列矩阵挖掘算法ESPE对原数据库和增加数据库一次扫描产生序列模式,通过对频繁模式和非频繁模式进行相应的剪枝减少了序列的比较和扫描次数,降低了算法时间和空间复杂度,实验证明该算法是有效和准确的。     

一种适用于应用层协议的特征提取算法

基于PrefixSpan算法,提出一种适用于应用层协议的特征提取算法。通过加入关于位置的约束,减少频繁序列模式的产生数量,结合特征提取过程的实际情况加入约束条件,从而在挖掘过程中减少投影数据库产生的个数,在构建投影数据库过程中,去除关于非频繁项的存储及投影数据库中序列数小于最小支持度的扫描过程。实验结果表明,与原算法相比,该算法的运行时间较短,提取的特征具有较高的准确率和较低的误报率。