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

3890 Journal of Software 软件学报 Vol.32, No.12, December 2021

此给出两条偏向参数更新规则.
规则 1. 对于非聚类中心样本:Silhouette 指标大于 0,说明该样本被划分到正确的簇,其成为聚类中心的可能
性应该降低,p k 应适当减小;Silhouette 指标小于 0,则该点没有被划分到正确的簇,其应该被划分到其他簇或成为
一个新的聚类中心,p k 应维持不变或适当增加.
规则 2. 对于聚类中心样本:Silhouette 指标大于 0,说明该样本是正确的聚类中心,p k 应维持不变或适当增
加;Silhouette 指标小于 0,说明该点不是正确的聚类中心,p k 应适当减小.
基于上述两条规则,为了将 Silhouette 转化为合适的Δp,定义如下转换函数:
1e− − Silhouette ()k
Δ p = o δ k ⋅ ⋅ (7)
+
1e − Silhouette ()k
O={o k } 1×N 存放聚类中心标志,如果 o k =1,表明样本点 i 是聚类中心;否则,o k =−1.参数δ调整Δp 的变动幅度.引
入基于 Silhouette 计算的Δp,当算法产生至少一个聚类中心后,偏向参数动态赋权的 AP 算法更新公式如下:
r (, )i k = ⎧ s ( , ) max( ( , )ik − a i k′ s ( , ))ik′ +
⎪ k′≠ k
(, )k = ∑
′
⎪ ak max(0, ( , ))r k k
⎪ k′≠ k
⎪ ⎛ ⎞
(, )k =
⎪ ⎨ ai min 0, ( , )r k k + ⎜ ∑ max(0, ( , ))r k k ⎟ ′ (8)
⎪ ⎝ k′≠ , i k ⎠
⎪ 1e− − Silhouette () k
⎪ Δ p = o δ ⋅ ⋅
⎪ k 1e+ − Silhouette () k
⎪ (, )k = ( , )k k + Δ
⎩ sk s p k
偏向参数动态调整的 AP 算法在复杂度上与标准 AP 算法没有差别,但是因为考虑到了样本点之间的相互
作用关系,使得偏向参数能够即时反映样本点当前迭代时刻的状态.对于基于聚类划分的采样问题来说,期望得
到的代表点能够更大程度地覆盖原始数据的空间区域,包含更多数据密度较小区域的特异性样本,而引入偏向
参数的动态调整能够在一定程度上消除原始数据密度分布给初始偏向参数带来的影响,从而能够找到更多低
数据密度空间区域中的代表性样本.引入轮廓系数动态改变偏向参数后,算法过程如下.
算法 1. adjustPreferenceAP(S,P,λ,δ,maxiter,conviter).
输入:数据集相似度矩阵 S={s ij } N×N ,偏向参数 P={p 11 ,...,p NN },阻尼系数λ,变动幅度δ,
最大迭代次数 maxiter,最大收敛状态比较次数 conviter;
输出:聚类中心 classcenter.
init R←{0} N×N , A←{0} N×N
init E←{0} N×conviter
for curriter←1 to maxiter do
init R old ←R, A old ←A
update R and A according to Eq.(8) line 1~ line 3
R←(1−λ)×R+λ×R old
A←(1−λ)×A+λ×A old
init classcenter←{False} N×1 , centernum←0
for k←1 to N do
if R[k][k]+A[k][k]>0
classcenter[k]←True
centernum←centernum+1
end if
end for
E[:,curriter%conviter]←classcenter