1、 本科 毕业 设计 (论文 ) （二零 届） 基于粒子群算法的图像聚类研究及实现 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 - 2 - 摘要： 图像聚类是数据挖掘中一项重要技术，其好坏将直接影响后续图像处理与分析任务的质量。图像聚类是指借助于无监督的学习过程去 发现图像中的隐藏模式，它具有独立发现知识的能力。粒子群算法（ Particle Swarm Optimization， PSO） 属于进化算法的一种，它与遗传算法相似，也是从随机解出发，通过迭代寻找最优解。然而，粒子群算法比遗传算法的规则更为简单，即没有交叉和变异操作，可以通过追随当前搜索到
2、的最优值来寻找全局最优。鉴于粒子群算法具有实现容易、精度高、收敛快等优点，经常被用来解决实际应用中的优化问题。本文提出了一种基于粒子群算法的图像聚类方法，有效弥补了基于K-MEANS 的图像聚类方法无法对图像进行有效聚类的缺陷。 本文中提出的方法在图像数据集上进行了仿真实验验证。 关键字： 图像聚类；粒子群算法（ PS0）；优化问题；迭代处理 - 3 - Research and Implementation of Image Clustering Based on Particle Swarm Optimization Abstract: Image clustering is an imp
3、ortant technique in data mining, and it will affect the qualities of the subsequent image processing and analysis tasks. Image clustering is also an unsupervised learning process for finding the hidden model in an image, having an independent ability of discovering knowledge. PSO is a kind of evolut
4、ionary algorithm, similar to genetic algorithm, which is based on a random solution and finds an optimal solution through iterations. However, its rule is simpler than genetic algorithm, the former has neither crossover nor mutation operations, but it finds a global optimum by following the optimal
5、value during the current search. PSO is often applied in solving practical problems, since it has the advantages of easy to implement, high accuracy and fast convergence. In this paper, we present an image clustering method based on PSO, which solves the problems of traditional K-MEANS-based method
6、that failure in image clustering. The proposed method was conducted on an image set for validating its performance. Key words: image clustering; Particle Swarm Optimization (PSO); optimization problem; iteration peocessing - 4 - 目录 1 引言 . 1 1.1 课题背景、意义 . 1 1.2 研究的基本内容及解决的问题 . 2 1.2.1 研究的基本内容 . 2 1.2
7、.2 解决的问题 . 2 2 聚类的相关研究 . 3 2.1 聚类简介 . 3 2.2 对聚类的典型要求 . 3 2.2.1 可伸缩性 . 3 2.2.2 处理不同类型属性的能力 . 3 2.2.3 发现任意形状的聚类 . 3 2.2.4 高维度 . 4 2.2.5 可解释性和通用性 . 4 2.3 典型的聚类算法 . 4 2.3.1 K-MEANS算法 . 4 2.3.2 K-MEDOIDS算法 . 4 2.3.3 Clara算法 . 5 2.3.4 Clarans算法 . 5 2.4 聚类的用途 . 5 3 粒子群算法 . 7 3.1 粒子群算法简介 . 7 3.2 基本的粒子群算法 .
8、7 3.2.1 粒子群算法原理 . 7 3.2.2 算法介绍 . 7 3.2.3 粒子群算法的参数设置 . 8 4 基于粒子群算法的聚类算法 . 10 4.1 传统的聚类算法 . 10 4.1.1 K-MEANS算法简介 . 10 4.1.2 K-MEANS算法流程 . 10 4.1.3 K-MEANS算法的缺点 . 11 4.2 粒子群聚类算法 . 11 4.2.1 算法流程 . 11 4.3 实验部分 . 14 4.3.1 MATLAB简介 . 14 4.3.2 使用的公式 . 14 4.3.3 实验原理 . 15 4.3.4 算法实现 . 15 4.3.5 算法结果 . 18 4.3.6
9、 算法结论 . 19 5 结论 . 20 5.1 总结 . 20 6 致谢 .错误 !未定义书签。 1 1 引言 1.1 课题背景、意义 图像聚类是数据挖掘中一项重要技术，图像聚类的好坏将直接影响后续图像处理与分析任务的质量。图像聚类是指利用无监督的学习过程发现在图像中的隐藏的模式，它具有独立发现知识的能力。粒子群算法属于进化算法的一种，它与遗传算法相似，也是从随机解出发，通过迭代寻找最优解，但它比遗传算法的规则更为简单，即没有交叉和变异操作，它通过追随当前搜索到的最优值来寻找全局最优。粒子群算法由于实现容易、精度高、收敛快等优点在解决实际问题中具有优越性。本课题主要研究的是基于粒子群算法的图
10、像聚类方法，针对传统 的基于K-MEANS 的图像聚类方法无法较好地对图像进行聚类，提出一种基于粒子群算法的图像聚类方法。该方法通过从随机解出发，迭代寻找全局最优解。提出的方法在图像数据集上进行仿真实验验证。 聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用。 随着计算机技术、网络技术和信息技术的迅速发展，一些规模巨大且结构复杂的数据在科学和工程应用领域不断出现。如何处理这些数据并从中得到有益的信息，越来越引起人们的普遍关注。大规模复杂数据集的出现对聚类分析技术提出了特殊的挑战，它要 求聚类算法有可伸缩性、处理不同类型数据、发现任意形状的簇、处理
11、高维数据的能力等，并要求聚类结果对用户来说应该是可判断的、能理解的和可用的。面对这些问题与要求，传统的聚类分析方法已经显得无能为力。 4 为解决上述问题，研究者们开始尝试各种智能聚类方法。群智能算法中的粒子群优化算法(PSO)逐渐引起人们的注意，并在聚类分析中取得了比传统方法更好的效果 。 PSO 算法主要是在群体的集群行为和自组织原则指导下的随机搜索和优化技术，它强调分布式、相对简单主体之间直接或间接的交互作用，具有很强的适应性。 4PSO 算法 潜在的并行性和分布式特点使其能够处理以数据库形式存在的大量数据；另一方面，聚类可以被看成一个复杂的全局优化问题，因此 PSO 算法可以用于聚类分析
12、。 3 2 1.2 研究的基本内容及解决的问题 1.2.1 研究的基本内容 1. 聚类算法 聚类分析是将具体或抽象的数据集划分为若干组或类的过程，聚类产生的每一组数据称为一个簇，簇中的每一数据称为一个对象。聚类的目的是使同一簇中对象的特性尽可能相似，不同簇对象间的特性差异尽可能地大。 2. 粒子群算法 粒子群优化算法 (panicle swarln optimization， PSO)是一种优化计算技术 ，是进化算法的一种，最早是由 Kennedy 与 Eberhan 于 1995 年提出的 。源于对鸟群捕食的行为研究的 PSO 算法是一种基于迭代的优化工具，概论简单、易于实现、参数较少、能有
13、效解决复杂优化任务，目前已广泛应用于函数优化、神经网络训练、模糊系统控制以及其它遗传算法的应用领域。 8 1.2.2 解决的问题 1. 比较并归纳传统的图像聚类方法的原理和特点 由 MacQueen 提出的 K 均值算法是解决聚类分析问题的一种经典算法，广泛应用于数据挖掘和知识发现领域中。它是一种爬山式的搜索算法，以其简单、快速和有效而被广泛使用。但是，传统 的 K-MEANS 算法存在两个固有的缺点： (1)对于随机的初始值选取可能会导致不同的聚类结果，甚至存在着无解的情况； (2)该算法是基于目标函数的算法，通常采用梯度法求解极值，由于梯度法的搜索方向是沿着能量减少的方向进行，使得算法很容
14、易陷入局部极值。6 2. 提出一种基于粒子群算法的新的聚类方法 针对 K-MEANS 算法所存在的不足，本文提出了一种基于粒子群算法的图像聚类方法，该方法从随机解出发，迭代寻找全局最优解。该算法不仅有效的克服了传统的 K-MEANS 算法存在的问题，而且有较快的收敛速度。 3 2 聚类的相关研 究 2.1 聚类简介 俗话说： “ 物以类聚，人以群分 ” ，在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用
15、 数学工具 进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。聚类分析内容非常丰富，有 系统聚类 法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。 12 2.2 对聚类的典型要求 2.2.1 可伸缩性 许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。 2.
16、2.2 处理不同类型属性的能力 许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型 (binary)，分类 /标称类型（ categorical/nominal），序数型（ ordinal）数据，或者这些数据类型的混合。 2.2.3 发现任意形状的聚类 许多聚类算法 基于 欧几里得 或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意4 形状簇的算法是很重要的。 2.2.4 高维度 一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三
17、维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的，特别是 考虑到这样的数据可能分布非常稀疏，而且高度偏斜。 2.2.5 可解释性和通用性 用户希望聚类结果是可解释的，可理解的，和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。 2.3 典型的聚类算法 2.3.1 K-MEANS 算法 K-MEANS 算法接受输入量 k ；然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所
18、获得一个 中心对象 （引力中心）来进行计算的。 K-MEANS 算法的工作过程说明如下：首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值） ； 不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数 . k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 2.3.2 K-MEDOIDS 算法 K-MEANS 有其缺点：产生类的大小相差不会很大，对于脏数据很敏 感
19、。 改进的算法：kmedoids 方法。这儿选取一个对象叫做 mediod 来代替上面的中心的作用，这样的一个5 medoid 就标识了这个类。步骤： 1，任意选取 K 个对象作为 medoids（ O1,O2,OiOk ）。 以下是循环的： 2，将余下的对象分到各个类中去（根据与 medoid 最相近的原则）； 3，对于每个类（ Oi）中，顺序选取一个 Or，计算用 Or 代替 Oi 后的消耗 E（ Or）。选择 E 最小的那个 Or 来代替 Oi。这样 K 个 medoids 就改变了，下面就再转到 2。 4，这样循环直到 K 个 medoids 固定下来。 这种算法对于脏数据和异常数据不
20、敏感，但计算量显然要比 K-MEANS 要大，一般只适合小数据量。 2.3.3 Clara 算法 上面提到 K-medoids 算法不适合于大数据量的计算。现在介绍 Clara 算法，这是一种基于采用的方法，它能够处理大量的数据。 Clara 算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用 K-medoids 算法得到最佳的 medoids。 Clara 算法从实际数据中抽取多个采样，在每个采样上都用 K-medoids 算法得到相应的（ O1,O2Oi Ok ），然后在这当中选取 E 最小的一个作为最终的结果 2.3.4 Clarans 算法 Clara 算法的效
21、率取决于采样的大小，一般不太可能得到最佳的结果。 在 Clara 算法的基础上，又提出了 Clarans 的算法，与 Clara 算法不同的是：在 Clara 算法寻找最佳的 medoids 的过程中，采样都是不变的。而 Clarans 算法在每一次循环的过程中所采用的采样都是不一样的。与上面所讲的寻找最佳 medoids 的过程不同的是，必须人为地来限定循环的次数 2.4 聚类的用途 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从消费者 数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一6 个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。聚类分析的算法可以分为划分法（ Partitioning Methods）、层次法（ Hierarchical Methods）、基于密度的方法（ density-based methods）、基于网格的方法（ grid-based methods）、基于模型的方法（ Model-Based Methods）。
