基于模拟退火粒子群算法的FCM聚类方法_李丽丽

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

２００８，４４（３０）

基于模拟退火粒子群算法的ＦＣＭ聚类方法

李丽丽１，刘希玉２，庄波３

ＬＩＬｉ－ｌｉ１，ＬＩＵＸｉ－ｙｕ２，ＺＨＵＡＮＧＢｏ３

１．山东师范大学信息科学与工程学院，济南２５００１４

２．山东师范大学管理与经济学院，济南２５００１４

３．滨州学院计算机科学技术系，山东滨州２５６６０３

１．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｄｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５００１４，Ｃｈｉｎａ

２．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＳｈａｎｄｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５００１４，Ｃｈｉｎａ

３．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＢｉｎｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｂｉｎｚｈｏｕ，Ｓｈａｎｄｏｎｇ２５６６０３，Ｃｈｉｎａ

Ｅ－ｍａｉｌ：ｌｉ＿ｌｉｌｉ００１＠１６３．ｃｏｍ

ＬＩＬｉ－ｌｉ，ＬＩＵＸｉ－ｙｕ，ＺＨＵＡＮＧＢｏ．ＦｕｚｚｙＣ－ｍｅａｎｓａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（３０）：１７０－１７２．

Ａｂｓｔｒａｃｔ：ＩｎｏｒｄｅｒｔｏｏｖｅｒｃｏｍｅｔｈｅｄｅｆｅｃｔｓｏｆｆｕｚｚｙＣ－ｍｅａｎｓａｌｇｏｒｉｔｈｍｓｕｃｈａｓｔｈｅｌｏｃａｌｏｐｔｉｍａａｎｄｓｅｎｓｉｔｉｖｉｔｙｔｏｉｎｉｔｉａｌｉｚａｔｉｏｎ，ａｎｅｗｆｕｚｚｙａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＳＡ－ＰＳＯｉｓｐｕｔｆｏｒｗａｒｄｉｎｔｈｉｓｐａｐｅｒ．ＴｈｅｎｅｗａｌｇｏｒｉｔｈｍｍａｋｅｓｕｓｅｏｆｔｈｅｃａｐａｃｉｔｙｏｆｇｌｏｂａｌｓｅａｒｃｈｉｎＰＳＯａｌｇｏｒｉｔｈｍａｎｄｔｈｅａｂｉｌｉｔｙｏｆｊｕｍｐｉｎｇｏｕｔｏｆｔｈｅｌｏｃａｌｏｐｔｉｍａｉｎＳＡ，ａｎｄｓｏｌｖｅｓｔｈｅｓｈｏｒｔｃｏｍｉｎｇｓｏｆＦＣＭ．Ｔｈｅｅｘ－ｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍａｖｏｉｄｓｔｈｅｌｏｃａｌｏｐｔｉｍａａｎｄｉｎｃｒｅａｓｅｓｔｈｅｃｏｎｖｅｒｇｅｎｃｅｓｐｅｅｄ．

Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒａｎａｌｙｓｉｓ；ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ；ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）；ｆｕｚｚｙＣ－ｍｅａｎａｌｇｏｒｉｔｈｍ；ｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎ

摘要：针对模糊Ｃ－均值（ＦＣＭ）聚类算法易陷入局部极小值和对初始值敏感的缺点，提出了一种基于模拟退火粒子群优化的模糊聚类算法。该算法利用粒子群强大的全局寻优能力和模拟退火算法跳出局部极值的能力，克服了模糊Ｃ－均值聚类算法的不足。实验表明，该算法有很好的全局收敛性，能够较快地收敛到最优解。

关键词：聚类分析；模拟退火算法；粒子群优化算法；模糊Ｃ－均值算法；全局优化

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．３０．０５２文章编号：１００２－８３３１（２００８）３０－０１７０－０３文献标识码：Ａ中图分类号：ＴＰ３０１

１引言

聚类分析的主要目的是通过对数据集的合理划分来发现数据集的结构特征，使同一簇中对象的特性尽可能相似，不同簇对象间的特性差异尽可能的大。在传统的聚类算法中，样本所属的分类都是唯一的，也即是硬划分。但实际上大多数事物并没有严格的属性，事物间没有明确的界限，不具有非此即彼的性质，所以模糊聚类的概念更适合事物的本质，能更客观地反映现实。ＦＣＭ是Ｂｅｚｋｅｋ于１９８１年提出的，它是目前广泛采用的一种聚类算法［１］。模糊Ｃ－均值聚类是模糊聚类算法中非常有效的一种，它能给出每个样本隶属于某个聚类的隶属度，但由于ＦＣＭ算法选取聚类中心点时采用随机选取易使得迭代过程陷入局部最优解，因此把进化计算引入模糊聚类中，以期达到全局寻优、快速收敛的目的。

Ｍｅｔｒｏｐｏｌｉｓ等人于１９５３年提出了模拟退火算法［２］，其基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比，固体退火过程的物理图像和统计性质是模拟退火算法的物理背景，Ｍｅｔｒｏｐｏｌｉｓ接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。固体退火是先将固体加热至熔化，然后徐徐冷却使之凝固成规整晶体的热力学过程。从统计物理学的观点看，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。

粒子群优化算法（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）是群体智能中的一种算法。最早是由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ于１９９５年提出的，是一种基于种群寻优的启发式搜索算法。它的基本概念源于对鸟群群体行为的研究［３］。由于粒子群优化算法概念简单，易于实现，并且具有较好的寻优特性，因此它在短期内得到迅速发展，目前已在许多领域中得到应用。本文将模拟退火算法和粒子群优化算法结合起来进行了改进，并将其引入模糊

基金项目：山东省自然科学基金重大项目（ｔｈｅＧｒａｎｄＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＳｈａｎｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．Ｚ２００４Ｇ０２）；山东省教育厅计划项目（ｔｈｅＳｃｉｅｎｔｉｆｉｃａｎｄＴｅｃｈｎｏｌｏｇｙＰｒｏｊｅｃｔｏｆＳｈａｎｄｏｎｇＥｄｕｃａｔｉｏｎＢｕｒｅａｕ，Ｎｏ．Ｊ０５Ｇ０１）；“泰山学者”建设工程专项经费资助（“ＴａｉｓｈａｎＳｃｈｏｌａｒ”ＰｒｏｊｅｃｔｏｆＳｈａｎｄｏｎｇＣｈｉｎａ）。

作者简介：李丽丽（１９８３－），女，硕士研究生，主要研究领域为进化计算、数据挖掘；刘希玉（１９６４－），男，教授，博士，博士生导师，主要研究领域：数据挖掘、人工神经网络、群体智能；庄波（１９７６－），男，硕士研究生，主要研究领域为数据挖掘。

收稿日期：２００７－１１－２３修回日期：２００８－０１－２８

１７０

２００８，４４（３０）聚类算法中，解决了模糊聚类易陷入局部极小值和对初始值敏感的缺点，并使其具有较快的收敛速度。

２ＦＣＭ算法

模糊聚类是将样本空间Ｘ＝｛ｘ１，ｘ２，…，ｘｉ，…，ｘｎ｝的样本点

分成ｃ类，ｃ为大于１的正整数［４］。任意一个样本点ｘｉ∈Ｘ（１≤

ｉ≤ｎ）不可能被严格地划分给某一类，定义样本点ｘｉ属于第ｊ

（１≤ｊ≤ｃ）类的程度ｗｉｊ（０≤ｗｉｊ≤１）。样本空间Ｘ的模糊聚类用模糊矩阵Ｗ＝（ｗｉｊ）描述，元素ｗｉｊ是矩阵Ｗ的第ｉ行第ｊ列元素，代表第ｉ个样本点隶属于第ｊ类的隶属度。Ｗ具有以下性质：

ｗｉｊ∈［０，１］

（１）ｃ

ｊ＝１

#ｗｉｊ

＝１

（２）０＜ｎ

ｉ＝１

#ｗｉｊ＜ｎ

（３）

为了计算各个样本点相对于聚类中心的隶属度，一般采用

ＦＣＭ算法。定义目标函数：

Ｊｍ

（Ｗ，Ｚ）＝ｎ

ｉ＝１

#ｃ

ｊ＝１#ｗｍ

ｉｊｄ２

ｉｊ（ｘｉ，ｚｊ），Ｚ＝（ｚ１，ｚ２，…，ｚｃ）其中ｍ（ｍ＞１）是模糊指数，ｚｊ表示第ｊ类的聚类中心，ｄ２

ｉｊ（ｘｉ，ｚｊ）＝‖ｘｉ－ｚｊ‖是样本点ｘｉ到聚类中心ｚｊ的欧氏距离。

聚类即是求目标函数在式（１）￣（３）约束下的最小值。ＦＣＭ算法通过对目标函数的迭代优化来取得对样本集的模糊分类。迭代过程如下［２］：

（１）随机地初始化Ｗ（０）

；初始化Ｚ（０）

并计算Ｗ（０）

。令迭代次数为ｋ＝１，选择聚类中心的个数ｃ，并选择模糊指数ｍ（ｍ＞１）。

（２）计算Ｗ

（ｋ）

。如果%ｉ和ｒ，ｄｉｒ（ｋ）＞０，则Ｗｉｊ（ｋ）＝

１

ｃ

ｒ＝１

#［（ｄｉｊ（ｋ）

ｄｉｒ（ｋ））２ｍ－１

］

。若存在ｉ和ｒ使得ｗｉｒ（ｋ）＝１，且对ｊ≠ｒ，ｗｉｊ（ｋ）＝０。

（３）计算Ｚ

（ｋ＋１）

。%ｊ，Ｚｊ（ｋ＋１）＝

ｎ

ｉ＝１

#ｗｍ

ｉｊ

ｘ

ｉ

ｎ

ｉ＝１

#ｗｍ

ｉｊ

。

（４）如果‖Ｗ

（ｋ）

－Ｗ

（ｋ＋１）

‖＜ε

，则停止迭代；否则令ｋ＝ｋ＋１，转步骤（２），其中ε

是预先给定的小正数。该算法对初值敏感，很大程度上依赖初始聚类中心的选择，当初始聚类中心严重偏离全局最优聚类中心时，用ＦＣＭ很可能陷入局部极小值。

３模拟退火粒子群算法（ＳＡ－ＰＳＯ）

模拟退火算法（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍ）于１９８３年

成功地应用在组合优化的问题上，其思想是通过模拟高温物体退火过程的方法来找到优化问题的全局最优或近似全局最优解［５］

。首先产生一个初始解作为当前解，然后在当前解的邻域

中，以概率Ｐ（Ｔ）选择一个非局部最优解，并令这个解再重复下去，从而保证不会陷入局部最优。开始时允许随着参数的调整，目标函数偶尔向增加的方向发展（对应于能量有时上升），以利于跳出局部极小区域。随着假想温度的降低（对应于物体的退火），系统活动性降低，最终以概率１稳定在全局最小区域。

ＰＳＯ算法是基于群体的，根据对环境的适应度将群体中的

个体移动到好的区域，然而它不对个体使用演化算子，而是将每个个体看作Ｄ维搜索空间中的一个没有体积的粒子，在搜索空间中以一定的速度飞行。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整［６］。第ｉ个微粒表示为Ｘｉ＝（ｘｉ１，ｘｉ２，…，ｘｉＤ），它经历过的最好位置（有最好的适应值）记为Ｐｉ＝

（ｐｉ１，ｐｉ２，…，ｐｉＤ），也称为ｐｂｅｓｔｉ。在群体所有微粒经历过的最好位置的索引号用符号ｇ表示，即ｐｇ，也称为ｇｂｅｓｔ。微粒ｉ的速度用Ｖｉ＝（ｖｉ１，ｖｉ２，…，ｖｉＤ）表示。对每一代，其第ｄ维（１≤ｄ≤Ｄ）根据如下方程变化［３］

ｖｉｄ＝ｗｖｉｄ＋ｃ１ｒａｎｄ１（ｐｉｄ－ｘｉｄ）＋ｃ２ｒａｎｄ２（ｐｇｄ－ｘｉｄ）（４）ｘｉｄ＝ｘｉｄ＋ｖｉｄ

（５）

其中：ｗ为惯性权重，通常是从０．９线性减小到０．２；ｃ１和ｃ２为加速常数，通常取值为２；ｒａｎｄ１和ｒａｎｄ２为两个在［０，１］范围内变化的随机函数，每一维的速度都被限制在ｖｍａｘ内。

由于粒子群优化算法有易陷入局部极值点，进化后期收敛慢，精度较差等缺点，而模拟退火算法有较强的跳出局部最优解的能力，因此将模拟退火算法应用到粒子群算法中。基于模拟退火的粒子群算法如下所述：

（１）对每个粒子初始化，设定退火初始温度Ｔ，温度冷却系数Ｃ，粒子数ｎ，随机产生ｎ个初始解或给出ｎ个初始解，随机产生ｎ个初始速度；

（２）根据当前位置和速度产生这个粒子的新的位置；Ｗｈｉｌｅ

（迭代次数＜规定迭代次数）ｄｏ（３）计算每个粒子新位置的适应值；

（４）对某个粒子，若粒子的适应值优于原来的个体极值

ｐｂｅｓｔｉ，设置当前适应值为ｐｂｅｓｔｉ；

（５）根据各个粒子的个体极值ｐｂｅｓｔｉ找出全局极值ｇｂｅｓｔ；（６）按式（４），更新自己的速度，并把它限制在ｖｍａｘ内；（７）按式（５），更新当前的位置，并把它限制在ｘｍａｘ内；（８）计算两个位置所引起的适应值的变化量ΔＥ；若ΔＥ≤

０，接受新值，若ｅｘｐ（－ΔＥ／Ｔ）＞ｒａｎｄ（０，１）也接受新值；否则就拒绝，ｘｋ＋１仍为ｘｋ。

４基于ＳＡ－ＰＳＯ的ＦＣＭ聚类

为了解决ＦＣＭ存在的问题，将模拟退火粒子群算法应用

于模糊聚类中。对于粒子群中每个个体的评价，定义如下的适应度函数：

ｆ

（ｘｉ）＝ｋＪｍ

（Ｗ，Ｚ）（６）

其中，ｋ为常数，Ｊｍ（Ｗ，Ｚ）为总的类间离散度和。如果聚类效果越好，则Ｊｍ（Ｗ，Ｚ）越小，个体适应度就越高。

用向量Ｚ＝（ｚ１，ｚ２，…，ｚｉ，ｚｃ）来表示一个聚类中心，也就是一个粒子。其中ｚｉ表示第ｉ类聚类中心的编码。每类ｎ维聚类中心采用实数编码，这样向量Ｚ就成了ｃ×ｎ列的一维行向量，最终求得的Ｚ就表示最优解。模拟退火粒子群模糊聚类算法实现过程可以描述为：

（１）给定类别数ｃ，模糊指数ｍ，群体规模Ｎ，学习因子ｃ１和ｃ２，惯性权重ｗ，退火初始温度Ｔ，温度冷却系数Ｃ。

（２）初始化Ｎ个聚类中心并对其进行编码，形成Ｎ个第１

李丽丽，刘希玉，庄波：基于模拟退火粒子群算法的ＦＣＭ聚类方法

１７１

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

２００８，４４（３０）的传输性能，如果网络条件或传输状况很差，可尝试将并行度设为１６。但并行度大于１６时，几乎不会对传输性能有所改善，反而还会使传输性能下降。

在局域网中进行相同的测试，增大ＴＣＰ并行度，传输带宽和传输时间几乎没有变化。可以得出结论，多并行流适用于拥塞环境下的数据传输，它能明显减轻拥塞程度。但如果每个ＴＣＰ应用都使用多并行流，网络的整体性能会下降，甚至可能导致网络崩溃。

解决这个问题，需要引入条状传输机制，采用并行传输和条状传输相结合的方式，实现分布式的数据存储，多台服务器之间并行地传输数据，而在每条传输线路上使用多ＴＣＰ并行流。

参考文献：

［１］ＡｌｌｃｏｃｋＷ，ＢｅｓｔｅｒＪ，ＢｒｅｓｎａｈａｎＪ，ｅｔａｌ．ＧｒｉｄＦＴＰ：ｐｒｏｔｏｃｏｌｅｘｔｅｎｓｉｏｎｓ

ｔｏＦＴＰｆｏｒｔｈｅｇｒｉｄ［Ｃ］／／ＧｌｏｂａｌＧｒｉｄＦｏｒｕｍ，ＰｒｏｐｏｓｅｄＲｅｃｏｍｍｅｎｄａ－ｔｉｏｎＧＦＤ－Ｒ－Ｐ．０２０，２００３－０４．

［２］ＡｌｌｃｏｃｋＷ，ＢｅｓｔｅｒＪ，ＢｒｅｓｎａｈａｎＪ，ｅｔａｌ．ＧｒｉｄＦＴＰ：ｐｒｏｔｏｃｏｌｅｘｔｅｎｓｉｏｎｓ

ｔｏＦＴＰｆｏｒｔｈｅｇｒｉｄ［ＥＢ／ＯＬ］．

（２００１－０３）．ｈｔｔｐ：／／ｗｗｗ－ｆｐ．ｍｃｓ．ａｎｌ．ｇｏｖ／ｄｓｌ／．［３］ＧＴ４．０ＧｒｉｄＦＴＰ［ＥＢ／ＯＬ］．［２００７－１２］．ｈｔｔｐ：／／ｗｗｗ．ｇｌｏｂｕｓ．ｏｒｇ／．

［４］ＲｉｚｋＰ，ＫｉｄｄｌｅＣ，ＳｉｍｍｏｎｄｓＲ．ＡＧｒｉｄＦＴＰｏｖｅｒｌａｙｎｅｔｗｏｒｋｓｅｒｖｉｃｅ［Ｃ］／／

ＩＥＥＥＧｒｉｄＣｏｍｐｕｔｉｎｇＣｏｎｆｅｒｅｎｃｅ，２００６．［５］Ｔｃｐｄｕｍｐ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｔｃｐｄｕｍｐ．ｏｒｇ／．

［６］Ｉｐｅｒｆ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｄａｓｔ．ｎｌａｎｒ．ｎｅｔ／Ｐｒｏｊｅｃｔｓ／Ｉｐｅｒｆ／．

［７］ＩｔｏＴ，ＯｈｓａｋｉＨ，ＩｍａｓｅＭ．Ａｕｔｏｍａｔｉｃｐａｒａｍｅｔｅｒｃｏｎｆｉｇｕｒａｔｉｏｎｍｅｃｈａ－

ｎｉｓｍｆｏｒｄａｔａｔｒａｎｓｆｅｒｐｒｏｔｏｃｏｌｇｒｉｄＦＴＰ［Ｃ］／／ＩＥＥＥＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００５ＳｙｍｐｏｓｉｕｍｏｎＡｐｐｌｉｃａｔｉｏｎｓａｎｄｔｈｅＩｎｔｅｒｎｅｔ，２００６．

［８］ＢｉｌｌＡｌｌｃｏｃｋＡｒｇｏｎｎｅＮａｔｉｏｎａｌＬａｂｏｒａｔｏｒｙ．ＰａｒａｌｌｅｌＴＣＰ［ＥＢ／ＯＬ］．

（２００５－０１－２７）．ｈｔｔｐ：／／ｉｓｏｃ．ｎｌ／ａｃｔｉｖ／２００５－Ｇｌｏｂｕｓ－Ａｌｌｃｏｃｋ／ＰａｒａｌｌｅｌＴＣＰ．ｐｄｆ．［９］ＯｈｓａｋｉＨ，ＩｍａｓｅＭ．ＯｎｍｏｄｅｌｉｎｇＧｒｉｄＦＴＰｕｓｉｎｇｆｌｕｉｄ－ｆｌｏｗａｐｐｒｏｘｉ－

ｍａｔｉｏｎｆｏｒｈｉｇｈｓｐｅｅｄｇｒｉｄｎｅｔｗｏｒｋｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００４ＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＡｐｐｌｉｃａｔｉｏｎｓａｎｄｔｈｅＩｎｔｅｒｎｅｔＷｏｒｋ－ｓｈｏｐｓ，２００４．

［１０］ＰａｄｈｙｅＪ，ＦｉｒｏｉｕＶ，ＴｏｗｓｌｅｙＤ，ｅｔａｌ．ＭｏｄｅｌｉｎｇＴＣＰｔｈｒｏｕｇｈｐｕｔ：ａ

ｓｉｍｐｌｅｍｏｄｅｌａｎｄｉｔｓｅｍｐｉｒｉｃａｌｖａｌｉｄａｔｉｏｎ［Ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆＡＣＭＳＩＧＣＯＭＭ’９８，１９９８：３０３－３１４．

（上接１３７页）

算法

ＦＣＭ算法

基于传统ＰＳＯ的ＦＣＭ基于ＳＡ－ＰＳＯ的ＦＣＭ

平均值

８２．９４３７７８．７１６８７８．４５３２

最好解

７８．４５３２７８．４５３２７８．４５３２

最差解

１５６．１５８７７８．９０１１７８．４５３２

表１

实验结果表

代粒子。每个粒子的ｐｂｅｓｔｉ为其当前位置，ｇｂｅｓｔ为当前种群中所有粒子中的最好位置。

（３）对每个聚类中心计算隶属度ｗｉｊ，其中ｉ＝１，２，…，ｎ；ｊ＝

１，２，…，ｃ。

（４）按式（６）计算每个粒子的适应度值，如果好于该粒子当前的最好位置的适应度，则更新该粒子个体最好位置。如果所有粒子中的最好位置的适应度好于当前全局最好位置的适应度，则更新全局最好位置。

（５）用式（４）和式（５）对每个粒子的速度和位置进行更新，产生下一代的粒子群。

（６）计算两个位置所引起的适应值的变化量ΔＥ；若ΔＥ≤０，接受新值，若ｅｘｐ（－ΔＥ／Ｔ）＞ｒａｎｄ

（０，１）也接受新值；否则就拒绝，ｘｋ＋１仍为ｘｋ。

（７）如果当前的迭代次数达到预先设定的最大次数，则停止迭代。在最后一代找到最佳解，否则重复转到步骤（３）。

５实验结果

实验采用著名的Ｉｒｉｓ（鸢尾花）植物样本数据进行测试，该

数据包括３种植物的１５Ｏ个样本，每个样本均为代表植物４种特征的４维向量。聚类类别为３，每类样本为５０，模糊指数

ｍ＝２。每类初始聚类中心取１５０个样本中的任意３个，初始聚

类中心作为粒子群算法的初值。采用模拟退火粒子群算法参数设置如下：退火初始温度Ｔ＝１００００００，温度冷却系数Ｃ＝０．８，惯性权重从ｗ＝０．９线性减小到ｗ＝０．５，学习因子ｃ１和ｃ２都取２，最大迭代次数５０。实验结果如表１所示。

实验结果显示，基于模拟退火粒子群算法的ＦＣＭ算法优于传统的ＦＣＭ算法和基于粒子群算法。从表１可以看出，传统的ＦＣＭ算法，容易陷入局部最小值，且收敛速度较慢，而提出的算法能够较快的收敛到最优解。

６结束语

提出的算法是将模拟退火算法、粒子群优化和ＦＣＭ相结合

的聚类算法。实验表明，该算法能有效解决传统的ＦＣＭ对于初始化敏感以及容易陷入局部极小的问题，具有较强的全局搜索能力，能够跳出局部极小值，聚类效果优于传统的ＦＣＭ聚类方法以及基于传统粒子群的ＦＣＭ聚类方法。

参考文献：

［１］ＢｅｚｄｅｋＪＣ．Ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎｗｉｔｈｆｕｚｚｙｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎａｌｇｏ－

ｒｉｔｈｍｓ［Ｍ］．ＮｅｗＹｏｒｋ：ＰｌｅｎｕｍＰｒｅｓｓ，１９８１：９５－１０７．

［２］王华秋，曹长修．基于模拟退火的并行粒子群优化研究［Ｊ］．控制与决

策，２００５，２０（５）：５００－５０４．

［３］ＭａｄａｒＪ，ＡｂｏｎｙｉＪ，ＳｚｅｉｆｅｒｔＦ．Ｉｎｔｅｒａｃｔｉｖｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉ－

ｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００５５ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓＤｅｓｉｇｎａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００５．

［４］张敏，于剑．基于划分的模糊聚类算法［Ｊ］．软件学报，２００４，１５

（６）：８５８－８６８．

［５］高鹰，谢胜利．基于模拟退火的粒子群优化算法［Ｊ］．计算机工程与应

用，２００４，４０（１）：４７－５０．

［６］周驰，高海兵，高亮，等．粒子群优化算法［Ｊ］．计算机应用研究，２００３（１２）：７－１２．

［７］刘靖明，韩丽川，侯立文．基于粒子群的Ｋ均值聚类算法［Ｊ］．系统工

程理论与实践，２００５（６）：５４－５８．

［８］李爱国，覃征，鲍复民，等．粒子群优化算法［Ｊ］．计算机工程与应用，

２００２，３８

（２１）：１－３．［９］侯志荣，吕振肃．基于ＭＡＴＬＡＢ的粒子群优化算法及其应用［Ｊ］．计算

机仿真，２００３（２０）：６８－７０．

１７２

聚类分析K-means算法综述

聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；

（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

粒子群优化算法综述

粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 0.引言 粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子 的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适 应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。 粒子群优化算法一般采用下面的公式对粒子进行操作

)()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数， 称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进 与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算 法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度 量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的 概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。 文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间 两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间；

蚁群聚类算法综述

计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x

粒子群算法综述

粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的

优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。

利用模拟退火算法设计方向图的原理和方法

第２４卷第７期计算机仿真２００７年７月文章编号：１００６—９３４８（２００７）０７—０１７６—０３ 利用模拟退火算法设计方向图的原理和方法 林欢欢，王英民，朱婷婷 （西北工业大学航海学院，陕西西安７１００７２） 摘要：在声纳系统中，基阵方向图的作用是用来指示目标方位的，它是一个声纳系统的核心和重要部分。由于声纳系统的使用环境比较复杂，如何快速、有效、多角度地设计基阵方向图是一个很值得关注的问题。为了解决这个问题，引入了模拟退火算法来进行方向图的辅助设计。模拟退火算法是近些年发展起来的一种全局优化算法，它最大的特点是可以根据不同的标准来进行优化。利用它来设计基阵方向图，可以省去很多繁琐的步骤，有效地简化方向图的设计。计算机仿真结果表明，模拟退火算法可以很好的完成在不同情况下设计基阵方向图的任务。 关键词：模拟退火算法；最佳指向性指数：列阵 中图分类号：ＴＮ３９１．９文献标识码：Ａ ＴｈｅＴｈｅｏｒｙａｎｄＭｅｔｈｏｄｆｏｒＤｅｓｉｇｎｉｎｇｔｈｅＯｐｔｉｍｕｍＤｉｒｅｃｔｉｏｎａｌＰａｔｔｅｒｎｏｆＡｃｏｕｓｔｉｃＡｒｒａｙｓｗｉｔｈＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ ＬＩＮＨｕａｎ—ｈｕａｎ，ＷＡＮＧＹｉｎｇ—ｍｉｎ，ＺＨＵＴｉｎｇ—ｔｉｎｇ （ＭａｒｉｎｅＣｏＨｅｇｅｏｆＮｏｒｔｈｗｅｓｔｅｒｎＰｏｌｙｔｅｃｈｎｉｃａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎＳｈａｎｘｉ７１００７２，Ｃｈｉｎａ）ＡＢＳＴＲＡＣＴ：Ｔｈｅｆｕｎｃｔｉｏｎｏｆｄｉｒｅｃｔｉｏｎａｌｐａｔｔｅｒｎｉｎｔｈｅｓｏｎａｒｓｙｓｔｅｍｉｓｔｏｄｅｔｅｃｔｔａｒｇｅｔ’Ｓｐｏｓｉｔｉｏｎ．Ｔｈｅｄｉｒｅｃｔｉｏｎａｌｐａｔｔｅｒｎｉｓ ｔｈｅｋｅｙａｎｄａｎｉｍｐｏｒｔａｎｔｐａｒｔｉｎｔｈｅｓｏｎａｒｓｙｓｔｅｍ．Ｂｅｃａｕｓｅｏｆｖａｒｉｏｕｓｃｏｎｄｉｔｉｏｎｓｉｎｗｈｉｃｈｔｈｅｓｏｎａｒｓｙｓｔｅｍｗｏｒｋｅｄ，ｈｏｗｔｏｄｅｓｉｇｎｔｈｅｄｉｒｅｃｔｉｏｎａｌｐａｔｔｅｒｎｉｓａｎｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍ．Ｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍ，ｔｈｅｍｅｔｈｏｄｏｆＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇｉｓｉｎｔｒｏｄｕｃｅｄ．ＴｈｅｍｅｔｈｏｄｏｆＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇｉｓａｇｌｏｂａｌｏｐｔｉｍｉｚｅｄｍｅｔｈｏｄｄｅｖｅｌｏｐｅｄｉｎｒｅｃｅｎｔｙｅａｒｓ． Ｔｏｄｅｓｉｇｎｔｈｅｄｉｒｅｃｔｉｏｎａｌｐａｔｔｅｒｎｗｉｔｈｉｔｃａｎｐｒｅｄｉｇｅｓｔｔｈｅｐｒｏｂｌｅｍ．Ｆｉｎａｌｌｙ，ｔｈｅｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｉｏｎｉｓｉｎｃｌｕｄｅｄｔｏｓｕｓｔａｉｎｔｈｅｍｅｔｈｏｄ． ＫＥＹＷＯＲＤＳ：Ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ；Ｏｐｔｉｍｕｍｄｉｒｅｃｔｉｏｎ；Ｌｉｎｅａｒｐｏｉｎｔａｒｒａｙ １引言 在声纳系统的设计中，声纳的指向性是一个非常重要的问题，它的设计好坏，直接决定了声纳的好坏。对于声纳指向性的设计，已经进行了很多年，虽然对于不同的阵型有不同的特定设计方法，如等间隔线列阵方向图设计的切比雪夫加权方法，但总体来讲，还没有可以适用于任意阵型的优化设计方法。其实我们换个角度来考虑，方向图的设计实际上就是一个最优化的问题，它就是要使得在目标方位上方向图的响应最大，可是目前还没有任何最优化的方法应用在方向图的设计上。如果把最优化方法应用在方向图设计上，那么不仅可以提供一种全新的思路来设计方向图，而且适用面非常广，可以根据不同的标准来调整方向图的设计，从而从根本上解决了方向图的设计问题。 在最优化方法的选择上，我选择了模拟退火算法。模拟退火算法（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ）首先由Ｋｉｒｋｐａｔｒｉｃｋ在１９８２年 收稿日期：２００６—０６—０６修回日期：２００６—０６—１６ －－－－——１７６－－－－——提出，Ｇｅｌａｔ和Ｖｅｃｃｈｉ（１９８３）紧随其后，这构成了传统的ｓＡ方法。之后ＳＡ方法经许多研究者的积极探索，又逐渐发展出快速ＳＡ方法和其他变形算法，如多结构ｓＡ方法Ｗａｎｇ（１９９４）。由于ｓＡ算法的有效性和稳健性表现在它并不依赖于初始值的选取，而且在某些情况下还可以给出明确上限计算时间，因此，其本身是一个全局优化算法，其应用领域已渗透到工程领域的各个方面。把模拟退火算法应用到线列阵的方向图设计上，根据不同的设计目标制定不同的标准，可以有效、快速的求得最优解，使方向图的设计变得轻松，简便。 ２模拟退火算法 退火是材料处理过程中的一种方法，即把材料加热到一定温度使其熔化，然后使其慢慢冷却达到结晶状态。在这个过程中，固体内部的自由能量达到最小。而所谓的模拟退火算法就是模拟该过程的优化算法。 模拟退火算法是基于ＭｏｎｔｅＣａｒｌｏ技术的，它以下列方 　万方数据万方数据

K-means-聚类算法研究综述

K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然

粒子群优化算法及其应用研究【精品文档】(完整版)

摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度

目录 摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22)

模拟退火算法算法的简介及程序

模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想: (1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起 点)，每个T值的迭代次数L (2) 对k=1，……，L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)

接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 算法对应动态演示图： 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则

基于聚类的图像分割方法综述

信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.wendangku.net/doc/5b12180203.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述 赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。 关键词：聚类算法；图像分割；分类 中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百 近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形 式为： 收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 —

启发式优化算法综述【精品文档】(完整版)

启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题

时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。

数据挖掘中的聚类算法综述

收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺　玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘　要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。 关键词:数据挖掘;聚类;聚类算法 中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1　引言 随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序 的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。 本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2　DM 中现有的聚类算法 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。 聚类 层次聚类算法 聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类 分割聚类算法基于密度的聚类基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类:概率聚类、最近邻 聚类、K 2medoids 、K 2means 基于约束的聚类算法 机器学习中的聚类算法 人工神经网络方法 基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法 子空间聚类 联合聚类 图1　聚类算法分类示意图 211　层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代 表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用 单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以

一种基于粒子群算法的聚类算法

第35卷第1期2009年3月延边大学学报(自然科学版) Journal of Yanbian University (Natural Science )Vol.35No.1Mar.2009 收稿日期:2008-10-18 作者简介:姜浩(1981— ),男,硕士研究生,研究方向为粒子群算法.文章编号:100424353(2009)0120064204 一种基于粒子群算法的聚类算法 姜浩,　崔荣一 (延边大学工学院计算机科学与技术系智能信息处理研究室,吉林延吉133002) 摘要:提出一种基于粒子群算法的聚类算法,该算法利用粒子群算法随机搜索解空间的能力找到最优解.首先,将样本所属类号的组合作为粒子,构成种群,同时引入极小化误差平方和来指导种群进化的方向.其次,通过对全局极值的调整,搜索到全局最优值.最后,通过仿真实验的对比,验证了该算法在有效性和稳定性上要好于K 2means 算法. 关键词:粒子群;聚类;极小化误差平方和中图分类号:TP301.6 文献标识码:A A Method of Clustering B ased on the P article Sw arm Optimization J IAN G Hao ,　CU I Rong 2yi (I ntelli gent I nf ormation Processing L ab.,De partment of Com puter Science and Technolog y , College of Engineering ,Yanbian Universit y ,Yanj i 133002,China ) Abstract :A clustering method based on the particle swarm optimization is provided ,using the ability of PSO algorithm which can search all of the solution space to find the optimum solution.Firstly ,the combination of the cluster number of the samples was taken as particles to consist a swarm.Meanwhile ,the evolution trend was used to modulate with the theory of the L MS error criterion.Secondly ,according to the modulating for global best ,the algorithm researched the global optimum.Finally ,the simulation results show that the new algorithm of proposed algorithm is more efficient and stable than K 2means algorithm.K ey w ords :particle swarm optimization ;clustering ;L MS error criterion 0　引言 聚类分析研究具有很长的历史,其重要性及 与其他研究方向的交叉特性得到人们的肯定[1].聚类是数据挖掘、模式识别等研究方向的重要研究内容之一,在识别数据的内在结构方面具有极其重要的作用.聚类技术广泛应用于语音识别、字符识别、图像分割、机器视觉、数据压缩和文献信息检索等领域.聚类的另一主要应用是数据挖据(多关系数据挖掘)、时空数据库应用(GIS 等)、序列和一类数据分析等.此外,聚类还应用于统计科学.值得一提的是,聚类分析对生物学、心理学、考 古学、地质学、地理学以及市场营销等研究也都有重要应用. 粒子群优化(Particle Swarm Optimization ,PSO )算法是由Eberhart 和Kennedy [2]于1995年提出的一类基于群智能的随机优化算法.该算法模拟鸟群飞行觅食的行为,通过个体之间的集体协作和竞争来实现全局搜索,是一种基于群智能的演化计算技术.同遗传算法相比,虽然同是基于迭代的进化算法,但没有交叉和变异算子,群体在解空间中根据自身经历的最好位置,以及群体最优解来进行搜索.由于PSO 算法有着参数少,