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

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

ˆ
ˆ
ˆ
ˆ
ˆ
Π Π = ˆ 以求解最大化 ( J Π , ) 的 W,记为 W ;其次,设定 W = W ,通过最大化 ( J Π , ) 求解最优的Π,即 Π .后者
W
W
可以通过将每个对象 x i 划分到相似性最高的簇来实现.算法根据如下规则将 x i 划分到簇π k 中去.
⎛ ⎛ ∑ [(Ix = ) o − f ( )]o 2 ⎞ ⎞
k = argmax(κ w (x ,v )) = i k argmax exp ⎜ ⎜ D w θ oO d id k ⎟ −∑ ⎟ ⎟ (8)
∈
∀ k ∀ k ⎜ d = 1 kd 2
⎝ ⎝ 2σ ⎠ ⎠
ˆ
ˆ
从而生成新的聚类划分 Π .求解W 可以通过定理 2 进行.
定理 2. 设定当 Π Π = ˆ 时,最大化公式(7)当且仅当
1 1
⎡ ∑ [ (Ix = ) o − f ( )]o 2 ⎞ ⎤ 1 θ− ⎡ ⎛ ⎛ ∑ [ (I x = ) o − f ( )]o 2 ⎞ ⎤ − 1 θ−
∈
∈
ˆ w = ⎢ exp ⎜ oO d id k ⎟ ⎥∑ ∑ D ⎢ exp ⎜ oO d id k ⎟ − ⎥∑ (9)
kd i x π∈ d = 1 i x π∈ −
⎢ k 2σ 2 ⎠ ⎦ ⎥ ⎣ ⎢ ⎝ k ⎝ 2σ 2 ⎠ ⎥ ⎣ ⎦
证明:根据公式(7),可以定义 K 个独立的子优化目标函数:
⎛
Jw k ,λ k ) = D w θ kd exp − (x − x jd ) ⎞ 2 ⎟ + ∑ λ k ( D w )1− ∑
id
(
⎜
k
⎝ d = 1 2σ 2 ⎠ d = 1 kd
⎛ D ∑ [(Ix = ) o − f ( )]o 2 ⎞
= w θ exp ⎜ oO d id k ⎟ − + ∑ λ ( D w )1− ∑ .
∈
d = 1 kd 2 k d = 1 kd
⎝ 2σ ⎠
ˆ
ˆ
)
)
设 ˆ (w k ,λ 最大化 Jw ˆ ( k ,λ ,有:
k
k
k
ˆ
∂ Jw ˆ ( k ,λ k ) = θ exp ⎜ ⎛ ∑ oO d [(Ix = id ) o − f k ( )]o 2 ⎞ ⎟ − ˆ w − λ ˆ =
∈
k
∂ ˆ w kd ⎜ ⎝ 2σ 2 ⎟ ⎠ kd k 0,
ˆ
∂ Jw ˆ ( ,λ )
1 ∑
k k k =− D ˆ w = 0.
ˆ
∂ λ k d = 1 kd
合并以上两个公式,可以得到公式(9). □
具体算法过程如下.
算法. KSCC.
输入:类属型数据集 DB,簇数目 K,激励强度θ.
输出:簇划分Π 及属性权重集合 W.
1. 初始化:生成数据集初始划分,记为Π (0) ;算法迭代次数 p,p=0.
REPEAT:
2. 更新 W:设定 Π ˆ Π = ()p ,根据公式(9)更新属性权重,得到 W (p+1) .
ˆ
3. 更新Π:设定W = W ( p+ 1) ,利用公式(8)将每个数据对象划分到簇,生成新的聚类集合Π (p+1) .
4. 迭代次数:p=p+1.
UNTIL 聚类集合不发生变化,即Π (p) =Π (p+1) .
EM 型算法对其初始状态具有一定依赖性,因此我们借助 k-modes [15] 算法对 KSCC 算法第一步中的数据集
进行初始划分.从算法结构可知,KSCC 算法与 k-means [16] 算法相似,算法中每一次迭代过程的时间复杂度为
O(KND),假设算法迭代次数为 P,KSCC 算法时间复杂度为 O(KNDP).算法在每步迭代过程中提高目标函数值,
且数据间相似度最大为 1,所以目标函数存在上界.因此在有限的迭代次数下,KSCC 算法是收敛的.
3.1 关于参数θ的讨论
在 KSCC 聚类过程中,通过核函数直接度量数据间的相似性,在核空间中每个属性都被自动赋予一个衡量
其重要程度的权值,通过特征选择寻找到相应的子空间.根据公式(9),簇π k 中属性 d 的权值计算为
θ θ
⎛ ⎛ ∑ [ (Ix = ) o f ( )]o 2 ⎞ ⎞ 1 θ− ⎛ ⎛− − 2(1− f (x )) (1− + ∑ [ ( )] )f o 2 ⎞ ⎞ 1 θ−
∈
∈
w θ ~ ⎜ ⎜ exp ⎜ oO d id k ⎟ − ⎟∑ ⎟ = ⎜ ⎜ ∑ exp ⎜ k id oO d k ⎟ ⎟ ⎟ .
kd
⎝ i x π∈ k ⎝ 2σ 2 ⎠ ⎠ ⎝ i x π∈ k ⎝ 2σ 2 ⎠ ⎠
上式中,1− ∑ [ ( )]f o 2 是表示类属型数据分布离散程度的基尼系数.θ作为激励强度,是控制权重的分配
∈
oO d k