基于模拟退火的扩展孤立森林异常检测算法

计算机与现代化 ›› 2023, Vol. 0 ›› Issue (01): 88-94.

基于模拟退火的扩展孤立森林异常检测算法

（1.常熟理工学院计算机科学与工程学院，江苏常熟 215500； 2.常熟市医学检验所，江苏常熟 215500）

出版日期:2023-03-02 发布日期:2023-03-02
作者简介:王诗愉（2000—），男，四川江油人，本科生，研究方向：机器学习与异常检测，E-mail： 834772398@qq.com；肖利东（2000—），男，福建晋江人，本科生，研究方向：机器学习与数据挖掘，E-mail：1328344592@qq.com；严心淳（1980—），男，江苏常熟人，高级工程师，硕士，研究方向：医学数据分析挖掘，E-mail: 32598601@qq.com；通信作者：应文豪（1979—），男，江苏常熟人，副教授，硕士生导师，博士，研究方向：数据挖掘与智能计算，E-mail: ywh@cslg.edu.cn。
基金资助:
国家重点研发计划项目（2018YFB1004901）；教育部人文社科基金资助项目（18YJCZH229）；国家自然科学基金资助项目（61972059）；江苏省教育科学“十三五”规划课题（X-a/2018/08）；江苏省大学生创新创业训练计划项目（202110333006）

Extended Isolated Forest Anomaly Detection Algorithm Based on Simulated Annealing

（1. School of Computer Science and Engineering， Changshu Institute of Technology， Changshu 215500， China；
2. Changshu Medicine Examination Institute， Changshu 215500， China）

Online:2023-03-02 Published:2023-03-02

摘要/Abstract

摘要： 扩展孤立森林（Extended Isolation Forest， EIF）有效解决了孤立森林（Isolation Forest， iForest）对局部异常点不敏感的问题，但EIF将轴平行的孤立条件更替为使用随机斜率的超平面，导致算法模型损失了一部分泛化能力，并由于大量的向量点乘运算增加了时间开销。针对上述情况，提出一种基于模拟退火的扩展孤立森林算法（Extended Isolation Forest based on Simulated Annealing， SA-EIF）。该算法根据每棵孤立树（Isolation Tree， iTree）对于数据集的预测结果计算每棵iTree的精度值和差异值，并基于此构建适应度函数，最终利用模拟退火算法筛选数棵检测性能较优的iTree构建集成学习模型。在ODDS 异常检测数据集中进行K折交叉验证的实验结果表明：SA-EIF算法对局部异常点敏感，较现有的EIF算法减少约20%~40% 的时间开销，提高约5%~10%的检测精度。

关键词: 扩展孤立森林, 孤立森林, 模拟退火, 异常检测

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

王诗愉, 肖利东, 严心淳, 应文豪. 基于模拟退火的扩展孤立森林异常检测算法[J]. 计算机与现代化, 2023, 0(01): 88-94.

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.

参考文献

［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]	吕美静1, 年梅1, 张俊1, 2, 付鲁森1. 基于自编码器的网络流量异常检测[J]. 计算机与现代化, 2024, 0(12): 40-44.
[2]	薛浩, 马静, 郭小宇. 基于Focal Loss改进LightGBM的供水管网毛刺数据检测[J]. 计算机与现代化, 2024, 0(09): 74-81.
[3]	农皓程, 任德均, 任秋霖, 刘澎笠, 黄德成. 基于改进ConvNeXt的软塑包装表面异常检测算法[J]. 计算机与现代化, 2023, 0(08): 12-17.
[4]	杨骏, 王劲林, 倪宏, 盛益强, . 工控网络异常检测中基于灵敏度的动态迁移算法[J]. 计算机与现代化, 2023, 0(05): 46-51.
[5]	白开峰, 赵宏斌, 张芸, 李妍, 崔静安, 刘千金, 杨华, 倪娜. 电网异常业务数据检测方法综述[J]. 计算机与现代化, 2023, 0(03): 79-83.
[6]	宋晓丽, 张勇波, 张培颖. 基于半监督学习的学生消费数据异常检测[J]. 计算机与现代化, 2022, 0(12): 13-17.
[7]	冉昊杰, 王宏智. 基于改进模拟退火算法的生鲜农产品配送中心选址[J]. 计算机与现代化, 2022, 0(10): 36-40.
[8]	白雪, 程宗毛. 无线传感网络监测质量的统计分析[J]. 计算机与现代化, 2021, 0(08): 1-5.
[9]	刘军, 彭慧娴, 黄斌, 托尼·谢伊. 基于BP-GamysBoost的乳腺癌诊断模型[J]. 计算机与现代化, 2021, 0(04): 8-14.
[10]	郝怡然, 盛益强, 王劲林, . 基于t-SNE降维预处理的网络流量异常检测[J]. 计算机与现代化, 2021, 0(02): 109-116.
[11]	顾国庆, 李晓辉. 基于箱线图异常检测的指数加权平滑预测模型[J]. 计算机与现代化, 2021, 0(01): 28-33.
[12]	杨永娇，肖建毅，赵创业，周开东. 基于Isolation Forest和Random Forest相结合的智能电网时间序列数据异常检测算法[J]. 计算机与现代化, 2020, 0(03): 99-.
[13]	杨永娇,唐亮亮. 一种基于深度Encoder-Decoder神经网络的智能#br# 电网数据服务器流量异常检测算法[J]. 计算机与现代化, 2019, 0(10): 66-.
[14]	肖晚霞1,2，董兴业1,2，林友芳1,2. 航班恢复问题的迭代局部搜索算法[J]. 计算机与现代化, 2019, 0(09): 1-.
[15]	杨永娇，邱宇，占力超. 基于宽度学习的智能电网数据服务器流量异常检测算法[J]. 计算机与现代化, 2019, 0(09): 77-.