基于局部敏感Hash的半監(jiān)督直推SVM增量學(xué)習(xí)算法

，，

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

近年來，隨著計算機網(wǎng)絡(luò)技術(shù)和傳感器技術(shù)的發(fā)展，應(yīng)用軟件和設(shè)備產(chǎn)生了大量的數(shù)據(jù).傳統(tǒng)機器學(xué)習(xí)大多為監(jiān)督學(xué)習(xí)，被用于處理如醫(yī)學(xué)[1]、交通[2]等領(lǐng)域中的帶全部所屬標(biāo)簽的樣本.然而在現(xiàn)實生活應(yīng)用中，大多數(shù)數(shù)據(jù)樣本是無標(biāo)簽樣本或是帶少量標(biāo)簽的樣本，而且對無標(biāo)簽的樣本加標(biāo)簽是非常困難的.若要將帶標(biāo)簽樣本和無標(biāo)簽樣本相結(jié)合進行學(xué)習(xí)，同時樣本不斷增加，則需要增量學(xué)習(xí)和半監(jiān)督學(xué)習(xí)相結(jié)合的算法.增量學(xué)習(xí)旨在獲得原訓(xùn)練樣本與新增樣本并集的最優(yōu)解，而半監(jiān)督學(xué)習(xí)則用于處理有標(biāo)簽數(shù)據(jù)和無標(biāo)簽數(shù)據(jù)共存的樣本.由于半監(jiān)督學(xué)習(xí)本身特點，被許多學(xué)者研究改進，用于許多領(lǐng)域，包括鐵路電力系統(tǒng)[3]、網(wǎng)絡(luò)應(yīng)用[4]和三維模型檢索[5]等.在半監(jiān)督學(xué)習(xí)中，直推式支持向量機(Transductive support vector machine，TSVM)[6]

是在學(xué)習(xí)樣本中包含少量標(biāo)簽樣本和大量無標(biāo)簽樣本中，把無標(biāo)簽樣本中隱藏空間信息應(yīng)用到最終分類器，從而提高分類器的性能和學(xué)習(xí)成本.在TSVM上，樣本標(biāo)注準(zhǔn)確性影響著算法準(zhǔn)確度方面的性能.TSVM每次迭代選取未標(biāo)記樣本中重要的樣本進行標(biāo)記，那么提高這些重要樣本標(biāo)記的準(zhǔn)確性就非常重要，如文獻[7]利用每次迭代中選取標(biāo)記的標(biāo)簽準(zhǔn)確性最高的無標(biāo)記樣本來提高最終分類器的分類精度；文獻[8]則在懲罰參數(shù)上做文章，來控制錯誤標(biāo)記的數(shù)量以提高性能；文獻[9]為了提高準(zhǔn)確度，利用游程計算標(biāo)記樣本，同時在速度方面，隨著無標(biāo)簽樣本不斷增加，每次迭代的樣本數(shù)量也增加，算法的訓(xùn)練速度就會明顯下降；因此，文獻[10]利用增量學(xué)習(xí)選取上次訓(xùn)練重要的已標(biāo)記樣本進行訓(xùn)練，避免對已標(biāo)記樣本全部重新訓(xùn)練；文獻[11]在每次迭代中，用聚類的方法增加樣本的數(shù)量；文獻[12]用半監(jiān)督聚類對未標(biāo)記樣本預(yù)分類.

面對帶少量標(biāo)簽和大量無標(biāo)簽且不斷增加的數(shù)據(jù)，上述半監(jiān)督TSVM學(xué)習(xí)算法都有其局限性：1) 雖然提高了準(zhǔn)確度或訓(xùn)練速度，但不具備增量學(xué)習(xí)能力，不能適應(yīng)不斷增長的數(shù)據(jù)；2) 如果跟增量學(xué)習(xí)相結(jié)合，其分類性能就會下降.筆者利用局部敏感Hash(Locality sensitive Hashing，LSH)思想方法，TSVM和增量學(xué)習(xí)思想相結(jié)合，提出一種基于主成分分析的局部敏感Hash的TSVM增量學(xué)習(xí)算法(Incremental TSVM with principal component analysis of locality sensitive Hashing，PCA-LSH-ITSVM).此算法利用LSH對新增無標(biāo)簽篩選并預(yù)標(biāo)記，提高訓(xùn)練速度，同時也提高分類精度.實驗結(jié)果表明：筆者算法能適應(yīng)帶少量標(biāo)簽和大量無標(biāo)簽且不斷增加的數(shù)據(jù)，并有較好的性能.

1 TSVM和LSH理論基礎(chǔ)

1.1 TSVM理論基礎(chǔ)

(1)

s.t.

(2)

TSVM學(xué)習(xí)訓(xùn)練就是獲得式(1)的最優(yōu)解，大致步驟為

1) 指定可調(diào)參數(shù)C，C*，利用傳統(tǒng)的支持向量機對已標(biāo)記樣本進行訓(xùn)練，得到初始分類器.

3) 通過2)得到的樣本與已標(biāo)記樣本一起重新做一次訓(xùn)練，得到新的分類器.對該分類器，利用某一規(guī)則對類別標(biāo)簽不同的樣本標(biāo)簽進行交換，然后重復(fù)這一步驟，直到樣本不存在符合交換規(guī)則的樣本為止.

1.2 LSH理論基礎(chǔ)

LSH算法理論基本思想：對兩個在原始空間中的鄰近或相似的數(shù)據(jù)樣本點進行相同的映射或投影變換，得到的數(shù)據(jù)點在新空間中仍然相鄰相近的概率很大，同時不相鄰的數(shù)據(jù)點被映射到新空間相似的概率很小.利用一組Hash函數(shù)[13]對原空間集合中數(shù)據(jù)進行Hash投影后，就得到了一個Hash桶(即Hash表).這樣就將原數(shù)據(jù)集合分到了多個Hash桶，同時這些Hash桶中的數(shù)據(jù)是相鄰相似的，且該Hash桶的數(shù)據(jù)樣本個數(shù)較小.因此在超大數(shù)據(jù)集中搜索相鄰相似的數(shù)據(jù)樣本的問題就變成了在Hash桶中的少量數(shù)據(jù)樣本中搜索的問題.

Hash函數(shù)需要滿足以下兩個條件：

1) 如果d(x,y)≤d1，則h(x)=h(y)的概率大于等于p1.

2) 如果d(x,y)≥d2，則h(x)=h(y)的概率小于等于p2.

其中：d(x,y)為x，y之間的距離；d1，d2為距離閾值；h(x)，h(y)為x，y的Hash表；p1為滿足上述條件最小的概率值；p2為滿足上述條件的最大概率值.

滿足上述兩個條件的Hash函數(shù)則稱為(d1,d2,p1,p2)Hash敏感函數(shù).局部敏感Hash：指利用一個或者多個(d1,d2,p1,p2)的敏感Hash函數(shù)對原始樣本數(shù)據(jù)集進行Hash映射，生成Hash表的過程.而局部敏感Hash函數(shù)族有多種，如漢明距離下的最小Hash函數(shù)族[14]、歐氏距離下的基于p-穩(wěn)定分布的Hash函數(shù)族[15]等.它們是根據(jù)不同距離量度進行劃分的.

2 基于PCA-LSH的半監(jiān)督ITSVM增量學(xué)習(xí)

2.1 PCA-LSH的構(gòu)建

利用主成分分析(Principal component analysis，PCA)投影得到的特征向量進行Hash編碼投影，而不是隨機的向量.這種特征子空間提供了很好的近似輸入空間，逼近誤差可以通過累積輸入特征成分的近似子空間占整個輸入空間的比率來控制.因此，通過PCA來替代LSH投影的隨機向量，可以很容易從一個給定的數(shù)據(jù)分布來確定一個合適的Hash函數(shù)數(shù)量.

(3)

設(shè)Hash編碼的一維空間向量區(qū)域為[1,P]，F(xiàn)(vi)為Hash函數(shù)，則1≤F(vi)≤P.P為Hash值向量每一維所能取得的最大值，即F(vi)為

(4)

式中：vi-min，vi-max分別為初始輸入樣本投影后特征向量的第i個特征值的最小值和最大值；round()為四舍五入函數(shù).

因此，輸入特征向量的Hash值向量h(x)為

h(x)={F(v1),F(v2),…,F(vi)}

(5)

然后利用h(x)組成Hash表H為

H=[h(x1),h(x2),…,h(xn)]

(6)

最后利用h(x)，H對新增樣本進行篩選.

2.2 基于PCA-LSH的ITSVM學(xué)習(xí)算法

將有標(biāo)簽樣本進行LSH后，每個樣本會得到一個Hash值向量，那么Hash值向量的標(biāo)簽為這個樣本的標(biāo)簽.同時LSH具有搜索近鄰和相似的數(shù)據(jù)樣本特點.因此可以在利用LSH對新增無標(biāo)簽進行篩選的同時，利用Hash值向量對應(yīng)的標(biāo)簽對篩選的樣本進行標(biāo)記.結(jié)合LSH快速搜索查詢和能標(biāo)記的特點，提出了一種基于PCA-LSH的ITSVM半監(jiān)督增量學(xué)習(xí)算法PCA-LSH-ITSVM，其在提高訓(xùn)練學(xué)習(xí)速度的同時，也提升了精度.

假設(shè)少量的有標(biāo)簽樣本集為Ω0，第一次新增無標(biāo)簽樣本集為Ω1，第二次新增無標(biāo)簽樣本集為Ω2，第一次TSVM增量學(xué)習(xí)后得到的SV集為Ω1SV，少量的有標(biāo)簽樣本集為Ω0，進行PCA-LSH后的Hash表為H0，第一次TSVM增量學(xué)習(xí)后得到的SV集LSH后Hash表H1，更新后的Hash表為H，第一次新增的每個樣本PCA-LSH后的Hash值向量為h(Ω1)，第一次新增樣本篩選后的樣本為Ω1LSH，第二次新增的每個樣本PCA-LSH后的Hash值向量為h(Ω2)，第二次新增樣本篩選后的樣本為Ω2LSH，f(x)=ω·x+b為TSVM的決策函數(shù).以上SV(Support vector)為支持向量.則PCA-LSH-ISVM算法的詳細描述如下：

1) 首先將Ω0通過PCA-LSH建立Hash表H0，其中每個Hash值向量帶標(biāo)簽，同時將Ω1每個樣本通過PCA-LSH得到Hash值向量為h(Ω1).

2) 篩選和初始標(biāo)記新增無標(biāo)簽樣本集Ω1：如果Ω1中樣本對應(yīng)的h(Ω1)落在H0中，則篩選出樣本并利用H0的標(biāo)記進行初始標(biāo)注，最后得到篩選后的樣本集Ω1LSH.

3) 將Ω0，Ω1LSH作為TSVM學(xué)習(xí)的訓(xùn)練集，訓(xùn)練得到?jīng)Q策函數(shù)f(x).

4) 利用f(x)對篩選后的Ω1LSH重新標(biāo)記，將標(biāo)記后的結(jié)果與上次(初始)標(biāo)記結(jié)果相比較.若存在不相同，則將該樣本設(shè)為無標(biāo)記樣本(標(biāo)記為0)但樣本還在Ω1LSH中，再將Ω0，Ω1LSH作為TSVM學(xué)習(xí)的訓(xùn)練集，訓(xùn)練得到新的決策函數(shù)f(x).否則結(jié)束本次增量TSVM學(xué)習(xí)，得到SV集為Ω1SV.

5) 利用f(x)對篩選后的Ω1LSH重新標(biāo)記，將標(biāo)記后的結(jié)果與上次標(biāo)記結(jié)果相比較.若存在不相同，但不是無標(biāo)簽(標(biāo)記為0)樣本，則將該樣本設(shè)為無標(biāo)記(標(biāo)記為0)樣本，同時將之前無標(biāo)記的樣本設(shè)置為這次的標(biāo)記，它們?nèi)匀辉讦?LSH.

6) 再將Ω0，Ω1LSH作為TSVM學(xué)習(xí)的訓(xùn)練集，重復(fù)步驟5)，直到兩次標(biāo)記結(jié)果相同.結(jié)束本次增量TSVM學(xué)習(xí)，得到SV集為Ω1SV.

7) 將Ω1SV通過PCA-LSH建立Hash表H1，其中每個Hash值向量帶標(biāo)簽，同時將Ω2每個樣本通過PCA-LSH得到Hash值向量為h(Ω1).再對Ω2進行篩選和初始標(biāo)記，得到Ω2LSH.再將Ω1SV，Ω2LSH合并，樣本集為Ω2LSH.

8) 將Ω0，Ω2LSH作為TSVM學(xué)習(xí)的訓(xùn)練集，訓(xùn)練得到?jīng)Q策函數(shù)f(x).重復(fù)步驟4)～6)(將其中的Ω1LSH改為Ω2LSH即可)，得到新的SV.

9) 下一個新增樣本重復(fù)步驟7)，8)，直到?jīng)]有新增樣本.得到最終決策函數(shù).

3 實 驗

為了驗證算法的性能，對比了筆者提出的PCA-LSH-ISVM算法與傳統(tǒng)TSVM算法、一般增量TSVM算法的精度和訓(xùn)練速度性能.其中ITSVM是指將上次TSVM學(xué)習(xí)訓(xùn)練得到的SV，本來有標(biāo)簽的樣本與增量無標(biāo)簽樣本進行TSVM學(xué)習(xí)訓(xùn)練.實驗在i5 M430處理器上進行，主頻為2.27 GHz，內(nèi)存為4 GB，軟件為PyCharm 5.0.3.

為了驗證算法的性能，將PCA-LSH-ITSVM，TSVM，ITSVM算法作對比.實驗在UCI標(biāo)準(zhǔn)數(shù)據(jù)集Steel，Magic，Default of credit card clients(Credit)分別進行：1) 實驗隨機從以上3 個數(shù)據(jù)集中隨機選取600 個樣本，其中一半為訓(xùn)練樣本，一半為測試樣本；2) 訓(xùn)練樣本去除部分標(biāo)簽，以有標(biāo)簽樣本集數(shù)量占總數(shù)的5%，10%，15%，20%的比例進行實驗；3) 在增量學(xué)習(xí)上，訓(xùn)練樣本分成初始樣本集(其為有標(biāo)簽樣本)和5 個無標(biāo)簽的增量樣本集.數(shù)據(jù)集個數(shù)、特征個數(shù)如表1所示.

表1 數(shù)據(jù)集Table 1 The data set 個

3.1 實驗分類精度結(jié)果及分析

在Hash函數(shù)參數(shù)P=8的情況下，對比各算法的分類性能.其中PCA-LSH只是對新增樣本進行篩選和初始標(biāo)記，并不改變樣本的原來屬性(未進行其他預(yù)處理)，這樣保證與其他算法訓(xùn)練學(xué)習(xí)的對象樣本一致性.實驗結(jié)果如表2～4所示.

表2不同算法在Steel中分類精度

Table2TheclassificationaccuracyofdifferentalgorithmsinSteel%

表3不同算法在Magic中分類精度

Table3TheclassificationaccuracyofdifferentalgorithmsinMagic%

表4不同算法在Credit中分類精度

Table4TheclassificationaccuracyofdifferentalgorithmsinCredit%

由上述實驗結(jié)果可知：

1) 當(dāng)訓(xùn)練樣本中初始帶標(biāo)簽樣本數(shù)量較多(比例為20%)時，由于帶標(biāo)簽樣本能較好地代表整體樣本集(其含有較多的分類信息)，因此三者算法的精度相近，但筆者提出的PCA-LSH-ITSVM算法精度最高，比傳統(tǒng)TSVM算法平均高2%左右.

2) 當(dāng)訓(xùn)練樣本中初始帶標(biāo)簽樣本數(shù)量較少(比例為5%)時，由于帶標(biāo)簽樣本不能較好地反應(yīng)整體的分類信息，算法TSVM，ITSVM分類性能很差，但筆者算法能有效地利用少量的帶標(biāo)簽樣本篩選并標(biāo)記無標(biāo)簽樣本使第一次訓(xùn)練的樣本能較好反應(yīng)出整體分布，從而提高分類性能，筆者算法分類精度比TSVM算法高了20%左右.

3) 隨著有標(biāo)簽樣本比例的升高，其分布信息能更好地反應(yīng)整體樣本，因此各算法的性能也在升高.

總之，筆者算法利用PCA-LSH較準(zhǔn)確地給無標(biāo)簽樣本進行初始標(biāo)記，避免了設(shè)定TSVM中初始正標(biāo)簽樣本數(shù)對精度影響；同時在第一次訓(xùn)練前，先利用PCA-LSH和有標(biāo)簽的少量樣本對第一次增量無標(biāo)簽樣本進行篩選標(biāo)記(相當(dāng)于是第一訓(xùn)練樣本能更好地反應(yīng)整體樣本)，使得第一次獲得SV集準(zhǔn)確.因此，在有標(biāo)簽樣本數(shù)量很少時，筆者算法保持良好的分類性能，而其他算法則性能較差；在有標(biāo)簽樣本數(shù)量多時，筆者算法比其他算法有更高的分類精度.

3.2 實驗訓(xùn)練速度結(jié)果及分析

在Hash函數(shù)參數(shù)P=8的情況下，對比各算法的分類性能.在訓(xùn)練樣本總數(shù)為300個時，算法在不同帶標(biāo)簽樣本比例下的速度，實驗結(jié)果如表5～7所示.

表5 不同算法在Steel中訓(xùn)練速度Table 5 The training speed of different algorithms in Steel

表6 不同算法在Magic中訓(xùn)練速度Table 6 The training speed of different algorithms in Magic

表7 不同算法在Credit中訓(xùn)練速度Table 7 The training speed of different algorithms in Credit

由上述實驗結(jié)果可知：

1) 在實驗有標(biāo)簽樣本的比例下，筆者算法的訓(xùn)練速度都優(yōu)于TSVM，ITSVM.當(dāng)訓(xùn)練樣本中初始帶標(biāo)簽樣本比例越小時，筆者算法的速度優(yōu)勢越明顯.

2) TSVM，ITSVM的訓(xùn)練速度隨著帶標(biāo)簽樣本比例的增加，會有加快的趨勢.其中ITSVM大部分速度都優(yōu)于TSVM，因為ITSVM就是增量學(xué)習(xí)，減少部分標(biāo)記樣本的迭代次數(shù).

3) 筆者算法的速度快且平穩(wěn).其速度在不同標(biāo)記樣本比重都是最優(yōu).因為筆者算法利用增量學(xué)習(xí)減少部分標(biāo)記樣本的迭代次數(shù)的同時，還利用PCA-LSH對增量樣本進行篩選，減少訓(xùn)練樣本的數(shù)量，減少迭代.

總之，筆者算法利用PCA-LSH對增量樣本進行篩選，而且增量學(xué)習(xí)使得訓(xùn)練速度明顯加快.因此當(dāng)初始標(biāo)簽樣本數(shù)量很少時，相對其他兩種算法，筆者算法訓(xùn)練速度有明顯優(yōu)勢；在有標(biāo)簽樣本數(shù)量多時，其他兩種算法訓(xùn)練速度加快，但筆者算法的訓(xùn)練速度還是有較大的優(yōu)勢.

4 結(jié) 論

為了提高機器學(xué)習(xí)在大數(shù)據(jù)集中的半監(jiān)督學(xué)習(xí)性能，基于局部敏感Hash和增量學(xué)習(xí)提出了一種基于主成分分析的局部敏感Hash的SVM快速增量學(xué)習(xí)算法PCA-LSH-ITSVM.該算法利用主成分分析與局部敏感Hash相結(jié)合的PCA-LSH對新增無標(biāo)簽樣本進行篩選和標(biāo)記，避免了設(shè)定TSVM中初始正標(biāo)簽樣本數(shù)對精度的影響，提高分類精度，同時由于是增量學(xué)習(xí)和對數(shù)據(jù)集篩選，減少了TSVM迭代次數(shù)，雙重加快了訓(xùn)練速度.實驗結(jié)果表明：在少量帶標(biāo)簽和大量無標(biāo)簽的數(shù)據(jù)中，該算法相對傳統(tǒng)TSVM和一般的TSVM在分類精度和訓(xùn)練速度有其明顯優(yōu)勢，尤其在帶標(biāo)簽樣本數(shù)量很少時.

[1] 龍勝春，堯麗君.行程長度紋理特征應(yīng)用于腸癌病理圖片識別[J].浙江工業(yè)大學(xué)學(xué)報，2015，43(1)：110-114.

[2] 邵奇可，李路，周宇，等.一種基于滑動窗口優(yōu)化算法的行人檢測算法[J].浙江工業(yè)大學(xué)學(xué)報，2015，43(2)：212-216..

[3] 劉子軍.基于TSVM的鐵路電力系統(tǒng)諧波檢測方法研究[M].重慶：重慶大學(xué)，2015.

[4] 李斌，李麗娟.基于改進TSVM的未知網(wǎng)絡(luò)應(yīng)用識別算法[J].電子技術(shù)應(yīng)用，2016，42(9)：95-98.

[5] 徐彩虹，劉志，潘翔，等.一種基于實例學(xué)習(xí)的三維模型檢測匹配方法[J].浙江工業(yè)大學(xué)學(xué)報，2012，40(3)：326-330.

[6] JOACHIMS T. Transdutive inference for text classicication using support vector machines[C]//International Conference on Machine Learning. San Francisco: Morgan Kaufman, 1999: 200-2009.

[7] 陳毅松，汪國平，董士海.基于支持向量機的漸進直推式分類學(xué)習(xí)算法[J].軟件學(xué)報，2003，14(3)：451-460.

[8] 王安娜，李云路，趙鋒云，等.一種新的半監(jiān)督直推式支持向量機分類算法[J].儀器儀表學(xué)報，2011，32(7)：1546-1550.

[9] 廖東平，魏璽章，黎湘，等.一種改進的漸進直推式支持向量機分類學(xué)習(xí)算法[J].信號處理，2008，24(2)：213-218.

[10] 彭新俊，王翼飛.雙模糊漸進直推式支持向量機算法[J].模式識別與人工智能，2009，22(4)：560-566.

[11] 薛貞霞，劉三陽，劉萬里.改進的直推式支持向量機算法[J].系統(tǒng)工程理論與實踐，2009，29(5)：142-148.

[12] 王立梅，李金鳳，岳琪.基于k均值聚類的直推式支持向量機學(xué)習(xí)算法[J].計算機工程與應(yīng)用，2013，49(14)：144-146.

[13] ANDONI A, INDYK P, NGUYEN H L. Beyond locality-sensitive Hashing[C]//Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2014: 1018-1028.

[14] GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via Hashing[J]. Peer-to-peer networking and application, 2000, 8(2): 216-228.

[15] DATAR M, IMMORLICA N, INDYK P, et al. Locality sensitive Hashing scheme based on p-stable distributions[C]//Proceedings of the Twentieth Annual Symposium on Computational Geometry. New York: ACM, 2004: 23-36.