一种基于遗传算法的K-means聚类算法
170 浏览量
2020-10-19
18:22:03
上传
评论 6
收藏 230KB PDF 举报
一种基于遗传算法的一种基于遗传算法的K-means聚类算法聚类算法
传统K-means算法对初始聚类中心的选取和样本的输入顺序非常敏感，容易陷入局部最优。针对上述问题，提
出了一种基于遗传算法的K-means聚类算法GKA，将K-means算法的局部寻优能力与遗传算法的全局寻优能力
相结合，通过多次选择、交叉、变异的遗传操作，最终得到最优的聚类数和初始质心集，克服了传统K-means
算法的局部性和对初始聚类中心的敏感性。
摘摘 要：要： 传统
关键词：关键词： 遗传算法；K-means；聚类
聚类分析是一个无监督的学习过程，是指按照事物的某些属性将其聚集成类，使得簇间相似性尽量小，簇内相似性尽量
大，实现对数据的分类[1]。聚类分析是数据挖掘技术的重要组成部分，它既可以作为独立的数据挖掘工具来获取数据库中数
据的分布情况，也可以作为其他数据挖掘算法的预处理步骤。聚类分析已成为数据挖掘主要的研究领域，目前已被广泛应用于
模式识别、图像处理、数据分析和客户关系管理等领域中。K-means算法是聚类分析中一种基本的划分方法，因其算法简单、
理论可靠、收敛速度快、能有效处理较大数据而被广泛应用，但传统的K-means算法对初始聚类中心敏感，容易受初始选定的
聚类中心的影响而过早地收敛于局部最优解，因此亟需一种能克服上述缺点的全局优化算法。
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。在进化过程中进行的遗传操
作包括编码、选择、交叉、变异和适者生存选择。它以适应度函数为依据，通过对种群个体不断进行遗传操作实现种群个体一
代代地优化并逐渐逼近最优解。鉴于遗传算法的全局优化性，本文针对应用最为广泛的K-means方法的缺点，提出了一种基于
遗传算法的K-means聚类算法GKA(Genetic K-means Algorithm)，以克服传统K-means算法的局部性和对初始聚类中心的敏感
性。
用遗传算法求解聚类问题，首先要解决三个问题：
(1)如何将聚类问题的解编码到个体中；
(2)如何构造适应度函数来度量每个个体对聚类问题的适应程度，即如果某个个体的编码代表良好的聚类结果，则其适应度
就高；反之，其适应度就低。适应度函数类似于有机体进化过程中环境的作用，适应度高的个体在一代又一代的繁殖过程中产
生出较多的后代，而适应度低的个体则逐渐消亡；
(3)如何选择各个遗传操作以及如何确定各控制参数的取值。
解决了这些问题就可以利用遗传算法来求解聚类问题，这也显示了遗传算法与求解问题无关的特性。
1 K-means算法算法
K-means聚类算法的目标是把包含n个对象的数据集x分为k个簇，使簇内具有较高的相似度，而簇间相似度较低。算法首先
随机选择k个对象作为初始聚类中心，再计算剩余数据对象到各聚类中心的距离并将其赋给最近的簇，然后重新计算每个簇的
平均值，不断重复此过程，直到准则函数收敛。
准则函数定义如下：
资源评论
