多哈希表投票樣例選擇算法

黃雅婕,翟俊海,2,周翔,申瑞彩,侯瓔真

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002;2.河北大學(xué) 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室,河北 保定 071002)

0 引言

數(shù)據(jù)預(yù)處理是數(shù)據(jù)挖掘的一個(gè)重要步驟,對(duì)原始數(shù)據(jù)進(jìn)行合理的預(yù)處理有利于減少后續(xù)處理的工作量。數(shù)據(jù)約簡是數(shù)據(jù)預(yù)處理的一種重要方法,主要包括屬性約簡和樣例選擇兩種方法。顧名思義,屬性約簡是對(duì)非必需的屬性進(jìn)行刪減,從而留下或選擇出對(duì)數(shù)據(jù)挖掘任務(wù)重要的屬性;樣例選擇是對(duì)每個(gè)樣例進(jìn)行評(píng)估,刪減掉不重要的樣例,篩選出對(duì)后續(xù)工作更重要的樣例。對(duì)結(jié)構(gòu)化的表格數(shù)據(jù)來說,前者對(duì)數(shù)據(jù)進(jìn)行的是縱向(列表示屬性)處理,后者對(duì)數(shù)據(jù)進(jìn)行的是橫向(行表示樣例)處理。從處理結(jié)果來看,二者對(duì)數(shù)據(jù)規(guī)約都產(chǎn)生了積極作用。本文重點(diǎn)進(jìn)行樣例選擇研究。

K-近鄰(K-NN, K-Nearest Neighbor)算法[1]是一種簡單但應(yīng)用非常廣泛的數(shù)據(jù)挖掘算法,其計(jì)算量主要體現(xiàn)在計(jì)算測試樣例與訓(xùn)練集中每一個(gè)樣例之間的歐氏距離。對(duì)于大規(guī)模訓(xùn)練集,K-NN的效率依然較低。為了提高K-NN算法的效率,Hart提出了歷史上第一個(gè)樣例選擇算法-壓縮近鄰算法(CNN, Condensed Nearest Neighbor)[2]。CNN算法是針對(duì)1-NN的樣例選擇算法,其目標(biāo)是找到訓(xùn)練集的最小一致子集,并對(duì)原訓(xùn)練集進(jìn)行替換,利用最小一致子集得出的樣例多數(shù)位于分類邊界附近。Gates提出的約簡近鄰規(guī)則樣例選擇算法(RNN,Reduced Nearest Neighbor)[3]是針對(duì)CNN產(chǎn)生的樣例子集不一定是最小一致子集這一不足而提出的改進(jìn)算法。RNN算法是對(duì)CNN算法選擇的樣例子集S進(jìn)行篩選,刪除S中的冗余樣例。然而,由于RNN算法是對(duì)CNN算法的結(jié)果進(jìn)行刪減,所以RNN算法的精確度對(duì)CNN算法的依賴度較高,只有CNN算法得到最小一致子集時(shí),RNN算法才能得到約簡后的最小一致子集;反之,則不能得到最小一致子集。Wilson提出的編輯近鄰樣例選擇算法(ENN,Edit Nearest Neighbor)[4]是針對(duì)CNN算法對(duì)噪聲敏感這一不足而提出的改進(jìn)算法。ENN算法得到的樣例子集大多分布在各個(gè)類的中心附近,因此該算法的壓縮比不高。Brighton等人提出的迭代過濾算法(ICF,Iterative Case Filtering)[5]是針對(duì)ENN算法壓縮比不理想的問題而提出的改進(jìn)算法。ICF算法為了提高壓縮比,選擇的是可達(dá)集大且覆蓋集小的樣例。Angiulli提出的基于Voronoi圖的快速壓縮近鄰算法(FCNN, Fast CNN)[6]是針對(duì)CNN算法與樣例順序有關(guān)的缺點(diǎn)提出的改進(jìn)算法。FCNN算法選出的樣例子集和訓(xùn)練集的樣例順序無關(guān)。翟等人[7]提出了一種概率神經(jīng)網(wǎng)絡(luò)樣例選擇算法,利用后驗(yàn)概率得到貝葉斯最優(yōu)判別邊界,不受特定分類器的限制, 能夠有效地得出樣例是否分布在分類邊界附近。

1998年,Piotr Indyk為了解決直接在高維空間下查找相似點(diǎn)面臨的維度災(zāi)難問題,提出了局部敏感哈希(LSH)[8]算法。LSH算法的核心是利用哈希沖突尋找同類型的點(diǎn),將高維空間上相似的點(diǎn)映射到海明空間中,然后利用海明距離將同類型的點(diǎn)映射到同一個(gè)哈希桶(buckets)中。2002年,Moses Charikar[9]提出了舍入算法中的相似度估計(jì)技術(shù)(SimHash),該算法通過分詞、映射、加權(quán)、合并和降維一系列操作來比較兩個(gè)文本間的相似度。Google公司的Manku等人[10]利用該算法實(shí)現(xiàn)了對(duì)搜索引擎爬蟲系統(tǒng)的網(wǎng)頁間的相似度估計(jì),是SimHash的著名應(yīng)用之一。2004年,Piotr Indyk等人[11]提出了基于P-stable分布的局部敏感哈希算法,該算法將原始空間中的點(diǎn)映射到一條隨機(jī)的直線上,將直線分成長度相等的線段,每一段代表一個(gè)哈希桶,避免了傳統(tǒng)LSH算法將數(shù)據(jù)映射到海明空間的麻煩,直接在歐式空間上進(jìn)行計(jì)算。Li等人[12]提出了一種基于最小割超平面和集成學(xué)習(xí)的全局低密度局部敏感哈希搜索算法,采用圖切方法構(gòu)造了一種新穎的全局低密度超平面候選集,采用最小信息增益法和隨機(jī)最大熵法貪婪地選擇超平面,采用集合學(xué)習(xí)方法查詢?nèi)纸谱罱彅?shù)據(jù)。LSH在大數(shù)據(jù)方面的應(yīng)用近年來也受到各位研究人員的關(guān)注。翟等人[13]提出了一種基于哈希技術(shù)和MapReduce的大數(shù)據(jù)集K-近鄰算法,利用SimHash和MapReduce編程框架解決了K-近鄰算法在大數(shù)據(jù)應(yīng)用方面的缺陷。張等人[14]提出了一種基于Spark的壓縮近鄰算法,利用Spark并行計(jì)算框架解決了壓縮近鄰算法在大數(shù)據(jù)應(yīng)用下的局限性的問題。Osman[15]等人提出了一種分布式局部敏感哈希法用于快速圖像相似度搜索,利用隨機(jī)分布式哈希方法將數(shù)據(jù)隨機(jī)分布到集群上的不同節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)上,使用相同的隨機(jī)哈希函數(shù)集來索引本地?cái)?shù)據(jù)。在查詢階段,在不同的節(jié)點(diǎn)中對(duì)查詢樣本進(jìn)行局部搜索。

盡管局部敏感哈希方法在數(shù)據(jù)降維以及近似近鄰查找方面受到了廣泛的關(guān)注,但是局部敏感哈希算法本身是基于概率方法的隨機(jī)映射,具有很強(qiáng)的隨機(jī)性,適用于不要求精確度的研究領(lǐng)域,但樣例選擇方法是在保證精確度的情況下提高數(shù)據(jù)集的壓縮比,所以傳統(tǒng)的局部敏感哈希方法不適用于本文的研究。針對(duì)這一問題,本文提出了一種基于P-stable分布的多哈希表投票樣例選擇算法,將數(shù)據(jù)映射到多個(gè)獨(dú)立的哈希表中,然后對(duì)每個(gè)哈希表中的樣例進(jìn)行投票,選擇出最終的樣例子集,利用投票方法提高算法的精確度及壓縮比。

1 相關(guān)工作

1.1 P-stable分布

對(duì)于任意P∈(0,2]存在穩(wěn)定分布，特別的：

1.2 基于P-stable分布的局部敏感哈希

定義3[18]給定一組X和距離度量D，取一組哈希函數(shù)既哈希族H={h:X→B}，當(dāng)滿足以下條件時(shí)，稱為(d1,d2;p1,p2)敏感,且如圖1所示。

For ?x,y∈X,ifD(x,y)≤d1,

then Prob[h(x)=h(y) ]≥p1

For ?x,y∈X,ifD(x,y)

thenProb[h(x)=h(y)]≤p2。

圖1 局部敏感哈希示意圖Fig.1 Schematic diagram of locally sensitive hashing

經(jīng)過哈希函數(shù)映射后，哈希桶中存放的是每個(gè)數(shù)據(jù)對(duì)應(yīng)的哈希值h1(v),…,hk(v)，但是這種存放方法既占用了一定的內(nèi)存，又不利于查找，于是提出了利用索引和關(guān)鍵字存儲(chǔ)的方法，定義了h1,h2兩個(gè)函數(shù)。

定義4[16]

定義5[16]

算法1：基于P-stable分布的LSH算法[16]

輸入：數(shù)據(jù)集D，查詢點(diǎn)q

輸出：查詢點(diǎn)q的近似點(diǎn)

1)利用隨機(jī)化方法構(gòu)造哈希族以及哈希函數(shù)h(v)=(h1(v),…,hk(v));

2)構(gòu)造函數(shù)h1和h2;

3)利用哈希函數(shù)h(v)將每個(gè)特征v進(jìn)行哈希變換得到h1(v),…,hk(v);

4)利用h1和h2對(duì)h1(v),…,hk(v)進(jìn)行哈希得到index和value值;

5)將特征v放入對(duì)應(yīng)的哈希桶，并存入其value值;

6)直到每個(gè)特征都計(jì)算完畢，取出與查詢點(diǎn)q距離近的點(diǎn)。其中，該方法對(duì)數(shù)據(jù)的處理僅需要對(duì)數(shù)據(jù)遍歷一次即可完成查詢，時(shí)間復(fù)雜度為O(n)。算法對(duì)應(yīng)的示意圖如圖2所示。

圖2 基于P-stable分布的LSH算法思想示意圖Fig.2 Schematic diagram ofLSH algorithm based on P-stable distribution

圖3 提出的算法流程圖Fig.3 Flow chart of the proposed algorithm

2 多哈希表投票樣例選擇算法

本節(jié)給出本文提出的多哈希表投票樣例選擇算法，算法包括4步：第一步，利用P-stable LSH構(gòu)造哈希族G，即k個(gè)哈希函數(shù)的集合。第二步，利用哈希族構(gòu)造L個(gè)具有k個(gè)哈希函數(shù)向量。第三步，對(duì)數(shù)據(jù)集進(jìn)行哈希變換，得到L個(gè)哈希表。第四步，從每個(gè)哈希表中按比例隨機(jī)選擇若干個(gè)樣例，得到L個(gè)樣例子集后，投票選出最終的樣例子集。算法的流程圖如圖3所示。

下面給出具體的算法：

算法2:多哈希表投票樣例選擇算法輸入:數(shù)據(jù)集D。輸出:選出的樣例子集S。1)初始化S=?;2)利用隨機(jī)化方法構(gòu)造具有k個(gè)哈希函數(shù)的哈希族;3)利用哈希族構(gòu)造L個(gè)哈希函數(shù)向量hi(v)=(hL1(v),…,hLk(v));4)利用定義4和定義5構(gòu)造函數(shù)h1和h2;5)利用哈希函數(shù)hi(v)將每個(gè)數(shù)據(jù)進(jìn)行哈希變換得到哈希值h1(v),…,hk(v);6)利用h1對(duì)h1(v),…,hk(v)進(jìn)行哈希變換得到index;7)利用h2將h1(v),…,hk(v)進(jìn)行哈希變換得到value;8)將數(shù)據(jù)v放入index對(duì)應(yīng)的哈希桶,并存入對(duì)應(yīng)的value值;9)直到L個(gè)哈希函數(shù)hi(v)都計(jì)算完畢后,隨機(jī)從每個(gè)哈希桶中選擇樣例,得到L個(gè)哈希表;10)對(duì)L個(gè)哈希表中的樣例進(jìn)行投票,得出最終的樣例子集S。

由于L遠(yuǎn)小于樣例數(shù)量，所以本文提出的方法的時(shí)間復(fù)雜度為o(n)。

3 實(shí)驗(yàn)結(jié)果及統(tǒng)計(jì)分析

為了驗(yàn)證本文算法的有效性，我們?cè)赨CI數(shù)據(jù)集上進(jìn)行了3個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1是在Iris數(shù)據(jù)集上驗(yàn)證本文方法的可行性及選出的樣例的代表性，實(shí)驗(yàn)將選擇出的樣例作為訓(xùn)練集，剩余樣例作為測試集，對(duì)剩余的樣例進(jìn)行分類，利用分類精度證明所選樣例能夠在能力保持的情況下對(duì)數(shù)據(jù)集具有一定的代表性。實(shí)驗(yàn)2是在6個(gè)UCI數(shù)據(jù)集上與CNN、ENN、RNN和ICF在壓縮比和所需時(shí)間兩方面進(jìn)行比較。實(shí)驗(yàn)3在6個(gè)UCI數(shù)據(jù)集上在壓縮比和所需時(shí)間兩方面與基于P-stable分布的局部敏感哈希方法進(jìn)行了對(duì)比。實(shí)驗(yàn)環(huán)境為PC機(jī)，四核2.5 GHz CPU，8 GB內(nèi)存Windows10操作系統(tǒng)，Python 3.7實(shí)驗(yàn)平臺(tái)。

實(shí)驗(yàn)1 在Iris數(shù)據(jù)集上的實(shí)驗(yàn)

實(shí)驗(yàn)1所用數(shù)據(jù)集是UCI經(jīng)典數(shù)據(jù)集Iris，數(shù)據(jù)集分為3類共150條數(shù)據(jù)，每類各50條，共有4個(gè)屬性值。利用本文算法得到的結(jié)果如表1所示。實(shí)驗(yàn)結(jié)果顯示選出的樣例在三種類別中分布穩(wěn)定，利用所選的16個(gè)樣例對(duì)剩余134個(gè)樣例進(jìn)行分類，分類精度為93.3%，證明所選樣例相對(duì)整個(gè)數(shù)據(jù)集具有極強(qiáng)的代表性。

實(shí)驗(yàn)2 與CNN、ENN、RNN和ICF的性能比較

實(shí)驗(yàn)2用6個(gè)UCI數(shù)據(jù)集從壓縮比和所需時(shí)間兩方面與CNN、ENN、RNN和ICF四種樣例選擇算法進(jìn)行了性能比較。壓縮比度量的是進(jìn)行樣例選擇后得到的樣例子集占整個(gè)數(shù)據(jù)集的比例，選擇后的樣例子集越小證明數(shù)據(jù)壓縮比例越高，也就是壓縮比越小，證明算法性能越好。實(shí)驗(yàn)中使用的6個(gè)UCI數(shù)據(jù)集的基本信息如表2所示。實(shí)驗(yàn)結(jié)果如表3、表4表示。

從表3和表4可以看出，本文提出的算法在Wine，Image，SPECT三個(gè)數(shù)據(jù)集上的壓縮比均優(yōu)于其他方法；在Waveform數(shù)據(jù)集上的壓縮比優(yōu)于ENN算法，高于其他三個(gè)算法；在Nursery和Mushroom數(shù)據(jù)集上優(yōu)于ENN，ICF兩個(gè)算法，高于其他兩個(gè)算法；在所需時(shí)間比較中，SPECT數(shù)據(jù)集明顯優(yōu)于其他四個(gè)數(shù)據(jù)集；在Waveform，Nursery兩個(gè)數(shù)據(jù)集上與CNN，ENN相差無幾，明顯優(yōu)于RNN和ICF算法；在Wine、Image和Mushroom數(shù)據(jù)集上優(yōu)于RNN，ICF算法，高于其他兩個(gè)算法。

表1 用本文算法選出的樣例分布情況

表2 實(shí)驗(yàn)所用UCI數(shù)據(jù)集的基本信息

表3 與其他方法在壓縮比方面的實(shí)驗(yàn)比較

實(shí)驗(yàn)3 與基于P-stable分布的局部敏感哈希方法在壓縮比方面的比較

實(shí)驗(yàn)3在6個(gè)UCI數(shù)據(jù)集上在壓縮比和所需時(shí)間兩方面與基于P-stable分布的局部敏感哈希方法(E2LSH)進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果如表5和表6所示。

表4 與其他方法在所需時(shí)間方面的實(shí)驗(yàn)比較

表5 與E2LSH在壓縮比方面的實(shí)驗(yàn)比較

表6 與E2LSH在所需時(shí)間方面的實(shí)驗(yàn)比較

從表5和表6可以看出，本文提出的方法在6個(gè)UCI數(shù)據(jù)集上的壓縮比均小于E2LSH方法，除在Wine, SPECT兩個(gè)數(shù)據(jù)集上的時(shí)間相差無幾，在其他4個(gè)數(shù)據(jù)集上的時(shí)間略有遜色外，本文提出的方法更適合針對(duì)小型數(shù)據(jù)集進(jìn)行數(shù)據(jù)壓縮。

4 結(jié)論

基于P-stable分布的局部敏感哈希方法是利用基于概率的方法對(duì)樣例進(jìn)行選擇，結(jié)果有很大的隨機(jī)性。針對(duì)這一問題，本文提出一種多哈希表投票樣例選擇算法，利用多數(shù)投票的方法來提高樣例選擇的有效性。實(shí)驗(yàn)證明，在壓縮比和所需時(shí)間兩方面與其他著名樣例選擇算法比較來看均有一定的優(yōu)勢，尤其在壓縮比方面與其他方法有一定競爭力。

但本文提出的算法也存在一定的劣勢。為了保證樣例選擇的準(zhǔn)確性，也就是保證放入同一個(gè)哈希桶的樣例同屬于一類，本文提出的算法利用了大量的存儲(chǔ)空間來存儲(chǔ)索引，其中會(huì)有一些空的哈希桶，這就造成了空間上的浪費(fèi)。另外，本文構(gòu)建的多種索引結(jié)構(gòu)，也對(duì)空間存儲(chǔ)有一定的要求，導(dǎo)致本文提出的方法不適合在單機(jī)條件下擴(kuò)展到大數(shù)據(jù)處理問題。

從現(xiàn)有環(huán)境下機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘面對(duì)的問題來看，規(guī)模較大的數(shù)據(jù)處理已經(jīng)成為主流，小數(shù)據(jù)集只能用作測試和改進(jìn)。從大數(shù)據(jù)的特點(diǎn)來看，其數(shù)據(jù)價(jià)值密度較低，提取出的有用信息可能屈指可數(shù)，如何處理大規(guī)模數(shù)據(jù)問題是我們現(xiàn)在面臨的困難。下一步工作將通過閱讀更多局部敏感哈希相關(guān)資料來改進(jìn)算法，使其更適應(yīng)大規(guī)模數(shù)據(jù)，以及通過學(xué)習(xí)使用大數(shù)據(jù)開發(fā)平臺(tái)來解決相關(guān)問題。