发布日期：2025-01-04 16:24 点击次数：141
聚类分析作为数据挖掘研究中的一种重要手段, 目的是从给定数据集中寻找数据之间的相似性, 并以此划分多个子集(每个子集为一个簇), 使得不同簇中的数据尽可能相异, 而同一簇中的数据尽可能相似, 即“物以类聚”[1].目前, 聚类分析已经在许多领域获得广泛应用, 包括模式识别、文本挖掘、机器学习、图像处理和基因表达等.
在聚类分析中, 子空间聚类因其能够从数据集的不同子空间中发现相应的簇[2]而得到广泛研究.现有子空间聚类方法依据提取子空间方法的不同大致可以分为两类.
● 以谱聚类[3]为代表的第1类方法, 只需将拉普拉斯矩阵生成的特征向量通过k-means[4]或其他经典方法进行聚类, 其本质是将聚类问题转化为图的最优划分问题, 是一种点对聚类方法, 代表算法包括PF算法[5]等.然而此类方法依赖于相似度矩阵, 并且在聚类过程中需要求解拉普拉斯矩阵的特征值与特征向量, 不仅耗时, 而且需要很大的内存空间, 算法的时间复杂度和空间复杂度分别为O(N3)和O(N2), 其中, N是数据集样本的数量.
● 第2类方法给簇内的每个属性赋予相应的权值, 在聚类过程中嵌入特征选择, 代表算法包括FWKM[6]等.该类型算法中, 簇内数据分布的方差越大, 则属性权重就越小.其中, Chen等人[7]通过子空间尺度的方法来优化投影子空间, 提出ASC算法.
本文着重于第2类方法, 因为第1类方法具有较大的时间和空间复杂度.
在第2类方法中, 大多数研究针对于连续型(数值型)数据.与连续型数据相比, 类属型数据属性取值为离散的符号, 这导致适用于连续型数据的子空间聚类算法不能直接迁移到类属型数据.本文研究类属型数据的子空间聚类问题, 因为类属型数据在现实世界中应用更为广泛, 例如, 投票数据(vote数据集)包含移民(immigration)和教育支出(education-spending)等16个属性, 其中每一个属性值都由Y或N这两个离散的符号组成.
由于类属型数据属性取值离散的特点, 使得类属性数据间的相似性度量比连续型数据更为困难.目前, 主流方法采取简单匹配系数(simple matching coefficient, 简称SMC)[8]及其一些改进方法[9], 但是这些方法都是基于特征之间相互独立这个假设, 而在许多实际应用中, 这种假设往往是不成立的[10].比如, 临床肺癌诊断数据(breastcancer数据集)中, 肿块密度(clump thickness)随着细胞大小(cell size)的增大以一种非线性的形式降低.当前, 发掘属性间非线性关系的主要方法包括深度神经网络和核(kernel)方法等.其中, 使用Mercer核函数隐式刻画属性间非线性关系的核方法, 因其数学表达的简洁性和计算的高效性, 已得到广泛研究和应用, 例如Kernel k-means(核k-均值)[11]算法.目前, 研究者已提出很多核聚类的方法, 但是它们同样多针对于连续型数据, 这是由于核函数中的内积计算在类属型数据中没有意义.
为了解决上述问题, 本文提出一种类属型数据核子空间聚类算法.该算法将原作用于连续型数据的核函数用来发掘类属型数据属性间的关系, 并且在非线性空间中进行自动的类属型属性加权, 实现特征选择.最后, 本文还定义了一种基于AIC准则的聚类有效性指标, 以验证聚类质量并估计类属型数据集划分的簇数目.
本文第1节主要是相关工作介绍.第2节介绍类属型数据核子空间聚类模型及聚类目标优化函数, 并提出一种高效求解该目标函数的方法.第3节给出算法的原理及具体描述, 并给出聚类有效性指标.第4节介绍实验环境和实验结果分析.第5节对本文进行总结, 并指出进一步的研究方向.
1 相关工作
本节介绍类属型数据子空间聚类的相关背景知识, 并分析若干代表性的相关工作.下面, 首先给出本文使用的符号定义.
令给定的数据集DB={x1, x2, …, xi, …, xN}, 其中, N为数据样本点数目.xi={xi1, xi2, …, xij, …, xiD}为一个D维数据对象, 表示DB中第i个样本点(i=1, 2, …, N), xij为xi的第j维属性(j=1, …, D).Od是第d个属性取值的集合, o∈Od表示其中的任一符号(离散值), 并用|Od|表示属性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({\boldsymbol{x}_i}, {\boldsymbol{x}_j}) = \sum\nolimits_{d = 1}^D {{w_{kd}} \cdot si{m_d}({\boldsymbol{x}_i}, {\boldsymbol{x}_j})} $
(1)
simd(xi, xj)表示样本xi和样本xj在第d维属性上的相似度; wkd表示属性d对簇πk的贡献程度, 越大说明越重要, 其中, wkd≥0并且$\sum\nolimits_{d = 1}^D {{w_{kd}}} = 1.$
从上式可以看出, 这类子空间聚类方法度量两个样本间的相似性时都是独立地计算每个维度上的相似性并累加起来, 优势在于较高的聚类效率.然而如前所述, 这种方法基于特征之间相互独立这个假设, 使得特征之间的关系被忽略不计, 而这个假设丢失了很多特征之间的信息.
为了解决上述问题, 研究者提出了核聚类方法, 将核方法引入到了聚类中.从度量学习的角度来看, 核方法就是一种度量方法, 通过直接度量数据间的相似性, 而不是将每个维度间的相似性累加起来, 隐式地考虑了特征之间的关系.
所谓核聚类就是把核方法和聚类算法进行耦合, 通过把输入空间的数据利用Mercer核非线性映射到高维特征空间, 增加了数据点的线性可分概率, 即扩大数据之间的差异, 在高维特征空间达到线性可聚的目的, 例如Kernel k-means(核k-均值)[11]算法.核k-均值算法首先通过“核化”的方式, 即利用一个非线性映射ϕ:Rn→H, x→ϕ(x), 将原始空间Rn中的样本x映射到一个高维的核空间H中, 通过黑盒的方式对原空间中样本的特征进行组合, 使得样本在核空间中变得线性可分(或近似线性可分); 然后, 在这个高维的核空间中进行传统的k-means聚类.其中, 核函数κ(x, z)=ϕ(x)·ϕ(z).
然而, 现有核方法主要作用于连续型数据.进行类属型数据核子空间聚类的困难主要包括两个方面.
● 首先, Mercer核函数是为连续型数据定义的, 类属型数据并不能直接进行“核化”.
● 其次, 当前核方法基于原始特征是同等重要这一假设的, 没有区分特征对不同簇类的重要程度.
本文提出一种类属型数据核子空间聚类模型, 以克服上述方法存在的缺陷.该方法不仅考虑了属性间的关系, 而且在核空间中能够进行自动的属性加权.本文基于新的核子空间相似性度量定义了一个聚类目标优化函数, 并提出了一种高效求解该目标函数的方法, 最后定义了一种类属型数据核子空间聚类算法, 称该算法为KSCC(kernel subspace clustering algorithm for categorical data).
2 类属型数据核子空间聚类模型
本节介绍类属型数据核子空间聚类模型以及聚类目标优化函数, 并提出了一种高效求解该目标函数的方法.如同其他子空间聚类方法一样, 首先需要解决类属型数据间相似性问题, 下面给出核子空间相似性度量.
2.1 核子空间相似性度量
如前所述, 现有主流子空间方法未考虑属性间的关系, 而核方法虽然在非线性空间中挖掘了属性间的关系, 但并未区分属性的重要程度.因此, 引入原作用于连续型数据的核函数将类属型数据投影到核空间, 并且在核空间中为每个簇类πk引入一个权值向量wk={wkd|d=1, 2, …, D}用于原始特征选择.wkd表示属性d对簇πk的贡献程度, 越大说明越重要.这里, wkd满足约束条件:
$\left\{ {\begin{array}{*{20}{l}}
{\forall k, d:{w_{kd}} \geqslant 0} \\
{\forall k:\sum\nolimits_{d = 1}^D {{w_{kd}}} = 1}
\end{array}} \right.$
(2)
此外, 为wkd引入指数θ(θ≠0)控制多属性聚类中的激励强度, 并假定θ为已知的常数[14].θ越大, 权值分布越平滑.形式上, 定义核子空间相似性度量为
$
{sim}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)={\kappa}_{w}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)
$
(3)
κw(xi, xj)表示特征加权的核函数, 为两个数据对象在每个属性上的组合形式引入权重.
以多项式核函数为例:
● 原多项式核函数为$\kappa ({\boldsymbol{x}_i}, {\boldsymbol{x}_j}) = {({\boldsymbol{x}_i} \cdot {\boldsymbol{x}_j} + 1)^p} = {\left( {\sum\nolimits_{d = 1}^D {{x_{id}}{x_{jd}}} + 1} \right)^p}$.
● 经过特征加权变为${\kappa _w}({\boldsymbol{x}_i}, {\boldsymbol{x}_j}) = {({\boldsymbol{x}_i} \cdot {\boldsymbol{x}_j} + 1)^p} = {\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {x_{id}}{x_{jd}}} + 1} \right)^p}.$
为了使类属型数据能够通过核函数映射到高维空间, 这里用符号向量化技术定义.
${x_{id}} = \langle I({x_{id}} = {O_{d1}}), I({x_{id}} = {O_{d2}}), ..., I({x_{id}} = {O_{d|{O_d}|}})\rangle .$
公式(3)与现有的类属型数据相似性度量相比, 不仅借助核方法来进行类属型数据的“核化”, 在非线性空间中考虑了特征之间的联系, 而且在映射后的核空间中进行了特征选择, 区分了特征对簇类有区别的重要.
2.2 类属型数据核子空间聚类目标函数
在聚类分析中, 定义簇为紧凑度(或分散度最小)的样本集合, 其中, 紧凑度以样本到簇中心的相似度来衡量.结合核子空间相似性度量公式, 定义类属型数据的核子空间聚类优化目标函数为
$J(\mathit{\Pi }, W) = \sum\limits_{k = 1}^K {\sum\limits_{{x_i} \in {\pi _k}} {\mathit{Sim}} } \left( {{\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{v}}_k}} \right) = \sum\limits_{k = 1}^K {\sum\limits_{{x_i} \in {\pi _k}} {{\kappa _w}} } \left( {{\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{v}}_k}} \right) $
(4)
vk是簇πk的中心, 簇πk在第d维上的中心为vkd.由于一个类属属性值由一个向量表示, 簇πk在第d维上的中心也应该由一个向量表示.令${v_{kd}} = \langle {f_k}({O_{d1}}), {f_k}({O_{d2}}), ..., {f_k}({O_{d|{O_d}|}})\rangle $, 这里, ${f_k}(o) = \frac{1}{{|\pi |}}\sum\nolimits_{{x_i} \in {\pi _k}} {I({x_{id}} = o)} $表示簇πk中属性值o∈Od的频度估计; I(·)为指示函数, I(true)=1, I(false)=0.从优化角度分析, 划分型聚类算法是求解目标函数的最优值过程.由于是以相似性度量为基础的目标函数, 所以本文以最大化公式(4)为优化目标.在计算过程中, 求和函数在核函数的内部运算(比如上述多项式核子空间函数), 导致wkd难以求解, 这大大增加了求解目标函数的难度.
本文提出一种高效求解该目标函数的优化方法, 将目标函数转换为现有主流方法的形式(如公式(1))以提高计算效率.下面对公式(4)定义的优化目标进一步分析.定理1表明, 对于所有上凸的核函数(θ≥1时), 求解公式(4)最大值等价于求解公式(5)目标函数最大值.
$J(\mathit{\Pi }, W) = \sum\limits_{k = 1}^K {\sum\limits_{{x_i} \in {\pi _k}} {\sum\limits_{d = 1}^D {w_{kd}^\theta } } } {\kappa _d}\left( {{\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{v}}_k}} \right) $
(5)
公式(5)中, κd(xi, vk)是指xi和vk在d维上映射函数的内积, 即第d维属性上的核函数.以多项式核函数为例:
$
\kappa_{d}\left(x_{i}, v_{k}\right)=\left(x_{i d} v_{k d}+1\right)^{p}.
$
定理1.当θ≥1时, 对于所有上凸的核函数κ(·, ·), 最大化公式(4)与最大化公式(5)同解.
证明:首先定义zd为核子空间相似性度量中两个输入对象在第d个属性上的组合, 当核函数输入对象为样本xi和簇中心vk时, zd表示xi与vk在第d个属性上的组合.令$f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right) = {\kappa _w}({\boldsymbol{x}_i}, {\boldsymbol{v}_k})$, f(·)是新定义的函数.可以发现, f(zd)=κd(xi, vk).下面用数学归纳法证明$\sum\nolimits_{d = 1}^D {w_{kd}^\theta f({z_d})} \leqslant f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right)$, s.t. Eq(2).
a. 当D=1, 2时, 不等式显然成立.
b. 假设当D=n时, 不等式成立, 即$\sum\nolimits_{d = 1}^n {w_{kd}^\theta f({z_d})} \leqslant f\left( {\sum\nolimits_{d = 1}^n {w_{kd}^\theta {z_d}} } \right)$.D=n+1时, 令${p_n} = \sum\nolimits_{d = 1}^n {{w_{kd}}} $, 则
$\begin{array}{*{20}{l}}
{1.}&{\sum\nolimits_{d = 1}^{n + 1} {w_{kd}^\theta f({z_d})} }&{ = w_{k(n + 1)}^\theta f({z_{n + 1}}) + \sum\nolimits_{d = 1}^n {w_{kd}^\theta f({z_d})} } \\
{2.}&{}&{ = w_{k(n + 1)}^\theta f({z_{n + 1}}) + p_n^\theta \sum\nolimits_{d = 1}^n {{{\left( {\frac{{{w_{kd}}}}{{{p_n}}}} \right)}^\theta }f({z_d})} } \\
{3.}&{}&{ \leqslant w_{k(n + 1)}^\theta f({z_{n + 1}}) + p_n^\theta f\left( {\sum\nolimits_{d = 1}^n {{{\left( {\frac{{{w_{kd}}}}{{{p_n}}}} \right)}^\theta }{z_d}} } \right)} \\
{4.}&{}&{ \leqslant f\left( {w_{k(n + 1)}^\theta {z_{n + 1}} + p_n^\theta \sum\nolimits_{d = 1}^n {{{\left( {\frac{{{w_{kd}}}}{{{p_n}}}} \right)}^\theta }{z_d}} } \right)} \\
{5.}&{}&{ = f\left( {w_{k(n + 1)}^\theta {z_{n + 1}} + \sum\nolimits_{d = 1}^n {w_{kd}^\theta {z_d}} } \right)} \\
{6.}&{}&{ = f\left( {\sum\nolimits_{d = 1}^{n + 1} {w_{kd}^\theta {z_d}} } \right).}
\end{array}$
所以$\sum\nolimits_{d = 1}^D {w_{kd}^\theta f({z_d})} \leqslant f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right)$得以证明.特别地, 当θ=1时, 不等式即为Jesson不等式.通过拉伸下界$\sum\nolimits_{d = 1}^D {w_{kd}^\theta f({z_d})} $使其上升至与$f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right)$相等位置, 然后调整wkd, 使$\sum\nolimits_{d = 1}^D {w_{kd}^\theta f({z_d})} $达到最大值.逐步迭代, 最终达到$f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right)$的最大值处.wkd的推导在第3节中给出.
定理1中, 当D=n+1时, 首先令${p_n} = \sum\nolimits_{d = 1}^n {{w_{kd}}} $.注意到, 由于此时D=n+1, 所以pn≠1, ${p_n} + {w_{k(n + 1)}} = \sum\nolimits_{d = 1}^{n + 1} {{w_{kd}}} = 1$.步骤2中, 由于${p_n} = \sum\nolimits_{d = 1}^n {{w_{kd}}} $, 所以$\sum\nolimits_{d = 1}^n {\frac{{{w_{kd}}}}{{{p_n}}}} = 1$符合约束条件, 因此可以把$\sum\nolimits_{d = 1}^n {{{\left( {\frac{{{w_{kd}}}}{{{p_n}}}} \right)}^\theta }f({z_d})} $利用情形b.中假设的不等式进行转换, 即步骤3中的不等式; 在步骤3中, ${w_{k(n + 1)}} + {p_n} = \sum\nolimits_{d = 1}^{n + 1} {{w_{kd}}} = 1$, 再次符合约束条件.这其实等价于D=2时的情况, 因此可以把两项通过不等式合并为一项, 即步骤4中的不等式.定理1定义zd作为两个输入对象在第d个属性上的组合, f(·)是新定义的函数, 目的是为了转换核函数的表示形式, 例如高斯核子空间函数:
${\kappa _w}({\boldsymbol{x}_i}, {\boldsymbol{x}_j}) = \exp \left( { - \sum\nolimits_{d = 1}^D {w_{kd}^\theta \frac{{{{({x_{id}} - {x_{jd}})}^2}}}{{2{\sigma ^2}}}} } \right) = f\left( {\sum\nolimits_{d = 1}^D {w_{kd}^\theta {z_d}} } \right), $
其中, ${z_d} = - \frac{{
