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

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

if centernum>0
init C←{0} 1×N
for k←1 to N do
C[k]←argmax j (R[k][j]+A[k][j])
end for
for k←1 to N do
calculate Δp according to Eq.(8) line 4
update S[k][k]←S[k][k]+Δp
end for
end if
if curriter≥conviter
conver←judge convergence by E (True or False)
if (conver and centernum) or (curriter=maxiter)
return classcenter
end if
end if
end for

3 分层增量采样

AP 算法中,聚类中心为真实样本点这一特性,使得其非常适用于代表点的采样.但是标准 AP 算法的复杂度
较高,不适用于大规模数据的代表点采样.本文结合分层及增量处理的采样策略,基于上述偏向参数的动态赋权
AP 算法,实现对数据集的高效采样,以期实现处理效率和采样质量的更好兼顾.
本文提出的分层增量采样方法框架如图 1 所示,是一层增量局部推选加一层合并推选的“1+1”模式的采样.
算法的输入为已划分好的子集序列,为了保证算法的计算效率,各子集的规模要相同或相近,可以采用顺序划分
或随机采样划分的方法.
2
n
1
将数据集划分为规模适中的子集{D ,D ,…,D },分层增量采样的第 1 层(增量局部推选)依次处理样本子集
i
i
D ,选出基于全局偏向参数信息和局部相似度信息的子集代表点 R ={r i1 ,r i2 ,…,r ix },构成子集代表点集 R.第 2 层
(合并推选)完全基于 R 的全局信息,即数据集的局部信息,从 R 中挑选出数据集的整体代表点 R′ {, ,..., }rr ′ = ′ r′ .
1 2 k
在增量局部推选层中,为了将更多的潜在代表点挑选出来,需要考虑数据集的全局相似度信息.因此,将样
本点基于整个数据集中的全局初始偏向参考度作为 AP 算法的输入.依据公式(1)计算数据集的全局偏向参数
i
PG={pg kk },每个子集的全局偏向参数集合为 PG .
合并推选层采样是对增量局部推选层采样结果的合并推选.在第 1 层中已经基于全局偏向参数获得了所
有潜在的整体代表点组成局部代表点集,在第 2 层采样中,只需基于局部代表点集的全部相似度信息,即整体数
据集的局部节点之间的相似度信息进行潜在代表点的采样选择,其中,仍采用公式(1)初始化其中局部代表点集
相对于整体数据集的局部偏向参数 PN={pn kk }.
结合截断值参数θ的引入,本文方法可考虑对原始的所有数据点间的相似度矩阵进行约简,将小于相似度
截断值的边进行删除,进而达到约简相似度矩阵的目的,加速 AP 算法的计算效率.综前所述,可归纳给出如下的
综合算法过程.
n
2
1
算法 2. ISAP({D ,D ,…,D },θ,λ,δ,maxiter,conviter).
2
1
n
输入:子集序列 D ,D ,…,D ,相似度截断值θ,阻尼系数λ,变动幅度δ,
最大迭代次数 maxiter,最大收敛状态比较次数 conviter;
输出:代表点集 R′,全局划分 Cluster.