[發明專利]一種改進的分層級聯的支持向量機并行化方法

在審

• 申請號: 201710237933.6
• 申請日: 2017-04-13
• 公開（公告）號: CN107194411A
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 王念濱;陳龍;何鳴;周連科;王紅濱;童鵬鵬;王瑛琦;陳錫瑞;趙新杰;王昆明
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種改進的Casade SVM并行化方法。

背景技術

在大數據時代下，隨著互聯網和信息技術的快速發展和廣泛應用，產生了與人們生活息息相關的各種海量數據。其中在這些紛亂混雜的數據中，非結構化的文本信息占主要部分。面對如此巨大的文本數據，人們很難迅速地獲取自身有用的信息。如何快速地處理和發掘這些數據信息成為當前面臨的一大難題，這也促進了文本分類相關技術的深入研究廣泛運用。文本分類是數據挖掘范圍中十分重要和熱門的技術，文本分類技術可以把數量巨大的非結構化文本數據采用計算機能理解的方法進行計算，從而幫助人們更好、快速地獲取真正需要的信息，廣泛應用在輿情分析、和個性化推薦等領域中。

支持向量機SVM是數據挖掘領域中在統計學習基礎上的一種分類算法，通過將分類間隔最大化來構造最優分類超平面，來增強模型的泛化能力。其優點是很少出現過擬合現象，而且不依賴于特征的維數，在高維空間中具有很好的泛化能力。因此本發明在進行文本分類任務相關研究時，選用SVM作為分類器，進行文本分類任務的研究。

Cascade SVM是一種分層級聯的SVM并行訓練算法，其基本思想是：通過對數據集切分和濾除每級訓練過程中的非支持變量來達到對模型加速訓練的效果。其中Cascade SVM算法的訓練過程如圖1所示，在開始第一層訓練時，將模型原始訓練集切分成獨立的訓練子集，然后在每個子數據集上獨立的進行SVM訓練，得到各自對應的局部支持向量，并將得到的局部支持向量兩兩進行合并成為下一層的輸入，照著這樣依次類推，直到最終結果合并為一個數據集，在此基礎上訓練出全局支持向量，然后驗證得到的全局支持向量是否滿足訓練的精度，如果滿足要求則訓練結束，否則將最后的得到的全局支持向量反饋合并到第一層的數據集，繼續進行迭代訓練，直至最后輸出訓練模型。

對于Cascade SVM算法這種二分級聯訓練結構，在大數據集下訓練時，能夠節省大量的計算時間和存儲空間，是一種應用廣泛SVM大規模并行訓練學習方法。但是這種層疊結構目前有兩個不足之處：

(1)由Cascade SVM的這種二分級聯結構可知，在模型并行訓練過程中，假設第一層執行N個獨立的SVM，那么第二層只能執行N/2個SVM，依照這種方式到最后一層只能進行一個SVM的訓練。假設模型訓練在包含N個節點的集群上進行訓練，那么在模型訓練過程中會出現大量的節點資源空閑，這樣導致集群的資源利用率不高。

(2)在整個層級訓練的過程中，第一層SVM訓練結束后，大部分的非支持向量被剔除掉，后面的層級訓練中濾除的非支持向量數量較少，但是消耗了計算所用的大量時間。

發明內容

本發明的目的在于提供一種能夠有效地降低訓練時間和資源空閑，能夠避免兩兩進行合并方式中存在過濾非邊界樣本不足的問題的改進的分層級聯的支持向量機并行化方法。

本發明的目的是這樣實現的：

(1)輸入訓練數據集到HDFS(Hadoop Distributed File System)分布式文件存儲系統；

(2)從HDFS上讀取訓練數據集，生成RDD(Resilient Distribute Dataset)彈性分布式數據集，并根據指定的N值切分成樣本均勻的子數據集，N為并行的機器數；

(3)對于

(4)在N/2^i-1個數據塊上分別進行獨立的SVM訓練，將訓練得到的支持向量合并為全局支持向量MDi；

(5)設c的值為本層得到支持向量的個數同上層得到支持向量個數的比值，如果c＞預設值；

(6)跳轉到步驟(10)；

(7)否則執行下面步驟；

(8)將MDi均勻切分為N/2ⁱ份子數據集；

(9)循環結束；

(10)將MDi作為全局支持向量，進行SVM訓練；

(11)直至滿足停機條件，輸出支持向量機模型。

本發明主要針對在大規模數據集下，采用SVM的分類器模型進行分類。為了實現文本分類的并行化，本發明將圍繞著在不損失文本分類精度的前提下，如何提高模型訓練效率進行詳細地闡述。針對如何通過改進的現有的Cascade SVM并行算法，有效提高文本分類的效率、實現文本分類的并行化是當前研究的關鍵問題。本發明主要針對當前主流的SVM并行算法Cascade SVM進行研究與改進，提出了一種改進的Casade SVM并行化方法。

(1)改進的Cascade SVM算法