信息技术与互联网的飞速发展，数据库应用规模、范围和深度的不断扩大，人们生产和收集数据的能力的不断提高，导致现实生活中各个领域的数据量以前所未有的速度海量增长着。面对如此庞杂的海量数据，如何找出这些大规模数据之间的内在关联性，从而提取出有用的信息，以建立供人们所用的知识资源，一直是研究者们的热点课题。　　 数据挖掘是指从大量数据中发现隐藏的、有效的、新颖的、对决策有潜在价值的和最终可被理解的模式的过程，其在现实生活的许多领域都有着广泛的应用。聚类分析是数据挖掘三大领域之一，业已被广泛研究了几十年，至今不论在理论还是方法上都取得了丰硕的研究成果。其中以基于划分方法中的K-means聚类算法最为经典。　　 K-means聚类算法的思想简单易行，而且时间复杂性接近线性，同时对大规模数据的挖掘具有高效性和可伸缩性。然而该算法存在着固有的缺陷：如算法对初始中心点敏感；聚类结果易陷入局部最优；算法适用于数值型数据和一般只能发现球状簇等。　　 本文主要研究和分析了经典的K-means聚类算法，给出其优缺点和现有的一些改进方法。针对上述谈到的K-means聚类算法的不足，在聚类算法被研究的这几十年，许多学者都给出了相应的改进方法和策略，尤其针对前两种缺陷的改进算法举不胜举。而本文也意在探讨K-means算法的初始中心敏感性，并结合了半监督学习、Leader方法和佳点集理论，提出两种新的初始中心选取方法。　　 论文所做的主要工作包括：　　 1、基于半监督和Leader方法，提出了一种新的选取K-means聚类算法初始中心的方法，即S_SLK算法。利用监督信息来改善无监督学习的性能，结合能够保持数据对象本身分布特性的Leader方法优化了K-means聚类算法的初始中心，并改善了由此导致的聚类结果不够稳定的缺陷。　　 2、运用佳点集理论能够得到比随机选取更好的点的优点，再次结合Leader方法，提出一种新的改进K-means的聚类算法。佳点集理论和Leader方法的结合方式从两种算法来体现，分别称为KLG和KGL算法。　　 3、将改进的KLG和KGL算法分别与传统算法和文献中的算法做了相应的比较，并尝试了在K-means算法中仅引入佳点集理论或Leader方法后的效果，同时与KLG和KGL算法做了比较，实验结果和一系列的比较结果表明，改进后的算法具有一定的可行性和有效性，且最终可得出KGL算法优于其他几种算法。