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

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

参数.图 1 给出了参数对于设定的 3 个属性权重的变化,这里设定 3 个属性的离散程度从属性 1 开始依次递增.
Attribute1
属性权重
Attribute2
Attribute3

-1 0.5 1 1.5 5 8
θ
Fig.1 Analysis of weight with different θ
图 1 不同θ值下,属性权重的分析
如图 1 所示,θ取值分以下几种情况讨论.
θ
(1) 当θ=0 时, w 为常数,每个属性将被分配相等的权重.
kd
θ D
+
(2) 当θ=1 时, 趋近于无穷大,又因为受到 ∑ w = 1的限制,所以θ→1 时,样本最小偏差的属性将
1 θ− d = 1 kd
得到加权,而其余属性被赋予零权重.这样其实是在每个簇中仅仅选择一个属性,其他属性都被忽略;
−
当 θ→1 时,所有属性的重要程度趋于一致.
(3) 当 0<θ<1 时,离散程度越大的属性,其权重越大.
(4) 当θ<0 和θ>1 时,属性权重与数据分布的离散程度成反比.因此结合定理 1,设定θ>1.然而注意到,当θ
过大时,属性权重之间的差异被降低.
实验将基于聚类质量结果来选择θ,具体在第 4 节给出.
3.2 聚类有效性指标

为了估计类属型数据集划分的簇数目,本节给出了一个新的聚类有效性指标.传统的试错过程 [17] 认为,当簇
数目 K 从最小取到最大的过程中,有效性指标最小的 K 值即为最佳的簇数目.新的聚类有效性指标基于有限样
本修正的 AIC(akaike information criterion)准则(简称 AICc) [18] .
2NP
ˆ
AICc = − 2ln( ).
L
N − P − 1
ˆ
这里,P 是聚类模型中自由参数的个数,N 为数据集中数据样本点数目, L 定义为模型似然函数的最大值.
对于类属型数据而言,应用 AICc 的难点在于似然函数的估计,原因是根据正态分布,模型误差是独立同分
布的假设条件下,类属型数据的似然函数是没有被明确定义的 [19] .由于我们定义了对象到中心的相似性,所以似
然函数可以通过用类属型数据间的距离来替换正态分布中的欧式距离来实现.我们定义第 i 个对象在第 k 个簇
中的似然函数为
1 ⎛ 1 D ⎞
L ki (δ 2 ) = exp − ⎜ 2 ∑ (1 κ − d ( , )) .
xv
k ⎟
i
π
2 δ ⎝ 2δ d = 1 ⎠
2 ˆ
2
2
上式中,δ 是高斯函数的方差,区别于公式(6)中的方差.定义 δ 是δ 的最大似然估计,可以得到:
K
δ 2 ˆ 1 k = ∑∑ D 1∑ (1 κ = − ( , )).
xv
N − K 1 d = i x π∈ k d i k
通过 ln( ) L = ∑∑ ln L ˆ (σ 2 ) 计算最大对数似然,对于 K 个类属型簇的平均 AICc 为
ˆ
K
k = 1 i x π∈ k ki
1 ⎛ 2NP − ˆ ⎞ = N + P − 1 + ln(2πδ 2 ) − K
N N − ⎝ ⎜ P − 1 2ln( ) L ⎟ ⎠ N − P − 1 N .
由于 ln(2π)是一个与 K 无关的常数,由此我们可以得出聚类有效性指标 V KC 如下.