基于记忆传递旗鱼优化的K均值混合迭代聚类

图1 记忆传递算子

Fig.1 Memory transfer operator

鱼苗个数取决于父代旗鱼个体基因对环境的适应性,对环境适应更好的个体产生更多的子代个体.鱼苗位置在空间上服从均匀分布,记忆传递规则定义为

(15)

\begin{matrix} P (F_{r}) = \{\begin{array}{l} \frac{1}{A_{1}}, & - A_{1} \leq (F_{r} - μ) \leq A_{1} \\ 0, & 其 他 \end{array} \end{matrix}

式中:μ为F_max的向量表示.为了平衡算法的搜索能力和搜索精度,采用自适应的σ定义不同迭代时期的变异剧烈程度,计算方式定义为

(16)

\begin{matrix} σ_{i} = \frac{h (i_{m a x} - i)}{i_{m a x}} \end{matrix}

式中:i_max为最大迭代次数;h为记忆算子初始阶段的变异幅度.记忆因子可以有效增强SFO的全局搜索能力和局部搜索精度,具体流程如图2所示.

图2

图2 改进旗鱼算法流程图

Fig.2 Flow chart of improved sailfish algorithm

MTSFO算法伪代码:

输入: 数据集、聚类数目

输出:聚类中心、分类结果、适应度值

初始化参数

While 不满足终止条件

更新沙丁鱼群和旗鱼鱼群

判断鱼群超出边界:

将样本边界外的值设置为边界值.

结束判断

旗鱼遍历

计算适应度值

结束遍历

沙丁鱼遍历

计算适应度值

结束遍历

按照适应度值对旗鱼和沙丁鱼进行排序

X_BSF = 最优适应度旗鱼

X_BS = 最优适应度沙丁鱼

更新旗鱼位置

更新沙丁鱼位置

B_p = X_BSF

用过适应度值计算S和A₁的值

While 迭代次数小于S

根据 B_p 的位置产生旗鱼后代.

判断后代个体的适应度值优于 B_p

由相应后代个体取代B_p的位置.

结束判断

End while

输出:聚类中心、分类结果、适应度值

2.2.2 适应度函数选择

适应度函数决定了优化群体进化的方向,直接影响种群算法的优化效果和解的质量^[11-12].为使MTSFO更好地优化聚类中心,提升聚类效果,本文采用的适应度函数为文献[7]采用的适应度函数的变体形式,不再以某一类适应度作为评价指标,采用不同簇内适应度总和作为全局适应度去指导算法收敛,适应度函数为

(17)

\begin{matrix} A_{D} = \overset{k}{\sum_{j = 1}} L_{j} \end{matrix}

(18)

L_{j} = \overset{N}{\sum_{i = 1}} \frac{d (x_{i}, C_{j})}{N_{j}}

式中: $A_{D} 为全局适应度; L_{j}$ 为一个种群的适应度; $d (x_{i}, C_{j})$ 为第j簇内的全体样本到该簇聚类中心的距离之和; $N_{j} 为第 j$ 簇中的样本数量.从适应度函数可知,当前聚类结果的适应度不仅与每个类别所有样本点到该簇聚类中心有关,也与该类样本数有关,反映的是该簇所有样本点到该聚类中心欧氏距离的均值大小.

3 MTSFO算法与KMC算法的混合迭代

3.1 最大最小距离积优化

采用最大最小距离积方法对KMC进行优化,选取密度较大且分布较稀疏的初始点代替原始算法随机选取初始点,避免初始点选取不当造成的聚类误差^[13-14],改进初始化的步骤如下.

(1) 从数据集M中随机选取1个样本点作为第1个初始点Z₁,加入集合Z并从M中删除.

(2) 计算更新后M中所有元素到Z₁ 的距离,选取距离Z₁ 最大的元素为Z₂.

(3) 将Z₂ 加入集合Z并从M中删除.

(4)分别计算更新后M中元素到Z中各个元素的距离,并存入距离矩阵 $D_{T e m p}$ 中.(5)找出M中每个元素对应 $D_{T e m p}$ 中的最大距离和最小距离值,求其乘积,并将最大乘积值对应的元素从M中删除,存入集合Z中.若Z中元素个数小于k,转到步骤(3);若Z中元素个数等于k,则初始点选取结束,输出包含k个初始点集合Z,即为得到的初始点.Z表达式为 $Z = {[\begin{array}{l} C_{1} & C_{2} & \dots & C_{k} \end{array}]}^{T},$ Z初始时是空集,用来存储由最大最小积得到的k个初始点. $D_{T e m p}$ 存储Z中各元素到M中各个元素距离的数组.

通过以上步骤可以完成最大最小距离积的初始化,得到的初始聚类中心避免了随机初始化引起的初始误差过大问题,有效减少聚类耗时.

3.2 混合迭代

KMC算法通过迭代求各个维度均值的方法获得聚类中心,其不足在于更新方法过于简单,容易陷入局部最优,导致优化精度过低.利用MTSFO的优化路径替代KMC的优化路径,实现MTSFO与KMC的混合迭代,扩大寻优范围,避免陷入局部最优的同时提高搜索精度.实验证明,此方法能较大提高算法优化效率,主程序流程图如图3所示,算法的基本步骤描述如下.

图3

图3 主程序流程图

Fig.3 Flow chart of main program

(1) 输入数据集M,根据数据集类别的个数确定该数据集中类的个数k.

(2) 用最大最小距离积法初始化每个类的中心点.

(3) 计算数据集M中的每个样本点到各个聚类中心的欧氏距离,按数值大小进行排序,将样本点所属类别归于最小欧氏距离的聚类中心.

(4) 使用KMC算法确定每个样本的类别.

(5) 在每个类别的鱼群中通过MTSFO进行寻优操作,得到新的聚类中心.若新得到的聚类中心适应度优于上次迭代的聚类中心,用新的聚类中心代替历史聚类中心.判断当前迭代是否达到结束条件,若未达到结束条件则执行步骤 (4),否则循环结束,输出寻优结果,结束程序.

4 实验结果分析与应用

硬件实验平台为i5-6300HQ处理器、GTX-960显卡、12 GB内存的计算机,软件平台为VS Code.

4.1 算法性能评价

为评价MTSFO-HIKMC的改进效果,将MTSFO-HIKMC与IMFO-KMC^[7]、K-means++^[15]和模糊C均值算法^[16]应用到国际标准数据集Iris、Seeds、CMC和Wine中比较性能优劣.算法参数设置如下:每种聚类算法的最大迭代次数都取30次,旗鱼鱼群大小设置为30,旗鱼与沙丁鱼的数量比例设置为7∶3,模糊C均值聚类中的权重指数取2.0.Iris、Seeds、CMC和Wine这4种UCI国际通用测试数据库中的数据集主要特征如表1所示.

表1 标准数据集特征

Tab.1 Characteristics of standard data set

数据集	n	d	k	3类样本数
Iris	150	4	3	(50, 50, 50)
Seeds	210	7	3	(70, 70, 70)
CMC	1473	9	3	(629, 333, 511)
Wine	178	13	3	(59, 71, 48)

注:3类样本分别如下,Iris包括山鸢尾、杂色鸢尾和维吉尼亚鸢尾;Seeds包括Kama、Rosa和Canadian 3种小麦品种的籽粒;CMC包括不使用、长期和短期使用避孕方法;Wine包括葡萄酒品种 1~3.

MTSFO-HIKMC改进方法分为初始化算法改进和搜索路径优化.为体现不同改进思路对算法起到的作用,利用消融实验分别对算法不同层面的改进进行测试,并与其他算法进行比较,以体现不同改进方法对算法产生的影响.

4.1.1 实验一:初始化改进效果评价

为评估最大最小距离积对算法起到的优化效果,采取消融实验分别对初始化优化和搜索路径优化进行实验以验证效果.图4为本文使用的适应度函数来评价IMFO-KMC、K-means++、FCM和结合最大最小距离积的旗鱼K均值混合迭代(SFO-HIKMC)算法的实验结果.从损失衰减数据可知,最大最小距离积法在初始化聚类算法方面有较好的优势,初始点的损失远低于未经过初始化优化的FCM算法,使得优化算法节约起始阶段的迭代次数,对聚类效率有较为明显的提升.从图4可知,适应度衰减曲线明显没有达到最优,尤其在对高维数据集CMC和Wine进行聚类时,最终适应度远高于经典的FCM算法,聚类结果距离数据集最优解还有较远的距离,分析原因是搜索路径单一,聚类结果陷入局部最优导致.

图4

图4 实验一中不同算法在4种数据集上的运行结果

Fig.4 Running results of different algorithms on 4 data sets (Experiment 1)

4.1.2 实验二:搜索路径改进效果评价

分析上述实验结果可知,通过最大最小距离积改进的算法能够在一个适应度较低的位置开始收敛,使算法能够通过更少的迭代次数收敛到全局最优.但是容易陷入局部最优解,优化精度不足,这与算法本身的搜索路径单一、没有足够能量冲出局部低洼地带有关^[17].在实验一的基础上通过自适应记忆传递优化算法对原始搜索路径进行优化得到MTSFO-HIKMC 算法,并与其他几种算法进行对比实验,以验证自适应记忆传递优化策略对聚类算法的优化效果.图5所示为IMFO-KMC、K-means++、FCM和MTSFO-HIKMC算法对不同数据集进行聚类的适应度衰减曲线.由图5可知,在实验一已经陷入局部的SFO-HIKMC算法可以多次跳出局部最优,达到更高的聚类精度.

图5

图5 实验二中不同算法在4种数据集上的运行结果

Fig.5 Running results of different algorithms on 4 data sets (Experiment 2)

表2为搜索路径改进前后的算法最终适应度.可知,改进后的算法相较于改进前的算法适应度均有大幅度下降,证明本文改进思路具有实用性.

表2 各类算法在不同数据集上的适应度

Tab.2 Adaptability of different algorithms on different data sets

数据集	算法	适应度
Iris	IMFO-KMC	96.4719
	K-means++	97.3617
	FCM	97.3580
	MTSFO-HIKMC	96.4351
Seeds	IMFO-KMC	312.0161
	K-means++	313.3064
	FCM	313.7096
	MTSFO-HIKMC	311.9355
CMC	IMFO-KMC	5532.8767
	K-means++	5545.7534
	FCM	5542.1917
	MTSFO-HIKMC	5532.6027
Wine	IMFO-KMC	16448.5294
	K-means++	16941.1765
	FCM	16566.1765
	MTSFO-HIKMC	16419.1177

为更客观评价MTSFO-HIKMC改进效果,采用Acc、ARI和NMI共3种评价指标对不同聚类算法进行评估^[18-19].其中,Acc表示聚类的准确率,即比较聚类结果是否和真实结果的一致性;ARI为调整兰德系数,用于衡量两个数据分布的吻合程度,值越大表示计算结果与真实值更相似;NMI为归一化互信息,用来表示两组数据之间的关联程度.

表3列出了3种算法实验得到的评价指标,该数据由10次独立实验数据求均值得到.从表中可知,MTSFO-HIKMC在Iris数据集上测得的Acc指标和IMFO-KMC相等且高于K-means++和FCM算法.在Wine数据集测得Acc指标高于其他3种算法.在Seeds和Wine数据集中,MTSFO-HIKMC的ARI指标相较于其他算法均有不同程度提升.可见,MTSFO-HIKMC相较于另外3种算法,在聚类精确度和聚类结果与真实情况的吻合程度方面具有一定优势.

表3 不同算法在4个数据集上的实验结果

Tab.3 Experimental results of different algorithms on 4 data sets

数据集	算法	Acc	ARI	NMI
Iris	IMFO-KMC	0.894 3	0.743 7	0.763 6
	K-means++	0.885 2	0.721 8	0.716 3
	FCM	0.893 1	0.729 6	0.759 8
	MTSFO-HIKMC	0.894 3	0.732 5	0.755 9
Seeds	IMFO-KMC	0.895 4	0.716 5	0.703 3
	K-means++	0.892 4	0.712 9	0.693 1
	FCM	0.894 3	0.714 6	0.694 2
	MTSFO-HIKMC	0.895 2	0.716 6	0.694 9
CMC	IMFO-KMC	0.712 3	0.371 2	0.425 5
	K-means++	0.566 3	0.365 1	0.418 1
	FCM	0.700 2	0.368 7	0.420 0
	MTSFO-HIKMC	0.707 9	0.371 5	0.420 6
Wine	IMFO-KMC	0.707 9	0.371 5	0.419 3
	K-means++	0.651 8	0.349 2	0.403 1
	FCM	0.696 6	0.360 2	0.405 2
	MTSFO-HIKMC	0.709 1	0.361 2	0.410 5

表4为4种算法在不同数据集单次迭代所需时间.其中,K-means++和FCM算法单次迭代时间优于MTSFO-HIKMC,而MTSFO-HIKMC消耗的时间成本相较于IMFO-KMC算法在4种测试数据集都有不同程度提升.在数据集CMC和Iris中,MTSFO-HIKMC的单次迭代时间相较于IMFO-KMC算法分别节省了7.82%和6.27%.可见,自适应记忆传递优化策略在提高搜索精度、增强全局搜索能力的同时,造成一定程度上时间成本的增加,但相较于收敛精度相似的IMFO-KMC算法,仍具有一定优势.

表4 各类算法在不同数据集单次迭代时间

Tab.4 Single iteration time of different algorithms in different data sets

数据集	算法	单次迭代时间/s
Iris	IMFO-KMC	0.035 1
	K-means++	0.004 2
	FCM	0.005 5
	MTSFO-HIKMC	0.032 9
Seeds	IMFO-KMC	0.170 9
	K-means++	0.006 4
	FCM	0.007 8
	MTSFO-HIKMC	0.164 7
CMC	IMFO-KMC	0.281 3
	K-means++	0.035 1
	FCM	0.062 7
	MTSFO-HIKMC	0.259 3
Wine	IMFO-KMC	0.033 5
	K-means++	0.004 5
	FCM	0.009 7
	MTSFO-HIKMC	0.031 9

分析上述实验结果可知,KMC算法思路简单、聚类精度低、初始聚类中心的随机选取导致算法稳定性差;FCM算法中引入模糊控制的概念,使用模糊聚类算法,使得迭代曲线趋于平滑.但是仍旧存在初始点选取随机性的问题,不仅增加了算法达到全局最优解的迭代次数,而且得到的聚类中心精度不高.IMFO-KMC受限于改进方法,收敛速度提高有限,相较于MTSFO-HIKMC需要更多次迭代去收敛才能达到足够精度;而MTSFO-HIKMC通过最大最小距离积的初始化,减少了到达最优位置的迭代次数,实验一和实验二也证明了自适应记忆传递优化策略使得聚类算法具有较强的全局搜索能力,使聚类算法不易陷入局部最优解,稳定性较强.由表4可知,MTSFO-HIKMC单次迭代算法相较于类似算法具有一定的先进性.由此,可以得出以下结论:MTSFO-HIKMC聚类精度高于传统K-means++算法和FCM算法,在高维数据聚类精度高于IMFO-KMC算法,而在低维数据聚类效果与IMFO-KMC算法接近.在迭代次数和单次迭代所花费的时间成本小于IMFO-KMC算法.本文改进算法具有一定的优越性,在预处理高维数据和实时性要求较高的场合具有较高的实用性.

4.2 测试函数上的性能指标

为了对MTSFO-HIKMC的收敛性有一个更加清晰、直观的了解,分别采用Sphere、Ackley、Three-hump camel、Levy和Bukin函数对MTSFO-HIKMC算法进行测试,并绘制其收敛曲线以直观反映其收敛性能.其中,Sphere和Ackley函数选择在30个维度下进行收敛测试,以反映其高维适应能力,而Three-hump camel、Levy和Bukin这3个函数具有多个局部最优^[20],用以测试MTSFO-HIKMC算法跳出局部最优的能力.图6为各收敛函数在三维可视化图像.

图6

图6 测试函数

Fig.6 Test function

图7为MTSFO-HIKMC在5个测试函数迭代60次的收敛情况.可知,在多峰函数上优化算法较早脱离局部最优,在6次迭代完成均已收敛到全局最优;在高维情况下的表现也较好,在30维的Ackley函数上出现3次跳出局部最优的情况,最终收敛于全局最优.由此可知,MTSFO-HIKMC算法在全局寻优能力有较好的表现.

图7

图7 5类测试函数的运行结果

Fig.7 Running results of 5 types of test functions

表5为MTSFO-HIKMC算法在5个测试函数上的收敛精度,数据为30次实验取得的均值.其中,MTSFO-HIKMC在高维数据和多峰函数搜索精度较高,尤其是在具有多个局部最优解的Bukin函数上,搜索精度依然非常高.可知,自适应记忆传递优化策略针对跳出局部最优的性能较强.

表5 MTSFO-HIKMC在5类测试函数上的精度

Tab.5 Accuracy of MTSFO-HIKMC on 5 types of test functions

序号	测试函数	精度
1	Sphere	5.358×10^-7
2	Ackley	1.493×10^-6
3	Three-hump Camel	2.812×10^-7
4	Levy	6.815×10^-6
5	Bukin	8.763×10^-8

5 结语

提出一种基于记忆传递旗鱼优化的K均值混合迭代聚类方法.首先通过最大最小距离积进行初始化KMC,然后利用自适应记忆传递修正策略改进SFO算法,提升了全局寻优能力和搜索精度,减少了由于SFO初始化误差较大造成的初始阶段多余的迭代次数,最后设计了MTSFO算法与KMC算法的混合迭代,提高了聚类精度,加快了收敛速度,应用价值明显.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

杨恺, 黄树成.

融合K-means和RBF神经网络的汉字识别算法

[J]. 计算机与数字工程, 2021, 49(7): 1286-1289.

YANG

Kai

, HUANG

Shucheng

Chinese character recognition algorithm based on K-means and RBF neural network

[J]. Computer & Digital Engineering, 2021, 49(7): 1286-1289.

DOI:10.1016/j.gsf.2021.101249 URL [本文引用: 1]

[2]

GUO

Z Z

, SHI

, HUANG

F M

, et al.

Landslide susceptibility zonation method based on C5.0 decision tree and K-means cluster algorithms to improve the efficiency of risk management

[J]. Geoscience Frontiers, 2021, 12(6): 101249.

[3]

陈湘中, 万烂军, 李泓洋, 等.

基于蚁群优化K均值聚类算法的滚轴故障预测

[J]. 计算机工程与设计, 2020, 41(11): 3218-3223.

CHEN

Xiangzhong

, WAN

Lanjun

, LI

Hongyang

, et al.

Rolling bearing fault prediction based on ant colony optimization K-Means clustering algorithm

[J]. Computer Engineering and Design, 2020, 41(11): 3218-3223.

[4]

马健.

基于改进的K-means算法初始化方法研究

[J]. 云南民族大学学报(自然科学版), 2020, 29(3): 274-278.

Jian

An initialization method based on an improved K-means algorithm

[J]. Journal of Yunnan Minzu University (Natural Sciences Edition), 2020, 29(3): 274-278.

[5]

王述红, 朱宝强, 王鹏宇.

模拟退火聚类算法在结构面产状分组中的应用

[J]. 东北大学学报(自然科学版), 2020, 41(9): 1328-1333.

WANG

Shuhong

, ZHU

Baoqiang

, WANG

Pengyu

Application of simulated annealing clustering algorithm in grouping of discontinuity orientation

[J]. Journal of Northeastern University (Natural Science), 2020, 41(9): 1328-1333.

[6]

李勇, 赵杰.

一种用于彩色图像分割的GA-K-Means方法

[J]. 科学技术与工程, 2020, 20(32): 13309-13316.

Yong

, ZHAO

Jie

A method based on GA-K-means for segmentation to color image

[J]. Science Technology and Engineering, 2020, 20(32): 13309-13316.

DOI:10.21595/jve.2020.21730 URL [本文引用: 1]

[7]

黄鹤, 李昕芮, 吴琨, 等.

引入改进飞蛾扑火的K均值交叉迭代聚类算法

[J]. 西安交通大学学报, 2020, 54(9): 32-39.

[本文引用: 4]

HUANG

, LI

Xinrui

, WU

Kun

, et al.

Hybrid ite-rative K-means clustering with improved moth-flame optimization

[J]. Journal of Xi’an Jiaotong University, 2020, 54(9): 32-39.

[本文引用: 4]

[8]

HADI

M S

, ALI

S K

, FADZILAN

M F

, et al.

Modelling of flexible beam based on ant colony optimization and cuckoo search algorithms

[J]. Journal of Vibroengineering, 2021, 23(4): 810-822.

[9]

SHADRAVAN

, NAJI

H R

, BARDSIRI

V K

The Sailfish Optimizer: A novel nature-inspired metaheuristic algorithm for solving constrained engineering optimization problems

[J]. Engineering Applications of Artificial Intelligence, 2019, 80: 20-34.

DOI:10.1016/j.engappai.2019.01.001 URL [本文引用: 1]

[10]

SINGH

, PRAKASH

Optical network unit placement in Fiber-Wireless (FiWi) access network by Moth-Flame optimization algorithm

[J]. Optical Fiber Technology, 2017, 36: 403-411.

DOI:10.1016/j.yofte.2017.05.018 URL [本文引用: 1]

[11]

刘振宇, 宋晓莹.

一种可用于分类型属性数据的多变量决策树算法

[J]. 东北大学学报(自然科学版), 2020, 41(11): 1521-1527.

LIU

Zhenyu

, SONG

Xiaoying

An applicable multivariate decision tree algorithm for categorical attribute data

[J]. Journal of Northeastern University (Natural Science), 2020, 41(11): 1521-1527.

[12]

李伟琨, 阙波, 王万良, 等.

基于多目标飞蛾算法的电力系统无功优化研究

[J]. 计算机科学, 2017, 44 (Sup.2): 503-509.

Weikun

, QUE

, WANG

Wanliang

, et al.

Multi-objective moth-flame optimization algorithm based optimal reactive power dispatch for power system

[J]. Computer Science, 2017, 44 (Sup.2): 503-509.

[13]

李建美, 高兴宝.

基于自适应变异的混沌粒子群优化算法

[J]. 计算机工程与应用, 2016, 52(10): 44-49.

粒子群优化算法参数少，寻优速度快，但其寻优效率低且在寻优后期易早熟收敛。为改善其寻优性能，在标准粒子群优化算法中，通过引入混沌映射和自适应变异策略，提出具有自适应变异的混沌粒子群优化（ACPSO）算法，以增强种群的全局寻优性能和局部寻优效率。六个基准测试函数的仿真结果表明，ACPSO算法比已有的五个算法具有更好的寻优能力。

Jianmei

, GAO

Xingbao

Chaotic particle swarm optimization algorithm with adaptive mutation

[J]. Computer Engineering and Applications, 2016, 52(10): 44-49.

Basic particle swarm optimization algorithm has fewer parameters and fast optimization speed, but it suffers some drawbacks such as low optimization efficiency and falling easily into local optimal point in the optimization process. To improve the global optimization performance and local optimization efficiency of particle swarm optimization algorithm, this paper proposes a chaotic particle swarm optimization algorithm with adaptive mutation （ACPSO） by introducing a chaotic mapping and an adaptive strategy. Compared to five existing algorithms, numerical results on six benchmark test functions indicate that ACPSO algorithm has better performance.

[14]

张滨丽, 卞兴超.

改进蚁群优化算法的最优物流配送路径设计

[J]. 现代电子技术, 2020, 43(9): 105-108.

ZHANG

Binli

, BIAN

Xingchao

An optimal logistics distribution path design based on improved ant colony optimization

[J]. Modern Electronics Technique, 2020, 43(9): 105-108.

DOI:10.1504/IJCSM.2021.114177 URL [本文引用: 1]

[15]

NIU

L D

, XIONG

L R

Optimisation and application research of ant colony algorithm in vehicle routing problem

[J]. International Journal of Computing Science and Mathematics, 2021, 13(2): 177.

[16]

TIAN

Research on robot optimal path planning method based on improved ant colony algorithm

[J]. International Journal of Computing Science and Mathematics, 2021, 13(1): 80-92.

DOI:10.1504/IJCSM.2021.114182 URL [本文引用: 1]

[17]

张保东, 张亚楠, 郭黎明, 等.

基于交叉算子和非均匀变异算子的飞蛾扑火优化算法

[J]. 计算机与数字工程, 2020, 48(11): 2622-2627.

ZHANG

Baodong

, ZHANG

Yanan

, GUO

Liming

, et al.

Moth-flame optimization algorithm based on crossover operator and non-uniform mutation operator

[J]. Computer & Digital Engineering, 2020, 48(11): 2622-2627.