[發明專利]一種基于交替乘子法的分布式大數據分類系統及方法

在審

• 申請號: 201410498542.6
• 申請日: 2014-09-25
• 公開（公告）號: CN104217022A
• 公開（公告）日: 2014-12-17
• 發明（設計）人: 廖士中;李子達
• 申請（專利權）人: 天津大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F9/44
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 李素蘭

技術領域

本發明屬于大數據處理領域軟件，特別是涉及大規模數據的分布式支持向量分類方法。

背景技術

近年來，大數據的處理越來越成為學術界和工業界研究與生產的核心話題。大數據處理涉及數據的產生、存儲、分析和處理等等。適當的分析處理大數據，得到相應問題的模式和規律，是大數據可以有效為生產生活服務的關鍵所在。眾多大數據分析方法中，機器學習方法擁有堅實的理論基礎，良好的實用表現，越來越成為大數據分析處理的主要方法。

本發明所涉及的技術包括：支持向量機、交替乘子法、MPI分布式通訊模型和隨機特征。三種技術分別介紹如下：

支持向量機是一種簡單高效的機器學習方法，特別是在分類問題上有良好的分類效果和合理的誤差界。使用支持向量機進行大數據的分類分析，成為近年來大數據處理的有效方法。支持向量機分為線性支持向量機和非線性支持向量機。分類速度上，線性支持向量機的處理速度明顯快于非線性支持向量機；分類效果上，由于引入了核函數，非線性支持向量機擁有更好的分類效果。

然而，支持向量機也存在一定的問題。支持向量機的訓練過程需要很多計算資源的支撐，比如足夠的內存、足夠的CPU處理速度等。然而，當數據量增長到一定級別時，單機上的內存和CPU速度往往不能夠滿足支持向量機的要求。因此，將數據分散，進行分布式的訓練顯得越發的迫切。

交替乘子法是一種分布式的優化方法，該方法通過將優化問題分為若干子問題，使得每個子問題可以在不同計算機上進行運算，再在若干子問題之間添加一致性的約束，通過分布式的通信模式，每個子問題和中心計算機進行信息交互，使得子問題上得到的解保持一致。可以通過交替乘子法修改線性支持向量機，使之成為分布式的線性支持向量機。

MPI是一種分布式的通信模型。該模型實現了一對一、一對多、多對多等通信模式。該模型有許多可靠的實現版本如MPICH、OpenMPI等等。這些實現都對上述不同的通信模式進行了實現。在軟件中使用MPI，可以實現分布式框架下不同計算機之間的高效通信。

隨機特征是一種近似的核函數表示方法。通過將數據映射為隨機特征，再使用線性支持向量機對數據進行分類，就可以將線性支持向量機的訓練速度上的優勢與非線性支持向量機的分類效果上的優勢結合在一起，達到又快又好地進行分類的目標。

參考文獻：

1、Boyd?S，Parikh?N，Chu?E，Peleato?B，Eckstein?J.Distributed?optimization?and?statistical?learning?via?the?alternating?direction?method?of?multipliers.Foundations?andin?Machine?Learning，2011，3(1)：1–122.

2、Forero?PA，Cano?A，Giannakis?GB.Consensus-based?distributed?support?vector?machines.Journal?of?Machine?Learning?Research，2010，11：1663-1707.

3、Li?FX，Sminchisescu?C.Fourier?kernel?learning.In：Fitzgibbon?A，Lazebnik?S，Perona?P，Sato?Y，Schmid?C?eds.Proceedings?of?the12th?European?Conference?on?Computer?Vision.Berlin：Springer，2012.459-473.

4、Chitta?R，Jin?R，Jain?AK.Efficient?Kernel?Clustering?Using?Random?Fourier?Features.In：Proceedings?of?IEEE12th?International?Conference?on?Data?Mining.2012.161-170.

5、Cortes?C，Mohri?M，Talwalkar?A.On?the?Impact?of?Kernel?Approximation?on?Learning?Accuracy.In：Teh?YW，Titterington?M?eds.Proceedings?of?the?13th?International?Conference?on?Artificial?Intelligence?and?Statistics.2010.113-120.

發明內容