1、毕业设计 开题报告 计算机科学与技术 基于粒子群算法的图像聚类研究与实现 一、 选题的背景、意义 图像聚类是数据挖掘中一项重要技术，图像聚类的好坏将直接影响后续图像处理与分析任务的质量。图像聚类是指利用无监督的学习过程发现在图像中的隐藏的模式，它具有独立发现知识的能力。粒子群算法属于进化算法的一种，它与遗传算法相似，也是从随机解出发，通过迭代寻找最优解，但它比遗传算法的规则更为简单，即没有交叉和变异操作，它通过追随当前搜索到的最优值来寻找全局最优。粒子群算法由于实现容易、精度高、收敛快等优点在解决实际问题 中具有优越性。本课题主要研究的是基于粒子群算法的图像聚类方法，针对传统的基于 K均值的图
2、像聚类方法无法较好地对图像进行聚类，提出一种基于粒子群算法的图像聚类方法。该方法通过从随机解出发，迭代寻找全局最优解。提出的方法在图像数据集上进行仿真实验验证。 聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用。 随着计算机技术、网络技术和信息技术的迅速发展，一些规模巨大且结构复杂的数据在科学和工程应用领域不断出现。如何处理这些数据并从中得到有益的信息，越来越引起人们的普遍关 注。大规模复杂数据集的出现对聚类分析技术提出了特殊的挑战，它要求聚类算法有可伸缩性、处理不同类型数据、发现任意形状的簇、处理高维数据的能力等，并要求聚类结果对用户来说应该是
3、可判断的、能理解的和可用的 。面对这些问题与要求，传统的聚类分析方法已经显得无能为力。 为解决上述问题，研究者们开始尝试各种智能聚类方法。群智能算法中的粒子群优化算法 (PSO)逐渐引起人们的注意，并在聚类分析中取得了比传统方法更好的效果 。 PSO 算法主要是在群体的集群行为和自组织原则指导下的随机搜索和优化技术，它强调分布式、相对简单主体之 间直接或间接的交互作用，具有很强的适应性和鲁棒性。 PSO 算法潜在的并行性和分布式特点使其能够处理以数据库形式存在的大量数据；另一方面，聚类可以被看成一个复杂的全局优化问题，因此 PSO 算法可以用于聚类分析。 二、 研究的基本内容与拟解决的主要问题
4、 1、研究的基本内容 1.1 聚类算法 聚类分析是将具体或抽象的数据集划分为若干组或类的过程，聚类产生的每一组数据称为一个簇，簇中的每一数据称为一个对象。聚类的目的是使同一簇中对象的特性尽可能相似，不同簇对象间的特性差异尽可能地大。 设模式样本集为 X=X， i=1， 2， ， n，其中 为 d 维模式向量，聚类问题就是要找到一个划分 C=C。， C2， ， Cm，满足： 11 , 2 , m, 1 , 2 , m ; imiiiijXCCiC C i j j （ ， )（ ， )并且使得总的类间离散度和： 1 ( , )kmikk x CJc d X Z 达到最小，其中 Zk 为第 k 个聚
5、类的中心， d(Xi， Zk )为样本到对应聚类中心距离，聚类别准则函数 c 即为各类样本到对应聚类中心距离的总和。这里 d( ix ， kz )为欧氏空间的距离，即 d( ix ， kz )=| ix - kz |。 1.2 粒子群算法 粒子群优化算法 (panicle swarln optimization， PSO)是一种优化计算技术，是进化算法的一种，最早是由 Kennedy 与 Eberhan 于 1995 年提出的 。源于对鸟群捕食的行为研究的 PSO算法是一种基于迭代的优化工具，概论简单 、易于实现、参数较少、能有效解决复杂优化任务，目前已广泛应用于函数优化、神经网络训练、模糊系
6、统控制以及其它遗传算法的应用领域。 在 PSO 算法中，粒子群在一个 n 维空间中搜索，其中的每个粒子所处的位置都表示问题的一个解。粒子通过不断调整自己的位置 x 来搜索新解。每个粒子都能记住自己搜索到的 最好解，记做 ，以及整个粒子群经历过的最好的位置，即目前搜索到的最优解，记做 。每个粒子都有一个速度，记作 V： 12( ) * ( ) ( ) * ( )i d i d i d l d g d l dv v r a n d p x r a n d p x （ 1） 其中 Vld 表示第 i 个粒子在第 d 维上的速度，为惯性权 重， 1， 2 为调节 idp 和 gdp相对重要性的参数，
7、rand()为随机数生成函数。这样，可以得到粒子移动的下一位置： ( ) ( ) ( )i i ix d x d v d (2) 从 (1)和 (2)式可以看出，粒子的移动方向由三部分决定，自己原有的速度 idv 、与自己最佳经历的距离（ idp - idx ）和与群体最佳经历的距离（ gdp - idx ），并分别由权重系数， 1 和 2 决定其相对重要性。 PS0 的基本算法步骤描述如下： (1)初始化粒子群，即随机设定各粒子的初始位置 和初始速度 V； (2)计算每个粒子的适应度值； (3)对每个粒子，比较它的适应度值和它经历过的最好位置 idp 的适应度值，如果更好，更新 gdp ；
8、(4)对每个粒子，比较它的适应度值和群体所经历的最好位置 gdp 的适应度值，如果更好，更新 gdp ； (5)根据 (1)式和 (2)式调整粒子的速度和位置； (6)如果达到结束条件 (足够好的位置或最大迭代次数 )，则结束，否则转步骤 (2)。 2、拟解决的主要问题 2.1 比较并归纳传统的图像聚类方法的原理和特点 由 MacQueen 提出的 K 均值算法是解决聚类分析问题的一种经典算法，广泛应用于数据挖 掘和知识发现领域中。它是一种爬山式的搜索算法，以其简单、快速和有效而被广泛使用。但是，传统的 K 均值算法存在两个固有的缺点： (1)对于随机的初始值选取可能会导致不同的聚类结果，甚至
9、存在着无解的情况； (2)该算法是基于目标函数的算法，通常采用梯度法求解极值，由于梯度法的搜索方向是沿着能量减少的方向进行，使得算法很容易陷入局部极值。 针对 K 均值算法所存在的不足，本文提出了一种基于粒子群算法的图像聚类方法，该方法从随机解出发，迭代寻找全局最优解。该算法不仅有效的克服了传统的 K 均值算法存在的问题，而且有较快的收敛速度 。 2.2 熟悉 MATLAB 开发语言中相关工具箱的使用方法 MATLAB 是由美国 mathworks 公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强
10、大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如 C、 Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。 三、 研究的方法与技术路线、研究 难点，预期达到的目标 研究的方法与技术路线：针对传统基于 K 均值的图像聚类方法中存在的缺陷，提出一种基于粒子群算法的图像聚类方法。该方法通过引入基于群体的具有全局寻优能力的优化工具，通过追随当前搜索到的最优值来寻找全局最优解，不仅有效地克服了传统的 K 均值的聚类方法容易陷入局部极小值和对初始值敏感的问题，而且具有较
11、快的收敛速度。提出的方法应能够在采集的图像数据集上进行实验，以验证它的可行性和有效性。 研究难点：熟悉 MATLAB 开发语言中相关工具箱的使用方法；了解聚类算法的数学描述和粒子群算法的聚类描述；能解决 传统聚类算法的不足，提出一种基于粒子群算法的图像聚类方法。该方法通过从随机解出发，迭代寻找全局最优解。提出的方法在图像数据集上进行仿真实验验证。 预期达到的目标：研究的是基于粒子群算法的图像聚类方法，采用 MATLAB 开发工具进行仿真实验，并对几种不同的图像聚类方法进行了效果上的比较。 四、 论文详细工作进度和安排 第七学期第 10 周至第 18 周（ 2011 年 01 月 06 日前）：
12、文献检索和资料收集，完成毕业论文（设计）文献综述、开题报告和外文翻译。 第八学期 第 1 周 至第 3 周（ 2011 年 03 月 11 日前）：撰写论文提纲，完 成毕业论文（设计）初稿、需求分析和概要设计。 第八学期 第 4 周 至第 12 周（ 2011 年 05 月 13 日前）：详细设计、系统调试、和毕业论文（设计）完成定稿。 第八学期第 13 周（ 2011 年 05 月 20 日前）：完成应用软件系统的设计和毕业论文（设计）送指导老师和评阅老师评阅，准备答辩。 第八学期第 14 周：参加毕业论文（设计）答辩。 五、 主要参考文献： 1V. K.Panchal, Harish Ku
13、ndra, Jagdeep Kaur. Comparative Study of Particle Swarm Optimization based Unsupervised Clustering Techniques. IJEITJ. 2009, 1(1): 22-27. 2 Swarm Intelligence: Foundations, Perspectives and ApplicationsJ.http:/ 3 J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar Evaluation of Comprehensive Learn
14、ing Particle Swarm Optimization C. Proceedings of 11th International Conference on Neural InformationProcessing (ICONIP2004), 2004,3316:230-235. 4李峻金 ,向阳 ,等 . 粒子群聚类算法综述 J.计算机应用研究 .2009,26(12): 2224-2229. 5 邹刚 ,孙即 祥 ,敖永红 .粒子群模糊聚类方法在病理图像分类中的应用 J.计算机工程与技术 .2009,30(22):5155-5158. 6 刘靖明 ,韩丽川 ,侯立文 . 一种新的聚类算法 粒子群聚类算法 J.计算机工程与应用 .2005,41(20):183-185. 7高鹰 ,谢胜利 ,等 . 基于聚类的多子群粒子群优化算法 J.计算机应用研究 ,2006,4. 8 杨久俊 ,邓辉文，滕姿 . 基于混合粒子群优化算法的聚类分析 J.计算机工程与设计 ,2008,29(22):2821-2825. 9 魏伟 波 ,潘振宽 .数据挖掘中的聚类算法综述 J.计算机应用研究 ,2007,1. 10 李明华 ,刘全 . 数据挖掘中的聚类算法的新发展 J.计算机应用研究 ,2008,1:13-17.
