Page 177 - 《软件学报》2020年第11期

徐鲲鹏 等:类属型数据核子空间聚类算法 3493

for categorical data is proposed, the algorithm considers the relationship between the attributes and each attribute assigned with weights
measuring its degree of relevance to the clusters, enabling automatic feature selection during the clustering process. A cluster validity
index is also defined to evaluate the categorical clusters. Experimental results carried out on some synthetic datasets and real-world
datasets demonstrate that the proposed method effectively excavates the nonlinear relationship among attributes and improves the
performance and efficiency of clustering.
Key words: clustering; categorical data; kernel method; nonlinear measure; subspace

聚类分析作为数据挖掘研究中的一种重要手段,目的是从给定数据集中寻找数据之间的相似性,并以此划
分多个子集(每个子集为一个簇),使得不同簇中的数据尽可能相异,而同一簇中的数据尽可能相似,即“物以类
[1]
聚” .目前,聚类分析已经在许多领域获得广泛应用,包括模式识别、文本挖掘、机器学习、图像处理和基因表
达等.
[2]
在聚类分析中,子空间聚类因其能够从数据集的不同子空间中发现相应的簇 而得到广泛研究.现有子空
间聚类方法依据提取子空间方法的不同大致可以分为两类.
[3]
[4]
• 以谱聚类 为代表的第 1 类方法,只需将拉普拉斯矩阵生成的特征向量通过 k-means 或其他经典方法
进行聚类,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类方法,代表算法包括 PF 算
[5]
法 等.然而此类方法依赖于相似度矩阵,并且在聚类过程中需要求解拉普拉斯矩阵的特征值与特征
3
2
向量,不仅耗时,而且需要很大的内存空间,算法的时间复杂度和空间复杂度分别为 O(N )和 O(N ),其
中,N 是数据集样本的数量.
• 第 2 类方法给簇内的每个属性赋予相应的权值,在聚类过程中嵌入特征选择,代表算法包括 FWKM [6]
[7]
等.该类型算法中,簇内数据分布的方差越大,则属性权重就越小.其中,Chen 等人 通过子空间尺度的
方法来优化投影子空间,提出 ASC 算法.
本文着重于第 2 类方法,因为第 1 类方法具有较大的时间和空间复杂度.
在第 2 类方法中,大多数研究针对于连续型(数值型)数据.与连续型数据相比,类属型数据属性取值为离散
的符号,这导致适用于连续型数据的子空间聚类算法不能直接迁移到类属型数据.本文研究类属型数据的子空
间聚类问题,因为类属型数据在现实世界中应用更为广泛,例如,投票数据(vote 数据集)包含移民(immigration)和
教育支出(education-spending)等 16 个属性,其中每一个属性值都由 Y 或 N 这两个离散的符号组成.
由于类属型数据属性取值离散的特点,使得类属性数据间的相似性度量比连续型数据更为困难.目前,主流
[8]
[9]
方法采取简单匹配系数(simple matching coefficient,简称 SMC) 及其一些改进方法 ,但是这些方法都是基于
特征之间相互独立这个假设,而在许多实际应用中,这种假设往往是不成立的 [10] .比如,临床肺癌诊断数据
(breastcancer 数据集)中,肿块密度(clump thickness)随着细胞大小(cell size)的增大以一种非线性的形式降低.当
前,发掘属性间非线性关系的主要方法包括深度神经网络和核(kernel)方法等.其中,使用 Mercer 核函数隐式刻
画属性间非线性关系的核方法,因其数学表达的简洁性和计算的高效性,已得到广泛研究和应用,例如 Kernel
k-means(核 k-均值) [11] 算法.目前,研究者已提出很多核聚类的方法,但是它们同样多针对于连续型数据,这是由
于核函数中的内积计算在类属型数据中没有意义.
为了解决上述问题,本文提出一种类属型数据核子空间聚类算法.该算法将原作用于连续型数据的核函数
用来发掘类属型数据属性间的关系,并且在非线性空间中进行自动的类属型属性加权,实现特征选择.最后,本
文还定义了一种基于 AIC 准则的聚类有效性指标,以验证聚类质量并估计类属型数据集划分的簇数目.
本文第 1 节主要是相关工作介绍.第 2 节介绍类属型数据核子空间聚类模型及聚类目标优化函数,并提出
一种高效求解该目标函数的方法.第 3 节给出算法的原理及具体描述,并给出聚类有效性指标.第 4 节介绍实验
环境和实验结果分析.第 5 节对本文进行总结,并指出进一步的研究方向.
1 相关工作

本节介绍类属型数据子空间聚类的相关背景知识,并分析若干代表性的相关工作.下面,首先给出本文使用