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

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

算法时间消耗影响最大的因素.在数据集规模不变的情况下,可以推算(t 1 +t 2 )正比于 MlogM,而标准 AP 算法处理
2
2
相同规模数据的时间复杂度为 O(K M log(KM)),显然,分层增量采样方法的效率更高.
2
在各子集上执行 AP 算法的空间复杂度为 O(M ),每一次增量推选过程中消耗的存储空间不变,因此增量执
2
行 K 次规模为 M 的 AP 算法的空间消耗为 s 1 =O(M ).依照上述设定,在局部代表点数为ρ⋅K⋅M 的情况下,在局部
2
2
2
2
2
2
代表点集上执行 AP 算法的空间消耗为 s 2 =O(ρ K M ),因此分层采样方法的空间复杂度为 O(ρ K M ).而标准 AP
2
2
算法的空间复杂度为 O(K M ).ρ是一个大于 0 且远小于 1 的数,因此分层增量采样方法在空间上的消耗同样优
于标准 AP 算法.分层增量采样方法在时间效率和存储空间方面均可以得到提升.
相比于标准的 AP 算法,ISAP 中引入了大规模数据的分层处理策略,在第 1 层处理中对原始数据进行一次
局部约简处理后,仅选取部分代表性数据参与第 2 层的再处理,从理论上看,可能会造成代表性数据对原始数据
信息携带不足的问题,进而导致最终采样得到的代表性样本在全局上的偏离问题.虽然如此,结合我们以前的相
关研究 [21,22] 发现:在增量学习过程中,如果阶段性选择的代表点集能够构成对目标问题解的一个整体有效的表
达,那么在增量过程中逐步筛选掉非代表性样本,仅基于保留下来的数据参与后续处理的做法,理论上在一定条
件下可以达到与全局方法的一致.
具体到 ISAP 算法,考虑在第 1 层处理后保留的局部代表性样本集是在整体上对原始数据空间区域进行代
表性表达,而非数据密度上的约简采样.这样,AP 算法自身的特性就显得非常有优势,不仅可以有效地约简冗余
数据,减少计算量,而且能够一定程度上解决原始数据空间中局部数据密度可能存在较大程度不平衡的问题,以
使得最终得到的采样结果更优.

5 实验分析

本文提出的代表点采样方法基于 AP 聚类,为检验算法有效性,同样与基于 AP 的其他聚类方法进行比较,
几种比较方法如下.
(1) 标准 AP 算法的代表点采样:使用文献[12]提出的标准 AP 算法来做代表点选取;
(2) 分层近邻传播算法 HAP 的代表点采样:使用文献[23]提出的一种基于底层推举和上层推举的层次 AP
算法来做代表点选取.该方法同样采用分层的策略,底层基于标准 AP 算法,上层基于自适应 AP 算法;
(3) 近邻赋值的增量式 AP 聚类算法 IAPNA 的代表点采样:使用文献[16]提出的一种增量式 AP 算法来做
代表点选取.该方法通过近邻赋值构建新增数据与已有数据之间的消息传递关系,增量式地扩充吸引
度和归属度矩阵,直至方法收敛得到结果.
相关算法实验中,首先需要计算样本点 i 和 j 之间的相似度 s(i,j),s(i,j)的值越大,表示两个样本越相近.实验
中,对两个样本点间的相似度 s(i,j)采用归一化计算定义:
max( )D − d ( , )i j
(, ) j =
si (9)
max( ) min( )− D
D
D={d(i,j)}是样本点之间的欧式距离矩阵,max 和 min 操作分别表示取矩阵元素中的最大值和最小值.上式
计算后,两个样本点完全相同时的相似度为 1,完全不同时的相似度为 0.
实验中,参考各自算法特点和相关文献,AP 算法的偏向参数取相似度矩阵中位值;对于 IAPNA 方法参数 pc,
根据算法输出簇数和采样质量选取对比选取;对于 ISAP 算法中的截断参数θ和变动幅度参数δ,一方面也可类似
地根据算法输出簇数和采样质量选取对比选取,其中的采样质量可以是使用有监督的交叉验证选取;或者使用
无监督的质量指标(如代表点间平均欧式距离)作为参照.
此外,截断参数θ一定程度上反映了数据点间距离度量合理性的界限范围,而变动幅度参数δ是从微观上对
−2
偏向参数进行调整,解释样本点对于轮廓系数的学习能力.由此,取θ选择范围可取[10 ,max(D)],δ选择范围可设
−3
−1
定为[10 ,10 ],其中,max(D)同公式(9)中的含义.
5.1 评价指标
实验从聚类质量、采样质量和方法效率这 3 个方面对代表点采样方法进行评价.标准化互信息(normalized