基于AR_TSM的时间序列motif关联规则挖掘方法研究

挖掘时间序列motif间潜在的关联规则可以在预测未来趋势方面发挥重要作用,时间序列motif即时间序列中先前未知的重复出现的模式。针对符号化时间序列提取motif导致信息丢失的问题,提出基于剪枝技术的motif提取算法PM_Motif,实现了保留原始信息的motif的精准快速提取;针对分割motif来发现其内部关联规则导致的规则不一致的问题,从motif间的关联规则入手,给出了基于AR_TSM方法的时间序列motif关联规则挖掘算法,从根本上避免了因motif分割引起的不确定性,保证了规则的一致性;最后,引入了关联规则评价参数RM,在多数据集上证明了关联规则的预测性能。     

低冗余计算的可达性查询保持图压缩策略

针对可达性查询保持图压缩（QPGC）算法存在冗余计算的问题,提出了一种高性能压缩策略。在求解顶点的祖先后代集阶段,针对普通图数据,提出一种基于拓扑排序的求解算法TSB,首先将图数据顶点拓扑排序,然后沿拓扑序列顺序（逆序）求解顶点的祖先（后代）集,避免了求解顺序不明确导致的冗余计算;针对最长路径较短的图数据,提出一种基于图聚合运算的求解算法AGGB,可在确定次数的聚合运算内完成顶点的祖先和后代集的求解。在求解可达性等价类阶段,提出一种分段统计剪枝算法PSP,先对祖先后代集分段统计,再比较统计值以实现粗匹配,剪除了部分不必要的精细匹配。实验结果表明,与QPGC算法相比：在祖先后代集求解阶段,TSB和AGGB在不同数据集上的性能平均提升94.22%和90.00%;在求解可达性等价类阶段,PSP算法在大部分数据集上性能提升超过70%;随着数据集的增大,TSB和AGGB配合PSP算法,性能提升了近28倍。理论分析和模拟实验表明,该策略与QPGC算法相比冗余计算更少、压缩速度更快。