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

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

enhancement with the proposed new method, the trained model performance using similar number of training samples can be significantly
improved compared to traditional data enhancement strategies.
Key words: data sampling; affinity propagation; dynamic weighting; incremental sampling; data augmentation

现代信息技术的不断发展和进步,使各个领域累计了大量的数据,广泛涉及图像、文本、音频以及其他各
类非结构化数据等.面对海量规模增长的数据内容,如何更有效地平衡信息获取的效率和有效性,正成为大数据
处理的新重要问题.数据采样(data sampling)技术是一种能够在一定程度上解决上述问题的手段之一,该技术考
虑从数据集中选取有代表性的样本作为整个数据集合的代表,在减小数据规模的同时,最大可能地保留数据集
的有用信息,从而精简地表达数据集合包涵的重点知识.
当前,与数据集代表点采样相关的研究更多的是围绕图像数据.文献[1]提出了多字典不变稀疏编码方法,在
不依赖人工标记、种子图像或其他先验知识的情况下,采集互联网上的代表性商标图像,为商标识别、商标侵
权检测、品牌保护等领域自动提供原型、代表性图像或弱标签训练图像.文献[2]使用图像位置信息和图像相关
标记,基于上下文和内容挖掘与位置和标记视觉相关联的图像,结合 k-means 聚类方法从视觉相关图像中选择
代表性图像,为世界著名标志性建筑提供浏览摘要.文献[3]基于情感特征生成图像摘要,通过概率情感模型提取
输入图像情感特征,在情感空间中对图像做聚类处理,结合覆盖性、情感一致性和显著性对簇排序并选择代表
性图像.文献[4]提出一种区别于大多数利用视觉特征系统的基于语义知识的图像集合摘要方法,其通过图像间
的语义相似度构建语义相关性网络,依据网络中心性选择代表性图像.文献[5]将图像自动摘要问题看作稀疏表
示的字典学习问题,将图像摘要任务看作是字典学习任务,去实现大规模图像数据集的代表性图像选择.
现有的代表点采样方法大多基于聚类 [6−9] 方法,通常可抽象为 3 个步骤:(1) 用一组特征向量来表示数据集
中的样本点,数值类型数据应用简单处理可转化为特征向量,图像数据则根据自身特点结合特征提取方法表示
为一组高维特征向量;(2) 在特征向量空间中,采用聚类方法将样本点划分为若干簇;(3) 利用样本点代表性排
序方法,从簇中选择具有代表性的样本.代表点采样方法可以从数据表示、聚类方法和代表点选择方法这 3 个
方面进行研究.针对样本点聚类和代表点排序,常用的方法是使用 AP(affinity propagation)算法 [6,7,10,11] 进行代表
点的选择.与传统聚类算法相比,AP 算法不需要预先设定聚类个数,对初始值不敏感,并且其生成的聚类中心是
数据集中真实存在的样本点,不仅具有很好的代表性,且可以直接将聚类中心当作簇代表点.尽管 AP 算法在处
理许多问题上具有优势,但它一个较大的不足是算法复杂度较高,在 Frey 等人所做的代表性灰度图像选择实验
中 [12] ,运行 1 次 AP 算法所消耗的时间与运行 100 次 k-center 算法所消耗的时间基本相同.与 K-means 算法相比,
AP 算法的时间复杂度正比于数据规模的平方,而 k-means 算法的时间消耗则是线性增长.当数据规模较大时,
AP 算法的计算时间将很长,且对存储空间要求也呈平方规模增长,这极大地限制了 AP 算法应用于大规模数据
处理的实用性.
针对大规模数据的代表点采样问题,本文提出了一种基于动态赋权近邻传播的数据增量采样算法 ISAP
(incremental data sampling using affinity propagation with dynamic weighting).主要包含两个策略.
(1) 近邻传播偏向参数的动态赋权.在 AP 算法的迭代过程中,利用样本点单次迭代聚类结果计算样本点
自身轮廓系数,对 AP 算法的重要参数——偏向参数做动态调整,使最终采样结果能够包含更多的潜
在性样本;
(2) 引入分层增量处理,将数据集划均匀划分为规模适中的子集,在各子集上分别执行全局偏向参数动态
赋权的 AP 算法,获得局部最优代表点集合;然后在局部最优代表点集合上执行局部偏向参数动态赋
权的 AP 算法,推选出整个数据集的最终代表点.
相比于现有的主要增量采样算法 [13,14] ,它们的主要目的在于实现数据密度上的均匀采样.而 ISAP 算法目的
在于实现数据空间上基于聚类划分的代表性样本获取.
为检验 ISAP 算法的性能及其在图像数据应用问题的价值,我们分别在人工合成数据集、UCI 标准数据集
和图像数据集上进行了代表性样本采样任务,对比一些经典的和较新的方法,结果表明:我们的方法与现有相关
方法在采样划分质量上处于同一水平,而计算效率则获得了大幅提升.进一步将新方法应用于深度学习的数据