1、K K 均值聚类（均值聚类（k k- -meansmeans）优化）优化 基于遗传算法基于遗传算法 一、一、 K K 均值聚类的算法和遗传算法的均值聚类的算法和遗传算法的概述概述 1、K 均值聚类（k-means）就是将对物理或抽象对象的集合分组成为由类似的对象组 成的多个簇的过程。 聚类分析是指事先不知样本的类别， 而利用样本的先验知识来构造分类 器 （无监督学习） ， 可以用两个准则来做(1)聚类准则函数， (2)误差平方和准则 （最常用的） 。 2、 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜 索算法。生物的进化过程主要是通过染色体之间的交叉和变异来完成的
2、，与此相对应，遗传 算法中最优解的搜索过程也模仿了生物的进化过程， 使用遗传操作数作用于群体进行遗传操 作，从而得到新一代群体，其本质是一种求解问题的高效并行全局搜索算法。它能在搜索过 程中自动获取和积累有关搜索空间的知识， 并自适应地控制搜索过程， 从而得到最优解或准 最优解。 算法以适应度函数为依据， 通过对群体个体施加遗传操作实现群体内个体结构重组 的迭代处理。在这一过程中，群体个体一代代地优化并逐渐逼近最优解。鉴于遗传算法的全 局优化性，本文给出了一种基于遗传算法的 K 均值聚类算法来克服 K 均值算法的局部性。 二、二、K K 均值算法的基本思想均值算法的基本思想 K 均值算法是一种
3、使用最广泛的聚类算法。算法以 K 为参数，把 n 个对象分为 K 个簇， 使簇内具有较高的相似度，而簇间相似度较低。算法首先随机选择 K 个对象，每个对象初始 地代表了一个簇的平均值或中心， 对剩余的每个对象根据其与各个簇中心的距离， 将它赋给 最近的簇，然后重新计算每个簇的平均值，不断重复该过程，直到准则函数收敛。准则函数 如下： 其中，ix 为簇 C 的平均值。i K 均值算法的描述如下： (1)任意选择 K 个记录作为初始的聚类中心。 (2)计算每个记录与 K 个聚类中心的距离，并将距离最近的聚类作为该点所属的类。 (3)计算每个聚集的质心(聚集点的均值)以及每个对象与这些中心对象的距离
4、，并根据最小 距离重新对相应的对象进行划分。重复该步骤，直到式(1)不再明显地发生变化。 三、基于遗传算法的三、基于遗传算法的 K K 均值聚类算法均值聚类算法 本文将遗传算法应用到聚类分析中， 把遗传算法的全局优化能力与聚类分析的局部优化 能力相结合来克服聚类算法的局部性，在种群进化过程中，引入 K 均值操作，同时，为了避 免早熟现象， 在种群中采用自适应方法动态调节交叉概率和变异概率， 使其能够随适应度自 动改变。算法具体步骤如下。 1 1 染色体编码染色体编码 染色体编码有很多种， 在聚类分析中较常用的是基于聚类中心的浮点数编码和基于聚类 划分的整数编码。由于聚类算法具有多维性、数量大等特点，聚类问题的样本数目一般远大 于其聚类数目，因此采用基于聚类中心的浮点数编码，将各个类别的中心编码为染色体。例 如对于一个类别为 3 的聚类问题， 假设数据集为 2 维。 初始的 3 个聚类中心点为(1, 2), (5, 4), (8, 7)，则染色体编码为(1, 2, 5, 4, 8, 7)。这种基于聚类中心的编码方式缩短了染 色体的长度，提高了遗传算法的速度，对于
