Extended Isolated Forest Anomaly Detection Algorithm Based on Simulated Annealing

Abstract

Abstract: Extended Isolation Forest （EIF） effectively solves the problem that Isolation Forest（iForest） is not sensitive to local abnormal points， but EIF replaces the isolated condition of axis-parallel with a hyperplane with random slope， which causes the algorithm model to lose part of the generalization ability， and increases time cost due to a large number of vector dot multiplication operations. In response to the above situation， an Extended Isolation Forest based on Simulated Annealing （SA-EIF） is proposed. The algorithm calculates the accuracy value and the difference value of each iTree （Isolation Tree） according to the prediction result of each iTree for the data set， then builds fitness function based on this. Finally， the iTree with better detection performance is selected by the simulated annealing algorithm to construct integrative learning model. The experimental results of K-fold cross-validation in the ODDS anomaly detection dataset indicate that the SA-EIF algorithm is sensitive to local anomalies， reducing the time cost by 20%~40% compared with EIF， and the recognition accuracy is about 5%~10% higher than EIF.

Key words: extended isolation forest, isolation forest, simulated annealing, anomaly detection

WANG Shi-yu, XIAO Li-dong, YAN Xin-chun, YING Wen-hao. Extended Isolated Forest Anomaly Detection Algorithm Based on Simulated Annealing[J]. Computer and Modernization, 2023, 0(01): 88-94.

References

［1］ LIU F T， TING K M， ZHOU Z H. Isolation-based anomaly detection［J］. ACM Transactions on Knowledge Discovery from Data， 2012，6（1）:1-39.
［2］ HAWKINS D M. Identification of Outliers［M］. Springer， 1980.
［3］ HODGE V J， AUSTIN J. A survey of outlier detection methodologies［J］. Artificial Intelligence Review， 2004，22（2）:85-126.
［4］杨永娇，肖建毅，赵创业，等. 基于Isolation Forest和Random Forest相结合的智能电网时间序列数据异常检测算法［J］. 计算机与现代化， 2020（3）:99-102.
［5］吴克河，张英，崔文超，等. 一种基于随机森林算法的MQTT异常流量检测方法［J］. 计算机与现代化， 2021（1）:61-64.
［6］ LING C X， SHENG V S， YANG Q. Test strategies for cost-sensitive decision trees［J］. IEEE Transactions on Knowledge and Data Engineering， 2006，18（8）:1055-1067.
［7］ DOMINGUES R， FILIPPONE M， MICHIARDI P， et al. A comparative evaluation of outlier detection algorithms: Experiments and analyses［J］. Pattern Recognition， 2018，74:406-421.
［8］ LI Z， ZHAO Y， BOTTA N， et al. COPOD: Copula-based outlier detection［C］// 2020 IEEE International Conference on Data Mining （ICDM）. 2020:1118-1123.
［9］ FRATTASI S， DELLA ROSA F. Mobile Positioning and Tracking: From Conventional to Cooperative Techniques［M］. John Wiley & Sons， 2017.
［10］ BREUNIG M M， KRIEGEL H P， NG R T， et al. LOF: Identifying density-based local outliers［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. 2000:93-104.
［11］ GOLDSTEIN M， UCHIDA S. A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data［J］. PLoS ONE， 2016，11（4）:e0152173.
［12］姚树春，刘正，张强. 基于混合遗传算法与互信息分析的高维小样本特征选择［J］. 计算机应用与软件， 2020，37（1）:247-255.
［13］ LIU F T， TING K M， ZHOU Z H. Isolation forest［C］// Proceedings of the 2008 8th IEEE International Conference on Data Mining. 2008:413-422.
［14］ BREIMAN L. Random forest［J］. Machine Learning， 2001，45:5-32.
［15］ TENG M Y. Anomaly detection on time series［C］// 2010 IEEE International Conference on Progress in Informatics and Computing. 2010:603-608.
［16］ MUJA M， LOWE D G. Scalable nearest neighbor algorithms for high dimensional data［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2014，36（11）:2227-2240.
［17］杨先圣，姜磊，彭雄，等. 基于大数据的异常检测方法研究［J］. 计算机工程与科学， 2018，40（7）:1180-1186.
［18］ GUHA S， MISHRA N， ROY G， et al. Robust random cut forest based anomaly detection on streams［C］// Proceedings of the 33rd International Conference on International Conference on Machine Learning. 2016:2712-2721.
［19］杨晓晖，张圣昌. 基于多粒度级联孤立森林算法的异常检测模型［J］. 通信学报， 2019，40（8）:133-142.
［20］ HARIRI S， KIND M C， BRUNNER R J. Extended isolation forest［J］. IEEE Transactions on Knowledge and Data Engineering， 2021，33（4）:1479-1489.
［21］ HARMAN R， LACKO V. On decompositional algorithms for uniform sampling from n-spheres and n-balls［J］. Journal of Multivariate Analysis， 2010，101（10）:2297-2304.
［22］ KADAO S G， SURVE R B. Ensamble learning: An approach in artificial intelligence［J］. International Journal of Advanced Research in Science， Communication and Technology， 2021. DOI: 10.48175/IJARSCT-V2-I3-327.
［23］李倩，韩斌，汪旭祥. 基于模糊孤立森林算法的多维数据异常检测方法［J］. 计算机与数字工程， 2020，48（4）:862-866.
［24］ PREISS B R. Data Structure and Algorithms: With Object-oriented Design Patterns in Java［M］. John Wiley & Sons， 1999.
［25］ ZHOU Z H. Ensemble learning［J］. Encyclopedia of Biometrics， 2009，1:270-273.
［26］ SAFAVIAN S R， LANDGREBE D. A survey of decision tree classifier methodology［J］. IEEE Transactions on Systems， Man， and Cybernetics， 1991，21（3）:660-674.
［27］ KIRKPATRICK S， GELATT C D， VECCHI M P. Optimization by simulated annealing［J］. Science， 1983，220（4598）: 671-680.
［28］ ZHOU Z H， WU J X， TANG W. Ensembling neural networks: Many could be better than all［J］. Artificial Intelligence， 2002，137（1-2）:239-263.
［29］ BRADLEY A P. The use of the area under the ROC curve in the evaluation of machine learning algorithms［J］. Pattern Recognition， 1997，30（7）:1145-1159.
［30］ FAWCETT T. An introduction to ROC analysis［J］. Pattern Recognition Letters， 2005，27（8）:861-874.

[1]	LYU Meijing1, NIAN Mei1, ZHANG Jun1, 2, FU Lusen1. Anomaly Detection of Network Traffic Based on Autoencoder [J]. Computer and Modernization, 2024, 0(12): 40-44.
[2]	XUE Hao, MA Jing, GUO Xiaoyu. Water Supply Pipeline Burr Data Detection Based on Improved LightGBM by Focal Loss [J]. Computer and Modernization, 2024, 0(09): 74-81.
[3]	NONG Hao-cheng, REN De-jun, REN Qiu-lin, LIU Peng-li, HUANG De-cheng. Surface Anomaly Detection Algorithm of Flexible Plastic Packaging Based on Improved ConvNeXt [J]. Computer and Modernization, 2023, 0(08): 12-17.
[4]	YANG Jun, WANG Jin-lin, NI Hong, SHENG Yi-qiang, . Dynamic Transfer Method Based on Sensitivity in Industrial Control Network Anomaly Detection [J]. Computer and Modernization, 2023, 0(05): 46-51.
[5]	SONG Xiao-li, ZHANG Yong-bo, ZHANG Pei-ying. Anomaly Detection of Student Consumption Data Based on Semi-supervised Learning [J]. Computer and Modernization, 2022, 0(12): 13-17.
[6]	RAN Hao-jie, WANG Hong-zhi. Distribution Center Site Selection of Fresh Agricultural Products Based on Improved Simulated Annealing Algorithm [J]. Computer and Modernization, 2022, 0(10): 36-40.
[7]	BAI Xue, CHENG Zong-mao. Statistical Analysis of Wireless Sensor Network Monitoring Quality [J]. Computer and Modernization, 2021, 0(08): 1-5.
[8]	LIU Jun, PENG Hui-xian, HUANG Bin, Tony SHAY. Breast Cancer Diagnosis Model Based on BP-GamysBoost [J]. Computer and Modernization, 2021, 0(04): 8-14.
[9]	HAO Yi-ran, SHENG Yi-qiang, WANG Jing-lin, . Anomaly Detection of Network Traffic Based on t-SNE Dimensionality Reduction Preprocessing [J]. Computer and Modernization, 2021, 0(02): 109-116.
[10]	YANG Yong-jiao, XIAO Jian-yi, ZHAO Chuang-ye, ZHOU Kai-dong. An Anomaly Detection Algorithm for Smart Grid Time Series Data #br# Based on Combination of Isolation Forest and Random Forest [J]. Computer and Modernization, 2020, 0(03): 99-.
[11]	YANG Yong-jiao, TANG Liang-liang. An Anomaly Detection Method for Network Traffic of Servers #br# in Smart Grid Based on Deep Encoder-Decoder Neural Network [J]. Computer and Modernization, 2019, 0(10): 66-.
[12]	XIAO Wan-xia1,2, DONG Xing-ye1,2， LIN You-fang1,2. An Iterated Local Search Algorithm for Aircraft Recovery Problem [J]. Computer and Modernization, 2019, 0(09): 1-.
[13]	YANG Yong-jiao， QIU Yu， ZHAN Li-chao. An Anomaly Detection Approach on Servers Traffic in Smart #br# Grid Based on Breadth Learning Algorithm [J]. Computer and Modernization, 2019, 0(09): 77-.
[14]	XIE Xiao-jun1, ZHUO Wen-he1, HU Peng2. Application of Improved SAGA Algorithm in Substation Inspection Job Scheduling [J]. Computer and Modernization, 2016, 0(11): 109-113.
[15]	YI Gui-sheng, HUANG Wen-hua. Application of Memetic Algorithm in Generating Test Paper Intelligently [J]. Computer and Modernization, 2016, 0(11): 114-117,121.