基于哈希学习的投票样例选择算法

黄雅婕，翟俊海，2*，周 翔，李 艳，2，3

（1.河北大学数学与信息科学学院，河北保定 071002；2.河北省机器学习与计算智能重点实验室（河北大学），河北保定 071002；3.北京师范大学珠海校区应用数学与交叉科学研究中心，广东珠海 519087）

0 引言

据国际数据公司（International Data Corporation，IDC）发布的Data Age2025 预测，全球数据量将从2019 年的45 ZB 增至2025 年的175 ZB，相当于每天产生491 EB 的数据。到2025 年，平均每人至少每18 s 就会进行一次数据交互，预计到2025 年将创造超过90 ZB 的数据。每年国内春节前后，中国铁路输送旅客总人数达3.1 亿，每天保持在千万人以上，这就代表每天有千万人数在火车站通过人脸识别检票进站。每年双十一当天的淘宝交易量也非常可观，2020 年“双十一”在26 min 时迎来流量最高值，订单创建峰值达每秒58.3万笔，是2009 年第一次“双十一”的1 457 倍。如此庞大的数据量既是发展的机遇，也给数据相关部门带来了不小的挑战，数据从获取、解析、存储和运用等方面都给相关人员带来了巨大的难度，数据约简便是解决该问题的方法之一。数据约简分为特征选择和样例选择两种，分别从属性和样例两个维度对原始数据进行压缩，其中样例选择方法能够更有针对性地减少数据冗余和相似样例，因此本文对现有检索方法进行改进并应用于样例选择方向。

本文的主要工作包括以下几个方面：

1）提出了一种基于哈希学习的投票样例选择算法，通过对高维数据进行降维，然后利用聚类和矢量量化方法对数据进行分类，对每类进行投票样例选择，从而选取能够代替原数据的样例子集；

2）利用聚类方法对降维后的数据进行分类，同时用海明码表示，以便于数据相似度计算，利用矢量量化方法将数据的海明码用聚类的海明码表示，同一类型具有相同的海明码，便于识别同类数据；

3）多次对分类后的数据进行随机选择，最后对多次选择出的数据进行投票，票数达到设定值则选中为最终的样例，该方法能够通过调节阈值控制样例子集的数量。

1 相关工作

近年来许多研究学者针对样例选择方向提出了一些代表方法。如Aslani 等［1］针对支持向量机（Support Vector Machines，SVM）的计算和存储复杂度高的问题提出了一种利用局部敏感哈希（Locality-Sensitive Hashing，LSH）方法快速选取样例的算法。通过哈希映射寻找同类样例，能够快速找到相似和冗余的训练样本，以便将它们从原始数据集中排除，因此，通过减少相似训练样本的数量，能够在不显著降低泛化能力的情况下加快支持向量机的训练阶段。该方法复杂度为线性级，内存消耗低，通过调节输入参数，可轻松控制选取率，在时间和性能上都能很好地应对庞大的数据集。针对目前局部密度方法存在分类准确率低的问题，Malhat 等［2］提出了基于全局密度和增强全局密度的样例选择算法，利用关联函数和不相关函数来评估样例。关联函数用来确定k个有类标签的最邻近样例中至少有一个样例与被给定样例的类标签不同，不相关函数用来确定k个最近邻中可能对该样例错误分类的样例的数量。该方法更适用于两类分类问题，对于多类数据的效果有待提高。针对非平衡问题，Zhu等［3］提出了一种近邻引用计数方法，样例的重要性对应于近邻引用的计数。引用计数是由一个样例作为不同类样例的最近邻的次数所决定的，对于被引用次数非零的样例，样例的重要性与被引用次数成反比。对于非平衡数据集，选取和少数样例数量相同的多数样例来平衡数据分布。该方法的优点是可以在不编辑噪声的情况下选择重要样例，并且可以通用于非平衡和平衡数据集的情况。Kim 等［4］提出了一种基于期望边缘的模式选择算法，用于识别可能成为支持向量的模式。该算法只选择位于支持向量机边缘边界和边缘区域内的模式，对其他模式包括噪声支持向量进行分解。该算法的优势在于能够自动估计训练模式的边缘，不需人工设置参数，且只使用SVM 进行模式选择，不受其他算法的影响。Rico-Juan 等［5］提出了基于投票启发式的排序样例选择的方法，首先通过考虑投票策略中分类器的参数k来提高约简集对有噪数据的容忍度。此外，还提出了一种用于样例选择的自导向准则，减少了传统方法中对外部用户参数进行调优的需要。该方法在标签噪声较高的情况下增强了算法对标签噪声的鲁棒性，结合两种扩展方法可以得到更优秀的准确率。de Haro-García 等［6］提出一种利用Boosting 原理的样例选择方法，应用Boosting 来获得所选样例的子集以提高最近邻规则的分类边缘，从而优化了最近邻规则的准确性。该方法基于构造样例子集的方式，类似于增强分类器方法。当新样例被添加到选定的子集时，该算法实现了误差的自动校正。利用这种增强设置，该算法能够纠正由于样例逐步添加所带来的偏差。

对于高维数据处理问题，通常采用数据降维的方法将高维数据转换到低维数据，进而对低维数据进行相似度计算。极具代表性的方法便是局部敏感哈希方法，利用稳定分布对数据进行降维，然后用随机哈希函数对数据进行相似性映射，使得同类型的样例存放在同一个哈希桶，不同的样例存放在不同的哈希桶。但这种方法从属于数据独立方法，对哈希函数的依赖性高，同时具有很大的不确定性，随机哈希函数对数据的映射有较大的误差，因此需要对数据进行相似度计算，从而提高分类能力。而基于哈希学习的方法（也称为数据依赖方法）是将数据进行降维后直接对数据进行转换，在对数据进行分类时只需要使用海明距离进行异或操作就可以得到，因此计算速度能够得到较大提升。

局部敏感哈希方法是Har-Peled 等［7］为了解决直接在高维空间下查找相似点面临的维度灾难问题提出的。该算法的核心是利用哈希冲突寻找同类型的点，将高维空间上相似的点映射到海明空间中，然后利用海明距离将同类型的点映射到同一个哈希桶（buckets）中。Charikar［8］提出了舍入算法中的相似度估计技术（SimHash），该算法通过分词、映射、加权、合并和降维一系列操作来比较两个文本间的相似度。Manku 等［9］利用该算法实现了对搜索引擎爬虫系统的网页间的相似度估计，是SimHash 的著名应用之一。Datar 等［10］提出了基于P-stable 分布的局部敏感哈希算法，该算法能够直接在欧氏空间上进行计算。Durmaz 等［11］提出了一种随机分布式哈希方法，使用局部敏感哈希方法，将数据随机分布到集群上的不同节点。在每个节点中，使用相同的随机哈希函数集来索引本地数据。然后在不同的节点中对查询样本进行局部搜索。Li 等［12］提出了一种基于最小割超平面和集成学习的全局低密度局部敏感散列搜索算法，采用图切方法构造了一种全局低密度超平面候选集，采用最小信息增益法和随机最大熵法贪婪地选择超平面，采用集合学习方法查询全局近似最近邻数据。Gong 等［13］提出了一种迭代量化（Iterative Quantization，ITQ）思想，通过交替极小化方法来进行零中心数据的旋转，从而最大限度地减小将该数据映射到零中心二值超立方体顶点的量化误差。通过简单地旋转投影数据，可以大大提高基于主成分分析（Principal Component Analysis，PCA）的二进制编码方案的性能。该方法既适用于无监督数据嵌入如PCA，也适用于有监督数据嵌入如典型相关分析（Canonical Correlation Analysis，CCA），其所得到的二进制编码方法明显优于其他方法。该方法的局限性是每个数据维度的投影只用一个比特，不能使用比数据维度更多的位，并且在使用足够的位时才能收敛到未压缩数据的性能。Deng 等［14］提出了一种自适应多比特量化哈希算法，利用聚类方法和不完全编码的方式相结合解决了目前相同比特编码方式带来的误差，有效纠正了目前单比特编码方法中存在的忽略数据近邻结构的问题。He 等［15］提出了一种采用k均值量化的哈希方法，在不查阅表的情况下近似码字之间的欧氏距离。样本量化后的类中心距离代表样本之间的距离，用海明码来表示前一步样本量化后的类中心，中间用最优化函数联系起来，保证目标函数的误差达到最小，最后采用海明码来表示类中心。该算法同时具有矢量量化方法的准确性和基于海明码的速度优势。沈琳等［16］对深度学习哈希方法进行了详细的综述。

近年来基于哈希方法的应用层出不穷。朱茂然等［17］提出了一种基于深度哈希的相似图片推荐系统，能够有效进行图片解析，计算图片相似性并排序。基于神经网络无监督学习的特点使该推荐系统能够实时捕捉用户视觉偏好信息进行精准营销，能够综合图片布局、色彩和色调等深层次信息，从视觉信息角度返回优质检索结果。林计文等［18］提出了一种面向图像检索的深度汉明嵌入哈希编码方式，在深度卷积神经网络的末端插入一层隐藏层，依据每个单元的激活情况获得图像的哈希编码；同时根据哈希编码本身的特征提出汉明嵌入损失，更好地保留原数据之间的相似性。该方法能够提升图像检索性能，较好改善短编码下的检索性能。

本文提出了一种基于哈希学习的投票样例选择算法。首先，将数据从高维空间映射到低维空间；然后，利用k-means 聚类思想结合矢量量化方法对数据进行分类；最后，对每个类中按比例多次随机选取样例，投票选择出最终具有代表性的样例子集。

2 基于k-means的哈希学习方法

2.1 矢量量化方法

矢量量化（Vector Quantization，VQ）方法［11］是一种有损压缩技术，在信号处理以及数据压缩等领域应用广泛，其优点是压缩比高、解码简单且能够很好地保留信号的细节。矢量量化方法是将一个向量空间中的点用其中的一个有限子集来进行编码的过程。矢量量化的基本原理是将输入矢量用码书中与之最匹配的码字的索引代替原输入，从而进行传输与存储，并且仅需要简单地查找表便可进行解码。

矢量量化是标量量化思想的一种推广，两种分量间存在4 种相互关联的性质：线性依赖性、非线性依赖性、概率密度函数的形状以及矢量维度。矢量量化的作用就是去掉数据之间的这些冗余，更好地压缩数据。

2.2 k-means算法

k-means 算法是经典的聚类算法，利用设定值k将样本通过迭代的方式按样本间的距离进行聚合，形成k个簇，每一簇便为一类。由于该算法比较稳定，速度较快并且误差较小，因此被广泛应用。k-means 算法如下：

2.3 基于k-means的哈希学习方法

基于k-means 的哈希学习方法结合了矢量量化方法和海明距离计算的优点，是经典的学习型哈希检索方法。对于给定的样本集合，该算法首先利用典型的哈希降维方法将高维特征变换到低维空间，根据当前维度需要的比特数决定相应个数的聚类中心，采用完全编码方式即b个比特位形成2b个聚类中心。然后按照向量量化思想指定每一个样本点和离它最近的聚类中心是同一类的，应该有相同的哈希编码，聚类中心通过k-means 聚类得到。接着按照矢量量化方法的思想，将任意两个样本之间的距离用其聚类中心的欧氏距离度量，而每个聚类中心又由唯一的哈希码确定，即任意两点间的距离可由其对应的聚类中心的哈希码间的海明距离确定，其关系满足下式：

其中：d(x，y)表示两点间的欧氏距离；ci(x)和ci(y)表示数据x和y的聚类中心；i和j表示x和y对应聚类中心的哈希码；d(i(x)，i(y)) 表示两点对应聚类中心的哈希码间的海明距离。

式（1）又可以用海明距离近似得到式（2）：

其中dh(i(x)，i(y))表示海明距离。式（2）可进一步记为：

其中：s是一个恒定的常数；是海明距离的均方根。

上述过程的量化误差为同一类的样本点和该类聚类中心之间的距离，距离越近越好，因此量化误差应该越小越好，可以表示为：

另外还需考虑聚类中心间的近似拟合误差，近似拟合误差意为原始空间中相近的聚类中心编码后在海明空间的海明距离，因此该误差也应该越小越好，表示为：

综合量化误差和近似拟合误差两种，可以得到目标函数如式（6）：

其中：λ为一常数，一般λ=10。

求解过程分为两步：1）更新样本编码和更新聚类中心；2）进行迭代求解。

聚类中心cj的更新如式（7）所示：

其中，wij=ninj/n2；ni和nj分别表示属于i和j类的样例个数。

2.4 采样方法

由于现有数据集的数量大多都是非常庞大的，无法对整个数据集进行直接建模，或者处理效率低下，非常影响现实问题的解决效率。对数据进行采样来改变数据集的大小，用少量的样本拟合数据的分布从而代表原数据，能够有效解决以上问题。好的采样样本应该能够覆盖原数据高概率的区域，并且相互独立。常用的采样方法有随机采样、接受-拒绝采样、重要性采样-加权采样等。

1）随机采样，即按照目标的分布函数进行采样。

2）接受-拒绝采样，即给定目标分布p(x)，对任意的x选取采样分布q(x)，选取一个包络函数使得p(x)≤M·q(x)。

3）重要性采样-加权采样。

对于目标分布p(x)，计算p(x)的期望，即：

E|f|=∫f(x)p(x)dx

3 基于哈希学习的投票样例选择算法

对于样例检索方法，基于海明距离的检索方法检索速度快，而矢量量化方法是基于查找表的，效果比基于距离的好。为了结合两种方法的优点，提出了一种改进样例选择方法。

本文算法分三个部分：首先是数据降维阶段，对于给定的样本集合采用典型的PCA 方法对数据进行降维，将高维数据投影到低维空间，利用矢量量化方法将量化后的类中心距离定义为样例之间的距离；然后进入样本编码学习阶段，采用k-means 聚类方法将样例分配给最近的聚类中心，并将聚类中心的哈希码赋值给该样例，直到类中心不再变化；最后，是样例选择阶段，对每一类的样例按比例进行多次随机选择，再对多次选择后的样例进行投票，从而选择出最有代表性的样例。由于本文算法仅需对数据集处理m次，每次对整个数据集进行遍历，m远小于n，所以算法的时间复杂度可达到O（n）。

4 实验与结果分析

为了验证本文算法的有效性，在3 个服从高斯分布的人工数据集和4 个UCI 数据集上进行了实验，为了方便展示，将本文算法记为LH-VIS（Voting Instance Selection algorithm based on Learning to Hash），并与经典的压缩近邻（Condensed Nearest Neighbor，CNN）算法［19］和文献［20］中的大数据线性复杂度样例选择算法LSH-IS-F（Instance Selection algorithm by Hashing with two passes）进行了比较。实验指标为测试精度、压缩比和运行时间。

压缩比度量的是原数据集与经过样例选择后的数据子集之间的比值，代表数据被压缩的比例，选择后的样例子集越小代表数据压缩比例越高，也就是压缩比越小，代表样例选择算法的性能越好。

测试精度指的是将原数据集划分成训练集和测试集，利用训练集经过样例选择后的数据子集训练分类器，用测试集测试该分类器的测试精度，当测试精度值越高时，则说明样例选择算法的性能越好，即所选样例能够在能力保持的情况下对数据集具有一定的代表性。

运行时间指的是从样例选择算法开始到算法执行完毕花费的时间，运行时间与算法的时间复杂度有关，运行时间越短代表样例选择算法的性能越好。

实验所用的三个人工数据集相应的概率分布在表1 中给出，7 个数据集的基本信息在表2 中给出。上述三种算法在相同环境下进行样例选择得到的测试精度、压缩比和运行时间如表3 所示。从表3 可以看出，从运行时间方面，在7 个数据集上本文算法LH-VIS 的执行时间均少于CNN 算法和LSH-IS-F 算法的执行时间，其原因是：LH-VIS 是对数据降维后直接将数据用海明码表示，利用海明距离进行相似度度量，海明距离计算相似度只需要异或操作；而LSH-IS-F 是利用随机哈希函数对数据进行映射，然后用欧氏距离进行相似度度量，所以LH-VIS 在时间上优于LSH-IS-F；而CNN 算法作为经典算法在规模较小和较为简单的数据集的所需时间较少，但是在处理规模较大和较为复杂的数据集时，所花费的时间大于本文算法。

表1 三个人工数据集相应的概率分布Tab.1 Corresponding probability distribution of three synthetic datasets

表2 实验所用7个数据集的基本信息Tab.2 Basic information of 7 datasets used in experiments

表3 三个算法在7个数据集上的测试精度、压缩比和运行时间比较Tab.3 Comparison of test accuracy，compression ratio and running time of 3 algorithms on 7 datasets

在压缩比方面，由于LH-VIS 在投票样例选择阶段可以通过调节参数控制样例选择的比例，压缩比可调节，所以LH-VIS 在压缩比方面优于CNN 算法和LSH-IS-F 算法，较两个对比算法平均提升了19%。

在测试精度方面，本文算法LH-VIS 的测试精度在大部分数据集上都能够高于另外两个算法，由于基于哈希学习的样例选择方法是通过学习的方式得出哈希函数，哈希函数来源于数据本身，所以分类准确率高。

5 结语

本文提出了一种基于哈希学习的投票样例选择算法，将数据从高维空间映射到低维空间，然后利用k-means 聚类结合矢量量化思想对数据进行分类，最后对每个类中按比例多次随机选取样例，投票选择出最终具有代表性的样例子集。

本文提出的算法有如下几个优点：1）原理简单，易于实现；2）运行时间短，训练速度快；3）压缩比可控；4）选择的样例质量高。

本文也存在一些可以改进的内容：1）算法对每个维度单独量化的方法可能忽略了数据的内在联系，不能很好地对数据进行映射；2）算法只利用了一种哈希学习方法进行组合选择，集成效果相对单一。

后续的工作有两个方向：一是可以参考多比特量化方法，考虑不同维度间的内在联系，从更合理地设置比特位的角度改进算法；二是可以结合其他哈希学习方法，利用多个哈希学习方法同时进行投票样例选择，预期效果会优于单一方法。