基于遗传算法的k-means聚类方法的研究

近年来数据挖掘引起了信息产业界的广泛关注，其主要原因是存在大量的可用数据，并且迫切需要将这些数据转换成有用的信息和知识。通过数据挖掘，可以将知识发现的研究成果应用于实际数据处理中，为科学决策提供支持。聚类分析是数据挖掘的一项基本任务，是一个无监督的学习过程，聚类的目标是在没有任何先验知识的前提下，将数据聚集成不同的类，使得相同类中的对象尽可能相似，不同类中的对象差别尽可能大。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。 在聚类分析中，k-means算法可以说是应用较为广泛的一种算法，但它的一个致命弱点是对初始值非常敏感而且容易陷入局部极小值，而遗传算法是一种通过模拟自然进化过程搜索最优解的方法，其显著特点是隐含并行性和对全局信息的有效利用能力，因此产生了基于遗传算法的k-means聚类方法(GKA)，它既能发挥遗传算法的全局寻优能力，又能兼顾k-means算法的局部搜索能力，从而更好地解决聚类问题，但其收敛速度与k-means算法相比就比较慢。本文以进一步提高算法收敛速度为目的，提出了一种改进的遗传k-means遗传算法。该算法是以GKA算法为基础，在允许个体包含空类的前提下对算法的各项操作作出改进；同时添加了增量式操作，对类中心和目标函数可以增量式计算，使算法的收敛速度得到了提高。本文还设计了一个聚类分析系统，利用该系统，经过实验验证基于遗传算法的k-means聚类方法的收敛效果要优于k-means算法；改进的GKA算法要比原GKA算法的收敛速度快，特别是当输入的变异概率比较小的时候，这种优势更明显。另外本文还提出将改进的GKA算法用于Web日志挖掘的用户聚类系统中。利用该算法对Web用户进行聚类可以避免初始值对聚类结果的影响，并且能搜索到全局最优解，更好的为用户提供个性化服务以及对Web站点进行改进优化。