12.47 分类型数据聚类有效性

聚类结果的有效性评价是聚类分析中的一个重要组成部分。不同聚类算法或同一算法不同参数设置往往在聚类同一数据时会产生不同的结果。因此，人们需要聚类有效性函数去评价聚类结果，并从众多聚类结果中寻找最适合于数据的一种划分。对于分类型数据而言，k-modes 优化目标函数[31] 、分类效用函数[32]和信息熵函数[12]是三个广泛使用的有效性评价函数。k-modes 优化目标函数是由 Huang在 1997 年提出，该目标函数是对 k-means 优化目标函数的扩展。通过使用“mode”代替“mean”，用简单匹配相异测度代替欧式距离。该目标函数能够最小化类内对象与类中心的距离和。基于目标函数，Huang 提出了 k-modes 聚类算法通过迭代优化方法求得该目标函数的局部最优解。此外，若干个改进 k-modes 聚类算法也被提出[33] 。分类效用函数是 Gluck 和 Corter 提出的[33] ，该函数试图最大化同类对象拥有相同特征和异类对象拥有不同特征的概率。COBWEB 增量算法[7]就是一种典型的以分类效用函数为目标函数的聚类算法，该算法试图通过最大化分类效用函数得到一个最优的聚类结果。

Mirkin [34] 采用分类效用函数去处理混合数据的聚类。信息熵函数是将信息理论应用到聚类评价中，用信息熵去度量类内属性值分布的差异性。以信息熵为聚类目标函数的聚类算法有 COOLCAT 算法[12]和 ACE 算法[14]等。这些算法试图通过最小化信息熵函数来获得一个最优的聚类结果。以上三种不同优化目标函数都从不同角度对聚类结果进行评价。如果将这三个评价函数去评价同一个聚类结果时，需要解决下面 3 个问题：① 三个目标函数有怎样的共性和差异性？② 类间信息是否被忽略？③ 以三个目标函数其中之一为聚类准则，如何确定该准则在一个给定数据集上的取值范围？针对上述问题 , Bai et al [35] 从解空间（优化）角度，构建了一个广义的有效性函数及其优化模型，理论分析发现在评价聚类结果时，分类效用函数等效于信息熵函数，k-modes 目标函数的最优解是分类效用函数的近似解，最小化广义有效性函数等于最大化某一类间分离函数。这表明使用这些类内信息评价聚类结果时，并不会忽略类间信息。对于一个给定的数据集，通过放宽某些变量的约束条件，将这些有效性函数最大化和最小化优化问题转化为凸规划问题，获得其上下界，进而实现函数的归一化。该研究成果为解决分类型数据聚类准则的选择，以及聚类算法的互学习对聚类有效性的影响等问题提供了理论基础。