文档介绍：总第期计算机与数字工程..
年第期
一种改进的遗传一均值聚类算法
王康颜雪松金建占志刚
中国地质大学计算机学院武汉
摘要文章提出一种基于改进遗传算法的一均值聚类算法。主要对算法遗传算子进行改进:交叉操作通过交换两
条染色体问的聚类中心进行重组,将一次一均值方法当作变异操作,并加入跨世代精英选择机制。通过实验证明:该算法
比传统的一均值算法具有较好的性能,同时比其他基于遗传算法的一均值算法具有更高的效率且更适用于规模较大的
数据集。
关键词遗传算法;一均值算法;聚类
中图分类号
—

,,
。. —
:—
,,.
—,
, .
,—,
】
聚类分析中的一种基本的划分方法。因其算法简
引言
单、理论可靠、收敛速度快、能有效处理较大数据而
聚类分析是一个无指导的学****过程,是指按照被广泛应用,但传统的一均值算法对初始聚类中
对象的某些属性将物理或抽象对象的集合分组成心敏感,因此需要一种能克服一均值缺点的全局
为由类似的对象组成的多个类或簇,使同簇中的对优化算法。
象间具有较高的相似度,而不同簇中的对象差别较遗传算法是演化算法的一个重要分支,它是模
大。聚类分析是数据挖掘技术中重要的组成部拟生物在自然环境中的遗传和演化过程而形成的
分,既可以作为独立的数据挖掘工具用来获得数据一种自适应全局优化搜索算法。在演化过程中进
库中的令人感兴趣的数据分布情况,也可以作为其行的遗传操作包括编码、选择、交叉重组、变异和适
他数据挖掘算法如特征和分类等的预处理。聚者生存选择。它以适应度函数为依据,通过对种群
类分析已成为数据挖掘主要的研究领域,目前已被个体不断进行遗传操作实现种群个体一代代地优
广泛应用于金融数据分类、空间数据处理、卫星图化并逐渐逼近最优解;借鉴遗传算法的全局优化
像分析和医学图像的自动检测中。一均值算法是性,本文提出了一种基于改进遗传算法的均值
收稿日期:年月日,修回日期:年月日
作者简介:王康,男,硕士研究生,研究方向:演化计算、数据挖掘。颜雪松,男,副教授,硕士生导师,研究方向:演化计
算、演化硬件。金建,男,硕士研究生,研究方向:演化计算。占志刚,男,硕士研究生,研究方向:智能计算。
年第期计算机与数字工程
聚类算法来克服传统一均值算法的局部性。值越小说明聚类结果越好即个体越优,适应度值越
大说明聚类结果越差即个体越劣。因此适应度函
一均值聚类算法的基本思想
数定义如下:
一均值聚类算法的目标是把包含个对象
一∑∑一面
的数据集一五∈,一,,⋯,,表示一∈
对象属性维数分为个簇,使簇内具有较高的其中为簇,的平均值。
相似度,而簇问相似度较低。算法先任意选择. 遗传操作
个对象作为初始的簇的平均值或中心,再计算每.. 选择操作
个对象与各个簇中心的距离并将其赋给最近的选择算子采用锦标赛选择法,本算法设定竞赛
簇,更新簇的平均值,不断重复此过程直到准则函规模为;即随机从种群中选择个个体,然后从
数收敛。个个体中选出适应度最小的个体作为父个体,重复
准则函数如下: 迭代以上步骤直到父个体的总数达到种群规模。
.. 交叉重组
一∑∑一面
,一∈