一种增强的K-prototypes混合数据聚类算法

李顺勇， 顾嘉成

(山西大学 数学科学学院, 山西 太原 030006)

0 引言

聚类分析是数据挖掘过程中一个不可或缺的环节[1,2]，聚类的目标是将相似的对象归到同一类中，不相似的归到不同的类中[3].聚类方法多种多样，大致可以从基于层次、密度、划分、网格、模型几个方面进行分类，如图1所示.

文献[4]首次提出K-means算法，但由于该算法中的代价函数是面向数值型数据的，所以此算法应用到其他类型的数据上时存在一些不足.文献[5]中提出的方法结合了UKF思想，提升了估计收敛速度，但是在处理分类型数据时该算法效果并不显著.基于此，文献[6]提出了K-modes算法，该算法用modes代替means，采用简单匹配差异度来度量距离，在处理分类型数据时有较好的效果.文献[7]中提出的算法将聚类算法与Autoencoder算法结合，提高了推荐质量.文献[8]提出了K-prototypes算法，该方法引入了参数控制两种属性数据在计算距离时所占的权重从而实现对混合型数据的聚类.之后又有类似算法被提出，例如EKP[9]、DP-MD-FN[10]、FKP-MD[11]等算法.陈韡等[12]考虑到样本与类的差异，对相异度公式进行改进，得到了较好的实验结果.文献[13]将信息熵与混合数据加权算法结合，解决了聚类算法过度依赖数据集总体分布的不足.当然，虽然很多学者提出了一些不同的新算法，但是仍然没有彻底解决K-prototypes存在的一些局限性.

K-prototypes由于其算法较为简单并且容易实现，在得到广泛应用的同时也凸显出了一些不足之处，主要体现在以下三点：(1)该方法的聚类效果易受初始原型选择影响；……