一種分布式大數(shù)據(jù)挖掘的快速在線學(xué)習(xí)算法

武靖娜, 楊 姝, 王劍輝

(沈陽(yáng)師范大學(xué) 教育技術(shù)學(xué)院, 沈陽(yáng) 110034)

?

一種分布式大數(shù)據(jù)挖掘的快速在線學(xué)習(xí)算法

武靖娜, 楊 姝, 王劍輝

(沈陽(yáng)師范大學(xué) 教育技術(shù)學(xué)院, 沈陽(yáng) 110034)

在大數(shù)據(jù)分析處理中,存在諸多問(wèn)題,如數(shù)據(jù)類型多,處理效率低,從中獲得有用的信息和知識(shí)以便指導(dǎo)后續(xù)的決策,這是機(jī)器學(xué)習(xí)的最終目標(biāo)。有效學(xué)習(xí)樣本逐漸增加,據(jù)此如何高效漸進(jìn)地學(xué)習(xí)分類器是一個(gè)非常有價(jià)值的問(wèn)題。大數(shù)據(jù)分析要求大量數(shù)據(jù)流的分布式挖掘要實(shí)時(shí)執(zhí)行,設(shè)計(jì)這樣獨(dú)特的分布式挖掘系統(tǒng):在線適應(yīng)傳入數(shù)據(jù)的特征;在線處理大量的異構(gòu)數(shù)據(jù);在分布式學(xué)習(xí)者之間的有限數(shù)據(jù)訪問(wèn)和通信能力。提出了一個(gè)基本的數(shù)據(jù)挖掘框架,并基于此研究了一種高效的在線學(xué)習(xí)算法?？蚣馨ㄒ粋€(gè)整體學(xué)習(xí)者和只能訪問(wèn)不同輸入數(shù)據(jù)部分的多個(gè)局部學(xué)習(xí)者。通過(guò)利用在局部學(xué)習(xí)者學(xué)習(xí)的相關(guān)性模型,提出的學(xué)習(xí)算法可以優(yōu)化預(yù)測(cè)精度而比現(xiàn)有最先進(jìn)的學(xué)習(xí)解決方案需要更少的信息交換和計(jì)算復(fù)雜度。

大數(shù)據(jù)分析; 分布式挖掘; 實(shí)時(shí); 在線學(xué)習(xí)算法

0 引 言

大數(shù)據(jù)分析包括處理在不同分布式數(shù)據(jù)源中的異構(gòu)數(shù)據(jù)生成互補(bǔ)的數(shù)據(jù)集[1-2]。因此,數(shù)據(jù)集不僅表現(xiàn)為他們極大的體積而且還表現(xiàn)為異構(gòu)和數(shù)據(jù)的分布式采集。分布式數(shù)據(jù)挖掘技術(shù)[3]已經(jīng)被提出來(lái)處理分布式數(shù)據(jù)在遺傳算法方面也有所應(yīng)用[4]。不同于傳統(tǒng)的集中式數(shù)據(jù)挖掘系統(tǒng),分布式數(shù)據(jù)挖掘系統(tǒng)通常使用集成學(xué)習(xí)技術(shù)包括在層次結(jié)構(gòu)的最低層次上操作的全球數(shù)據(jù)集的子集的多個(gè)局部學(xué)習(xí)者[5-7]的層次結(jié)構(gòu),并且一個(gè)或多個(gè)集合的學(xué)習(xí)者組合所有局部學(xué)習(xí)者的輸出。通過(guò)允許更大和更多樣化的數(shù)據(jù)集進(jìn)行分析來(lái)擴(kuò)大知識(shí)獲取的前沿,這樣的分布式數(shù)據(jù)挖掘系統(tǒng)伴隨著重要的設(shè)計(jì)挑戰(zhàn)是這項(xiàng)工作的重點(diǎn)。

大數(shù)據(jù)分析包括5個(gè)基本方面:

1) 可視化分析:不管是對(duì)數(shù)據(jù)分析專家還是普通用戶,數(shù)據(jù)可視化是數(shù)據(jù)分析工具最基本的要求?？梢暬梢灾庇^的展示數(shù)據(jù),讓數(shù)據(jù)自己說(shuō)話,讓觀眾聽到結(jié)果。

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

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

4) 語(yǔ)義引擎:我們知道由于非結(jié)構(gòu)化數(shù)據(jù)的多樣性帶來(lái)了數(shù)據(jù)分析的新的挑戰(zhàn),我們需要一系列的工具去解析,提取,分析數(shù)據(jù)。語(yǔ)義引擎需要被設(shè)計(jì)成能夠從"文檔"中智能提取信息。

5) 數(shù)據(jù)質(zhì)量和數(shù)據(jù)管理:數(shù)據(jù)質(zhì)量和數(shù)據(jù)管理是一些管理方面的最佳實(shí)踐。通過(guò)標(biāo)準(zhǔn)化的流程和工具對(duì)數(shù)據(jù)進(jìn)行處理可以保證一個(gè)預(yù)先定義好的高質(zhì)量的分析結(jié)果。

在分布式系統(tǒng)中,每個(gè)局部學(xué)生只有有限的訪問(wèn)整個(gè)數(shù)據(jù)集的權(quán)限。有2種類型的數(shù)據(jù)分區(qū):在基于分布式數(shù)據(jù)挖掘的實(shí)例中,每個(gè)局部學(xué)習(xí)者有訪問(wèn)整個(gè)實(shí)例的一個(gè)子集的權(quán)限,而在基于特征的分布式數(shù)據(jù)挖掘,每個(gè)局部學(xué)習(xí)者有訪問(wèn)所有實(shí)例的特征空間的一個(gè)子集權(quán)限。在本文研究中,特別注重情景與功能分布式數(shù)據(jù)。由于大的數(shù)據(jù)量和個(gè)體學(xué)習(xí)者的有限通信能力,在此系統(tǒng)中是非常昂貴的,如果可行,將是在集中挖掘中花費(fèi)十分昂貴。適合局部學(xué)習(xí)者的數(shù)據(jù)增長(zhǎng)的非常快,數(shù)據(jù)的統(tǒng)計(jì)特性也可能隨時(shí)間動(dòng)態(tài)改變。

為了處理這些挑戰(zhàn),提出了分布式網(wǎng)絡(luò)學(xué)習(xí)機(jī)的總體框架:1)在線學(xué)習(xí)。不同于多數(shù)的分布式數(shù)據(jù)挖掘?qū)W習(xí)算法,這個(gè)新的學(xué)習(xí)機(jī)是可以處于脫機(jī)狀態(tài)。學(xué)習(xí)算法訓(xùn)練模型在不同的學(xué)習(xí)者上以在線的方式,只需要一個(gè)經(jīng)過(guò)訓(xùn)練的數(shù)據(jù)。2)學(xué)習(xí)者之間的相互協(xié)作。此設(shè)計(jì)的主要目的在于處理這幾個(gè)問(wèn)題:如何搭配學(xué)習(xí)者最優(yōu)選擇局部學(xué)習(xí)者的學(xué)習(xí)模型,局部學(xué)習(xí)者如何優(yōu)化更新他們的合作學(xué)習(xí)模式。3)交叉學(xué)習(xí)者相關(guān)開發(fā)。通過(guò)評(píng)估他們學(xué)習(xí)模型之間的交叉把局部學(xué)習(xí)者分到有相關(guān)的組中。在同一組中的學(xué)習(xí)者有著很高的關(guān)聯(lián)性能夠相互協(xié)調(diào)的訓(xùn)練;不同組中的學(xué)習(xí)者將會(huì)單獨(dú)分開訓(xùn)練。因此,可以控制計(jì)算復(fù)雜性和信息交換通過(guò)調(diào)整交叉相關(guān)性閾值在局部學(xué)習(xí)者中。

1 系統(tǒng)框架

目標(biāo)是在學(xué)習(xí)者的權(quán)向量的正則化約束[10]之下,設(shè)計(jì)算法能夠確定學(xué)習(xí)模型且預(yù)測(cè)誤差在給定的情況下均方最小化。在每個(gè)周期n相應(yīng)的優(yōu)化問(wèn)題表示如下:

(1)

算法1 整體權(quán)重更新:

(2)

(3)

為了解決這個(gè)問(wèn)題,提出了在線算法[11]來(lái)更新整體學(xué)習(xí)者的權(quán)重向量w和每個(gè)局部學(xué)習(xí)者的學(xué)習(xí)模型bk。接下來(lái)將要討論詳細(xì)的改進(jìn)算法。

(4)

(5)

最小的整體訓(xùn)練剩余為

(6)

(7)

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

通過(guò)檢查方差矩陣CTC,提出了如下的算法2和在局部學(xué)習(xí)者之間以更少的信息交換和更快的收斂速度相關(guān)更新預(yù)測(cè)精度。

算法2 相關(guān)權(quán)重更新

(8)

確定相關(guān)局部學(xué)習(xí)者和局部學(xué)習(xí)者的集合Covk。

(9)

(10)

(11)

2 實(shí)驗(yàn)分析

在這一部分,提供了初步實(shí)驗(yàn)結(jié)果來(lái)表明分布式算法的效率關(guān)于KDD數(shù)據(jù)集。這個(gè)數(shù)據(jù)集包含了7周的網(wǎng)絡(luò)流量4g的壓縮二進(jìn)制TCP轉(zhuǎn)儲(chǔ)數(shù)據(jù),這是被加工成大約500萬(wàn)連接記錄,其中隨機(jī)選擇5萬(wàn)條記錄作為訓(xùn)練數(shù)據(jù)集。每個(gè)連接記錄標(biāo)記作為一個(gè)“正?！钡倪B接或攻擊。

通過(guò)分布式算法分類每個(gè)連接標(biāo)簽y∈{1,0}來(lái)建造預(yù)測(cè)模型,0表明正常連接,1代表攻擊。在這50 000條記錄中,35.3%受到攻擊。每個(gè)記錄包含40個(gè)屬性。每一個(gè)局部學(xué)習(xí)者包含所有或者部分基分類器如表1所示。

表1 基分類器

使用2個(gè)指標(biāo)----精度和召回來(lái)衡量分布式學(xué)習(xí)系統(tǒng)的性能。在第一個(gè)實(shí)驗(yàn)中,利用10個(gè)局部學(xué)習(xí)者檢測(cè)該算法的性能。選擇10 000個(gè)訓(xùn)練數(shù)據(jù)樣本和10 000個(gè)測(cè)試數(shù)據(jù)樣本。為了做比較,引入三元學(xué)習(xí)算法基準(zhǔn),所有的都使用一種離線的方式訓(xùn)練數(shù)據(jù)樣本:Ada-boost算法[13-14],L-2Boosting算法[15],Meta-L[16]算法。L-2Boosting算法以各自的局部學(xué)習(xí)者的輸出作為它的輸入,使用一個(gè)L2線性回歸來(lái)改正模型。然而,從整體學(xué)習(xí)者到局部學(xué)習(xí)者沒(méi)有反饋。因此,在訓(xùn)練過(guò)程中每個(gè)局部學(xué)習(xí)者的模型是固定的。在Meta-L算法中,整體學(xué)習(xí)者簡(jiǎn)單結(jié)合了局部學(xué)習(xí)者的輸出以一種附加的形式,不能自適應(yīng)地調(diào)整權(quán)重分配到不同局部學(xué)習(xí)者中。

結(jié)果如表2所示。很明顯算法2和Ada-boost算法有同樣高的精確度。因此,它是非常重要的更新模型對(duì)于整體學(xué)習(xí)者和局部學(xué)習(xí)者朝著一個(gè)方向合作,能增加總體預(yù)測(cè)精度。在第一個(gè)實(shí)驗(yàn)中,收斂速度是無(wú)法評(píng)估的。第2個(gè)實(shí)驗(yàn)中,檢查算法2的運(yùn)行時(shí)間行為,設(shè)置采用同第一個(gè)實(shí)驗(yàn)中局部學(xué)習(xí)者一樣的數(shù)據(jù)。圖1展示出了結(jié)果,可以看出,使用正確的局部學(xué)習(xí)者之間的關(guān)聯(lián)性,算法收斂速度是加快的。

圖1 預(yù)測(cè)精度的進(jìn)化 表2 不同算法的效率

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

3 結(jié) 論

提出了一個(gè)對(duì)于在線學(xué)習(xí)算法大規(guī)模分布式數(shù)據(jù)挖掘應(yīng)用程序的通用框架設(shè)計(jì),專注于分布式功能分布式數(shù)據(jù)線性回歸問(wèn)題通過(guò)不同局部的學(xué)習(xí)者。對(duì)于整體學(xué)習(xí)者和局部學(xué)習(xí)者的最佳回歸量是經(jīng)過(guò)嚴(yán)格推斷得出來(lái)的,然后設(shè)計(jì)了2種在線算法能收斂到最優(yōu)回歸量:合作更新算法和相關(guān)的更新算法。實(shí)驗(yàn)表明,相關(guān)更新算法明顯優(yōu)于合作方面的更新算法在所需的計(jì)算復(fù)雜性和通信成本方面,預(yù)測(cè)精度有輕微的差別。結(jié)果表明,巧妙利用局部學(xué)習(xí)者之間的關(guān)聯(lián)信息, 基于應(yīng)用程序的需求和最終用戶提出了在線學(xué)習(xí)算法可以靈活地平衡計(jì)算復(fù)雜度,溝通成本和預(yù)測(cè)準(zhǔn)確性。

[1]程學(xué)旗,靳小龍,王元卓,等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J]. 軟件學(xué)報(bào), 2014,25(9):1889-1908.

[2]申彥. 大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究[D]. 揚(yáng)州:江蘇大學(xué), 2013.

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

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

[5]張凌志,薛晶心,張媛. 微信模式下個(gè)體知識(shí)學(xué)習(xí)的特征和交流模式研究[J]. 情報(bào)理論與實(shí)踐, 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ì)量模型中的加總偏誤與內(nèi)生性:一種數(shù)值模擬方法[J]. 數(shù)量經(jīng)濟(jì)技術(shù)經(jīng)濟(jì)研究, 2013,30(12):140-157.

[8]石斌,劉思峰,黨耀國(guó),等. 無(wú)偏灰色預(yù)測(cè)模型遞推解法及其優(yōu)化[J]. 系統(tǒng)工程理論與實(shí)踐, 2011,31(8):1532-1538.

[9]唐述,龔衛(wèi)國(guó),仲建華. 稀疏平滑特性的多正則化約束圖像盲復(fù)原方法[J]. 軟件學(xué)報(bào), 2013,24(5):1143-1154.

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

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

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

[13]曹瑩,苗啟廣,劉家辰,等. AdaBoost算法研究進(jìn)展與展望[J]. 自動(dòng)化學(xué)報(bào), 2013,39(6):745-758.

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

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

[16]王凌,鄭大鐘. Meta-heuristic算法研究進(jìn)展[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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(60970112)。

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

1673-5862(2016)01-0100-05

TP393.08

A

10.3969/ j.issn.1673-5862.2016.01.023