基于改进的OPTICS聚类和LOPW的离群数据检测算法

计算机工程与科学

基于改进的OPTICS聚类和LOPW的离群数据检测算法

肖雪,薛善良

(南京航空航天大学计算机科学与技术学院,江苏南京 210016)

收稿日期:2018-06-05 修回日期:2018-08-15 出版日期:2019-05-25 发布日期:2018-05-25

An outlier detection algorithm based on

improved OPTICS clustering and LOPW

XIAO Xue,XUE Shanliang

(College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China)

Received:2018-06-05 Revised:2018-08-15 Online:2019-05-25 Published:2018-05-25

摘要/Abstract

摘要：

针对现有的离群数据检测算法时间复杂度过高，且检测质量不佳的不足，提出一种新的基于改进的OPTICS聚类和LOPW的离群数据检测算法。首先，使用改进的OPTICS聚类算法对原始数据集进行预处理，筛选由聚类形成的可达图得到初步离群数据集；然后，利用新定义的基于P权值的局部离群因子LOPW计算初步离群数据集中对象的离群程度，计算距离时引入去一划分信息熵增量确定属性的权重，提高离群检测准确性。实验结果表明，改进后的算法不仅提高了运算效率，而且提高了对离群数据检测的精确度。

关键词: LOF算法, 离群数据检测, OPTICS聚类, 信息熵, 加权距离

Abstract:

Aiming at the problems of the high time complexity and poor detection quality of current outlier detection algorithms, we propose a new outlier detection algorithm based on the improved OPTICS clustering and LOPW. Firstly, the original data set is preprocessed by the improved OPTICS clustering algorithm and the preliminary outlier dataset is obtained by filtering the reachability graph of clustering results. Then, we use the newly defined local outlier factor based on Pweight (LOPW) to calculate the degree of outliers of the objects in the primary outlier dataset. When distances calculated, the leaveone partition information entropy gain is introduced to determine the weight of features, thus improving the precision of outlier detection. Experimental results show that the improved algorithm can improve the computational efficiency and the precision of outlier detection.

Key words: LOF algorithm, outlier detection, OPTICS clustering, information entropy, weighted distance

肖雪,薛善良. 基于改进的OPTICS聚类和LOPW的离群数据检测算法[J]. 计算机工程与科学.

XIAO Xue,XUE Shanliang.

An outlier detection algorithm based on

improved OPTICS clustering and LOPW

[J]. Computer Engineering & Science.

[1]	杨先圣1,姜磊1，彭雄2，周倩1，刘菊君1. 基于大数据的异常检测方法研究[J]. 计算机工程与科学, 2018, 40(07): 1180-1186.
[2]	刘国梁，钱晓东. 基于加权网络结构的冷门资源推荐算法[J]. 计算机工程与科学, 2018, 40(05): 916-923.
[3]	黄冬梅1，杜艳玲1,2，张律文1. 基于信息熵种子点选取的流线可视化[J]. 计算机工程与科学, 2018, 40(03): 411-417.
[4]	高双，桑庆兵，严大卫. 基于非下采样轮廓波变换和多核学习的盲图像质量评价[J]. 计算机工程与科学, 2017, 39(06): 1171-1178.
[5]	陈曦，成韵姿. 一种优化组合相似度的协同过滤推荐算法[J]. 计算机工程与科学, 2017, 39(01): 180-187.
[6]	吴思博，陈志刚，黄瑞. 基于相关系数的ID3优化算法[J]. 计算机工程与科学, 2016, 38(11): 2342-2347.
[7]	李少年，吴良刚. 基于邻域信息熵度量数值属性快速约简算法[J]. J4, 2016, 38(02): 350-355.
[8]	梅松青，周洪建. 基于信息熵的局部线性嵌入[J]. J4, 2014, 36(09): 1806-1811.
[9]	秦立龙1,王振宇2. 改进粒子群算法在调制模式识别中的应用[J]. J4, 2013, 35(7): 102-107.
[10]	朱文杰1,2，王强2，翟献军1. 基于信息熵的SVM入侵检测技术[J]. J4, 2013, 35(6): 47-51.
[11]	史志才，夏永祥. 基于粗糙集的入侵检测方法研究[J]. J4, 2012, 34(2): 13-18.
[12]	赵茜，王新生. 一种动态信任度量与预测方法研究[J]. J4, 2010, 32(9): 20-22.
[13]	陈凤娟，孙静. 粗糙集信息观中的绝对约简[J]. J4, 2010, 32(5): 97-99.
[14]	徐果毅朱宁波朱晓林卢晓阳. 基于颜色直方图熵值及分块主色的图像检索[J]. J4, 2008, 30(9): 44-46.
[15]	唐文胜[1,2] 罗娟[2] 彭宇行[1] 王威[2]. WSN中一种基于联合信息熵的拥塞公平性控制算法[J]. J4, 2008, 30(8): 53-56.