High-Dimensional Data Stream Outlier Detection Algorithm Based on Angle Distribution

Abstract

Abstract:

To improve outlier detection in high-dimensional data stream, a novel high-dimensional data stream outlier detection (DSOD) algorithm based on angle distribution was proposed. To identify the normal point, border point and outlier accurately, the method of angle distribution-based outlier detection algorithm was employed. To reduce the computational complexity, a smallscale calculation set of data stream was established, which is composed of normal set, border set. To solve the problem of concept drift, an updated mechanism for the normal set and border set was developed. The experimental results on real data sets demonstrate that DSOD is more efficient than Simple variance of angles (Simple VOA) and angel-based outlier detection (ABOD) and is very suitable for the outlier detection of large data streams.

Key words: angle distribution, data stream, high-dimensional, outlier detection

CLC Number:

TP 301.6

PIAO Changhao1,HUANG Zhi1,SU Ling2,LU Sheng1. High-Dimensional Data Stream Outlier Detection Algorithm Based on Angle Distribution[J]. Journal of Shanghai Jiaotong University, 2014, 48(05): 647-652.

References

［1］Angiulli F, Fassetti F. Distancesbased outlier que

ries in data stream: the novel task and algorithms［J］. Data Mining and Knowledge Discovery, 2010, 20 (2): 290324.

［2］Joel W, Giannella C. Innetwork outlier detection in wireless sensor networks ［J］. Knowledge and Information System, 2013, 34 (1): 2354.

［3］夏英, 刘申艺. 实时异常轨迹检测方法及其应用［J］. 重庆邮电大学学报, 2011, 23 (4): 496499.

XIA Ying, LIU Shenyi. Real time trajectory anomaly detection method and its application ［J］. Journal of Chongqing University of Posts and Telecommunications, 2011, 23 (4): 496499.

［4］Zhang Y, Hamm N, Meratnia N, et al. Statisticsbased outlier detection for wireless sensor networks ［J］. International Journal of Geographical Information Science, 2012, 26 (8): 13731392.

［5］Angiulli F, Fassetti F. DOLPHIN: An efficient algorithm for mining distancesbased outliers in very large datasets ［J］. ACM Transactions on Knowledge Discovery for Data (TKDD), 2009, 3(2): 157.

［6］Breunig M, Kriegel H, Ng R, et al. LOF: Identifying densitybased local outliers ［C］// Proceeding of the 2000 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2000: 93104.

［7］王柯柯, 崔贯勋. 基于单元的快速的大数据集离群数据挖掘算法［J］. 重庆邮电大学学报，2010, 22（5）: 673677.

WANG Keke, CUI Guanxun. Fast outlier data mining algorithm based on cell in large datasets ［J］. Journal of Chongqing University of Posts and Telecommunications, 2010, 22 (5): 673677.

［8］Kriegel H P, Schubert M, Zimek A. Anglebased outlier detection in high dimensional data ［C］// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2008: 444452.

［9］Pham N, Pagh R. A nearlinear time approximation algorithm for anglebased outlier detection in high dimensional data ［C］// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 877885.

［10］Hawkins D. Identification of outliers ［M］. London: Chapman and Hall, 1980: 1188.

[1]	CHEN Changchuan, LIU Kai, LIU Renguang, FENG Xiaozong, QIN Yanjia, DAI Shaosheng, ZHANG Tianqi. Clustering Separation Method Based on Multi-Source Partial Discharge Signal Data Stream [J]. Journal of Shanghai Jiao Tong University, 2022, 56(8): 1014-1023.
[2]	PENG Zhigang,OUYANG Hua,WU Yadong,TIAN Jie. Discrete Noise Control of Automobile Cooling Fan by Combining Rotor and Stator Phase Modulation Principle [J]. Journal of Shanghai Jiaotong University, 2019, 53(4): 396-404.
[3]	ZIA-UR REHMAN Muhammad1, LI Tian-rui1 (李天瑞), LI Tao2 (李涛). Exploiting Empirical Variance for Data Stream Classification [J]. Journal of shanghai Jiaotong University (Science), 2012, 17(2): 245-250.
[4]	LONG Zhenzhen1，2，ZHANG Ce2，WANG Weiping3，ZHANG Zhengwen4. A Dynamic Framework for TargetGrouping Based onClustering Data Streams [J]. Journal of Shanghai Jiaotong University, 2010, 44(07): 921-0925.