Ａn Outlier Detection Algorithm in Big Data Based on Improved KNN

doi:10.3969/j.issn.1006-2475.2017.05.013

Abstract

Abstract: Aiming at the two shortcomings of KNN algorithm in the field of large data outlier detection, high dimension data is difficult to deal with and time complexity is too high. A classification method based on AOR (Attribute Overlapping Rate) is proposed, and the KNN algorithm is improved. At first the data were reduced the dimension based on AOR, making data processing dimension great increase. Then the traditional KNN algorithm was improved by pruning, reducing lots of invalid computation. The experimental results show that this algorithm has a great improvement on the operational efficiency and accuracy of the large data samples with high dimension and large capacity.

Key words: , big data； KNN； reduce dimension； attribute overlapping rate； pruning

HUANG Jian-li, DU Jin-ran, XIE Jia-quan, QIN Ke. Ａn Outlier Detection Algorithm in Big Data Based on Improved KNN[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.05.013.

References

［1］刘大有,陈慧灵,齐红,等. 时空数据挖掘研究进展［J］. 计算机研究与发展, 2013,50(2):225-239.
［2］贺瑶,王文庆,薛飞. 基于云计算的海量数据挖掘研究［J］. 计算机技术与发展, 2013,23(2):69-72.
［3］王朝勇. 支持向量机若干算法研究及应用［D］. 长春:吉林大学, 2008.
［4］孟伟,王宝树,赵健. 基于神经网络与主观Bayes理论的雷达识别研究［J］. 计算机工程, 2002,28(7):156-158.
［5］ Markwardt C B. Non-linear least squares fitting in IDL with MPFIT［J］. Astronomical Data Analysis Software & Systems, 2009,411(3):251-254.
［6］胡彩平,秦小麟. 一种基于密度的局部离群点检测算法DLOF［J］. 计算机研究与发展, 2010,47(12):2110-2116.
［7］王习特,申德荣,白梅，等. BOD:一种高效的分布式离群点检测算法［J］. 计算机学报, 2016,39(1):36-52.
［8］李婷. 基于深度学习的盲文识别方法［J］. 计算机与现代化, 2015(6):37-40.
［9］ Kut A, Birant D. Spatio-temporal outlier detection in large databases［J］. Journal of Computing and Information Technology, 2006,14(4):291-297.
［10］Knorr E M, Ng R T, Tucakov V. Distance-based outliers：Algorithms and applications［J］. The VLDB Journal on Very Large Data Bases, 2000,8(4):237-253.
［11］刘义,景宁,陈荦,等. MapReduce框架下基于R-树的k-近邻连接算法［J］. 软件学报, 2013,24(8):1836-1851.
［12］stermark R. A fuzzy vector valued KNN for automatic outlier detection［J］. Applied Soft Computing, 2009,9(4):1263-1272.
［13］赵玉丹,王倩, 范九伦,等. 基于模糊KNN的刑侦图像场景分类［J］. 计算机应用研究, 2014,31(10):3158-3160.
［14］王茜,杨正宽. 一种基于加权KNN的大数据集下离群检测算法［J］. 计算机科学, 2011,38(10):177-180.
［15］张忠平,徐晓云,王培. 基于KNN图的空间离群点挖掘算法［J］. 计算机工程, 2011,37(4):37-39.
［16］苗忠义,赵朋朋,胡鹏昱,等. 基于属性高频字的深网数据库重叠率估计［J］. 计算机工程, 2009,35(13):28-30.
［17］张桂杰,张健沛,杨静,等. 基于链接相似性聚类的重叠社区识别［J］. 电子学报, 2015,43(7):1329-1335.

[1]	FU Hong-lin, ZHANG Tai-hong, YANG Ya-ting, Aizimaiti Aiwanier, MA Bo. Scenes Text Modification Network for Uyghur Based on Generative Adversarial Network [J]. Computer and Modernization, 2024, 0(01): 41-46.
[2]	LI Xiang, ZHUANG Yi. Critical Fault Point Identification Method for Routing Algorithms Using XGBoost [J]. Computer and Modernization, 2023, 0(11): 75-81.
[3]	LI Shi-yue, MENG Jia-na, YU Yu-hai, LI Xue-ying, XU Ying-ao. Aspect Based Sentiment Analysis Model Based on Knowledge Enhancement [J]. Computer and Modernization, 2023, 0(10): 1-8.
[4]	LIU Rui-xue, LI Wen, LIU Fang, DU Shou-guo. Prediction of Time Series with Missing Value Based on Tensor Autoregressive Completion [J]. Computer and Modernization, 2023, 0(09): 51-58.
[5]	TANG Yu-lin, HUANG Deng-shan, CHEN Shu-lu, CHEN Peng-ming. SFIM Image Fusion Method Combining IHS and Adaptive Filtering [J]. Computer and Modernization, 2023, 0(09): 70-76.
[6]	MAO Ming-yang, XU Sheng-chao. Continuous Attribute Discretization Algorithm of Rough Sets for BP Neural Networks Based on Particle Swarm Optimization#br# [J]. Computer and Modernization, 2023, 0(09): 115-119.
[7]	LIU Xian-zhuo, DENG Wei-si, XIE En-yan. Adaptive Protection System for Distribution Network Considering Grid Connection of Distributed Generation [J]. Computer and Modernization, 2023, 0(09): 120-126.
[8]	WANG Jia-chen, ZHANG Hong-xin, LIU Qing-hua, . CT Image Generation of Pneumonia Based on Generative Adversarial Network [J]. Computer and Modernization, 2023, 0(07): 20-24.
[9]	ZHANG Jun, SU Wen-hao. Optimization Method of Hadoop File Archiving Based on LZO [J]. Computer and Modernization, 2023, 0(06): 1-6.
[10]	SU Jin-ku, GUI Zhi-ming. Prediction of Short-term Taxi Flow Based on Spatio-temporal Characteristics [J]. Computer and Modernization, 2023, 0(05): 32-38.
[11]	PENG Sui, XU Liang, ZHANG Zhi-qiang, LOU Yuan-yuan, YU Hao, QIN Xiao-hui. Probabilistic Voltage Stability Evaluation Algorithm Based on Mixed Vine Copula and ILHS [J]. Computer and Modernization, 2022, 0(12): 6-12.
[12]	WANG Ying-ying, ZHUANG Yi, SUN Yi-fan. Reliability Evaluation Model of BP Neural Network Based on Particle Swarm Optimization [J]. Computer and Modernization, 2022, 0(12): 42-49.
[13]	WEN Zi-xin, LI Shao-ying, WANG Bin-cheng, LIU Bo, . Face Clustering Method Based on Nearest Neighborhood Aggregation [J]. Computer and Modernization, 2022, 0(12): 81-87.
[14]	GAO Feng, ZHUANG Yi, LIU Xiao. A Trusted Transmission Scheme of SDN Based on Path Tracking Feedback [J]. Computer and Modernization, 2022, 0(12): 102-110.
[15]	MIAO Zi-jing, MEI Xin. Chinese Event Detection Based on Multi-lexicon Feature Augmentation [J]. Computer and Modernization, 2022, 0(09): 13-18.