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

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

1. ∑ n+ 1 wf ( )z = w θ ( f z 1 ∑ ) + n w f ( )z
θ
θ
d = 1 kd d ( k n+ 1) n+ d = 1 kd d θ
θ
( )
2. = w θ ( kn+ 1) ( f z n+ 1 ) + p n∑ n ⎛ ⎜ w ⎞ kd ⎟ f z d
⎝ d = 1 p n ⎠
⎛ n ⎛ w ⎞ θ ⎞
θ
3. ≤ w θ ( kn+ 1) ( f z n+ 1 ) + p f ⎜ n ∑ d = 1 ⎜ kd ⎟ z ⎟ d
⎜ ⎝ ⎝ p n ⎠ ⎟ ⎠
⎛ n ⎛ w ⎞ θ ⎞
⎜
θ
4. ≤ fw θ ( kn+ 1) n+ z + p n∑ ⎜ kd ⎟ z ⎟
⎜ 1 d = 1 p d ⎟
⎝ ⎝ n ⎠ ⎠
θ
5. = f w ( θ 1) n+ ∑ n w z )
+
z
( kn+ 1 d = 1 kd d
6. = ( ∑ n+ 1 1 wz ) f .
θ
kd d
d =
所以 ∑ D wf ()z ≤ ( f ∑ D wz ) 得以证明.特别地,当θ=1 时,不等式即为 Jesson 不等式.通过拉伸下界
θ
θ
d = 1 kd d d = 1 kd d
∑ D d = 1 wf ()z d 使其上升至与 ( f ∑ D d = 1 wz ) 相等位置,然后调整 w kd ,使 ∑ D d = 1 wf ()z d 达到最大值.逐步迭代,最终
θ
θ
θ
kd
kd
kd d
θ
达到 ( f ∑ D d = 1 wz ) 的最大值处.w kd 的推导在第 3 节中给出. □
kd d
定理 1 中,当 D=n+1 时,首先令 p = ∑ n w .注意到,由于此时 D=n+1,所以 p n ≠1, p + w 1) ∑ n+ 1 w = 1.
=
n d = 1 kd n ( k n+ d = 1 kd
步骤 2 中,由于 p = ∑ n w ,所以 ∑ n w kd = 1 符合约束条件,因此可以把 ∑ n ⎛ ⎜ w ⎞ kd ⎟ θ f ()z 利用情形 b.中假设
n d = 1 kd d = 1 p n d = 1 ⎝ p n ⎠ d
的不等式进行转换,即步骤 3 中的不等式;在步骤 3 中, w ( kn+ 1) + p = n ∑ n+ 1 1 w = kd 1,再次符合约束条件.这其实等价
d =
于 D=2 时的情况,因此可以把两项通过不等式合并为一项,即步骤 4 中的不等式.定理 1 定义 z d 作为两个输入对
象在第 d 个属性上的组合,f(⋅)是新定义的函数,目的是为了转换核函数的表示形式,例如高斯核子空间函数:
⎛ (x − x ) ⎞ 2
θ
κ w (, j ) = xx exp − ⎜ ⎜ D w θ kd id jd ⎟ ∑ ⎟ = ( 2 ∑ D wz ) f ,
i
kd d
⎝ d = 1 2σ ⎠ d = 1
|| x − x || 2
其中, z =− id jd ,f(x)=exp(x).
d
2σ 2
在核函数中,高斯核函数无论对于大样本还是小样本都有较好的性能,且比其他核函数参数较少,是应用最
广的核函数.选择高斯核函数代入目标函数,则公式(5)可改写成:
( )] ⎞
K D ⎛ (x − v ) ⎞ 2 K D ⎛ ∑ [( Ix = id ) o − f o 2
k
( J Π , ) = W w θ kd exp − ∑∑∑ ⎜ id 2 kd ⎟ = ∑ ∑ ∑ w θ kd exp ⎜ − o O d ⎟ (6)
∈
k = 1 i x π ∈ k d = 1 ⎝ 2σ k = ⎠ 1 i x π ∈ k d = 1 ⎜ ⎝ 2σ 2 ⎟ ⎠
N
高斯核函数中的参数σ 定义为数据集 DB 的全局方差,σ = 2 1 i= ∑∑ D 1∑ [Ix = ) o − f o 2
2
( )] .
(
ND 1 d = o∈ O d id k
3 KSCC 聚类算法
本节介绍算法的原理及具体描述,并提出一个新的聚类有效性指标,用于验证聚类质量和估计类属型数据
集划分的簇的数目.
针对公式(6),这是一个带约束的非线性优化问题,应用拉格朗日乘子法,结合上述定义,优化目标函数可转
换为
⎛ ∑ [ ( Ix = ) o − ( )] ⎞ 2
K D id f o K ⎛ D ⎞
k
max ( J Π , ) = W w θ exp ⎜ − o O d ⎟ + ∑∑ ∑ λ k ⎜ 1− ∑ w kd ⎟ ∑ (7)
∈
kd
k = 1 i x π k d = 1 ⎜ ⎝ 2σ 2 ⎠ k = ⎟ 1 ⎝ d = 1 ⎠
∈
本文采用 EM 型算法对其优化,即通过迭代法求 J 的局部最优值.根据这个原理,每次迭代过程首先设定