基于期望最大化的K-Means聚类算法

景 源，郝金山

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引言

在数据挖掘领域中，聚类技术是应用广泛且十分重要的技术.聚类分析已经应用在各种方面，比如其在机器学习，文本分类，图像处理，语音处理，模式识别等领域.

常见的聚类方法有模型方法，密度方法[1]，网格方法[2]，层次划分方法[3]和划分的方法.其中EM算法[4-10]属于模型方法.K-means算法[11-17]属于划分的方法.在这些方法中最著名的就是kmeans方法，kmeans方法具有简单，快速，有效等诸多优点，但它也有非常明显的不足.Kmeans算法过于依赖于初始聚类中心.

文献[8]中，提出一种基于稀疏约束非负矩阵分解的kmeans聚类方法，通过在在非负矩阵分解过程中对基矩阵列向量施加l1和l2范数稀疏约束，实现高维数据的低维表示，然后利用在低维数据聚类中性能良好的kmeans算法对稀疏降维后的数据进行聚类.该方法适合于高维数据，并有良好的性能.但缺点是需要消耗的时间较长.文献[9]中先根据类簇指标确定需要聚类的数k，之后采用基于密度的思想，首先将聚类样本分为核心点、边界点和孤立点，之后排除孤立点和边界点并取核心点的中心点作为k个聚类中心后再进行kmeans聚类.虽然算法比原始的kmeans算法准确率得到提高，但同样耗时较长，而且在已知k值的情况下，有可能出现k值对不上的情况.文献[10]通过定义的平均类间最大相似度指标值来确定最佳的k值，将所有数据点中密度较高的点作为备选聚类中心，将备选点中密度最大的两个……