正在加载图片...
第6期 朱书伟,等:融合并行混沌莹火虫算法的K-调和均值聚类 ·873. 优化算法进行改进,以充分利用其全局搜索能力,如 这里采用欧式距离计算样本到聚类中心的 融合粒子群)、变邻域搜索)、改进候选组搜索) 距离,参数p对算法的性能具有重要的影响,且 等混合聚类算法。此外,将模糊概念引入KHM中 当p≥2时聚类的效果比较好2]。算法通过不断 也得到了一定的关注6)。目前,各种群智能优化 地迭代使目标函数值不断减小并保持稳定,每次 算法已被广泛地应用于各个领域中[81),并且依据 迭代过程中,各个簇的中心点c()=1,2,…,k)的 没有免费的午餐定律,本文提出新的混合聚类算法。 更新如下[3) 萤火虫算法(firefly algorithm,FA)是由剑桥学者 Yang等[2.1)在2008年提出的一种新颖的群智能算 ∑,mw(c/x)XU(x)Xx i=1 (2) 法,具有结构简单、可调参数少、宜于并行处理等特 点,可以有效解决各种优化问题,并能够成功应用到 ∑mum(cy/x,)X0uw() 聚类问题中提高算法的准确性和鲁棒性[。很多 式中:成员函数m和权重函数wKv的定义分别为 学者已经对它开展了不少研究工作,引入混沌原理 式(3)和式(4)。 改进的FA具有一定的优势,Fister等[s]对现有的混 Ix:-c‖p-2 mkH(C/x:)= (3) 沌萤火虫算法(chaos-based firefly algorithm,CFA) lx-l-p-2 进行了总结,它们的主要思想都是基于算法参数的 改进,其中Gandomi等[u6]采用各种混沌映射模型进 x-6 WKHM(x:)= (4) 行了比较全面的对比分析。然而,仅对参数的调整 (,g-6) 无法更全面有效地利用混沌优化的优点,混沌局部 1.2 萤火虫算法的相关定义 搜索(chaotic local search,CLS)[91o]是一种能够有 在FA中萤火虫彼此吸引主要取决于2个因 效提高算法优化性能的策略。 素:亮度和吸引度。亮度决定了个体所处位置的好 本文从进一步提高FA的优化性能出发,提出 坏及其移动方向,吸引度决定了移动的距离,通过亮 一种新颖的CFA,并将其融入到KHM以获得一种 度和吸引度的不断更新,实现目标优化。通常直接 更有效的混合聚类方法。在FA中引入一种并行混 利用目标函数值的大小表示萤火虫i的亮度I,即 沌局部搜索策略,将CLS与并行混沌优化(parallel L=f:),x:=[xax2…xa]。FA的相关定 chaotic optimization,PC0)[7-l8]相结合,提高FA的 义如下12.13 局部搜索能力,具有更高的搜索效率,并能够有效避 定义1萤火虫i与j之间的吸引度为 免局部最优。将这种改进的CFA融入到KHM中优 B=Boe-r (5) 化其目标函数,通过对实际数据集的实验可以看出 式中:B。为在r=0处的吸引度,一般可取值为1;y 本文所提的聚类算法能够获得更好的性能指标,有 为光强吸收系数,对算法的性能具有重要的影响,通 效抑制了陷入局部最优的问题。 常情况下可以取y=1;r,为萤火虫i与j之间的空 1算法概念与定义 间距离,一般采用欧氏距离计算。 定义2萤火虫i被更亮的萤火虫j吸引而移 1.1K-调和均值算法 动的位置为 K-调和均值算法的原理基本上与K-means是相 xi=x;+B(Xi-xi)+aEi (6) 似的,不同的是其使用调和均值(harmonic means, 式中:x:、x为萤火虫i和j的位置:a为步长因子, HM)代替算术均值来计算目标函数,能够有效解决 可设为常数:e:为服从均匀分布的随机数向量。 对初始类中心点选取的敏感性问题。假定数据集 X=[x1x2…x.]包含n个数据,它们被划分 2基于改进FA的K-调和均值聚类 到k个聚类簇,每个簇的中心用c,(G=1,2,…,k)表 2.1并行混沌局部搜索策略改进的FA 示,KHM的目标函数为[) 基本的FA缺乏变异机制,当处于局部极值时 KHM(X,C)= -,i=1,2,…,n 难以摆脱,且当前最优解xg周围是搜索到更优解的 1 最有利的区域,而FA在优化过程中采用对其随机 2x:-G1 扰动的方式,搜索效率不高。混沌优化方法能够有 (1) 效地跳出局部最优并搜索到全局最优解,现有文献优化算法进行改进,以充分利用其全局搜索能力,如 融合粒子群[3] 、变邻域搜索[4] 、改进候选组搜索[5] 等混合聚类算法。 此外,将模糊概念引入 KHM 中 也得到了一定的关注[6⁃7] 。 目前,各种群智能优化 算法已被广泛地应用于各个领域中[8⁃11] ,并且依据 没有免费的午餐定律,本文提出新的混合聚类算法。 萤火虫算法( firefly algorithm, FA) 是由剑桥学者 Yang 等[12⁃13]在 2008 年提出的一种新颖的群智能算 法,具有结构简单、可调参数少、宜于并行处理等特 点,可以有效解决各种优化问题,并能够成功应用到 聚类问题中提高算法的准确性和鲁棒性[14] 。 很多 学者已经对它开展了不少研究工作,引入混沌原理 改进的 FA 具有一定的优势,Fister 等[15]对现有的混 沌萤火虫算法( chaos⁃based firefly algorithm, CFA) 进行了总结,它们的主要思想都是基于算法参数的 改进,其中 Gandomi 等[16]采用各种混沌映射模型进 行了比较全面的对比分析。 然而,仅对参数的调整 无法更全面有效地利用混沌优化的优点,混沌局部 搜索( chaotic local search, CLS) [9⁃10] 是一种能够有 效提高算法优化性能的策略。 本文从进一步提高 FA 的优化性能出发,提出 一种新颖的 CFA,并将其融入到 KHM 以获得一种 更有效的混合聚类方法。 在 FA 中引入一种并行混 沌局部搜索策略,将 CLS 与并行混沌优化( parallel chaotic optimization, PCO) [17⁃18] 相结合,提高 FA 的 局部搜索能力,具有更高的搜索效率,并能够有效避 免局部最优。 将这种改进的 CFA 融入到 KHM 中优 化其目标函数,通过对实际数据集的实验可以看出 本文所提的聚类算法能够获得更好的性能指标,有 效抑制了陷入局部最优的问题。 1 算法概念与定义 1.1 K⁃调和均值算法 K⁃调和均值算法的原理基本上与 K⁃means 是相 似的,不同的是其使用调和均值( harmonic means, HM)代替算术均值来计算目标函数,能够有效解决 对初始类中心点选取的敏感性问题。 假定数据集 X =[x1 x2 … xn ] 包含 n 个数据,它们被划分 到 k 个聚类簇,每个簇的中心用 cj(j = 1,2,…,k) 表 示,KHM 的目标函数为[3] KHM(X,C) = ∑ n i = 1 k ∑ k j = 1 1 ‖xi - cj‖p ,∀i = 1,2,…,n (1) 这里采用欧式距离计算样本到聚类中心的 距离,参数 p 对算法的性能具有重要的影响,且 当 p≥2 时聚类的效果比较好[ 2] 。 算法通过不断 地迭代使目标函数值不断减小并保持稳定,每次 迭代过程中,各个簇的中心点 cj( j = 1,2,…,k) 的 更新如下[3] 。 cj new = ∑ n i = 1 mKHM(cj / xi) × wKHM(xi) × xi ∑ n i = 1 mKHM(cj / xi) × wKHM(xi) (2) 式中:成员函数 mKHM和权重函数 wKHM的定义分别为 式(3)和式(4)。 mKHM(cj / xi) = ‖xi - cj‖-p-2 ∑ K j = 1 ‖xi - cj‖ - p - 2 (3) wKHM(xi) = ∑ k j = 1 ‖xi - cj‖-p-2 (∑ k j = 1 ‖xi - cj‖-p ) 2 (4) 1.2 萤火虫算法的相关定义 在 FA 中萤火虫彼此吸引主要取决于 2 个因 素:亮度和吸引度。 亮度决定了个体所处位置的好 坏及其移动方向,吸引度决定了移动的距离,通过亮 度和吸引度的不断更新,实现目标优化。 通常直接 利用目标函数值的大小表示萤火虫 i 的亮度 Ii,即 Ii =f(xi), xi = [xi1 xi2 … xid ] 。 FA 的相关定 义如下[12⁃13] : 定义 1 萤火虫 i 与 j 之间的吸引度为 β = β0 e -γr 2 ij (5) 式中: β0 为在 r = 0 处的吸引度,一般可取值为 1; γ 为光强吸收系数,对算法的性能具有重要的影响,通 常情况下可以取 γ = 1;rij为萤火虫 i 与 j 之间的空 间距离,一般采用欧氏距离计算。 定义 2 萤火虫 i 被更亮的萤火虫 j 吸引而移 动的位置为 xi new = xi + β(xj - xi) + α εi (6) 式中: xi 、 xj 为萤火虫 i 和 j 的位置;α 为步长因子, 可设为常数; εi 为服从均匀分布的随机数向量。 2 基于改进 FA 的 K⁃调和均值聚类 2.1 并行混沌局部搜索策略改进的 FA 基本的 FA 缺乏变异机制,当处于局部极值时 难以摆脱,且当前最优解 xpg 周围是搜索到更优解的 最有利的区域,而 FA 在优化过程中采用对其随机 扰动的方式,搜索效率不高。 混沌优化方法能够有 效地跳出局部最优并搜索到全局最优解,现有文献 第 6 期 朱书伟,等:融合并行混沌萤火虫算法的 K⁃调和均值聚类 ·873·
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有