1、 中文 6027 字 出处： Murthy C A, Chowdhury N. In search of optimal clusters using genetic algorithmsJ. Pattern Recognition Letters, 1996, 17(8): 825-832. 本科毕业设计外文翻译 （ 2014 届） 论文题目 基于遗传算法的聚类分析研究 2 基于遗传算法的聚类分析研究 CA Murthy, N Chowdhury 摘要 ： 遗传算法（ GAs）通常被描述成能够在一个有限样本函数值 内寻找最优值的搜索过程。在本文中， GAs 用于尝试寻找关于聚类问题的目标函数
2、值的最优值。一些在模拟和实际数据集上的实验结果展示了这种方法的有效性。K-Means 算法是解决聚类问题的最常用算法之一，对实验结果 的分析也展示了本文所提出的算法也 能够改善 K-Means 算法 的输出结果。 一、 引言 聚类是观察数据内在结构的一种重要的手段。更具体地，聚类分析的目标（ Anderberg, 1973; Devijver and Kittler, 1982; Jain and Dubes, 1988; Tou and Gonzalez, 1974）是将模式特别是高维空间的向量分成簇的过程，使得同一簇内的的数据高度同质，不同 簇内的数据高度相异。我们假设给定的模式属于 n维
3、的欧几里德空间，那么相异度就可以用欧氏距离来度量。 我们假定模式集 M 是12 , ,., mx x x，其中ix是第 i个模式向量。聚类中心数是 k。如果聚类集合用12, ,., kC C C表示，那么需满足以下几个条件： 1P 1. , f o r i = 1 , . . . , k .P 2 . C f o r i j , a n dP 3 . iijkiiCCCM 聚类方法大体上可分为两种：层次聚类和非层次聚类（ Anderberg, 1973）K-means 算法是众多非层次方法中应用最为广泛的算法，其主要在给定的目标函数上寻优。 它力求寻找到模式和其聚类中心欧 氏距离之和的最小值，
4、但是这种算法容易收敛到局部最优解（ Selim and Ismail, 1984）。 复杂问题的全局最优解已被证明不能在一个可行计算时间内找到（ Spath, 1980）。这就使得一些解决内在优化问题的近似方法得以发展。许多这类技术能够找到局部最优解，却不一定能够达到全局最优解（ Selim and Ismail, 1984）。在本文中，我们 尝试 使用遗传算法（ GAs） 寻找聚类问题的最优解。实验结果将在 3 一些模拟和实际的数据上呈现。 第二部分是问题描述，第三部分是我们所提的遗传算法的细节，第三部分 是实验结果与分析。 二、 问题描述 已有一些方法度量如何将给定数聚集进行聚类。 一种用
5、于聚类的原则是尽量减少来自各个聚类集合的数据点的欧氏距离平方之和。数学描述如下： 12212 1121 . , , . . . ,2 . ( ) / # 1 , 2 , . . . , , #3 . ( , , . . . , )4 . 1 2 3 ( , , . . . , )jjkjjxCj j jkk j x CkC C C M kz x C f o r j kx C C Cf C C C x zP P P f C C C是 的 个 数 据 集 合其 中是 中 的 一 个 模 式 向 量 ， 是 中 数 据 点 的 数 目目 标 函 数 是 。 在 满 足 第 一 部 分 ， ， 的 条
6、 件 下 最 小 化目标函数 f 是非凸的，因此聚类问题可能找到局部最小值而 不是全局最小解（ Selim and Ismail, 1984）。 事实上，为了找到最优解12, ,., kC C C， M 中所有可能的聚类中心都被考虑。因此，考虑到计算机的内存和速度，在允许的时间内找到问题的精确解只有在理论上存在可能 。如果通过枚举 的方式 求解，那么有( , )S mk 中可能 （ Anderberg, 1973; Spath, 1980） ，其中 11( , ) ( 1 )!k k j mjkS m k jjk 这明显地显示了 在有限的计算时间内采用 枚举法 解决现实生活中绝大多数的聚类问题是不可能的。例如，本文所使用的原油数据（ Johnson and Wichern, 1982） ,精确解要求 考虑 (56,3)S 种划分（ 18(56, 3) 10S ）。 因此，启发式的估算方法是在寻找一种折中或者在
