武靖娜, 楊 姝, 王劍輝
(沈陽師范大學(xué) 教育技術(shù)學(xué)院, 沈陽 110034)
?
一種分布式大數(shù)據(jù)挖掘的快速在線學(xué)習(xí)算法
武靖娜, 楊 姝, 王劍輝
(沈陽師范大學(xué) 教育技術(shù)學(xué)院, 沈陽 110034)
在大數(shù)據(jù)分析處理中,存在諸多問題,如數(shù)據(jù)類型多,處理效率低,從中獲得有用的信息和知識以便指導(dǎo)后續(xù)的決策,這是機器學(xué)習(xí)的最終目標(biāo)。有效學(xué)習(xí)樣本逐漸增加,據(jù)此如何高效漸進地學(xué)習(xí)分類器是一個非常有價值的問題。大數(shù)據(jù)分析要求大量數(shù)據(jù)流的分布式挖掘要實時執(zhí)行,設(shè)計這樣獨特的分布式挖掘系統(tǒng):在線適應(yīng)傳入數(shù)據(jù)的特征;在線處理大量的異構(gòu)數(shù)據(jù);在分布式學(xué)習(xí)者之間的有限數(shù)據(jù)訪問和通信能力。提出了一個基本的數(shù)據(jù)挖掘框架,并基于此研究了一種高效的在線學(xué)習(xí)算法。框架包括一個整體學(xué)習(xí)者和只能訪問不同輸入數(shù)據(jù)部分的多個局部學(xué)習(xí)者。通過利用在局部學(xué)習(xí)者學(xué)習(xí)的相關(guān)性模型,提出的學(xué)習(xí)算法可以優(yōu)化預(yù)測精度而比現(xiàn)有最先進的學(xué)習(xí)解決方案需要更少的信息交換和計算復(fù)雜度。
大數(shù)據(jù)分析; 分布式挖掘; 實時; 在線學(xué)習(xí)算法
大數(shù)據(jù)分析包括處理在不同分布式數(shù)據(jù)源中的異構(gòu)數(shù)據(jù)生成互補的數(shù)據(jù)集[1-2]。因此,數(shù)據(jù)集不僅表現(xiàn)為他們極大的體積而且還表現(xiàn)為異構(gòu)和數(shù)據(jù)的分布式采集。分布式數(shù)據(jù)挖掘技術(shù)[3]已經(jīng)被提出來處理分布式數(shù)據(jù)在遺傳算法方面也有所應(yīng)用[4]。不同于傳統(tǒng)的集中式數(shù)據(jù)挖掘系統(tǒng),分布式數(shù)據(jù)挖掘系統(tǒng)通常使用集成學(xué)習(xí)技術(shù)包括在層次結(jié)構(gòu)的最低層次上操作的全球數(shù)據(jù)集的子集的多個局部學(xué)習(xí)者[5-7]的層次結(jié)構(gòu),并且一個或多個集合的學(xué)習(xí)者組合所有局部學(xué)習(xí)者的輸出。通過允許更大和更多樣化的數(shù)據(jù)集進行分析來擴大知識獲取的前沿,這樣的分布式數(shù)據(jù)挖掘系統(tǒng)伴隨著重要的設(shè)計挑戰(zhàn)是這項工作的重點。
大數(shù)據(jù)分析包括5個基本方面:
1) 可視化分析:不管是對數(shù)據(jù)分析專家還是普通用戶,數(shù)據(jù)可視化是數(shù)據(jù)分析工具最基本的要求??梢暬梢灾庇^的展示數(shù)據(jù),讓數(shù)據(jù)自己說話,讓觀眾聽到結(jié)果。
2) 數(shù)據(jù)挖掘算法:可視化是給人看的,數(shù)據(jù)挖掘就是給機器看的。集群、分割、孤立點分析還有其他的算法讓我們深入數(shù)據(jù)內(nèi)部,挖掘價值。這些算法不僅要處理大數(shù)據(jù)的量,也要處理大數(shù)據(jù)的速度。
3) 預(yù)測性分析能力:數(shù)據(jù)挖掘可以讓分析員更好的理解數(shù)據(jù),而預(yù)測性分析可以讓分析員根據(jù)可視化分析和數(shù)據(jù)挖掘的結(jié)果做出一些預(yù)測性的判斷。
4) 語義引擎:我們知道由于非結(jié)構(gòu)化數(shù)據(jù)的多樣性帶來了數(shù)據(jù)分析的新的挑戰(zhàn),我們需要一系列的工具去解析,提取,分析數(shù)據(jù)。語義引擎需要被設(shè)計成能夠從"文檔"中智能提取信息。
5) 數(shù)據(jù)質(zhì)量和數(shù)據(jù)管理:數(shù)據(jù)質(zhì)量和數(shù)據(jù)管理是一些管理方面的最佳實踐。通過標(biāo)準(zhǔn)化的流程和工具對數(shù)據(jù)進行處理可以保證一個預(yù)先定義好的高質(zhì)量的分析結(jié)果。
在分布式系統(tǒng)中,每個局部學(xué)生只有有限的訪問整個數(shù)據(jù)集的權(quán)限。有2種類型的數(shù)據(jù)分區(qū):在基于分布式數(shù)據(jù)挖掘的實例中,每個局部學(xué)習(xí)者有訪問整個實例的一個子集的權(quán)限,而在基于特征的分布式數(shù)據(jù)挖掘,每個局部學(xué)習(xí)者有訪問所有實例的特征空間的一個子集權(quán)限。在本文研究中,特別注重情景與功能分布式數(shù)據(jù)。由于大的數(shù)據(jù)量和個體學(xué)習(xí)者的有限通信能力,在此系統(tǒng)中是非常昂貴的,如果可行,將是在集中挖掘中花費十分昂貴。適合局部學(xué)習(xí)者的數(shù)據(jù)增長的非???數(shù)據(jù)的統(tǒng)計特性也可能隨時間動態(tài)改變。
為了處理這些挑戰(zhàn),提出了分布式網(wǎng)絡(luò)學(xué)習(xí)機的總體框架:1)在線學(xué)習(xí)。不同于多數(shù)的分布式數(shù)據(jù)挖掘?qū)W習(xí)算法,這個新的學(xué)習(xí)機是可以處于脫機狀態(tài)。學(xué)習(xí)算法訓(xùn)練模型在不同的學(xué)習(xí)者上以在線的方式,只需要一個經(jīng)過訓(xùn)練的數(shù)據(jù)。2)學(xué)習(xí)者之間的相互協(xié)作。此設(shè)計的主要目的在于處理這幾個問題:如何搭配學(xué)習(xí)者最優(yōu)選擇局部學(xué)習(xí)者的學(xué)習(xí)模型,局部學(xué)習(xí)者如何優(yōu)化更新他們的合作學(xué)習(xí)模式。3)交叉學(xué)習(xí)者相關(guān)開發(fā)。通過評估他們學(xué)習(xí)模型之間的交叉把局部學(xué)習(xí)者分到有相關(guān)的組中。在同一組中的學(xué)習(xí)者有著很高的關(guān)聯(lián)性能夠相互協(xié)調(diào)的訓(xùn)練;不同組中的學(xué)習(xí)者將會單獨分開訓(xùn)練。因此,可以控制計算復(fù)雜性和信息交換通過調(diào)整交叉相關(guān)性閾值在局部學(xué)習(xí)者中。
目標(biāo)是在學(xué)習(xí)者的權(quán)向量的正則化約束[10]之下,設(shè)計算法能夠確定學(xué)習(xí)模型且預(yù)測誤差在給定的情況下均方最小化。在每個周期n相應(yīng)的優(yōu)化問題表示如下:
(1)
算法1 整體權(quán)重更新:
(2)
(3)
為了解決這個問題,提出了在線算法[11]來更新整體學(xué)習(xí)者的權(quán)重向量w和每個局部學(xué)習(xí)者的學(xué)習(xí)模型bk。接下來將要討論詳細的改進算法。
(4)
(5)
最小的整體訓(xùn)練剩余為
(6)
(7)
每一個局部學(xué)習(xí)者在每一個周期中基本的學(xué)習(xí)過程可以簡要的總結(jié)為如下。 整體學(xué)習(xí)者更新完w之后, 發(fā)送訓(xùn)練消息到局部學(xué)習(xí)者。 每個局部學(xué)習(xí)者使用這個消息來更新它自己的權(quán)重向量bk。 直觀來說以合作方式這是一個比較好的訓(xùn)練所有局部學(xué)習(xí)者。 當(dāng)每一個局部學(xué)習(xí)者更新它的學(xué)習(xí)模型時候, 需要把所有其他局部學(xué)習(xí)者的訓(xùn)練誤差考慮在內(nèi), 為了在最后預(yù)測輸出時最小化誤差。 然而, 這種方法可能引起不必要的信息交換和可能的過度學(xué)習(xí)問題, 尤其當(dāng)一些局部的學(xué)習(xí)者是關(guān)聯(lián)松散, 需要訓(xùn)練有素的相互獨立性格。對于分布式數(shù)據(jù)挖掘這些屬性是理想的, 從學(xué)習(xí)者不僅具有好的預(yù)測精度還要能夠很快適應(yīng)時變數(shù)據(jù)動態(tài)與穩(wěn)定的信息交換的能力中獲得。 這促使下一步的訓(xùn)練算法的生成。
通過檢查方差矩陣CTC,提出了如下的算法2和在局部學(xué)習(xí)者之間以更少的信息交換和更快的收斂速度相關(guān)更新預(yù)測精度。
算法2 相關(guān)權(quán)重更新
(8)
確定相關(guān)局部學(xué)習(xí)者和局部學(xué)習(xí)者的集合Covk。
(9)
(10)
(11)
在這一部分,提供了初步實驗結(jié)果來表明分布式算法的效率關(guān)于KDD數(shù)據(jù)集。這個數(shù)據(jù)集包含了7周的網(wǎng)絡(luò)流量4g的壓縮二進制TCP轉(zhuǎn)儲數(shù)據(jù),這是被加工成大約500萬連接記錄,其中隨機選擇5萬條記錄作為訓(xùn)練數(shù)據(jù)集。每個連接記錄標(biāo)記作為一個“正?!钡倪B接或攻擊。
通過分布式算法分類每個連接標(biāo)簽y∈{1,0}來建造預(yù)測模型,0表明正常連接,1代表攻擊。在這50 000條記錄中,35.3%受到攻擊。每個記錄包含40個屬性。每一個局部學(xué)習(xí)者包含所有或者部分基分類器如表1所示。
表1 基分類器
使用2個指標(biāo)----精度和召回來衡量分布式學(xué)習(xí)系統(tǒng)的性能。在第一個實驗中,利用10個局部學(xué)習(xí)者檢測該算法的性能。選擇10 000個訓(xùn)練數(shù)據(jù)樣本和10 000個測試數(shù)據(jù)樣本。為了做比較,引入三元學(xué)習(xí)算法基準(zhǔn),所有的都使用一種離線的方式訓(xùn)練數(shù)據(jù)樣本:Ada-boost算法[13-14],L-2Boosting算法[15],Meta-L[16]算法。L-2Boosting算法以各自的局部學(xué)習(xí)者的輸出作為它的輸入,使用一個L2線性回歸來改正模型。然而,從整體學(xué)習(xí)者到局部學(xué)習(xí)者沒有反饋。因此,在訓(xùn)練過程中每個局部學(xué)習(xí)者的模型是固定的。在Meta-L算法中,整體學(xué)習(xí)者簡單結(jié)合了局部學(xué)習(xí)者的輸出以一種附加的形式,不能自適應(yīng)地調(diào)整權(quán)重分配到不同局部學(xué)習(xí)者中。
結(jié)果如表2所示。很明顯算法2和Ada-boost算法有同樣高的精確度。因此,它是非常重要的更新模型對于整體學(xué)習(xí)者和局部學(xué)習(xí)者朝著一個方向合作,能增加總體預(yù)測精度。在第一個實驗中,收斂速度是無法評估的。第2個實驗中,檢查算法2的運行時間行為,設(shè)置采用同第一個實驗中局部學(xué)習(xí)者一樣的數(shù)據(jù)。圖1展示出了結(jié)果,可以看出,使用正確的局部學(xué)習(xí)者之間的關(guān)聯(lián)性,算法收斂速度是加快的。
圖1 預(yù)測精度的進化 表2 不同算法的效率
算法精確度/%撤銷率/%算法285.382.1Ada-boost算法88.184.3L-2Boosting算法72.269.5Meta-L算法73.171.8
提出了一個對于在線學(xué)習(xí)算法大規(guī)模分布式數(shù)據(jù)挖掘應(yīng)用程序的通用框架設(shè)計,專注于分布式功能分布式數(shù)據(jù)線性回歸問題通過不同局部的學(xué)習(xí)者。對于整體學(xué)習(xí)者和局部學(xué)習(xí)者的最佳回歸量是經(jīng)過嚴(yán)格推斷得出來的,然后設(shè)計了2種在線算法能收斂到最優(yōu)回歸量:合作更新算法和相關(guān)的更新算法。實驗表明,相關(guān)更新算法明顯優(yōu)于合作方面的更新算法在所需的計算復(fù)雜性和通信成本方面,預(yù)測精度有輕微的差別。結(jié)果表明,巧妙利用局部學(xué)習(xí)者之間的關(guān)聯(lián)信息, 基于應(yīng)用程序的需求和最終用戶提出了在線學(xué)習(xí)算法可以靈活地平衡計算復(fù)雜度,溝通成本和預(yù)測準(zhǔn)確性。
[1]程學(xué)旗,靳小龍,王元卓,等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J]. 軟件學(xué)報, 2014,25(9):1889-1908.
[2]申彥. 大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究[D]. 揚州:江蘇大學(xué), 2013.
[3]胡文瑜,孫志揮,張柏禮. 分布式數(shù)據(jù)挖掘中的最優(yōu)K相異性取樣技術(shù)[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2008,38(3):385-389.
[4]劉天華,殷守林. 一種改進的遺傳卡爾曼算法在室內(nèi)定位中的研究[J]. 沈陽師范大學(xué)學(xué)報(自然科學(xué)版), 2015,33(2):265-269.
[5]張凌志,薛晶心,張媛. 微信模式下個體知識學(xué)習(xí)的特征和交流模式研究[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]覃瓊霞,江濤,陸文聰. 計量模型中的加總偏誤與內(nèi)生性:一種數(shù)值模擬方法[J]. 數(shù)量經(jīng)濟技術(shù)經(jīng)濟研究, 2013,30(12):140-157.
[8]石斌,劉思峰,黨耀國,等. 無偏灰色預(yù)測模型遞推解法及其優(yōu)化[J]. 系統(tǒng)工程理論與實踐, 2011,31(8):1532-1538.
[9]唐述,龔衛(wèi)國,仲建華. 稀疏平滑特性的多正則化約束圖像盲復(fù)原方法[J]. 軟件學(xué)報, 2013,24(5):1143-1154.
[10]于彥偉,王沁,鄺俊,等. 一種基于密度的空間數(shù)據(jù)流在線聚類算法[J]. 自動化學(xué)報, 2012,38(6):1051-1059.
[11]陳曉曦,王延杰,劉戀. 小波閾值去噪法的深入研究[J]. 激光與紅外, 2012,42(1):105-110.
[12]龍建武,申鉉京,陳海鵬. 自適應(yīng)最小誤差閾值分割算法[J]. 自動化學(xué)報, 2012,38(7):1134-1144.
[13]曹瑩,苗啟廣,劉家辰,等. AdaBoost算法研究進展與展望[J]. 自動化學(xué)報, 2013,39(6):745-758.
[14]李闖,丁曉青,吳佑壽. 一種改進的AdaBoost算法----AD AdaBoost[J]. 計算機學(xué)報, 2007,30(1):103-109.
[15]宋捷,吳喜之. 一種新的Boosting回歸樹方法[J]. 統(tǒng)計與信息論壇, 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。
國家自然科學(xué)基金資助項目(60970112)。
武靖娜(1986-),女,遼寧朝陽人,沈陽師范大學(xué)碩士研究生; 通信作者:楊 姝(1963-),女,遼寧沈陽人,沈陽師范大學(xué)教授,博士。
1673-5862(2016)01-0100-05
TP393.08
A
10.3969/ j.issn.1673-5862.2016.01.023