一種分布式大數據挖掘的快速在線學習算法

武靖娜, 楊 姝, 王劍輝

(沈陽師范大學 教育技術學院, 沈陽 110034)

?

一種分布式大數據挖掘的快速在線學習算法

武靖娜, 楊 姝, 王劍輝

(沈陽師范大學 教育技術學院, 沈陽 110034)

在大數據分析處理中,存在諸多問題,如數據類型多,處理效率低,從中獲得有用的信息和知識以便指導后續的決策,這是機器學習的最終目標。有效學習樣本逐漸增加,據此如何高效漸進地學習分類器是一個非常有價值的問題。大數據分析要求大量數據流的分布式挖掘要實時執行,設計這樣獨特的分布式挖掘系統:在線適應傳入數據的特征;在線處理大量的異構數據;在分布式學習者之間的有限數據訪問和通信能力。提出了一個基本的數據挖掘框架,并基于此研究了一種高效的在線學習算法。框架包括一個整體學習者和只能訪問不同輸入數據部分的多個局部學習者。通過利用在局部學習者學習的相關性模型,提出的學習算法可以優化預測精度而比現有最先進的學習解決方案需要更少的信息交換和計算復雜度。

大數據分析; 分布式挖掘; 實時; 在線學習算法

0 引 言

大數據分析包括處理在不同分布式數據源中的異構數據生成互補的數據集[1-2]。因此,數據集不僅表現為他們極大的體積而且還表現為異構和數據的分布式采集。分布式數據挖掘技術[3]已經被提出來處理分布式數據在遺傳算法方面也有所應用[4]。不同于傳統的集中式數據挖掘系統,分布式數據挖掘系統通常使用集成學習技術包括在層次結構的最低層次上操作的全球數據集的子集的多個局部學習者[5-7]的層次結構,并且一個或多個集合的學習者組合所有局部學習者的輸出。通過允許更大和更多樣化的數據集進行分析來擴大知識獲取的前沿,這樣的分布式數據挖掘系統伴隨著重要的設計挑戰是這項工作的重點。

大數據分析包括5個基本方面:

1) 可視化分析:不管是對數據分析專家還是普通用戶,數據可視化是數據分析工具最基本的要求。可視化可以直觀的展示數據,讓數據自己說話,讓觀眾聽到結果。

2) 數據挖掘算法:可視化是給人看的,數據挖掘就是給機器看的。集群、分割、孤立點分析還有其他的算法讓我們深入數據內部,挖掘價值。這些算法不僅要處理大數據的量,也要處理大數據的速度。

3) 預測性分析能力:數據挖掘可以讓分析員更好的理解數據,而預測性分析可以讓分析員根據可視化分析和數據挖掘的結果做出一些預測性的判斷。

4) 語義引擎:我們知道由于非結構化數據的多樣性帶來了數據分析的新的挑戰,我們需要一系列的工具去解析,提取,分析數據。語義引擎需要被設計成能夠從"文檔"中智能提取信息。

5) 數據質量和數據管理:數據質量和數據管理是一些管理方面的最佳實踐。通過標準化的流程和工具對數據進行處理可以保證一個預先定義好的高質量的分析結果。

在分布式系統中,每個局部學生只有有限的訪問整個數據集的權限。有2種類型的數據分區:在基于分布式數據挖掘的實例中,每個局部學習者有訪問整個實例的一個子集的權限,而在基于特征的分布式數據挖掘,每個局部學習者有訪問所有實例的特征空間的一個子集權限。在本文研究中,特別注重情景與功能分布式數據。由于大的數據量和個體學習者的有限通信能力,在此系統中是非常昂貴的,如果可行,將是在集中挖掘中花費十分昂貴。適合局部學習者的數據增長的非常快,數據的統計特性也可能隨時間動態改變。

為了處理這些挑戰,提出了分布式網絡學習機的總體框架:1)在線學習。不同于多數的分布式數據挖掘學習算法,這個新的學習機是可以處于脫機狀態。學習算法訓練模型在不同的學習者上以在線的方式,只需要一個經過訓練的數據。2)學習者之間的相互協作。此設計的主要目的在于處理這幾個問題:如何搭配學習者最優選擇局部學習者的學習模型,局部學習者如何優化更新他們的合作學習模式。3)交叉學習者相關開發。通過評估他們學習模型之間的交叉把局部學習者分到有相關的組中。在同一組中的學習者有著很高的關聯性能夠相互協調的訓練;不同組中的學習者將會單獨分開訓練。因此,可以控制計算復雜性和信息交換通過調整交叉相關性閾值在局部學習者中。

1 系統框架

目標是在學習者的權向量的正則化約束[10]之下,設計算法能夠確定學習模型且預測誤差在給定的情況下均方最小化。在每個周期n相應的優化問題表示如下:

(1)

算法1 整體權重更新:

(2)

(3)

為了解決這個問題,提出了在線算法[11]來更新整體學習者的權重向量w和每個局部學習者的學習模型bk。接下來將要討論詳細的改進算法。

(4)

(5)

最小的整體訓練剩余為

(6)

(7)

每一個局部學習者在每一個周期中基本的學習過程可以簡要的總結為如下。 整體學習者更新完w之后, 發送訓練消息到局部學習者。 每個局部學習者使用這個消息來更新它自己的權重向量bk。 直觀來說以合作方式這是一個比較好的訓練所有局部學習者。 當每一個局部學習者更新它的學習模型時候, 需要把所有其他局部學習者的訓練誤差考慮在內, 為了在最后預測輸出時最小化誤差。 然而, 這種方法可能引起不必要的信息交換和可能的過度學習問題, 尤其當一些局部的學習者是關聯松散, 需要訓練有素的相互獨立性格。對于分布式數據挖掘這些屬性是理想的, 從學習者不僅具有好的預測精度還要能夠很快適應時變數據動態與穩定的信息交換的能力中獲得。 這促使下一步的訓練算法的生成。

通過檢查方差矩陣CTC,提出了如下的算法2和在局部學習者之間以更少的信息交換和更快的收斂速度相關更新預測精度。

算法2 相關權重更新

(8)

確定相關局部學習者和局部學習者的集合Covk。

(9)

(10)

(11)

2 實驗分析

在這一部分,提供了初步實驗結果來表明分布式算法的效率關于KDD數據集。這個數據集包含了7周的網絡流量4g的壓縮二進制TCP轉儲數據,這是被加工成大約500萬連接記錄,其中隨機選擇5萬條記錄作為訓練數據集。每個連接記錄標記作為一個“正常”的連接或攻擊。

通過分布式算法分類每個連接標簽y∈{1,0}來建造預測模型,0表明正常連接,1代表攻擊。在這50 000條記錄中,35.3%受到攻擊。每個記錄包含40個屬性。每一個局部學習者包含所有或者部分基分類器如表1所示。

表1 基分類器

使用2個指標----精度和召回來衡量分布式學習系統的性能。在第一個實驗中,利用10個局部學習者檢測該算法的性能。選擇10 000個訓練數據樣本和10 000個測試數據樣本。為了做比較,引入三元學習算法基準,所有的都使用一種離線的方式訓練數據樣本:Ada-boost算法[13-14],L-2Boosting算法[15],Meta-L[16]算法。L-2Boosting算法以各自的局部學習者的輸出作為它的輸入,使用一個L2線性回歸來改正模型。然而,從整體學習者到局部學習者沒有反饋。因此,在訓練過程中每個局部學習者的模型是固定的。在Meta-L算法中,整體學習者簡單結合了局部學習者的輸出以一種附加的形式,不能自適應地調整權重分配到不同局部學習者中。

結果如表2所示。很明顯算法2和Ada-boost算法有同樣高的精確度。因此,它是非常重要的更新模型對于整體學習者和局部學習者朝著一個方向合作,能增加總體預測精度。在第一個實驗中,收斂速度是無法評估的。第2個實驗中,檢查算法2的運行時間行為,設置采用同第一個實驗中局部學習者一樣的數據。圖1展示出了結果,可以看出,使用正確的局部學習者之間的關聯性,算法收斂速度是加快的。

圖1 預測精度的進化 表2 不同算法的效率

算法精確度/%撤銷率/%算法285.382.1Ada-boost算法88.184.3L-2Boosting算法72.269.5Meta-L算法73.171.8

3 結 論

提出了一個對于在線學習算法大規模分布式數據挖掘應用程序的通用框架設計,專注于分布式功能分布式數據線性回歸問題通過不同局部的學習者。對于整體學習者和局部學習者的最佳回歸量是經過嚴格推斷得出來的,然后設計了2種在線算法能收斂到最優回歸量:合作更新算法和相關的更新算法。實驗表明,相關更新算法明顯優于合作方面的更新算法在所需的計算復雜性和通信成本方面,預測精度有輕微的差別。結果表明,巧妙利用局部學習者之間的關聯信息, 基于應用程序的需求和最終用戶提出了在線學習算法可以靈活地平衡計算復雜度,溝通成本和預測準確性。

[1]程學旗,靳小龍,王元卓,等. 大數據系統和分析技術綜述[J]. 軟件學報, 2014,25(9):1889-1908.

[2]申彥. 大規模數據集高效數據挖掘算法研究[D]. 揚州:江蘇大學, 2013.

[3]胡文瑜,孫志揮,張柏禮. 分布式數據挖掘中的最優K相異性取樣技術[J]. 東南大學學報(自然科學版), 2008,38(3):385-389.

[4]劉天華,殷守林. 一種改進的遺傳卡爾曼算法在室內定位中的研究[J]. 沈陽師范大學學報(自然科學版), 2015,33(2):265-269.

[5]張凌志,薛晶心,張媛. 微信模式下個體知識學習的特征和交流模式研究[J]. 情報理論與實踐, 2015,38(7):67-71.

[6]ANHAI D, PEDRO D, ALON H. Learning to match the schemas of data sources:a multistrategy approach[J]. Machine Learning, 2003,50(3):279-301.

[7]覃瓊霞,江濤,陸文聰. 計量模型中的加總偏誤與內生性:一種數值模擬方法[J]. 數量經濟技術經濟研究, 2013,30(12):140-157.

[8]石斌,劉思峰,黨耀國,等. 無偏灰色預測模型遞推解法及其優化[J]. 系統工程理論與實踐, 2011,31(8):1532-1538.

[9]唐述,龔衛國,仲建華. 稀疏平滑特性的多正則化約束圖像盲復原方法[J]. 軟件學報, 2013,24(5):1143-1154.

[10]于彥偉,王沁,鄺俊,等. 一種基于密度的空間數據流在線聚類算法[J]. 自動化學報, 2012,38(6):1051-1059.

[11]陳曉曦,王延杰,劉戀. 小波閾值去噪法的深入研究[J]. 激光與紅外, 2012,42(1):105-110.

[12]龍建武,申鉉京,陳海鵬. 自適應最小誤差閾值分割算法[J]. 自動化學報, 2012,38(7):1134-1144.

[13]曹瑩,苗啟廣,劉家辰,等. AdaBoost算法研究進展與展望[J]. 自動化學報, 2013,39(6):745-758.

[14]李闖,丁曉青,吳佑壽. 一種改進的AdaBoost算法----AD AdaBoost[J]. 計算機學報, 2007,30(1):103-109.

[15]宋捷,吳喜之. 一種新的Boosting回歸樹方法[J]. 統計與信息論壇, 2010,25(5):9-13.

[16]王凌,鄭大鐘. Meta-heuristic算法研究進展[J]. 控制與決策, 2000,15(3):257-262.

A new fast online learning algorithm based on distributed mining of big data

WUJingna,YANGShu,WANGJianhui

(College of Education Technology, Shenyang Normal University, Shenyang 110034, China)

In big data analysis and processing, there are many problems, such as data types, low processing efficiency. Getting useful information and knowledge to guide the subsequent decisions is the ultimate goal of machine learning. Effective learning samples increase gradually, so how effectively to learn classifier is a very valuable problem. Big data analysis requires a large amount of data flow to perform real-time distributed mining. It designs unique distributed mining system: online adapting to the characteristics of the incoming data; online processing a large amount of heterogeneous data; the limited data ability to access between distributed learners and communication. It proposes a basic framework of data mining, and based on this it researches a kind of efficient online learning algorithm. Framework contains the whole different learners and local learners which can only have access to the input data. By using the local correlation model, the learning algorithm can optimize the prediction precision than the existing advanced learning solutions, which requires less exchange of information and computational complexity.

big data analysis; distributed mininrg; real-time; online learning algorithm

2015-08-26。

國家自然科學基金資助項目(60970112)。

武靖娜(1986-),女,遼寧朝陽人,沈陽師范大學碩士研究生; 通信作者:楊 姝(1963-),女,遼寧沈陽人,沈陽師范大學教授,博士。

1673-5862(2016)01-0100-05

TP393.08

A

10.3969/ j.issn.1673-5862.2016.01.023