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

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

1
n
calculate global similarity matrix SG N×N base D ∪…∪D
calculate global preference PG 1×N base θ and SG according to Eq.(1)
for i←1 to n do
i
M←|D |
calculate similarity matrix S M×M base D 1 M× i
S[S<θ]←0
i
init PG ←∅
for j←1 to M do
i
add PG[D [j]] to PG i
end for
i
i
R ←adjustPreferenceAP(S,PG ,λ,δ,maxiter,conviter)
end for
init R←∅
for i←1 to n do
i
for j←1 to |R | do
i
add R [j] to R
end for
end for
K←|R|
calculate lobal similarity matrix SL K×K base R
SL[SL<θ]←0
calculate lobal preference PL 1×K base θ and SL according to Eq.(1)
R′←adjustPreferenceAP(S,PL,λ,δ,maxiter,conviter)
init Cluster←{{∅}} 1×|R′| , NR←D\R′
for r←1 to |R′| do
add R′[r] to Cluster[r]
end for
for i←1 to |NR| do
c←argmax r∈1,…,|R′| (SG[NR[i]][R′[r]])
add NR[i] to Cluster[c]
end for
return R′, Cluster
选出数据集的整体代表点后,如果需要实现单簇多代表点的选择,则可依据最大相似度将非代表点分配给
一个代表点,完成基于最大相似度分配的全局簇划分.然后依据最终的簇划分,在每个簇中选取一组点放入代表
点集.
4 算法分析

2
假设数据集被划分为 K 个规模为 M 的子集(K<<M),对各子集执行 AP 算法的时间复杂度为 O(M logM),时
2
间总和为 t 1 =O(KM logM).假设各子集推选出的平均局部代表点数与子集规模 M 的比例为ρ(0<ρ<<1),即各子集
推选出的平均局部代表点数为ρ⋅M,则局部代表点总数为ρ⋅K⋅M.在局部代表点集合上再次执行 AP 算法的时间
2
2
2
为 t 2 =O(ρ K M logρKM),因此分层增量采样方法耗费的总时间为 t 1 +t 2 .需要明确的是:子集规模 M 要远大于子集
个数 K,子集推选出的平均局部代表点数与子集规模的比例ρ是一个大于 0 且远小于 1 的数.因此,子集规模是对