研究综述
4424
计算机应用研究
第26卷
初始条件是相互独立的。层次方法是一种静态的聚类方法,已做的合并或分裂操作不能返回,簇之间也不能交换数据对象,在某步没有选择好合并或分裂点的情况下,可能会导致低质量的聚类结果。由于进行合并或分裂操作需要搜索和估算大量的对象或簇,使得层次方法的可伸缩性较差,同时由于缺乏关于全局状态或簇的规模等信息,该方法可能对有重叠的簇的划分失效‘引。
划分方法则通过评价函数某种簇的原型将数据集直接分解成若干个无关联的簇的集合。它努力优化某种标准目标误差函数,该函数可能强调数据的全局或者局部结构。划分方法主要有K一均值(K-me卸s)和K-中心点(K medoid8)两种类型。K.均值算法对处理大数据集是相对可伸缩的和高效的,K.中心点算法能在一定程度上消除K-均值算法对孤立点的敏感性。划分方法一般要求事先给定簇的个数,并且对初始值和噪声数据敏感。由于划分方法基于对象间的距离和对某种标准的优化进行聚类,这种方法只能发现球状簇而不能发现任意形状的簇,同时算法极易陷入局部最优。
通过以上分析可以看出,层次方法和划分方法的优缺点交错对应,还没有一种方法能同时具有它们的优点。
2基本粒子群聚类算法
为了突破传统聚类方法的瓶颈,一些研究者尝试将粒子群智能算法用于聚类分析,通过将聚类视为一种优化问题,利用PS0算法的全局寻优能力来得到一个对数据集的近似最优划分。
2002年0ITImn等人¨’提出了一种基于粒子群优化的无指导图像分类算法。这是最早提出的基于PS0的聚类算法,以后的粒子群聚类算法大都遵循其基本思想。在他们的算法中,簇的个数由用户预先给定,粒子群中的每个粒子包含一个表示簇中心的数据向量,代表一种候选的划分,整个粒子群则代表了对数据集的多种划分。算法首先将一组随机的簇中心赋值给各个粒子,对于每个粒子,按照最小距离原则对图像像素进行划分操作,随后根据给定的粒子适应度函数,按照Ps0算法的步骤找到一个最优粒子。根据最优粒子的位置从而得到一个对数据集的近似最优划分。他们将该算法应用在对合成图像、
人脑的核磁共振图像以及仙oe湖的(美国)地球资源(探测)
卫星图像的聚类分析中。结果显示,基于Ps0的方法能得到较小的簇内距离和较大的簇间距离。应用在由两种画笔生成的合成图像中,结果表明基于Ps0的方法不会陷入局部最优。
在om阳n等人工作的基础上,Merwe等人埔1提出了基本Ps0聚类算法,用于对一般数据集进行聚类操作。基本Ps0聚类算法中粒子的适应性函数为L。
上:塾堕唑竽业型
(1)
巴5亩v毒。,
(2)
口『(’,■)=√。毛(私一咏)2
—F———一
(3)
万方数据
其中:M为数据的维数;,v。为聚簇的个数;昂表示样本的数据
向量;厅i表示簇e中样本的个数;鸭表示簇c!『中样本的均值
(中心)。基本PsO聚类算法的流程如下:
算法l基本Ps0聚类算法
begin
a)随机选择簇的中心并赋值给各个粒子,随机产生粒子的速度;b)对每个粒子按照最小距离原则对数据进行划分,按照式(1)计算各个粒子的适应值.更新个体极值;
c)根据各个粒子的个体极值,找出全局极值和全局极值位置;
d)按粒子群优化算法的速度公式更新粒子的速度,并把它限制在口。。内;
e)按粒子群优化算法的位置公式更新粒子的位置;
untiI满足终止条件
f)输出最优粒子的位置即最优的札个聚类中心
end
算法的终止条件可以是达到一定的循环次数、簇的中心变化很小或簇的成员不再改变。
基本Ps0聚类算法提供了一条新的解决传统聚类问题的有效途径。从此各种基于粒子群思想的聚类算法被陆续提出并被应用在图像分割与识别、文本聚类、入侵检测等领域。
已有的粒子群聚类算法大都是与传统聚类方法结合,将聚类视为一种优化问题,应用粒子群优化算法的全局寻优能力和
分布式随机搜索特性解决传统聚类算法易陷入局部最优和对初值敏感问题。一些混合算法通过改变PS0算法与传统聚类方法的结合方式以及应用改进的Ps0算法有效提高了算法的收敛速度和全局寻优能力。目前应用粒子群算法解决自动聚类问题的研究还较少。
粒子群优化算法与K-均值算法相结合
继0m舢等人。刊提出基本的PS0聚类算法并取得初步成
功后,研究者借鉴其基本思路,开始将PS0算法与K.me柚s算法结合用于聚类分析,目的是采用Ps0算法的连续优化形式,即利用Ps0算法的全局搜索能力降低K.mea啮算法陷入局部2003年Me刑e等人¨’最早提出了一般形式下PsO与K.
文献[9]对0m功n于2002年提出的基于粒子群优化的图目前,将Ps0算法与K meaIl8算法相结合用于聚类的方3粒子群聚类研究现状
3.1
最优的概率。
me棚相结合的混合聚类方法。该算法的基本思路是先用K.
mea璐方法得到一组簇的中心,然后在粒子群初始化时将其赋值给某个粒子.其余粒子随机初始化,最后用基本PSO聚类算
法即算法l完成聚类。该算法采用K me舢+PS0的组合方式
有效提高了收敛速度,并在一定程度上提高了聚类的有效性。
像聚类算法进行了更细致的研究,对适应度函数作了改进以达到同时最小化平均误差函数和簇内距离,以及最大化簇间距离的目标,同时讨论了P!sO控制参数对算法性能的影响。
法大致可以分为三种:a)先用K—me锄s算法进行一次快速分
类,其结果作为粒子群中某个粒子的初值,然后执行基本Ps0聚类步骤,该方法可以简记为K.me锄s+Pso;b)在基本Pso
聚类算法中,每次迭代时根据聚簇的结果按照K.mea|Is方法求
粒子群聚类算法综述_李峻金_机械/仪表_工程科技_专业资料 暂无评价0人阅读0次下载举报文档 粒子群聚类算法综述_李峻金_机械/仪表_工程科技_专业资料。第 26...
粒子群聚类算法综述_信息与通信_工程科技_专业资料。粒子群算法的概述第26 卷第 12期2009年12月 计算机应用研究ApplicationResearchofComputers Vol.No.2612Dec....
粒子群算法综述【摘要】 :粒子群算法(pso)是一种新兴的基于群体智能的启发式 全局搜索算法,具有易理解、易实现、全局搜索能力强等特点,倍 受科学与工程领域的广泛...
粒子群聚类算法综述 5页 免费 基于粒子群的聚类算法改... 55页 3下载券...%粒子群聚类算法 function [m_pattern]=C_PSO(m_pattern,patternNum) disType=...
粒子群优化算法及其应用综... 3页 免费 粒子群聚类算法综述 5页 2财富值...2003 M 文章编号: 100120920 ( 2003) 0220129206 微粒群算法综述谢晓锋, 张...
粒子群聚类算法综述 5页 免费 基于粒子群的K均值聚类算... 5页 免费一种基于粒子群算法的聚类算法...
一种基于粒子群的聚类算法_专业资料。针对缸中心点算法对初始化敏感和容易陷入局部极值的缺点,提出一种基于粒子群算法和密度初始化改进的K-中心点聚类算法。该算法...
粒子群聚类算法代码_IT/计算机_专业资料。用MATLAB语言实现的粒子群聚类算法,... 粒子群聚类算法综述 5页 免费 基于粒子群优化的文档聚... 6页 免费 免疫...
粒子群聚类算法综述 5页 免费 粒子群聚类MATLAB代码 4页 1下载券基于粒子群优化的文档聚类算法...
热门文档