K-means聚类算法的研究

聚类是数据挖掘领域中重要的技术之一，用于发现数据中未知的分类。聚类分析已经有了很长的研究历史，其重要性已经越来越受到人们的肯定。聚类算法是机器学习、数据挖掘和模式识别等研究方向的重要研究内容之一，在识别数据对象的内在关系方面，具有极其重要的作用。聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割，图像处理中，主要用于数据压缩、信息检索。聚类的另一个主要应用是数据挖掘、时空数据库应用、序列和异常数据分析等。此外，聚类还应用于统计科学，同时，在生物学、地质学、地理学以及市场营销等方面也有着重要的作用。 本文是对聚类算法K-means的研究。首先介绍了聚类技术的相关概念。其次重点对K-means算法进行了分析研究，K-means算法是一种基于划分的方法，该算法的优点是简单易行，时间复杂度为O(n)，并且适用于处理大规模数据。但是该算法存在以下缺点：需要给定初始的聚类个数K以及K个聚类中心，算法对初始聚类中心点的选择很敏感，容易陷入局部最优，并且一般只能发现球状簇。本文针对聚类个数K的确定、初始K个聚类中心的选定作了改进，给出了改进的算法MMDBK(Max-Min and Davies-Bouldin Index based K-means，简称MMDBK)。算法的出发点是确保发现聚类中心的同时使同一类内的相似度大，而不同类之间的相似度小。算法采用Davies-Bouldin Index聚类指标确定最佳聚类个数，改进的最大最小距离法选取新的聚类中心，以及聚类中心的近邻查找法来保证各个类之间的较小的相似度。文中最后使用KDD99数据集作为实验数据，对K-means算法以及MMDBK算法进行了仿真实验。结果显示改进后的MMDBK算法在入侵检测中是有效的。