贾子琪，宋 玲

(1.南阳理工学院 计算机与软件学院，河南 南阳 473004；2.广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引 言

经典k-means算法[1]在计算簇的均值以及数据对象之间的相异度时使用的是欧式距离，仅适用于连续特征的数值型数据集，对于离散特征的分类型数据集，k-means算法不再适用。Huang对k-means算法[1]进行扩展，使用“modes”代替“means”，提出适用于分类型数据聚类的k-modes算法[2]。k-modes算法采用简单汉明距离计算相异度，忽略了数据对象间同一分类特征的差异性，弱化了簇内相似性，没有充分反映同一分类特征下两个特征值之间的相异度；采用随机选择的方法确定初始簇中心和k值，采用基于频率的方法重新计算和更新簇中心，给聚类结果带来很大的不确定性。

1 相关工作

Ahmad等[3]通过共现分析来反映同一特征下特征值之间的距离，如果特征值之间的共现程度高，则将该特征作为新的簇中心。该方法反映了特征之间的潜在关系，改善了同一特征下特征值相异度系数的计算，但忽略了数据对象本身的异同。Hus等[4]提出了一种基于概念层次的相异度系数。该方法过于依赖用户的经验以及对待聚类数据集专业知识的了解，不利于一般用户的使用，聚类范围有局限性。Ng等[5]扩展了简单汉明距离，考虑当前聚类中modes的影响，基于特征值在簇内出现的频率提出了新的相异度系数。该方法最小化了目标函数，提高了聚类精度，但其相异度系数的计算仍然存在问题。IDMKCA算法只反映了相同特征之间的内在关系，没有考虑不同特征值之间的相似性。……