k均值课程设计---K均值聚类（k-means）优化

1、 模式识别课程设计报告 姓 名： 陈继智 学 号： 20091002205 班级序号： 191094 01 指导老师： 蒋良孝 时 间： 2012 年 4 月 K 均值 聚类 （ k-means）优化 基于遗传算法 一、 K 均值 聚类的算法 和遗传算法的 概述 1、 K 均值 聚类 （ k-means） 就是将对物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。 聚类分析是指事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习） ，可以用两个准则来做 (1)聚类准则函数 ， (2)误差平方和准则（最常用的） 。 2、 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成

2、的一种自适应全局优化搜索算法。生物的进化过程主要是通过染色体之间的交叉和变异来完成的，与此相对应 ，遗传算法中最优解的搜索过程也模仿了生物的进化过程，使用遗传操作数作用于群体进行遗传操作，从而得到新一代群体，其本质是一种求解问题的高效并行全局搜索算法。它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程，从而得到最优解或准最优解。算法以适应度函数为依据，通过对群体个体施加遗传操作实现群体内个体结构重组的迭代处理。在这一过程中，群体个体一代代地优化并逐渐逼近最优解。鉴于遗传算法的全局优化性，本文给出了一种基于遗传算法的 K 均值聚类算法来克服 K 均值算法的局部性。 二、 K

3、 均值算法的基本思想 K 均值算法是一种使用最广泛的聚类算法。算法以 K 为参数，把 n 个对象分为 K 个簇，使簇内具有较高的相似度，而簇间相似度较低。算法首先随机选择 K 个对象，每个对象初始地代表了一个簇的平均值或中心，对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇的平均值，不断重复该过程，直到准则函数收敛。准则函数如下： 其中， ix 为簇 C 的平均值。 i K 均值算法的描述如下： (1)任意选择 K 个记录作为初始的聚类中心。 (2)计算每个记录与 K 个聚类中心的距离，并将距离最近的聚类作为该点所属的类 。 (3)计算每个聚集的质心 (聚集点的均值 )以及每个对象与这些中心对象的距离，并根据最小距离重新对相应的对象进行划分。重复该步骤，直到式 (1)不再明显地发生变化。 三、 基于遗传算法的 K 均值聚类算法 本文将遗传算法应用到聚类分析中，把遗传算法的全局优化能力与聚类分析的局部优化能力相结合来克服聚类算法的局部性，在种群进化过程中，引入 K 均值操作，同时，为了避