一种基于改进果蝇优化的K-mediods聚类算法  

A New K-mediods Clustering Algorithm Based on Improved Fruit Fly Optimization Algorithm

作　　者：王全民 杨晶 张帅帅 WANG Quan-min;YANG Jing;ZHANG Shuai-shuai(School of Information,Beijing University of Technology,Beijing 100124,China)

机构地区：[1]北京工业大学信息学部,北京100124

出　　处：《计算机技术与发展》2018年第12期17-22,共6页Computer Technology and Development

基　　金：国家自然科学基金(61272500)

摘　　要：经典的果蝇优化算法存在收敛精度不高、易陷入早熟收敛和局部最优的缺点,对此,提出一种新的果蝇优化算法。该算法在初始位置选取时利用混沌思想使初始值均匀分布在解空间中,算法后期收敛时,使用禁忌搜索跳出局部最优,避免早熟收敛。针对K-mediods聚类算法易陷入局部最优的缺点,将改进的果蝇优化算法与K-mediods聚类算法融合形成一种新的K-mediods算法,利用改进果蝇优化算法的全局寻优特点优化K-mediods,使得算法可达到更好的聚类效果。在对比性实验中,采用标准优化测试函数验证改进的果蝇算法性能,结果表明改进的果蝇优化算法在寻优速度和精度上效果更优。在人工数据集与UCI数据集上对新的K-mediods算法与其他算法聚类效果进行比较,结果表明新的K-mediods算法在聚类准确率和效率上均有所提高,同时适用于高维数据的聚类。The classical fruit fly optimization algorithm has the disadvantages of low convergence accuracy,falling into premature convergence and local optimum easily.Therefore,we propose an improved fruit fly optimization algorithm.When the initial location is selected,the initial value is uniformly distributed in the solution space by using logistic mapping.When the algorithm converges at the later stage,Tabu search is used to jump out of the local optimum and avoid premature convergence.The improved fruit fly optimization algorithm is combined with K-mediods clustering algorithm with strong local search ability to improve the K-mediods algorithm’s low clustering accuracy and easy falling into the local optimal solution,so as to achieve better clustering results.The improved fruit fly algorithm is tested by standard optimization test function through the targeted experiment.The results show that the improved fruit fly algorithm is superior to the classical FOA algorithm in the optimization precision and the optimization speed.Comparing the clustering results of the new K-mediods algorithm with other algorithms on the artificial data set and the UCI dataset,the results show that the new K-mediods algorithm improves both the accuracy and the efficiency of the clustering,which is suitable for the clustering of high-dimensional data.

关 键 词：聚类 果蝇优化算法 混沌映射 FOA 禁忌搜索 K-mediods 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]