基于动态双子种群的差分进化K中心点聚类算法

摘要/Abstract

摘要： 随着海量大数据的出现，聚类算法需要新型计算模式来提高计算速度与运行效率。本文提出一种基于动态双子种群的差分进化K中心点聚类算法DGP-DE-K-mediods(Dynamic Gemini Population based DE-K-mediods)。DGP-DE-K-mediods利用动态双子种群方法，解决聚类算法在维持种群密度的时候避免陷入局部最优的问题；采用差分进化(Differential Evolution, DE)算法来提高全局最优能力的强健性；基于Hadoop云平台来并行处理DGP-DE-K-mediods，加快算法的运行速度和效率；描述基于MapReduce的并行聚类算法的编程过程；DGP-DE-K-mediods利用UIC的大数据分类的案例数据和网络入侵检测这种大数据应用来仿真算法的效果。实验结果表明，与已有的聚类算法相比，DGP-DE-K-mediods在检测精度、运行时间上有明显的优势。

关键词: 云计算, 并行处理, K中心点聚类, 差分进化, 入侵检测系统

Abstract: With the appearance of massive big data, some new parallel computing models have been proposed for clustering algorithm. A dynamic gemini population based differential evolution K-mediods clustering algorithm called DGP-DE-K-mediods in cloud environments is proposed in this paper. In DGP-DE-K-mediods, gemini population scheme is adopted to improve the problem of being easily trapped into a local optimum while maintaining population diversity. The differential evolution algorithm is also used to make DGP-DE-K-mediods have strong global optimization capabilities. The DGP-DE-K-mediods clustering algorithm is designed and implemented in parallel under the Hadoop MapReduce framework and thus the time of the big data process has been significantly reduced. The programming model of MapReduce has been also described in detail for parallel cluster algorithm. A serial of simulation experiments are also done using UIC datasets and the intrusion detection processing of big data. Experimental results show that the overall detection effect of DGP-DE-K-mediods is significantly better than the existing intrusion detection algorithms.

Key words: cloud computing, parallel process, K-mediods clustering, differential evolution, intrusion detection system

邓斌涛, 徐胜超. 基于动态双子种群的差分进化K中心点聚类算法[J]. 计算机与现代化, 2021, 0(07): 54-59.

DENG Bin-tao, XU Sheng-chao. A Differential Evolution K-mediods Clustering Algorithm Based on Dynamic Gemini Population[J]. Computer and Modernization, 2021, 0(07): 54-59.

参考文献

［1］宋杨. 基于关联规则的并行优化算法研究［D］. 哈尔滨:哈尔滨工程大学, 2016.
［2］李欢,刘锋,朱二周. 基于改进K-means算法的海量数据分析技术研究［J］. 微电子学与计算机, 2016,33(5):52-57.
［3］吴诗极,李川,唐常杰. 面向大规模信息网络的高效自适应聚类算法［J］. 计算机科学与探索, 2014(4):406-416.
［4］任重鲁,李金明. 非负矩阵分解在微阵列数据分类和聚类发现中的应用［J］. 计算机工程与科学, 2014,36(7):1389-1397.
［5］ JIANG Z B, WANG J, SONG Q, et al. A refined cluster-analysis-based multibaseline phase-unwrapping algorithm［J］. IEEE Geoscience and Remote Sensing Letters, 2017,14(9):1565-1569.
［6］ SCARLATA S, FINAMORE P, SANTANGELO S, et al. Cluster analysis on breath print of newly diagnosed COPD patients: Effects of therapy［J］. Journal of Breath Research, 2018,12(3). DOI:10.1088/1752-7163/aac273.
［7］张新萍,张孝远,刘杰. 基于差分进化算法的模糊核聚类算法及其在故障诊断中的应用［J］. 电力系统保护与控制, 2014,42(17):102-106.
［8］ DONG C R, YEUNG D S, WANG X Z, et al. An improved differential evolution and its application to determining feature weights in similarity-based clustering［J］. Neurocomputing, 2014,146:95-103.
［9］ WANG Z J, ZHAN Z H, LIN Y, et al. Dual-strategy differential evolution with affinity propagation clustering for multimodal optimization problems［J］. IEEE Transactions on Evolutionary Computation, 2018,22(6):894-908.
［10］王凤领. 一种改进差分进化的自动聚类算法研究［J］. 数学的实践与认识, 2018,48(21):187-194.
［11］SU Y X, CHI R. Multi-objective particle swarm-differential evolution algorithm［J］. Neural Computing and Applications, 2017,28(2):407-418.
［12］罗维佳,乔少杰,韩楠,等. 面向LBSN的k-medoids聚类算法［J］. 中国科学技术大学学报, 2017,47(1):70-79.
［13］CASSALES G W, CHARO A S, KIRSCH-PINHEIRO M, et al. Improving the performance of Apache Hadoop on pervasive environments through context-aware scheduling［J］. Journal of Ambient Intelligence & Humanized Computing, 2016,7(3):333-345.
［14］APACHE HADOOP. Hadoop Open Source Web Site 2019［EB/OL］. ［2020-12-02］. http://hadoop.apache.org/.
［15］HE H, DU Z H, ZHANG W Z, et al. Optimization strategy of Hadoop small file storage for big data in healthcare［J］. The Journal of Supercomputing, 2016,72(10):3696-3707.

［16］高鹏. 云计算环境下的入侵检测算法研究［D］. 保定:河北大学, 2016.

［17］杨青,张亚文,张琴,等. 基于Hadoop的多维关联规则挖掘算法研究及应用［J］. 计算机工程与科学, 2019,41(12):2127-2133.
［18］马汉达,郝晓宇,马仁庆. 基于Hadoop的并行PSO-kmeans算法实现Web日志挖掘［J］. 计算机科学, 2015,42(z1):470-473.
［19］GOLDER P A, YEOMANS K A. The use of cluster analysis for stratification［J］. Applied Statistics, 1973,22(2):213.
［20］SIDDIQUE K, AKHTAR Z, KHAN F A, et al. KDD cup 99 data sets: A perspective on the role of data sets in network intrusion detection research［J］. Computer, 2019,52(2):41-51.
［21］BUCZAK A L, GUVEN E. A survey of data mining and machine learning methods for cyber security intrusion detection［J］. IEEE Communications Surveys & Tutorials, 2016,18(2):1153-1176.
［22］ASHFAQ R A R, WANG X Z, HUANG J Z, et al. Fuzziness based semi-supervised learning approach for intrusion detection system［J］. Information Sciences, 2017,378:484-497.
［23］YE Y F, LI T, ADJEROH D, et al. A survey on malware detection using data mining techniques［J］. ACM Computing Surveys, 2017,50(3):1-40.

[1]	何玉鹏, 陶勇, 王必恒, 赵英男. 智能配电网边缘计算研究现状与展望[J]. 计算机与现代化, 2023, 0(08): 87-92.
[2]	杨波, 徐胜超. 基于SRv6服务链的云网专线场景安全防护方法[J]. 计算机与现代化, 2023, 0(08): 107-111.
[3]	曾依浦, 戴毅茹, 陈雨田. 基于反向学习和精英提升的无速度项动态粒子群算法[J]. 计算机与现代化, 2023, 0(03): 113-120.
[4]	毛明扬, 徐胜超. 可信赖云计算的通信终端攻击行为识别算法[J]. 计算机与现代化, 2022, 0(11): 37-42.
[5]	曹禹, 李晓辉, 刘忠麟, 贾贺, 费志伟. 云环境大数据工作流编排管理系统研究综述[J]. 计算机与现代化, 2022, 0(01): 41-53.
[6]	张晓敏. 基于布隆过滤器属性基的多关键词可搜索方案[J]. 计算机与现代化, 2021, 0(08): 104-111.
[7]	吴君才, 刘雪芳. 基于云计算和深度信念网络的数字资源配置[J]. 计算机与现代化, 2021, 0(05): 78-82.
[8]	郑滔, 刘梦赤, 冯嘉美. 基于Apache Flink的RDF流数据查询[J]. 计算机与现代化, 2020, 0(11): 47-55.
[9]	陆歌皓, 杨丹妮. 区块链即服务的发展现状与展望[J]. 计算机与现代化, 2020, 0(10): 31-35.
[10]	张羽1,2，郭春1,2，申国伟1,2，平源3. 一种基于信息熵的IDS告警预处理方法[J]. 计算机与现代化, 2020, 0(05): 111-.
[11]	鄂翔南1，刘泽平2，张子晔3. 基于差分进化算法的面目标瞄准点寻优[J]. 计算机与现代化, 2019, 0(12): 27-.
[12]	梁慈1,陈世平2. 基于包簇映射架构的包漂移策略研究[J]. 计算机与现代化, 2019, 0(11): 112-.
[13]	丁顺1,陈世平2. 基于包簇映射机制的实验平台建设及应用[J]. 计算机与现代化, 2019, 0(11): 120-.
[14]	文婷婷,李洪赭. 面向云服务平台的弹性负载均衡算法[J]. 计算机与现代化, 2019, 0(10): 28-.
[15]	张苏宁，王月娟，吴水明，景栋盛. 基于Krylov子空间方法的网络入侵数据聚类[J]. 计算机与现代化, 2019, 0(10): 121-.