12.43 分类型数据聚类算法研究进展

在大数据环境下，许多数据是缺乏先验信息的，对数据标注的成本也越来越高，一个最自然的方法是对数据进行适当划分之后再进行相关的数据处理，而聚类分析是数据划分的一种重要技术手段[1] 。在许多实际应用中，分类型变量是一种非常重要的数据表现形式[2] 。比如，在问卷调查中，客户的兴趣爱好、家庭住址、教育情况都是分类型变量；在电子邮件过滤中，将邮件分为垃圾邮件和合法邮件；在医学中，一个病人受伤的程度可分为轻微的、中度的和严重的；在市场营销中，经常将客户分为高、中、低端客户。由于在现实世界中分类型数据的大量存在，分类型数据的聚类问题引起了广泛的关注。目前，分类型数据的聚类算法大致可分为三类[3] 。

(1) 基于相异测度的聚类：参照数值型数据聚类方法，定义出适合于分类型数据的相异测度，并设计出相应的分类型数据聚类算法，代表性算法有k-modes 算法[4-5]和 ROCK 算法[6]等聚类算法。

(2) 基于概率统计的聚类：针对分类型属性取值有限的特点，用概率统计方法对其进行描述，将类原型定义为概率分布的形式，且对象与类间的相似性也用概率来表示。代表性算法有 COBWEB [7] 、COBWEB/3 [8] 、ECOBWEB [9] 、COP-COBWEB [10]和基于 LTM 的多维聚类[11]等算法。

(3) 基于信息熵理论的聚类：利用信息熵来刻画类的有效性，认为一个类内属性值分布越均匀，则信息熵越大。代表性算法有 COOLCAT [12] 、LIMBO [13] 和 ACE [14-15] 等聚类算法。

由于分类型数据不能直接进行数值运算，相应的聚类模型及其算法设计与数值型数据有较大不同，主要体现在：

(1) 分类型变量缺乏几何特性：分类型变量通常含有一定的语义，没有几何特性，不能直接进行数值计算，也不便于可视化展示，分类型变量的特性更多是通过其频率的大小来体现变量值的分布。

(2) 数据驱动相似性计算：数值型数据相似性的计算大多数情况都假定对象在不同属性上是相互独立的，而分类型数据的相似性不仅要考虑到对象在同一属性上变量值的相似性，还要考虑其他属性上变量值对相似性的影响。

(3) 知识驱动相似性计算：不同相似性定义会产生不同的类结构，分类型变量相似性计算要尽可能考虑不同应用场景的语义知识，而数值型数据计算相似性时通常数据与语义是分离的。本文围绕分类型数据 k-mode 型算法的类中心表示和收敛性分析、分类型数据流聚类算法、分类型数据聚类有效性和混合型数据聚类算法四个方面综述了其相应的研究进展，并给出了未来研究方向的思考。