[發(fā)明專利]一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710275575.8
• 申請(qǐng)日: 2017-04-25
• 公開(kāi)（公告）號(hào): CN107194414A
• 公開(kāi)（公告）日: 2017-09-22
• 發(fā)明（設(shè)計(jì)）人: 姚明海;林宣民;陳志浩;顧勤龍;王憲保
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 杭州之江專利事務(wù)所(普通合伙)33216
• 代理人: 林蜀

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)模式識(shí)別領(lǐng)域，特別是涉及一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法。

背景技術(shù)

近年來(lái)，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和傳感器技術(shù)的發(fā)展，應(yīng)用軟件和設(shè)備產(chǎn)生了大量的高維數(shù)據(jù)，且規(guī)模呈幾何級(jí)數(shù)增加。如何從這些數(shù)據(jù)中學(xué)習(xí)、抽取出有用的知識(shí)，至少有兩個(gè)主要的問(wèn)題需要解決：一是如何處理不斷增長(zhǎng)的數(shù)據(jù)，同時(shí)保持學(xué)習(xí)訓(xùn)練得到模型的高性能；以及其如何快速適應(yīng)動(dòng)態(tài)環(huán)境。第一個(gè)問(wèn)題可以通過(guò)增量學(xué)習(xí)的重要信息來(lái)解決。對(duì)于第二個(gè)問(wèn)題，可以通過(guò)快速刪除在學(xué)習(xí)中的不重要的數(shù)據(jù)來(lái)減少學(xué)習(xí)時(shí)間。

支持向量機(jī)（SVM）是一種以統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ)的機(jī)器學(xué)習(xí)技術(shù)，主要應(yīng)用于求解監(jiān)督學(xué)習(xí)問(wèn)題。在實(shí)際應(yīng)用中，訓(xùn)練樣本常常表現(xiàn)出上述的特點(diǎn)，這就要求分類器不斷地對(duì)新樣本重新訓(xùn)練。而增量學(xué)習(xí)旨在獲得原訓(xùn)練樣本與新增樣本并集的最優(yōu)解。因此，對(duì)于不斷增長(zhǎng)的數(shù)據(jù)集來(lái)說(shuō)，SVM增量學(xué)習(xí)具有其獨(dú)特的優(yōu)勢(shì)。Syed 最早提出了基于支持向量機(jī)的增量學(xué)習(xí)算法：固定劃分增量學(xué)習(xí)算法。其基本思想是：每次增量過(guò)程只保留支持向量集，舍棄非支持向量集，并本次SV集與所有新增樣本作為下一次增量學(xué)習(xí)的訓(xùn)練樣本。但事實(shí)上，這樣沒(méi)有對(duì)新增樣本進(jìn)行篩選，將其中沒(méi)用不重要的樣本也進(jìn)行了訓(xùn)練，導(dǎo)致增量訓(xùn)練速度變慢了；同時(shí)其中的一些糟糕的樣本有可能會(huì)影響精度。也有引入卡羅需-庫(kù)恩-塔克條件（KKT）條件，來(lái)提取新增樣本中的有用信息，即卡羅需-庫(kù)恩-塔克條件的SVM增量學(xué)習(xí)（KKT-ISVM）。后來(lái)的文獻(xiàn)都是基于KKT條件進(jìn)行改進(jìn)。也有的文獻(xiàn)引入了錯(cuò)誤驅(qū)動(dòng)的概念，把錯(cuò)分類樣本也考慮在內(nèi)。而2014年的文獻(xiàn)《一種新的基于 KKT 條件的錯(cuò)誤驅(qū)動(dòng) SVM 增量學(xué)習(xí)算法》提出新的基于KKT條件的錯(cuò)誤驅(qū)動(dòng)SVM增量學(xué)習(xí)。這些增量學(xué)習(xí)大部分利用KKT條件來(lái)篩選新增樣本，雖然克服了前一類方法在學(xué)習(xí)過(guò)程中可能丟失重要數(shù)據(jù)樣本的缺陷，但是其篩選速度慢，影響了訓(xùn)練學(xué)習(xí)的總體速度，在實(shí)時(shí)工業(yè)生產(chǎn)中無(wú)法滿足要求。

發(fā)明內(nèi)容

為解決現(xiàn)有技術(shù)的不足，提供一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法，這種算法充分利用歷史訓(xùn)練結(jié)果，在學(xué)習(xí)過(guò)程中選擇最有可能成為新SV的樣本，舍棄對(duì)分類結(jié)果沒(méi)有貢獻(xiàn)的歷史樣本，從而達(dá)到加快訓(xùn)練速度，減少存儲(chǔ)空間的目的。

為實(shí)現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：

一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法，包括以下步驟：

步驟1：訓(xùn)練初始樣本集得到支持向量集（SV集），SV集可以充分描述整個(gè)訓(xùn)練樣本集的特征，和訓(xùn)練樣本集是等價(jià)的；

步驟2：使用局部敏感哈希函數(shù)進(jìn)行哈希編碼投影，得到SV集對(duì)應(yīng)的哈希編碼集，稱為PCA-LSH方法；

步驟3：將新來(lái)的樣本通過(guò)同樣的PCA-LSH方法進(jìn)行哈希編碼，得到對(duì)應(yīng)的哈希編碼值，篩選出與上一步得到的SV集的哈希編碼值相鄰近的樣本，得到新增樣本篩選后的樣本集；

步驟4：將這些經(jīng)過(guò)篩選的新增樣本與初始訓(xùn)練樣本得到的SV集一起進(jìn)行訓(xùn)練來(lái)更新分類器；

步驟5：步驟(3)和(4)進(jìn)行迭代，直到?jīng)]有新的樣本到來(lái)為止。

上述的一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法，所述的步驟2包括以下子步驟：

步驟21，利用主成分分析（PCA）投影得到特征向量，使得這種特征子空間擁有很好的近似輸入空間，逼近誤差可以通過(guò)累積輸入特征成分的近似子空間占整個(gè)輸入空間的比率來(lái)控制；

步驟22，利用PCA-LSH方法將之前訓(xùn)練得到的支持向量集（SV集）進(jìn)行局部敏感哈希投影，得到各個(gè)支持向量對(duì)應(yīng)的哈希編碼值，組成一個(gè)初始化的哈希表。

上述的一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法，所述的步驟3包括以下子步驟：

步驟31，判斷是否有新增樣本進(jìn)入，如果有，則繼續(xù)第二子步驟；如果沒(méi)有則直接將SV集輸出，此時(shí)的SV集就是最終的分類器f的分類判斷標(biāo)準(zhǔn)；

步驟32，利用PCA-LSH方法將新增樣本進(jìn)行逐一的哈希編碼，得到一系列哈希編碼值；

步驟33，根據(jù)預(yù)先設(shè)定的正確率，篩選出新增樣本中哈希值落在初始化哈希表的樣本，這樣使得鄰近原SV集的新增樣本得以保留，這些樣本是影響新分類器SV集的重要數(shù)據(jù)樣本；如果都不存在，則直接跳到下一個(gè)新增樣本集篩選；如果有，繼續(xù)步驟四。

上述的一種基于局部敏感哈希的SVM快速增量學(xué)習(xí)算法，所述的步驟4包括以下子步驟：

步驟41，將篩選出來(lái)的符合要求的樣本和初始化SV集一起作為下一次SVM學(xué)習(xí)的訓(xùn)練集，得到一個(gè)新的SV集；