Detecting outliers in data stream based on grid coupling

Abstract

Abstract:

The grid-based data analysis method processes data in units of grids, avoiding the point-to-point calculation of data objects and greatly improving the efficiency of data analysis. However, the traditional grid-based method processes the grid independently in the analysis process, ignoring the coupling relationship between the grids and resulting in unsatisfactory analysis accuracy. In this paper, the grids are no longer processed independently and the coupling relationship between grids are considered, when the grids are used to detect outliers in data stream. A grid coupling based outliers detection algorithm for data streams (GCStream-OD) is proposed. The algorithm exactly expresses the correlation between data stream objects through grid coupling, and improves the efficiency of the algorithm through pruning strategy. Experimental results on five real data streams show that GCStream-OD has higher quality and efficiency of outliers detection.

Key words: outliers detection, data stream, grid coupling

YANG Jie，ZHANG Dong-yue，ZHOU Li-hua，HUANG Hao，DING Hai-yan. Detecting outliers in data stream based on grid coupling [J]. Computer Engineering & Science.

References ［11］

［1］	Hang J,Kamber M,Pei J.Data mining: Concepts and techniques ［M］.Amsterdam:Elsevier,2011.
［2］	Beutel A,Faloutsos C.User behavior modeling and fraud detection［J］.IEEE Intelligent Systems,2016,31(2):84-86.
［3］	Jiang B C,Yang W H,Yang C Y.An SPC-based forward-backward algorithm for arrhythmic beat detection and classification［J］.Industrial Engineeering & Management Systems,2013,12(4):380-388.
［4］	Sadik M S,Gruenwald L.DBODDS: Distance based outlier detection for data streams［C］∥Proc of International Conference on Database and Expert Systems Applications,2010: 122-136.
［5］	Angiulli F, Fassetti F.Detecting distance-based outliers in streams of data［C］∥Proc of the 16th ACM Conference on Information and Knowledge Management,2007: 811-820.
［6］	Elahi M,Li K,Nisar W,et al.Efficient clustering-based outlier detection algorithm for dynamic data stream［C］∥Proc of 2008 5th International Conference on Fuzzy Systems and Knowledge Discovery,2008:298-304.
［7］	Zhang Xin-rong,Xu Bao-guo.The outlier detection algorithm and its application in the statistical monitoring model based on modified scaling［J］.Computer Engineering & Science,2011,33(2): 168-172.(in Chinese)
［8］	Chen Y,Tu L.Density-based clustering for real-time stream data［C］∥Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2007: 133-142.
［9］	Zhang Dong-yue, Zhou Li-hua,Wu Xiang-yun,et al.Data stream clustering based on grid coupling［J］.Journal of Software,2019,30(3): 667-683.(in Chinese)
［10］	Zhou Xiao-yun, Sun Zhi-hui, Zhang Bai-li, et al. A fast outlier detection algorithm for high dimensional categorical data streams ［J］.Journal of Software,2007,18(4): 933-942.(in Chinese)
［11］	Yang Yi-dong, Sun Zhi-hui, Zhu Yu-quan, et al. A fast outlier detection algorithm for data streams based on dynamic grids ［J］.Journal of Software,2006,17(8): 1796-1803.(in Chinese)
［12］	Knorr E M,Ng R T.Algorithms for mining distance based outliers in large datasets［C］∥Proc of the International Conference on Very Large Data Bases,1998: 392-403.
［13］	Breunig M M,Kriegel H P,Ng R T,et al.LOF: Identifying density-based local outliers［J］.ACM SIGMOD Record,2000,29(2): 93-104.
［14］	Pokrajac D,Lazarevic A,Latecki L J.Incremental local outlier detection for data streams［C］∥Proc of 2007 IEEE Symposium on Computational Intelligence and Data Mining,2007: 504-515.
［15］	Salehi M,Leckie C,Bezdek J C,et al.Fast memory efficient local outlier detection in data streams［J］.IEEE Transactions on Knowledge and Data Engineering,2016,28(12): 3246-3260.
［16］	Barnett V,Lewis T.Outliers in statistical ［M］.3rd ed.New York: John Wiley and Sons,1994.
［17］	Hawkins D M.Identification of outliers［M］.London: Chapman and Hall,1980.
［18］	Guha S,Rastogi R,Shim K.ROCK: A robust clustering algorithm for categorical attributes［J］.Information Systems,2000,25(5): 345-366.
［19］	Ng R T,Han J.CLARANS: A method for clustering objects for spatial data mining［J］.IEEE Transactions on Knowledge & Data Engineering,2002,14(5): 1003-1016.
［20］	Liu F T,Ting K M,Zhou Z H.Isolation-based anomaly detection［J］.ACM Transactions on Knowledge Discovery from Data,2012,6(1):1-39.
［21］	Reiss A,Stricker D.Introducing a new benchmarked dataset for activity monitoring［C］∥Proc of 2012 16th International Symposium on Wearable Computers,2012: 108-109.
［22］	Cattral R,Oppacher F,Deugo D.Evolutionary data mining with automatic rule generalization［J］.Recent Advances in Computers,Computing and Communications,2002,1(1): 296-300.
［23］	Tan S C,Ting K M,Liu T F,et al.Fast anomaly detection for streaming data［C］∥Proc of the 22nd International Joint Conference on Artificial Intelligence,2011: 1511-1516.
［24］	Stolfo J S,Fan W,Lee W,et al.Cost-based modeling and evaluation for data mining with application to fraud and intrusion detection:
	Results from the JAM project by Salvatore［C］∥Proc of the DARPA Information Survivability Conference,2000: 1-15.
	附中文参考文献：
［7］	张新荣，徐保国.基于改进尺度的统计建模数据中离群点去除算法及应用［J］.计算机工程与科学,2011,33(2): 168-172.
［9］	张东月，周丽华，吴湘云，等.基于网格耦合的数据流聚类［J］.软件学报,2019,30(3): 667-683.
［10］	周晓云，孙志挥，张柏礼，等.高维类别属性数据流离群点快速检测算法［J］.软件学报,2007,18(4):933-942.
［11］	杨宜东，孙志挥，朱玉全，等.基于动态网格的数据流离群点快速检测算法［J］.软件学报,2006,17(8): 1796-1803.

[1]	ZHANG Xi-long, HAN Meng, CHEN Zhi-qiang, WU Hong-xin, LI Mu-hang. A Boosting classification algorithm for imbalanced drift data stream based on Hellinger distance [J]. Computer Engineering & Science, 2022, 44(05): 788-799.
[2]	WEN Kai, GENG Xiao-hai, ZHU Lu-wei, XU Meng-meng, . Frequent itemsets mining for data stream based on AO algorithm [J]. Computer Engineering & Science, 2020, 42(12): 2259-2264.
[3]	XIONG Ju-xia1,2,3,WU Jin-zhao1,2,3. Dynamic mining of sensitive data streams in heterogeneous complex information networks [J]. Computer Engineering & Science, 2020, 42(04): 628-633.
[4]	ZHANG Xin-yu, AN Jian-cheng, CAO Rui. A data stream classification algorithm based on adaptive random forest ensemble model [J]. Computer Engineering & Science, 2020, 42(03): 543-549.
[5]	YUAN Quan1,2,GUO Jiang-fan1,ZHAO Xue-hua1. An imbalanced data stream classification algorithm based on ensemble learning [J]. Computer Engineering & Science, 2019, 41(08): 1519-1524.
[6]	LIANG Yi1，HOU Ying1，CHEN Cheng1，JIN Yi2. A survey of task management techniques for big data stream computing [J]. Computer Engineering & Science, 2017, 39(02): 215-226.
[7]	ZHANG Pan-pan，YIN Shao-hong. An ensemble classification algorithm for uncertain data streams containing concept drift [J]. Computer Engineering & Science, 2016, 38(07): 1510-1516.
[8]	WANG Chengzhang1,LIN Xuelian1,TAN Jingfang2. Dynamic data distribution for stream processing system [J]. J4, 2014, 36(10): 1846-1853.
[9]	HU Jian,WU Maomao. An improved algorithm for mining maximal frequent itemsets over data streams [J]. J4, 2014, 36(05): 963-970.
[10]	ZHANG Yupei,LIU Shuhui. Ensemble classification based on feature drifting in data streams [J]. J4, 2014, 36(05): 977-985.
[11]	CAO Bowei,XUE Qing. Study of frequently item set search method for equipment combat simulation [J]. J4, 2013, 35(6): 152-155.
[12]	CAO Bowei,XUE Qing,TANG Zaijiang. Study of improved Bayesian classification method for data stream of equipment combat simulation [J]. J4, 2013, 35(12): 167-172.
[13]	GAN Liang1,2,YU Lili3,LI Runheng1,JIA Yan1,JIN Xin4. A Reverse Dominant Point Set Based Algorithm for Top- k Queries in DSMS [J]. J4, 2012, 34(6): 59-64.
[14]	LI Hua,LI Minbo,GU Shengxi. A RFID Integration Middleware Framework for Enterprise Applications [J]. J4, 2012, 34(1): 111-118.
[15]	CHENG Wencong1,ZOU Peng2,JIA Yan2. A Network Security Situation Awareness Model Based on Stream Cube [J]. J4, 2011, 33(8): 8-13.