基于相对距离的反k近邻树离群点检测

doi:10.3969/j.issn.0372-2112.2020.05.014

电子学报 ›› 2020, Vol. 48 ›› Issue (5): 937-945.DOI: 10.3969/j.issn.0372-2112.2020.05.014

基于相对距离的反k近邻树离群点检测

杨晓玲^1,2, 冯山¹, 袁钟²

1. 四川师范大学数学科学学院, 四川成都 610066;
2. 西南交通大学信息科学与技术学院, 四川成都 611756

收稿日期:2019-07-04 修回日期:2019-09-09 出版日期:2020-05-25
- 通讯作者:
- 冯山
- 作者简介:
- 杨晓玲 女,1993年1月出生,四川乐山人,2016年和2019年分别在西华师范大学和四川师范大学获得理学学士和理学硕士学位.现为西南交通大学计算机科学与技术专业的博士生,从事粗糙集、离群点检测和数据挖掘有关的研究.E-mail:yangxlt1993@163.com
- 基金资助:
- 国家自然科学基金 (No.61673285，No.61976182，No.61572406）; 四川省青年科技基金 (No.2017JQ0046）; 四川省国际科技创新合作重点项目 (No.2019YFH0097）

Outlier Detection Based on Reversed K-Nearest Neighborhood MST of Relative Distance Measure

YANG Xiao-ling^1,2, FENG Shan¹, YUAN Zhong²

1. School of Mathematical Science, Sichuan Normal University, Chengdu, Sichuan 610066, China;
2. School of Information Science and Technology, Southwest Jiaotong University, Chengdu, Sichuan 611756, China

Received:2019-07-04 Revised:2019-09-09 Online:2020-05-25 Published:2020-05-25
- Corresponding author:
- FENG Shan
- Supported by:
- National Natural Science Foundation of China (No.61673285, No.61976182, No.61572406); Youth Science and Technology Fund of Sichuan Provicne (No.2017JQ0046); Key Program of Sichuan Province International Science and Technology Innovation Cooperation Project (No.2019YFH0097)

摘要/Abstract

摘要： 针对分布复杂且离群类型多样的数据集进行离群检测困难的问题，提出基于相对距离的反k近邻树离群检测方法RKNMOD（Reversed K-Nearest Neighborhood）.首先，将经典欧氏距离、对象局部密度和对象邻域结合，定义了对象的相对距离，能同时有效检出全局和局部离群点.其次，以最小生成树结构为基础，采取最大边切割法以快速分割离群点和离群簇.最后，人工合成数据集和UCI数据集试验均表明，新算法的检测准确率更高，为分布异常且离群类型多样的数据集的离群检测提供了一条有效的新途径.

关键词: 离群点, 离群簇, 反k近邻, 最小生成树, 相对距离度量

Abstract: For outlier detection difficulty of data sets with complex distribution and various types of outliers, a new outlier detection method based on reversed k-nearest neighborhood MST of relative distance measure is proposed. Firstly, relative distance of object is defined with the combination of classical distance, local density and neighborhood of object, which can be used to detect global outliers and local outliers both. Secondly, on basis of minimum spanning tree structure, by tactics of maximum-edge-cutting, outliers and outlier clusters can be obtained. Finally, experiments of synthetic and UCI data sets show that the new algorithm is much more correct and effective. It is a new effective way for detecting outliers of data sets with abnormal distribution and diversity outlier types.

Key words: outlier, outlier cluster, reversed nearest neighborhood, MST(minimum spanning tree), relative distance metric

中图分类号:

TP18

杨晓玲, 冯山, 袁钟. 基于相对距离的反k近邻树离群点检测[J]. 电子学报, 2020, 48(5): 937-945.

YANG Xiao-ling, FENG Shan, YUAN Zhong . Outlier Detection Based on Reversed K-Nearest Neighborhood MST of Relative Distance Measure[J]. Acta Electronica Sinica, 2020, 48(5): 937-945.

参考文献

[1] Xue Z X,Shang Y L,Feng A F.Semi-supervised outlier detection based on fuzzy rough C-means clustering[J].Mathematics and Computers in Simulation,2010,80(9):1911-1921.
[2] Han J W,Kamber M,Pei J.Data Mining:Concepts and Techniques[M].San Francisco:Morgan Kaufmann,2011.543-584.
[3] 薛安荣,姚林,鞠时光,陈伟鹤,马汉达.离群点挖掘方法综述[J].计算机科学,2008,35:11-18. Xue A R,Yao L,Ju S G,Chen W H,Ma H D.Survey of outlier mining[J].Computer Science,2008,35:11-18.(in Chinese)
[4] Markus G,Seiichi U,Dongxiao Z.A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data[J].PLOS ONE,2016,11(4):1-31.
[5] Aggarwal,Charu C.Outlier Analysis[M].Berlin,Germany:Second Edition,Springer,2017.
[6] Wu D F.A regression sequences based method for high dimensional outlier detection[J].Journal of Discrete Mathematical Sciences and Cryptography,2017,20(4):931-943.
[7] Goldstein M,Dengel A.Histogram-based outlier score(HBOS):A fast unsupervised anomaly detection algorithm[A].Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012)[C].Germany:2012.59-63.
[8] Ramaswamy S.Rastogi R.Shim K.Efficient algorithms for mining outliers from large data sets[A].ACM Sigmod International Conference on Management of Data[C].New York,USA:ACM,2000.427-438.
[9] Jiang F,Sui Y F,Cao C G.A rough set approach to outlier detection[J].International Journal of General Systems,2008,37(5):519-536.
[10] Yuan Z,Zhang X Y,Feng S.Hybrid data-driven outlier detection based on neighborhood information entropy and its developmental measures[J].Expert Systems with Applications,2018,112(12):243-257.
[11] Chen Y M,Miao D Q,Zhang H Y.Neighborhood outlier detection[J].Expert Systems with Applications,2010,37(12):8745-8749.
[12] Wang X,Wang X L,Ma Y,et al.A fast MST-inspired kNN-based outlier detection method[J].Information Systems,2015,48(3):89-112.
[13] Tang X Q,Zhu P.Hierarchical clustering problems and analysis of fuzzy proximity relation on granular space[J].IEEE Transactions on Fuzzy Systems,2013,21(5):814-824.
[14] Yamanishi K,Takeuchi J I,Williams G,et al.On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms[J].Data Mining and Knowledge Discovery,2004,8(3):275-300.
[15] Wu N,Zhang J.Factor-analysis based anomaly detection and clustering[J].Decision Support Systems,2006,42(1):375-389.
[16] Knorr E M,Ng R T.Algorithms for mining distance-based outliers in large datasets[A].Proceedings of the 24th VLDB Conference[C].New York,USA:VLDB,1998.392-403.
[17] Ramaswamy S,Rastogi R,Kyuseok S.Efficient algorithms for mining outliers from large data sets[A].Proceedings of the 2000 ACM SIGMOD international conference on Management of data[C].New York,USA:ACM,2000.427-438.
[18] Angiulli F,Pizzuti C.Fast outlier detection in high-dimensional spaces[A].Proceeding of 6th European Conference on Principles of Data Mining and Knowledge Discovery[C].Finland (Helsinki):ACM,2002.15-26.
[19] Wu M,Jermaine C.Outlier Detection by sampling with accuracy guarantees[A].Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA:ACM,2006.767-772.
[20] 朱庆生,唐汇,冯骥.一种基于自然最近邻的离群检测算法[J].计算机科学,2014,41(3):276-278. Zhu Q S,Tang H,Feng J.Outlier detection algorithm based on natural nearest neighbor[J].Computer Science,2014,41(3):276-278.(in Chinese)
[21] Breunig M M,Kriegel H P,Ng R T,Sander J.LOF:Identifying density-based local outliers[A].ACM Sigmod International Conference on Management of Data[C].New York,USA:ACM,2000.93-104.
[22] 胡彩平,秦小麟.一种基于密度的局部离群点检测算法DLOF[J].计算机研究与发展,2010,47(12):2110-2116. Hu C P,Qin X L.A density-based local outlier detecting algorithm[J].Journal of Computer Research and Development,2010,47(12):2110-2116.(in Chinese)
[23] 王敬华,赵新想,张国燕.NLOF:一种新的基于密度的局部离群点检测算法[J].计算机科学,2013,40(8):181-185. Wang J H,Zhao X X,Zhang G Y.NLOF:A new density-based local outlier detecting algorithm[J].Computer Science.2013,40(8):181-185.(in Chinese)
[24] Jin W,Anthony K H,Han J W,Wang W.Ranking outliers using symmetric neighborhood relationship[A].Pacific-Asia Conference on Knowledge Discovery and Data Mining[C].Berlin,GER:Springer,2006.577-593.
[25] Radovanovic M,Nanopoulos A,Ivanovic M.Reverse nearest neighbors in unsupervised distance-based outlier detection[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1369-1382.
[26] 朱利,邱媛媛,于帅,原盛.一种基于快速k-近邻的最小生成树离群点检测方法[J].计算机学报,2017,40(12):2857-2870. Zhu L,Qiu Y Y,Yu S,Yuan S.A fast kNN-based MST outlier detection method[J].Chinese Journal of Computers,2017,40(12):2857-2870.(in Chinese)
[27] Zhu Q S,Fan X G,Feng J.Outlier detection based on K-Neighborhood MST[A].IEEE International Conference on Information Reuse and Integration[C].Las Vegas,USA:IEEE,2015.718-724.
[28] Alsuwaiyel M H.Algorithms Design Techniques and Analysis[M].Beijing:Publishing House of Electronics Industry,2013.239-246.
[29] Bay S D.The UCI KDDN repository[DB/OL].http://kdd.Ics.Uci.edu.2011-10-15.
[30] Harkin S,He H X,Williams G J,et al.Outlier detection using replicator neural networks[A].Proc of the 4th Int Conf on Data Warehousing and Knowledge Discovery[C].Aix-en-Provence:Springer-Verlag,2002.170-180.

基于相对距离的反k近邻树离群点检测

Outlier Detection Based on Reversed K-Nearest Neighborhood MST of Relative Distance Measure

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李青青, 马慧芳, 李举, 李志欣, 姜彦斌. 属性网络中结合用户偏好的社区搜索和离群点检测[J]. 电子学报, 2022, 50(9): 2172-2180.
[2]	彭涛, 杨妮亚, 徐原博, 王冰冰, 刘露. 双类型异质网中基于排序和聚类的离群点检测方法[J]. 电子学报, 2018, 46(2): 281-288.
[3]	杨金鸿, 邓廷权. 一种基于单簇核PCM的SVDD离群点检测方法[J]. 电子学报, 2017, 45(4): 813-819.
[4]	高志奇, 陶海红, 赵继超. 基于联合稀疏功率谱恢复的机载雷达稳健STAP算法研究[J]. 电子学报, 2016, 44(11): 2796-2801.
[5]	陈波, 金添, 陆必应, 周智敏, 吴文浩. 穿墙雷达中基于最小生成树的建筑物内部结构重构技术[J]. 电子学报, 2015, 43(9): 1682-1688.
[6]	宋岚, 文堂柳, 黎海生, 王杉. 基于云模型、图论和互信息的遥感影像分割方法[J]. 电子学报, 2015, 43(8): 1518-1525.
[7]	王超, 杨静, 张健沛. 基于稀疏化最小生成树聚类的个性化轨迹隐私保护算法[J]. 电子学报, 2015, 43(11): 2338-2344.
[8]	郑金华, 刘磊, 刘文盼, 邹娟. 一种自适应小生境分布性保持策略[J]. 电子学报, 2012, 40(11): 2330-2335.
[9]	江峰;杜军威;葛艳;眭跃飞;曹存根. 基于粗糙集理论的序列离群点检测[J]. 电子学报, 2011, 39(2): 345-350.
[10]	江峰;眭跃飞;曹存根. 基于边界和距离的离群点检测[J]. 电子学报, 2010, 38(3): 700-705.
[11]	宣善立;梁栋;朱明;范益政;王年. 一种基于修正的最小生成树及其邻接谱的特征匹配算法[J]. 电子学报, 2010, 38(2): 269-274.
[12]	刘中华;周静波;陈 ;金忠. 距离保持投影非线性降维技术的可视化与分类[J]. 电子学报, 2009, 37(8): 1820-1825.
[13]	张少敏;支力佳;赵大哲;赵宏;杨金柱;. 基于区域联合Rényi熵的多模医学图像配准[J]. 电子学报, 2009, 37(10): 2320-2325.
[14]	郝志宇, 云晓春, 张宏莉. MTree_-Nix网络模拟路由计算与查找策略[J]. 电子学报, 2008, 36(3): 477-481.
[15]	邵超, 黄厚宽, 赵连伟. P-ISOMAP:一种新的对邻域大小不甚敏感的数据可视化算法[J]. 电子学报, 2006, 34(8): 1497-1501.