黃雅婕，翟俊海，2*，周 翔，李 艷，2，3

（1.河北大學數學與信息科學學院，河北保定 071002；2.河北省機器學習與計算智能重點實驗室（河北大學），河北保定 071002；3.北京師范大學珠海校區(qū)應用數學與交叉科學研究中心，廣東珠海 519087）

0 引言

據國際數據公司（International Data Corporation，IDC）發(fā)布的Data Age2025 預測，全球數據量將從2019 年的45 ZB 增至2025 年的175 ZB，相當于每天產生491 EB 的數據。到2025 年，平均每人至少每18 s 就會進行一次數據交互，預計到2025 年將創(chuàng)造超過90 ZB 的數據。每年國內春節(jié)前后，中國鐵路輸送旅客總人數達3.1 億，每天保持在千萬人以上，這就代表每天有千萬人數在火車站通過人臉識別檢票進站。每年雙十一當天的淘寶交易量也非?？捎^，2020 年“雙十一”在26 min 時迎來流量最高值，訂單創(chuàng)建峰值達每秒58.3萬筆，是2009 年第一次“雙十一”的1 457 倍。如此龐大的數據量既是發(fā)展的機遇，也給數據相關部門帶來了不小的挑戰(zhàn)，數據從獲取、解析、存儲和運用等方面都給相關人員帶來了巨大的難度，數據約簡便是解決該問題的方法之一。數據約簡分為特征選擇和樣例選擇兩種，分別從屬性和樣例兩個維度對原始數據進行壓縮，其中樣例選擇方法能夠更有針對性地減少數據冗余和相似樣例，因此本文對現有檢索方法進行改進并應用于樣例選擇方向。

本文的主要工作包括以下幾個方面：

1）提出了一種基于哈希學習的投票樣例選擇算法，通過對高維數據進行降維，然后利用聚類和矢量量化方法對數據進行分類，對每類進行投票樣例選擇，從而選取能夠代替原數據的樣例子集；

2）利用聚類方法對降維后的數據進行分類，同時用海明碼表示，以便于數據相似度計算，利用矢量量化方法將數據的海明碼用聚類的海明碼表示，同一類型具有相同的海明碼，便于識別同類數據；

3）多次對分類后的數據進行隨機選擇，最后對多次選擇出的數據進行投票，票數達到設定值則選中為最終的樣例，該方法能夠通過調節(jié)閾值控制樣例子集的數量。

1 相關工作

近年來許多研究學者針對樣例選擇方向提出了一些代表方法。如Aslani 等［1］針對支持向量機（Support Vector Machines，SVM）的計算和存儲復雜度高的問題提出了一種利用局部敏感哈希（Locality-Sensitive Hashing，LSH）方法快速選取樣例的算法。通過哈希映射尋找同類樣例，能夠快速找到相似和冗余的訓練樣本，以便將它們從原始數據集中排除，因此，通過減少相似訓練樣本的數量，能夠在不顯著降低泛化能力的情況下加快支持向量機的訓練階段。該方法復雜度為線性級，內存消耗低，通過調節(jié)輸入參數，可輕松控制選取率，在時間和性能上都能很好地應對龐大的數據集。針對目前局部密度方法存在分類準確率低的問題，Malhat 等［2］提出了基于全局密度和增強全局密度的樣例選擇算法，利用關聯(lián)函數和不相關函數來評估樣例。關聯(lián)函數用來確定k個有類標簽的最鄰近樣例中至少有一個樣例與被給定樣例的類標簽不同，不相關函數用來確定k個最近鄰中可能對該樣例錯誤分類的樣例的數量。該方法更適用于兩類分類問題，對于多類數據的效果有待提高。針對非平衡問題，Zhu等［3］提出了一種近鄰引用計數方法，樣例的重要性對應于近鄰引用的計數。引用計數是由一個樣例作為不同類樣例的最近鄰的次數所決定的，對于被引用次數非零的樣例，樣例的重要性與被引用次數成反比。對于非平衡數據集，選取和少數樣例數量相同的多數樣例來平衡數據分布。該方法的優(yōu)點是可以在不編輯噪聲的情況下選擇重要樣例，并且可以通用于非平衡和平衡數據集的情況。Kim 等［4］提出了一種基于期望邊緣的模式選擇算法，用于識別可能成為支持向量的模式。該算法只選擇位于支持向量機邊緣邊界和邊緣區(qū)域內的模式，對其他模式包括噪聲支持向量進行分解。該算法的優(yōu)勢在于能夠自動估計訓練模式的邊緣，不需人工設置參數，且只使用SVM 進行模式選擇，不受其他算法的影響。Rico-Juan 等［5］提出了基于投票啟發(fā)式的排序樣例選擇的方法，首先通過考慮投票策略中分類器的參數k來提高約簡集對有噪數據的容忍度。此外，還提出了一種用于樣例選擇的自導向準則，減少了傳統(tǒng)方法中對外部用戶參數進行調優(yōu)的需要。該方法在標簽噪聲較高的情況下增強了算法對標簽噪聲的魯棒性，結合兩種擴展方法可以得到更優(yōu)秀的準確率。de Haro-García 等［6］提出一種利用Boosting 原理的樣例選擇方法，應用Boosting 來獲得所選樣例的子集以提高最近鄰規(guī)則的分類邊緣，從而優(yōu)化了最近鄰規(guī)則的準確性。該方法基于構造樣例子集的方式，類似于增強分類器方法。當新樣例被添加到選定的子集時，該算法實現了誤差的自動校正。利用這種增強設置，該算法能夠糾正由于樣例逐步添加所帶來的偏差。

對于高維數據處理問題，通常采用數據降維的方法將高維數據轉換到低維數據，進而對低維數據進行相似度計算。極具代表性的方法便是局部敏感哈希方法，利用穩(wěn)定分布對數據進行降維，然后用隨機哈希函數對數據進行相似性映射，使得同類型的樣例存放在同一個哈希桶，不同的樣例存放在不同的哈希桶。但這種方法從屬于數據獨立方法，對哈希函數的依賴性高，同時具有很大的不確定性，隨機哈希函數對數據的映射有較大的誤差，因此需要對數據進行相似度計算，從而提高分類能力。而基于哈希學習的方法（也稱為數據依賴方法）是將數據進行降維后直接對數據進行轉換，在對數據進行分類時只需要使用海明距離進行異或操作就可以得到，因此計算速度能夠得到較大提升。

局部敏感哈希方法是Har-Peled 等［7］為了解決直接在高維空間下查找相似點面臨的維度災難問題提出的。該算法的核心是利用哈希沖突尋找同類型的點，將高維空間上相似的點映射到海明空間中，然后利用海明距離將同類型的點映射到同一個哈希桶（buckets）中。Charikar［8］提出了舍入算法中的相似度估計技術（SimHash），該算法通過分詞、映射、加權、合并和降維一系列操作來比較兩個文本間的相似度。Manku 等［9］利用該算法實現了對搜索引擎爬蟲系統(tǒng)的網頁間的相似度估計，是SimHash 的著名應用之一。Datar 等［10］提出了基于P-stable 分布的局部敏感哈希算法，該算法能夠直接在歐氏空間上進行計算。Durmaz 等［11］提出了一種隨機分布式哈希方法，使用局部敏感哈希方法，將數據隨機分布到集群上的不同節(jié)點。在每個節(jié)點中，使用相同的隨機哈希函數集來索引本地數據。然后在不同的節(jié)點中對查詢樣本進行局部搜索。Li 等［12］提出了一種基于最小割超平面和集成學習的全局低密度局部敏感散列搜索算法，采用圖切方法構造了一種全局低密度超平面候選集，采用最小信息增益法和隨機最大熵法貪婪地選擇超平面，采用集合學習方法查詢全局近似最近鄰數據。Gong 等［13］提出了一種迭代量化（Iterative Quantization，ITQ）思想，通過交替極小化方法來進行零中心數據的旋轉，從而最大限度地減小將該數據映射到零中心二值超立方體頂點的量化誤差。通過簡單地旋轉投影數據，可以大大提高基于主成分分析（Principal Component Analysis，PCA）的二進制編碼方案的性能。該方法既適用于無監(jiān)督數據嵌入如PCA，也適用于有監(jiān)督數據嵌入如典型相關分析（Canonical Correlation Analysis，CCA），其所得到的二進制編碼方法明顯優(yōu)于其他方法。該方法的局限性是每個數據維度的投影只用一個比特，不能使用比數據維度更多的位，并且在使用足夠的位時才能收斂到未壓縮數據的性能。Deng 等［14］提出了一種自適應多比特量化哈希算法，利用聚類方法和不完全編碼的方式相結合解決了目前相同比特編碼方式帶來的誤差，有效糾正了目前單比特編碼方法中存在的忽略數據近鄰結構的問題。He 等［15］提出了一種采用k均值量化的哈希方法，在不查閱表的情況下近似碼字之間的歐氏距離。樣本量化后的類中心距離代表樣本之間的距離，用海明碼來表示前一步樣本量化后的類中心，中間用最優(yōu)化函數聯(lián)系起來，保證目標函數的誤差達到最小，最后采用海明碼來表示類中心。該算法同時具有矢量量化方法的準確性和基于海明碼的速度優(yōu)勢。沈琳等［16］對深度學習哈希方法進行了詳細的綜述。

近年來基于哈希方法的應用層出不窮。朱茂然等［17］提出了一種基于深度哈希的相似圖片推薦系統(tǒng)，能夠有效進行圖片解析，計算圖片相似性并排序?；谏窠浘W絡無監(jiān)督學習的特點使該推薦系統(tǒng)能夠實時捕捉用戶視覺偏好信息進行精準營銷，能夠綜合圖片布局、色彩和色調等深層次信息，從視覺信息角度返回優(yōu)質檢索結果。林計文等［18］提出了一種面向圖像檢索的深度漢明嵌入哈希編碼方式，在深度卷積神經網絡的末端插入一層隱藏層，依據每個單元的激活情況獲得圖像的哈希編碼；同時根據哈希編碼本身的特征提出漢明嵌入損失，更好地保留原數據之間的相似性。該方法能夠提升圖像檢索性能，較好改善短編碼下的檢索性能。

本文提出了一種基于哈希學習的投票樣例選擇算法。首先，將數據從高維空間映射到低維空間；然后，利用k-means 聚類思想結合矢量量化方法對數據進行分類；最后，對每個類中按比例多次隨機選取樣例，投票選擇出最終具有代表性的樣例子集。

2 基于k-means的哈希學習方法

2.1 矢量量化方法

矢量量化（Vector Quantization，VQ）方法［11］是一種有損壓縮技術，在信號處理以及數據壓縮等領域應用廣泛，其優(yōu)點是壓縮比高、解碼簡單且能夠很好地保留信號的細節(jié)。矢量量化方法是將一個向量空間中的點用其中的一個有限子集來進行編碼的過程。矢量量化的基本原理是將輸入矢量用碼書中與之最匹配的碼字的索引代替原輸入，從而進行傳輸與存儲，并且僅需要簡單地查找表便可進行解碼。

矢量量化是標量量化思想的一種推廣，兩種分量間存在4 種相互關聯(lián)的性質：線性依賴性、非線性依賴性、概率密度函數的形狀以及矢量維度。矢量量化的作用就是去掉數據之間的這些冗余，更好地壓縮數據。

2.2 k-means算法

k-means 算法是經典的聚類算法，利用設定值k將樣本通過迭代的方式按樣本間的距離進行聚合，形成k個簇，每一簇便為一類。由于該算法比較穩(wěn)定，速度較快并且誤差較小，因此被廣泛應用。k-means 算法如下：

2.3 基于k-means的哈希學習方法

基于k-means 的哈希學習方法結合了矢量量化方法和海明距離計算的優(yōu)點，是經典的學習型哈希檢索方法。對于給定的樣本集合，該算法首先利用典型的哈希降維方法將高維特征變換到低維空間，根據當前維度需要的比特數決定相應個數的聚類中心，采用完全編碼方式即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 采樣方法

由于現有數據集的數量大多都是非常龐大的，無法對整個數據集進行直接建模，或者處理效率低下，非常影響現實問題的解決效率。對數據進行采樣來改變數據集的大小，用少量的樣本擬合數據的分布從而代表原數據，能夠有效解決以上問題。好的采樣樣本應該能夠覆蓋原數據高概率的區(qū)域，并且相互獨立。常用的采樣方法有隨機采樣、接受-拒絕采樣、重要性采樣-加權采樣等。

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 基于哈希學習的投票樣例選擇算法

對于樣例檢索方法，基于海明距離的檢索方法檢索速度快，而矢量量化方法是基于查找表的，效果比基于距離的好。為了結合兩種方法的優(yōu)點，提出了一種改進樣例選擇方法。

本文算法分三個部分：首先是數據降維階段，對于給定的樣本集合采用典型的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）進行了比較。實驗指標為測試精度、壓縮比和運行時間。

壓縮比度量的是原數據集與經過樣例選擇后的數據子集之間的比值，代表數據被壓縮的比例，選擇后的樣例子集越小代表數據壓縮比例越高，也就是壓縮比越小，代表樣例選擇算法的性能越好。

測試精度指的是將原數據集劃分成訓練集和測試集，利用訓練集經過樣例選擇后的數據子集訓練分類器，用測試集測試該分類器的測試精度，當測試精度值越高時，則說明樣例選擇算法的性能越好，即所選樣例能夠在能力保持的情況下對數據集具有一定的代表性。

運行時間指的是從樣例選擇算法開始到算法執(zhí)行完畢花費的時間，運行時間與算法的時間復雜度有關，運行時間越短代表樣例選擇算法的性能越好。

實驗所用的三個人工數據集相應的概率分布在表1 中給出，7 個數據集的基本信息在表2 中給出。上述三種算法在相同環(huán)境下進行樣例選擇得到的測試精度、壓縮比和運行時間如表3 所示。從表3 可以看出，從運行時間方面，在7 個數據集上本文算法LH-VIS 的執(zhí)行時間均少于CNN 算法和LSH-IS-F 算法的執(zhí)行時間，其原因是：LH-VIS 是對數據降維后直接將數據用海明碼表示，利用海明距離進行相似度度量，海明距離計算相似度只需要異或操作；而LSH-IS-F 是利用隨機哈希函數對數據進行映射，然后用歐氏距離進行相似度度量，所以LH-VIS 在時間上優(yōu)于LSH-IS-F；而CNN 算法作為經典算法在規(guī)模較小和較為簡單的數據集的所需時間較少，但是在處理規(guī)模較大和較為復雜的數據集時，所花費的時間大于本文算法。

表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 在投票樣例選擇階段可以通過調節(jié)參數控制樣例選擇的比例，壓縮比可調節(jié)，所以LH-VIS 在壓縮比方面優(yōu)于CNN 算法和LSH-IS-F 算法，較兩個對比算法平均提升了19%。

在測試精度方面，本文算法LH-VIS 的測試精度在大部分數據集上都能夠高于另外兩個算法，由于基于哈希學習的樣例選擇方法是通過學習的方式得出哈希函數，哈希函數來源于數據本身，所以分類準確率高。

5 結語

本文提出了一種基于哈希學習的投票樣例選擇算法，將數據從高維空間映射到低維空間，然后利用k-means 聚類結合矢量量化思想對數據進行分類，最后對每個類中按比例多次隨機選取樣例，投票選擇出最終具有代表性的樣例子集。

本文提出的算法有如下幾個優(yōu)點：1）原理簡單，易于實現；2）運行時間短，訓練速度快；3）壓縮比可控；4）選擇的樣例質量高。

本文也存在一些可以改進的內容：1）算法對每個維度單獨量化的方法可能忽略了數據的內在聯(lián)系，不能很好地對數據進行映射；2）算法只利用了一種哈希學習方法進行組合選擇，集成效果相對單一。

后續(xù)的工作有兩個方向：一是可以參考多比特量化方法，考慮不同維度間的內在聯(lián)系，從更合理地設置比特位的角度改進算法；二是可以結合其他哈希學習方法，利用多個哈希學習方法同時進行投票樣例選擇，預期效果會優(yōu)于單一方法。