基于角度分布的高维数据流异常点检测算法

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (05): 647-652.

• 自动化技术、计算机技术 • 上一篇下一篇

基于角度分布的高维数据流异常点检测算法

朴昌浩1，黄质1，苏岭2，禄盛1

（1.重庆邮电大学模式识别及应用研究所，重庆 400065； 2.重庆长安汽车股份有限公司，重庆 400023）

收稿日期:2013-08-30
基金资助:
国家自然科学基金资助项目(11247325)，重庆市科委自然科学基金资助项目(CSTC2013yykfC60005,CSTC2011BB4145,CSTC2013jcsfjcssX0022,CSTC2013jcyjjq60002)

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

PIAO Changhao1,HUANG Zhi1,SU Ling2,LU Sheng1

(1. Institute of Pattern Recognition and Applications, Chongqing University of Posts and Telecommunications, Chongqing 400065, China;2.Chongqing Changan Automobile Company Limited, Chongqing 400023, China)

Received:2013-08-30

摘要/Abstract

摘要：

为了有效检测高维数据流中的异常点，提出一种基于角度分布的高维数据流异常点检测（DSOD）算法.运用基于角度分布的方法准确识别高维数据集中的正常点、边界点以及异常点；构造了基于正常集、边界集的小规模数据流型计算集，以降低算法在空间以及时间上的开销；建立了正常集、边界集的更新机制，以解决大数据流的概念转移问题.在真实数据集上的实验结果表明，所提出的DSOD算法的效率高于Simple VOA算法与ABOD算法，并且适用于大数据流上的异常点检测.

关键词：
中图分类号：文献标志码： A

关键词: 角度分布, 数据流, 高维, 异常点检测

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

中图分类号:

TP 301.6

朴昌浩1，黄质1，苏岭2，禄盛1. 基于角度分布的高维数据流异常点检测算法[J]. 上海交通大学学报（自然版）, 2014, 48(05): 647-652.

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.

参考文献

［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]	陈昌川, 刘凯, 刘仁光, 冯晓棕, 覃延佳, 代少升, 张天骐. 基于多源局部放电信号数据流聚类分离方法[J]. 上海交通大学学报, 2022, 56(8): 1014-1023.
[2]	刘海涛a, 魏汝祥b, 蒋国萍a. 软件成本数据的相似性度量[J]. 上海交通大学学报（自然版）, 2012, 46(11): 1736-1740.
[3]	龙真真,张策，王维平，张正文. 一种基于数据流聚类的动态目标分群框架[J]. 上海交通大学学报（自然版）, 2010, 44(07): 921-0925.