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

3494 Journal of Software 软件学报 Vol.31, No.11, November 2020

的符号定义.
令给定的数据集 DB={x 1 ,x 2 ,…,x i ,…,x N },其中,N 为数据样本点数目.x i ={x i1 ,x i2 ,…,x ij ,…,x iD }为一个 D 维数据
对象,表示 DB 中第 i 个样本点(i=1,2,…,N),x ij 为 x i 的第 j 维属性(j=1,…,D).O d 是第 d 个属性取值的集合,o∈O d
表示其中的任一符号(离散值),并用|O d |表示属性 d 中离散取值的总数.典型的硬聚类算法是将 DB 划分成 K 个
簇的集合Π={π 1 ,π 2 ,…,π K },π k 为 DB 的第 k 个簇(k=1,2,…,K),且任意两个簇的交集是空集,K(K>1)是给定的簇数
目.簇π k 包含的数据对象数目记为|π k |.
目前,许多基于特征选择的类属型数据子空间聚类方法相继被提出,主要区别在于属性加权方式的不同.
• WKM [12] 算法根据簇内对象到类属属性模的平均距离赋予属性相应的权重.
• wk-modes [13] 利用熵来计算各个簇中每个属性的权重.
• 新近出版的 SCC [14] 根据核密度估计方法定义了概率距离函数,并基于簇内类别平滑差异进行加权.
这些方法虽然属性加权方式不同,但都根据以下形式计算数据间相似度.
sim (,xx ) = D w ⋅ ∑ sim ( ,xx ) (1)
i j d = 1 kd d i j
sim d (x i ,x j )表示样本 x i 和样本 x j 在第 d 维属性上的相似度;w kd 表示属性 d 对簇π k 的贡献程度,越大说明越重要,
其中,w kd ≥0 并且 ∑ D w = 1.
d = 1 kd
从上式可以看出,这类子空间聚类方法度量两个样本间的相似性时都是独立地计算每个维度上的相似性
并累加起来,优势在于较高的聚类效率.然而如前所述,这种方法基于特征之间相互独立这个假设,使得特征之
间的关系被忽略不计,而这个假设丢失了很多特征之间的信息.
为了解决上述问题,研究者提出了核聚类方法,将核方法引入到了聚类中.从度量学习的角度来看,核方法
就是一种度量方法,通过直接度量数据间的相似性,而不是将每个维度间的相似性累加起来,隐式地考虑了特征
之间的关系.
所谓核聚类就是把核方法和聚类算法进行耦合,通过把输入空间的数据利用 Mercer 核非线性映射到高维
特征空间,增加了数据点的线性可分概率,即扩大数据之间的差异,在高维特征空间达到线性可聚的目的,例如
n
Kernel k-means(核 k-均值) [11] 算法.核 k-均值算法首先通过“核化”的方式,即利用一个非线性映射φ:R →H,x→
n
φ(x),将原始空间 R 中的样本 x 映射到一个高维的核空间 H 中,通过黑盒的方式对原空间中样本的特征进行组
合,使得样本在核空间中变得线性可分(或近似线性可分);然后,在这个高维的核空间中进行传统的 k-means 聚
类.其中,核函数κ(x,z)=φ(x)⋅φ(z).
然而,现有核方法主要作用于连续型数据.进行类属型数据核子空间聚类的困难主要包括两个方面.
• 首先,Mercer 核函数是为连续型数据定义的,类属型数据并不能直接进行“核化”.
• 其次,当前核方法基于原始特征是同等重要这一假设的,没有区分特征对不同簇类的重要程度.
本文提出一种类属型数据核子空间聚类模型,以克服上述方法存在的缺陷.该方法不仅考虑了属性间的关
系,而且在核空间中能够进行自动的属性加权.本文基于新的核子空间相似性度量定义了一个聚类目标优化函
数,并提出了一种高效求解该目标函数的方法,最后定义了一种类属型数据核子空间聚类算法,称该算法为
KSCC(kernel subspace clustering algorithm for categorical data).

2 类属型数据核子空间聚类模型
本节介绍类属型数据核子空间聚类模型以及聚类目标优化函数,并提出了一种高效求解该目标函数的方
法.如同其他子空间聚类方法一样,首先需要解决类属型数据间相似性问题,下面给出核子空间相似性度量.
2.1 核子空间相似性度量

如前所述,现有主流子空间方法未考虑属性间的关系,而核方法虽然在非线性空间中挖掘了属性间的关系,
但并未区分属性的重要程度.因此,引入原作用于连续型数据的核函数将类属型数据投影到核空间,并且在核空
间中为每个簇类π k 引入一个权值向量 w k ={w kd |d=1,2,…,D}用于原始特征选择.w kd 表示属性 d 对簇π k 的贡献程