基于MapReduce的时序数据离群点挖掘算法

Outlier Mining Algorithm for time series data based on MapReduce

1.
School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;
2.
Yuanping Brach, Shuo Huang Railway Development Company Limited, Xinzhou 034100, China

摘要: 针对海量数据中离群点的挖掘,将网格聚类和MapReduce编程模型相结合,排除不可能包含离群点的网格,再用LOF算法对剩余网格中的数据进行离群点检测。为了提高网格聚类的检测精度,本文提出了一种基于聚类半径的改进算法。实验表明了该算法的有效性,同时分析了在节点数不同的情况下,网格聚类所用时间,证明了基于MapReduce的网格聚类适合处理海量时序数据。
- 海量时序数据 /
- 网格聚类 /
- MapReduce /
- LOF /
- 聚类半径
Abstract: Aiming at outlier mining in massive time series data, the paper combined grid clustering with MapReduce programming model to exclude grids that was impossible to contain outlier, and then used LOF Algorithm to detect outliers from the rest grids. In order to improve the detection accuracy of the grid clustering, this paper proposed an improved algorithm based on clustering radius. Experimental results showed the effectiveness of the improvement. Experiment also analyzed the execution time grid cluster cost under the circumstances with different number of nodes, which proved it was suitable for handling massive time series data combined MapReduce with grid clustering.
- massive time series data /
- grid clustering /
- MapReduce /
- LOF /
- clustering radius

[1]	刘明华,张晋昕.时间序列的异常点诊断方法[J]. 中国卫生统计,2011,28（4）：478-481.
[2]	郭逸重. 一种基于孤立点挖掘的Hadoop数据清洗算法的研究[D]. 广州：华南理工大学, 2012.
[3]	杨正宽.基于距离的离群挖掘算法研究[D]. 重庆：重庆大学, 2011.
[4]	郑斌祥,席裕庚,杜秀华．基于离群指数的时序数据离群挖掘[J]．自动化学报,2004,30（1）：70-77．
[5]	文琪,彭宏．小波变换的离群时序数据挖掘分析[J]．电子科技大学学报,2005,34（4）：556-558．
[6]	翁小清,沈钧毅．基于滑动窗口的多变量时间序列异常数据的挖掘[J]．计算机工程,2007,33（12）：102-104．
[7]	杜洪波,张颖．基于LLM的时间序列异常子序列检测算法[J]．沈阳工业大学学报,2009,31（3）：328-332．
[8]	江小平,李成华,向文,等.k-means聚类算法的Map-Reduce并行化实现[J].华中科技大学学报（自然科学版）,2011,39 （增刊I）：120-124.
[9]	曹洪其, 余岚, 孙志挥. 基于网格聚类技术的离群点挖掘算法[J]. 计算机工程,2006,32（11）：119-122.
[10]	张天佑. 基于网格划分的高维大数据集离群点检测算法研究[D].长沙：中南大学,2011.