引用本文

王玲, 孟建瑶, 李俊飞, 彭开香. 基于多维时态关联规则的演化模糊推理预测算法. 自动化学报, 2018, 44(8): 1446-1459. doi: 10.16383/j.aas.2018.c170222

WANG Ling, MENG Jian-Yao, LI Jun-Fei, PENG Kai-Xiang. An Evolving Fuzzy Inference Algorithm With Multi-dimensional Temporal Association Rules. ACTA AUTOMATICA SINICA, 2018, 44(8): 1446-1459. doi: 10.16383/j.aas.2018.c170222

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170222

关键词

多维时态关联规则，模糊推理，演化，概念漂移 

摘要

挖掘时态关联规则的目的是为了发现带有时态信息的项集之间有趣的关系.由于数据库经常动态更新，时态关联规则的挖掘也应该适应数据库的更新.然而，现有的大多数算法不仅需要重新挖掘更新的数据库，浪费了大量的时间和效率，而且不能利用已存在的规则定量地预测某些项的变化趋势.本文提出了一个基于多维时态关联规则的演化模糊推理预测建模算法（Evolving fuzzy inference model based on multidimensional temporal association rules，EFI-MTAR），主要优势是构建了一种基于多维时态关联规则的模糊推理建模算法（Fuzzy inference modeling algorithm based on multidimensional temporal association rules，FI-MTAR），实现了对时间序列的定量预测.此外，为了降低规则更新的代价和加快规则预测的速度，提出了概念漂移检测策略来处理时间序列数据以适应数据库的动态更新.实验结果表明了本文提出算法的有效性和准确性.

文章导读

多维实时序列数据是现实世界中一种普遍存在且具有重要意义的数据类型, 例如工业现场的监控数据、互联网节点的通信流量数据、气象数据、医疗监测数据以及语音视频数据等.这些数据通常以时间点或时间区间的形式存在, 且呈现出多属性、非平稳、动态性以及信息的非线性等特征, 因此, 如何有效地从这些海量实时序列数据中挖掘有用的知识, 并进行实时预测已经成为各个领域的研究热点.

近年来, 时间序列定量预测技术已经开展了许多方法的研究, 例如文献[1-2]通过组合模型的方式来预测时间序列.文献[3]采用时间搜索模型将连续时间序列数据转换为离散空间来挖掘股票数据中的频繁模式, 在此基础上对股票价格进行短期趋势预测.文献[4]通过应用多元自适应回归曲线和逐步回归建立基于指标选择的时间序列模型.此外, 还通过支持向量回归(Support vector regression, SVR)建立预测模型, 并采用遗传算法(Genetic algorithm, GA)进行优化.文献[5]针对时序动态关联规则挖掘中, 支持度向量在时间特性上不宜观察其整体变化趋势与预测问题, 提出将小波变换应用到动态关联规则挖掘中, 并建立自回归模型预测整体趋势变化.但这些方法主要还是将时间序列数据作为一个整体来分析和构建全局模型.

值得注意的是, 能够观察到的多维实时序列数据往往仅是系统的部分演化数据, 无法通过历史数据建立一个全局模型覆盖整个数据空间.为了及时有效地分析多维实时序列数据, 往往更为合理的方式是对时间序列的局部可用数据进行在线分析, 而不是全局序列数据.关联规则挖掘[6]可以发现存在于数据中属性之间有趣的关联关系, 以语言和规则相结合的产物呈现最终的挖掘结果, 更易于操作人员的理解和管理者的决策支持.考虑到时间序列的特性, 衍生出了时态关联规则挖掘方法[7-12], 实际是加了时间约束的关联规则, 目的是找出时态事务集中同一维属性与时间之间的关联, 以及基于时域的不同维属性之间的关系等, 更好地挖掘隐藏在数据中的与时间关联的知识.因此, 我们的重点是发现多维实时序列数据中的局部模式, 当某一属性发生变化后或导致多个属性紧接着发生变化, 它们之间可能是按时间的顺序关系或因果关系.针对多维实时序列数据的时态关联规则挖掘吸引了一些学者进行研究.文献[13]提出了基于两个项的时态关系来挖掘时态关联规则, 但在挖掘的过程中对参数的依赖性较强, 且并不适合获取多个项之间的时态关系.文献[14]基于密度的子空间聚类将集群定义为存在于多维数据集的子空间中的高密度区域, 提出一种将多元时间序列转换为符号序列的算法, 能够捕获时间序列变量组之间的相互依赖性和共同变化的顺序模式.文献[15]提出一种新型的多属性时间序列模式, 通过修剪单时间序列中的冗余模式以及避免过度计数的关联, 捕获时间序列变量组之间的相互依赖和共同变化的顺序模式.文献[16]为了避免一段时间出现的频繁项目对结果的影响, 将时间转化为粒度, 并考虑不同级别粒度的时态数据挖掘, 设计了一个三阶段的挖掘框架.

虽然这种时态关联规则已经保留了多维时间序列隐含的过程变化信息, 定性地描述了多维时间序列数据间的时态关系, 但这种知识并没有提供定量预测多维时间序列的未来运动趋势的能力.通过重构时态关联规则的前件和后件, 并借鉴模糊Takagi-Sugeno (T-S)模型的规则形式构造局部模型可以估计多维时间序列的未来值.此外, 上述方法主要针对离线数据进行挖掘, 但时态数据库通常会动态更新, 时态关联规则挖掘要与数据的变化保持同步, 避免对数据集中所有的数据重新进行挖掘而增加计算复杂度.因此, 本文提出了基于多维时态关联规则的演化模糊推理算法, 主要包含初始时态关联规则挖掘、基于多维时态关联规则的模糊推理预测、概念漂移检测与系统演化更新三个部分: 1)采集部分时间序列数据集完成时态关联规则的初始化挖掘; 2)借鉴区间TS模糊推理方法重构时态关联规则, 利用优化算法辨识规则后件参数, 进而实现对时态数据的模糊推理预测; 3)随着时间序列流数据不断添加到数据库, 需要增量地挖掘时态关联规则.为了适应时间序列数据发生概念的漂移, 利用滑动窗技术划分时间序列数据.若当前滑动窗中的数据发生概念漂移, 则认为已有规则库中的时态关联规则已不再适用当前窗口中的数据, 需要对当前窗口中的数据重新进行时态关联规则的挖掘, 并将所得规则按时间顺序存储到规则库中; 若当前滑动窗中的数据没有发生概念漂移, 则需对时态关联规则对应的数据点进行更新, 继续等待下一个时间序列滑动窗口的到来, 直到时间序列数据采集结束.

图 1  滑动窗的实现过程

图 2  系统演化更新

图 3  数据集Air Quality的拟合曲线

为了处理时间序列数据, 时态关联规则挖掘广泛地用于各种实际应用.通常时态数据库中的时间序列数据是动态变化的, 而现有的时态关联规则挖掘技术对于最近更新的数据进行挖掘时, 往往要依赖所有的时间序列数据进行重复挖掘, 造成了资源的浪费.本文提出了一种新的算法, 不仅可以动态更新时态关联规则, 而且通过结合模糊推理可以实现时态关联规则的推理预测.本文采用了滑动窗技术对时间序列分块处理, 通过概念漂移检测实现系统演化更新, 避免了重复性地对模型进行重建的工作.

此外, 为了更有效地利用时态关联规则进行定量预测, 构建了基于多维时态关联规则的模糊推理预测方法, 通过实验对比研究, 表明了本文算法的有效性、可扩展性和准确性.

作者简介

孟建瑶

北京科技大学自动化学院硕士研究生.主要研究方向为数据挖掘和机器学习.E-mail:18810481455@163.com

李俊飞  

北京科技大学自动化学院硕士研究生.主要研究方向为数据挖掘和机器学习.E-mail:hpuljfei@163.com

彭开香  

北京科技大学自动化学院教授.主要研究方向为复杂工业系统的故障诊断与一体化控制.E-mail:kaixiang@ustb.edu.cn

王玲  

北京科技大学自动化学院副教授.主要研究方向为数据挖掘, 机器学习与复杂系统建模.本文通信作者.E-mail:lingwang@ustb.edu.cn