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

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

2 AP 算法中偏向参数的动态赋权

AP 算法 [12] 是一种 exemplar-based 聚类方法,它将所有数据样本看作是网络中的节点,通过节点间的双向消
息传递,收敛得到最优的簇代表点集合.AP 算法与其他聚类方法的最大不同点是:其生成的聚类中心是数据集
中真实存在的样本,具有很好的代表性,可以直接作为簇的代表点.
在基于聚类方法的代表点采样问题中,聚类质量与代表点采样质量紧密相关,聚类质量的提升,在一定程度
上能够解决采样结果的代表性问题.AP 算法改善聚类质量的一个方向是偏向参数,偏向参数直接影响最终聚类
数目,决定聚类质量的好坏.偏向参数一般根据经验设置为统一常数 [12,15,16] ,在 AP 算法的迭代过程中恒定不变,
即所有样本点成为簇代表点的可能性从始至终是一样的.但是在实际情况中,样本点之间的差异使得它们成为
簇代表点的可能性不尽相同;此外,在迭代过程中因为信息交换的影响,样本点成为簇代表点的概率是会变动
的.因此,给所有样本点设置同样且恒定的偏向参数的做法并不恰当,容易导致不好的聚类结果.为便于后续讨
论,表 1 中汇总给出了本小节与新方法有关的符号信息.
Table 1 Summary of relevant symbols on chapter 2
表 1 第 2 节新方法相关符号汇总
符号 意义
P={p k} 1×N 输入 AP 算法的偏向参数
S={s(i,j)} N×N 输入 AP 算法的相似度矩阵
θ 相似度截断值
R={r(i,j)} N×N 吸引度
A={a(i,j)} N×N 归属度
Silhouette(i) 一个样本点的轮廓系数
Δp k 样本点的偏向参数变动量
O={o k} 1×N 聚类中心标识

2.1 初始偏向参数定义

在实际问题中,根据局部密度、语义性等信息可以知道,样本点成为簇代表点的可能性是有区别的,所以将
偏向参数 P={p k } 1×N 设置为统一常数的做法并不恰当.
为了充分考虑数据本身所蕴含的信息,减少信息迭代中不必要的计算,文献[17,18]依据数据集中样本点的
分布情况,为每个样本赋予不同的初始偏向参数.本文方法仅考虑样本点在局部范围内与其他样本之间的平均
相似度,不考虑比例系数的影响,采用如下初始偏向参数计算公式:
∑ (( , )s i k ⋅ ( I cutoff ))
p = ik≠ (1)
∑ ik≠ ( I cutoff )
k
其中,
• I(⋅)为指示函数;
• 参数 cutoff 表示不等式 s(i,k)≥θ的结果:如果 s(i,k)≥θ成立,则 I(cutoff)=1;否则为 0.
参数θ定义为相似度截断值,其大小的设置与数据集所有样本点间的相似度紧密程度相关,其在某种程度
上也反映了原始距离度量 s(⋅,⋅)的上限合理尺度.

2.2 偏向参数动态赋权
标准 AP 算法的输入是相似度矩阵 S={s(i,j)} N×N 以及包含在 S 中的偏向参数 P={p k } 1×N (s(k,k)←p k ),p k 表示
样本点 k 被选为聚类中心的可能性.对于 N 个样本点的聚类问题,AP 算法旨在找到一组聚类中心,将每一个非中
心点分配给唯一的聚类中心,以便最大化非中心点和其聚类中心之间的相似性以及各聚类中心的偏向参数的
总和.一种典型的 AP 算法二元变量因子图 [12] 如图 2(1)所示.