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

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

度,越大说明越重要.这里,w kd 满足约束条件:
,: w ≥
⎧ ⎪ ∀ kd kd 0
⎨ D (2)
⎪ ⎩ ∀ : k ∑ d = 1 w = 1
kd
此外,为 w kd 引入指数θ(θ≠0)控制多属性聚类中的激励强度,并假定θ为已知的常数 [14] .θ越大,权值分布越平
滑.形式上,定义核子空间相似性度量为
sim(x i ,x j )=κ w (x i ,x j ) (3)
κ w (x i ,x j )表示特征加权的核函数,为两个数据对象在每个属性上的组合形式引入权重.
以多项式核函数为例:
p
⋅
• 原多项式核函数为 (,κ xx j ) = (x x j + 1) = p (∑ D d = 1 id jd ) 1 .
xx +
i
i
p
D
⋅
θ
• 经过特征加权变为 κ w (,xx j ) = (x x j + 1) = p (∑ d = 1 wx x + 1 ) .
i
i
kd id
jd
为了使类属型数据能够通过核函数映射到高维空间,这里用符号向量化技术定义.
x =〈 ( I x = O ), (I x = O ),..., (I x = O ) .〉
id id d 1 id d 2 id d O |
| d
公式(3)与现有的类属型数据相似性度量相比,不仅借助核方法来进行类属型数据的“核化”,在非线性空间
中考虑了特征之间的联系,而且在映射后的核空间中进行了特征选择,区分了特征对簇类有区别的重要.
2.2 类属型数据核子空间聚类目标函数
在聚类分析中,定义簇为紧凑度(或分散度最小)的样本集合,其中,紧凑度以样本到簇中心的相似度来衡量.
结合核子空间相似性度量公式,定义类属型数据的核子空间聚类优化目标函数为
K
K
( , ) =
( J Π ,W = ) ∑∑ Sim xv k ∑∑ κ w ( , )xv k (4)
i
i
k = 1 i x π ∈ k k = 1 i x π ∈ k
v k 是簇π k 的中心,簇π k 在第 d 维上的中心为 v kd .由于一个类属属性值由一个向量表示,簇π k 在第 d 维上的中
1
心也应该由一个向量表示.令 v =〈 f (O ), f (O ),..., f (O )〉 ,这里, f o = ∑ ( I x = ) o 表示簇π k 中属
()
2
|
d
k
k
k
kd
d
d O
k
1
|π | i x π∈ k id
| d
性值 o∈O d 的频度估计;I(⋅)为指示函数,I(true)=1,I(false)=0.从优化角度分析,划分型聚类算法是求解目标函数的
最优值过程.由于是以相似性度量为基础的目标函数,所以本文以最大化公式(4)为优化目标.在计算过程中,求
和函数在核函数的内部运算(比如上述多项式核子空间函数),导致 w kd 难以求解,这大大增加了求解目标函数的
难度.
本文提出一种高效求解该目标函数的优化方法,将目标函数转换为现有主流方法的形式(如公式(1))以提
高计算效率.下面对公式(4)定义的优化目标进一步分析.定理 1 表明,对于所有上凸的核函数(θ≥1 时),求解公式
(4)最大值等价于求解公式(5)目标函数最大值.
K
D
( J Π , )W = ∑∑∑ w κ θ d ( , )xv k (5)
kd
i
k = 1 i x π k d = 1
∈
公式(5)中,κ d (x i ,v k )是指 x i 和 v k 在 d 维上映射函数的内积,即第 d 维属性上的核函数.以多项式核函数为例:
p
κ d (x i ,v k )=(x id v kd +1) .
定理 1. 当θ≥1 时,对于所有上凸的核函数κ(⋅,⋅),最大化公式(4)与最大化公式(5)同解.
证明:首先定义 z d 为核子空间相似性度量中两个输入对象在第 d 个属性上的组合,当核函数输入对象为样
θ
本 x i 和簇中心 v k 时,z d 表示 x i 与 v k 在第 d 个属性上的组合.令 ( f ∑ D d = 1 wz ) κ= w (, )xv k ,f(⋅)是新定义的函数.可
i
kd d
以发现,f(z d )=κ d (x i ,v k ).下面用数学归纳法证明 ∑ D wf ()z ≤ ( f ∑ D wz ) ,s.t. Eq(2).
θ
θ
d = 1 kd d d = 1 kd d
a. 当 D=1,2 时,不等式显然成立.
θ
θ
b. 假设当 D=n 时,不等式成立,即 ∑ n wf ()z ≤ ( f ∑ n wz ) .D=n+1 时,令 p = ∑ n w ,则
d = 1 kd d d = 1 kd d n d = 1 kd