K-均值聚类算法初始中心选取相关问题的研究

数据挖掘是指从数据库中发现隐含的、新颖的、对决策有潜在价值的知识和规则的过程,已经在许多领域得到了广泛的应用。聚类分析是数据挖掘领域最为重要的技术之一,至今已在理论和方法上取得了丰硕的研究成果。聚类已经被广泛的研究了许多年,主要集中在基于距离的聚类算法上,其中以K-均值聚类算法最为经典。 K-均值算法是一种典型的基于划分的方法,该算法的优点是思想简单易行,时间复杂性接近线性,对大规模数据的挖掘具有高效性和可伸缩性。但是该算法存在如下缺点:聚类个数K需要预先给定;算法对初值敏感;算法易陷入局部极小,并且一般只能发现球状簇。 本文主要深入研究和分析了聚类算法中的经典K-均值聚类算法,总结出其优点和不足。重点分析了K-均值聚类算法对初始值的依赖性,并用大量的实验验证了随机选取初始值对聚类结果的影响性。针对K-均值算法对初始中心值选取的依赖性,提出了两种新的初始中心值选取方法。 主要研究内容和工作成果如下: 1.基于Huffman树构造的思想,提出了一种新的选取K-均值聚类算法初始中心点方法,改善K-均值聚类算法随机选取初始中心点而导致的聚类结果不稳定,容易陷入局部最优而非全局最优的不良结果。 2.采用最大距离法来选取K-均值聚类算法初始中心点,使得选出的中心点能在一定程度上代表不同的簇,提高了划分初始数据集的效率,克服了K-均值聚类算法中随机选取的初始中心点很大可能过于邻近,多个初始中心被选择在同一簇中,而小簇中没有聚类种子的不好情况。另外引入特征加权的方法,区别不同特征对聚类的贡献不同,来提高聚类的有效性。