Page 225 - 《软件学报》2021年第12期

陈晓琪 等:基于动态赋权近邻传播的数据增量采样方法 3889

⎧ ri s ( , ) max( ( , )i j − a i k + s ( , ))i k
(, )j =
⎪ kj≠
⎪ ⎛ ⎞
(, )j =
⎪ ai min 0, ( , )r j j + ⎜ ⎜ ∑ max(0, ( , )) ,r k j ⎟ ⎟ j ≠ i (3)
⎨
⎪ ⎝ ki ≠ , j ⎠
⎪ (, )i = ∑
⎪ ai ki ≠ max(0, ( , ))r k i
⎩
吸引度 r(i,j)表示样本点 j 作为样本点 i 的聚类中心的合适程度,归属度 a(i,j)表示样本点 i 选择样本点 j 作
为聚类中心的合适程度.对于任意的样本点 k,如果其对于自身的归属度 a(k,k)和吸引度 r(k,k)之和大于 0,则样本
点 k 是一个聚类中心.
从标准 AP 算法的迭代过程和聚类中心选取方法可以看出,偏向参数 P={p k } 1×N (s(k,k)←p k )的大小直接影响
最终聚类数目.在大多数基于 AP 过程的算法中,各样本的 p k 被设为同一常数并且在迭代过程中保持不变.一旦
p k 被确定,聚类结果也就被确定下来,过程中没有其他的方法来对结果进行修正.为了降低初始 p k 对聚类结果的
影响,可以引入额外的信息在聚类过程中动态改变偏向参数.本文考虑引入节点的轮廓系数对每一次迭代产生
的中间结果进行评价,从而依据评价结果动态改变每个点的 p k .即:当 AP 算法产生至少一个聚类中心时,认为点
与点之间产生了相互作用.依照这一思想,AP 算法的因子图模型结构将相应地发生变化,在原本的聚类约束条
件下,将新增有关于聚类中心的约束,改变后的因子图模型及其信息传递如图 2(2)所示.新的因子图新增了聚类
约束条件 F,该约束表示当产生至少一个聚类中心时,各节点之间存在相互作用,新增约束公式及改变后的全局
函数 S(C)如下:
⎧ ⎪ 0, ∑ c > 0
ii
Fc 11 ,...,c NN ) = ⎨ i
(
k
⎪ ⎩ −∞ , otherwise (4)
( ) + ∑
Max S C ∑ S c + ij ij E c : j ∑ I c : i ∑ F k (c 11 ,...,c NN )
:( ) =
( ) +
i
j
, ij j i k
依据 max-sum 算法,可以从新的全局函数及信息传递过程中 [17,20] 推导出如下公式:
ρ ij s − ij max(s + ik α = ⎧ ik )
⎪ kj
≠
⎪ ⎛ ⎞
⎪ α ij min 0,ρ = ⎜ ⎜ jj ∑ max(0,ρ + ij ⎟ ) ⎟
⎪ ⎝ ki ≠ , j ⎠
⎪
⎨ α max(0,ρ = ∑ ) (5)
⎪ ii ki
⎪ ki ≠
⎪ ϕ =− max(s + α ii′ ) s + α ii − γ + ik
ii′
ik
ii
′≠
⎪ ii
⎪ γ ik max(0,ϕ =− ii i k ′ )
⎩
′≠
与公式(2)比较可以发现,新增信息量γ ik 和ϕ ik 不影响原本吸引度和归属度的更新过程.因此,引入额外信息
改变 p k 不会改变 AP 算法的核心公式.
轮廓系数是确定聚类质量的一种常用指标,通常用来评价整体聚类质量的好坏,但也可以用来评估某一个
样本点簇归属的合适程度.假设数据集被划分为 x 个子集{C 1 ,C 2 ,…,C x },a(i)是子集 C k 中的样本点 i 到同簇其他
样本点间的平均相似度,b(i,C j )(i≠j)是样本点 i 到子集 C j 中所有样本点的平均相似度.b(i,:)=min{b(i,C j )}.一个样
本点的簇归属合适程度计算方法如下:
(,:) a i
Silhouette () i = bi − ( ) (6)
max{ ( ), ( ,:)}
ai b i
Silhouette(i)的取值范围为[−1,1]:越接近 1,则样本点 i 的簇归属越合理;接近−1,说明样本点 i 应属于其他簇;
为 0,则说明样本点 i 在两个簇的边界上.
在 AP 算法迭代产生聚类中心的情况下,引入对样本点的轮廓系数评价.参考 Silhouette 指标的结果可以得
知样本点是否被正确地划分,以及被选作聚类中心的样本点是否是正确的聚类中心,从而调整每个样本的偏向
参数{p k },动态改变样本点成为聚类中心的可能性.显然,聚类中心样本与非聚类中心样本在调整上存在差异,因