随着信息技术的发展,数据归属变得复杂、难以被完全统计,非预分类数据快速增长。对于非预分类数据的挖掘,聚类成为优良解法。作为硬聚类算法的典型代表,K-means在处理速度和伸缩性上具有明显优势和不可替代的地位,但其对于非值属性不具备有处理能力。同时由于均值只能处理数值型数据,大多范畴属性聚类的研究工作集中在k-modes或K-prototype的基础上,少有工作对数据进行整体考虑。因而K-modes和K-prototype存在的属性“消融”缺陷一直存在。本文提出了一种新的距离计算方法和计数表结构,并介绍了由k-means发展而来的、在范畴属性聚类中获得了良好、稳定的聚类结果的范畴属性聚类方法。本文提出的EFficient EK-means与k-modes的时间复杂度为同一量级。1.提出了一种聚类算法中的范畴属性的处理方法EK-means。通过选取随机中心并使用海鸣威距离完成初始聚类,获得初始簇。之后延展均值距离的数学含义,将其使用到范畴属性中,得到范畴属性均值距离的计算方式,使簇可以被作为整体考虑。将K-means的可处理数据类型扩展到范畴属性数据,并对非对称数据具有处理意义。本文在来自UCI的蘑菇集上对范畴属性均值距离的可用性、准确性和时间复杂度方面进行了实验,结果表明范畴属性均值距离可以用于范畴属性的聚类。同时,相比较于K-modes,EK-means可获得平均10.7%的准确度提升以及超两倍的稳定性。2.提出了一种基于范畴属性均值距离的高效聚类方法Efficient EK-means。由于EK-means具有较高的时间复杂度,因此在EK-means的基础上引入数据表结构——计数表,对每个簇和簇内对象的值域进行统计,并通过迭代减少遍历数据集的次数,达到降低时间的复杂度的目的。本文在来自UCI的蘑菇集,国会投票数据集,汽车评估集和平衡秤四个范畴属性数据集上进行了对比实验,结果显示,对比EK-means,Efficient EK-means的时间复杂度下降了 n,时间复杂度为O(n);对比k-modes,Efficient EK-means在时间复杂度参数数量不变的前提下,最多可以提升16%的准确度,同时具有更稳定的聚类结果。