ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (1): 94-110.doi: 10.7544/issn1000-1239.2017.20150804

• 人工智能 • 上一篇    下一篇

界标窗口下数据流最大规范模式挖掘算法研究

闻英友1,3,王少鹏1,2,赵宏1,3   

  1. 1(东北大学计算机科学与工程学院 沈阳 110819); 2(内蒙古大学计算机学院 呼和浩特 010021); 3(医学影像计算教育部重点实验室(东北大学) 沈阳 110819) (wangshaopeng1984@163.com)
  • 出版日期: 2017-01-01
  • 基金资助: 
    国家自然科学基金项目(60903159,61173153,61402096,61163011,61262082,61662054);中央高校基本科研业务费专项资金项目(N110818001,N100218001,N130504007,N120104001);国家“八六三”高技术研究发展计划基金项目(2015AA016005);沈阳市科技计划项目(1091176 -1-00);内蒙古自然科学基金项目(2015MS0612) This work was supported by the National Natural Science Foundation of China (60903159, 61173153, 61402096, 61163011, 61262082, 61662054), the Fundamental Research Funds for the Central Universities (N110818001, N100218001, N130504007, N120104001), the National High Technology Research and Development Program of China (863 Program)(2015AA016005), the Science and Technology Plan of Shenyang of China (1091176-1-00), and the Natural Science Foundation of Inner Mongolia (2015MS0612).

The Maximal Regular Patterns Mining Algorithm Based on Landmark Window over Data Stream

Wen Yingyou1,3, Wang Shaopeng1,2, Zhao Hong1,3   

  1. 1(College of Computer Science and Engineering, Northeastern University, Shenyang 110819 ); 2(College of Computer Science, Inner Mongolia University, Huhhot 010021); 3(Key Laboratory of Medical Image Computing (Northeastern University), Ministry of Education, Shenyang 110819 )
  • Online: 2017-01-01

摘要: 首次对界标窗口下数据流最大规范模式挖掘问题进行了研究.为了克服nave算法在处理该问题时不具有增量计算的缺点,提出了一种基于边界界标窗口技术的数据流最大规范模式挖掘(data stream maximal regular patterns mining based on boundary landmark window, DSMRM-BLW)算法.该算法将数据流上的第1个待处理窗口定义为边界界标窗口,使用nave算法对其进行处理;之后每个窗口上的最大规范模式都可以基于前一个窗口上的最大规范模式集合增量获得,可以克服nave算法的缺点.实验结果表明:DSMRM-BLW算法是处理界标窗口下数据流最大规范模式挖掘的有效方法,与nave算法相比,具有相同的执行结果,但时间与空间效率得到了很大的提高.

关键词: 数据流, 界标窗口, 最大规范模式, 增量计算, 边界界标窗口技术

Abstract: Mining regular pattern is an emerging area. To the best of our knowledge, no method has been proposed to mine the maximal regular patterns about data stream. In this paper, the problem of mining maximal regular patterns based on the landmark window over data stream is focused at the first time. In order to resolve the issue that the nave algorithm which is used to handle the maximal regular patterns mining based on the landmark window over data stream does not have the characteristic of incremental computation, the DSMRM-BLW(data stream maximal regular patterns mining based on boundary landmark window) algorithm is proposed. It takes the first window as the boundary landmark window, and handles it with the nave algorithm. For all other windows, it can obtain the maximal regular patterns over them based on the ones over the adjacent last window incrementally, and can overcome the drawback of the nave algorithm. It is revealed by the extensive experiments that the DSMRM-BLW algorithm is effective in dealing with the maximal regular patterns mining based on the landmark window over data stream, and outperforms the nave algorithm in execution time and space consumption.

Key words: data stream, landmark window, maximal regular pattern, incremental calculation, boundary landmark window technology

中图分类号: