陳雪
(廣州工商學(xué)院 廣東省廣州市 510850)
數(shù)據(jù)挖掘是指通過數(shù)據(jù)統(tǒng)計、在線云分析、專家智庫系統(tǒng)以及情報檢索、訓(xùn)練學(xué)習(xí)等多種數(shù)據(jù)分析工具與經(jīng)驗法則的體系辦法,對計算機互聯(lián)網(wǎng)中待計算解決的程序任務(wù)進(jìn)行分析拆解,進(jìn)而獲取大數(shù)據(jù)背后隱藏其中的信息量。數(shù)據(jù)挖掘的任務(wù)表現(xiàn)形式主要有分類分析、聚類分析、關(guān)聯(lián)度分析、特異族群分析、異常分析以及演變分析多種。隨著90年代互聯(lián)網(wǎng)技術(shù)以及桌面電腦、移動終端產(chǎn)品的普及應(yīng)用,如今的互聯(lián)網(wǎng)應(yīng)用所要調(diào)用的數(shù)據(jù)規(guī)模,早已遠(yuǎn)超以往的數(shù)據(jù)軟件計算能力所能滿足。
當(dāng)前階段,想要解決數(shù)據(jù)挖掘算法效率低下的問題,就必須要應(yīng)用數(shù)據(jù)并行化技術(shù),將待計算的數(shù)據(jù)元素分別配置給計算機包含的多組PE處理單元,這樣當(dāng)計算機執(zhí)行順序程序任務(wù)時,就可以將所有處理單元的數(shù)據(jù)同時操作了。云計算技術(shù)的根本特點在于計算任務(wù)的并行與分布,也正因如此云計算技術(shù)才能夠在極短的時間內(nèi)處理海量的數(shù)據(jù)計算任務(wù)。這樣并行分布式的計算與以往傳統(tǒng)的單機編程計算的工作機制完全不同,它更注重多個計算機集群之間的聯(lián)機運行效率,除了數(shù)據(jù)挖掘計算的效率與準(zhǔn)確性得到了極大提升以外,在計算資源的合理化配置策略下,閑置計算資源將會得到充分的調(diào)動,因此計算成本將會得到極大程度縮減[1]。根據(jù)權(quán)威報告結(jié)果表明,2009年由Apache基金會所開發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)“Hadoop”,在910個分布式節(jié)點構(gòu)成的集群中,僅需要約193秒即可完成超過1TB容量的數(shù)據(jù)排序分析計算。上述實例說明了數(shù)據(jù)并行化技術(shù)在互聯(lián)網(wǎng)數(shù)據(jù)挖掘用途中擁有著絕對的效率優(yōu)勢,在云環(huán)境中實現(xiàn)并行化的數(shù)據(jù)挖掘計算,可以在分布式文件系統(tǒng)的基礎(chǔ)上,為現(xiàn)有的計算任務(wù)提供一個分布式且結(jié)果輸出一致的虛擬對象存儲系統(tǒng),而后再借助綜合分布的NET語言集成系統(tǒng)以及運行引擎,以潛在語義分析、神經(jīng)網(wǎng)格與配置部署策略等多種數(shù)據(jù)處理方法獲得我們想要得到的數(shù)據(jù)結(jié)果。
規(guī)則關(guān)聯(lián)問題簡單理解,就是將所用的用戶數(shù)據(jù)、或數(shù)據(jù)庫事務(wù)放在同一個交叉銷售條件下,對數(shù)據(jù)之間在時間性、空間性或其它方面的關(guān)聯(lián)規(guī)則進(jìn)行挖掘與形式化描述。其中事務(wù)T與全項集D中的元素t與i的區(qū)別就在于,是否符合事務(wù)規(guī)則“x→y”的描述,而“x→y”規(guī)則是通過數(shù)據(jù)挖掘算法得到的映射結(jié)果,因此它需要由支持度與關(guān)聯(lián)度兩個要素來共同構(gòu)成相關(guān)規(guī)則描述[2]。其中支持度是指在所有商品交易項集中關(guān)聯(lián)規(guī)則的頻度,它可以用數(shù)據(jù)x與y的交易數(shù)與所有數(shù)據(jù)交易量的比值來表示,記作“support(x→y)”,用算法語句表示為如下:
而關(guān)聯(lián)規(guī)則的確信度則表示所有商品交易項集中關(guān)聯(lián)規(guī)則的強度,它可以用數(shù)據(jù)x與y之間的交易數(shù)與包含x的交易數(shù)比值來表示,記作“confidence(x→y)”,用算法語句表示為如下:
confidence(x→y)=丨T:X∪Y?T,T?A丨
數(shù)據(jù)分類是云計算在處理、收集以及應(yīng)用消息時最常使用的一種數(shù)據(jù)挖掘方法,同關(guān)聯(lián)規(guī)則問題不同的是,數(shù)據(jù)分類還需要在數(shù)據(jù)的字段類型以及數(shù)據(jù)結(jié)構(gòu)方面對同屬于一個描述維度的數(shù)據(jù)進(jìn)行分類歸集。以字段類型分類為例,包含全項的D中同時存在著文本類、時間類、數(shù)值類等多種字段類型時,由于它們的相關(guān)規(guī)則并不是可以用量化值來篩選的,無法用四則運算或簡單的函數(shù)調(diào)用的方法來建立分類規(guī)則映射。因此需要先對數(shù)據(jù)的字段類型進(jìn)行標(biāo)準(zhǔn)化處理,而后再將其以“字符匹配”的方法進(jìn)行歸集處理,除了數(shù)值類這種包含可量化屬性的數(shù)據(jù)集合必須要直接進(jìn)行量化計算以外,其余數(shù)據(jù)的挖掘處理均可以采用模糊匹配[3]。
以數(shù)據(jù)倉庫的工程師與平臺架構(gòu)師來說,只有理解了數(shù)據(jù)組件適合處理什么樣的數(shù)據(jù)業(yè)務(wù),才能夠根據(jù)不同的數(shù)據(jù)分類要求選擇合適的數(shù)據(jù)清洗方法。無論是哪種數(shù)據(jù)清洗或匹配識別機制,數(shù)據(jù)分類方法大多情況下存在著如下幾個共同點:一是數(shù)據(jù)清洗時,需要始終將時間類與數(shù)值類的數(shù)據(jù)當(dāng)做清洗重點,而其余文本數(shù)據(jù)則要視數(shù)據(jù)倉使用需求來決定是否需要模糊匹配,例如備注或評價的文字?jǐn)?shù)據(jù)通常不具備清洗的必要性;二是建立數(shù)據(jù)維度模型時,應(yīng)當(dāng)根據(jù)數(shù)據(jù)編碼型字段以及時間類字段的標(biāo)準(zhǔn)作為清洗維度,以數(shù)值的量化屬性作為度量,視該種數(shù)據(jù)對數(shù)字業(yè)務(wù)的重要程度來確定數(shù)據(jù)分類的量化屬性;三是需要明確數(shù)據(jù)分類清洗的取值范圍,例如以年齡大于“0”為分類條件時,若出現(xiàn)與匹配規(guī)則的邏輯相悖的不合理數(shù)值,應(yīng)當(dāng)先用默認(rèn)值填充后,再對數(shù)據(jù)項集進(jìn)行分類清洗處理。
數(shù)據(jù)聚類即按照“物以類聚”的思想,將數(shù)據(jù)中包含相似屬性的子項歸聚為一類,當(dāng)前主流的云計算平臺采用的數(shù)據(jù)聚類算法主要包括如下四種:k-means算法、clarans算法、密度聚類算法、k-medoids算法與層次聚類算法。它與數(shù)據(jù)分類的最大區(qū)別在于:分類挖掘是一種數(shù)據(jù)預(yù)測行為,即根據(jù)已知的用戶信息推斷它歸屬于哪一個潛在的數(shù)據(jù)管理類別;而聚類挖掘則更關(guān)注于數(shù)據(jù)對象的劃分行為,即在事先不知道數(shù)據(jù)類別的前提下,通過數(shù)據(jù)自行聚類得到管理模板[4]。以最常使用的k-means算法為例對聚類處理方法進(jìn)行說明,該聚類算法的基本邏輯為如下:聚類問題的處理目的是將n個樣本數(shù)集歸集為k個數(shù)據(jù)簇,但除了樣本信息以外,數(shù)據(jù)管理者或數(shù)據(jù)使用者并不清楚在整個聚類中包含多少個簇。因此需要采用“評價指標(biāo)法”來衡量聚類算法簇的數(shù)目,當(dāng)簇內(nèi)樣本的相似度較高,而簇間樣本相似度低時,用簇間度量屬性來表述,就是簇內(nèi)樣本距離小,簇間樣本距離大。
數(shù)據(jù)預(yù)測主要是采用如下處理思路:
數(shù)據(jù)抽樣,即在海量數(shù)據(jù)的全項集D中隨機抽取一定量的樣本組成新的集合P,并構(gòu)建相應(yīng)的數(shù)據(jù)模型。這種處理方法的優(yōu)勢在于算法并行化時處理難度較低,計算資源占用較小。但當(dāng)D的樣本分布均勻度較差時,數(shù)據(jù)挖掘的精度與質(zhì)量也將會受到極大影響。
數(shù)據(jù)集成,以MapReduce方法為例進(jìn)行說明,首先對代表海量數(shù)據(jù)的全項集D進(jìn)行簡單的數(shù)據(jù)劃分,而后再將其以數(shù)據(jù)塊的形式進(jìn)行并行劃分處理,最后再將數(shù)據(jù)結(jié)果進(jìn)行合并,執(zhí)行算法并行時需要MPI程序的編寫支持,而Mapreduce中專門為數(shù)據(jù)庫開發(fā)人員準(zhǔn)備了并行程序編寫的簡單接口,這樣在執(zhí)行算法并行任務(wù)的過程中,只要將數(shù)據(jù)以分片的形式加工處理,就可以在程序reduce階段重新將算法輸出的數(shù)據(jù)結(jié)果進(jìn)行整合。基于MapReduce的數(shù)據(jù)集成并行方法在解決了樣本數(shù)據(jù)不均化分布的問題同時,也優(yōu)化了數(shù)據(jù)集群節(jié)點之間的任務(wù)交互與分配流程,使算法并行不再受到本地內(nèi)存大小的限制,為數(shù)據(jù)同步與通信預(yù)留更多的資源分配空間。
如表1所示為Hadoop開源云平臺的子項目與主要包列表,由上可以看出,Hadoop是一個可提供共享系統(tǒng)與分析系統(tǒng)的分布式數(shù)據(jù)架構(gòu)平臺,它實現(xiàn)數(shù)據(jù)挖掘算法并行化的核心組件是MapReduce與HDFS。它的整體架構(gòu)包括如下內(nèi)容:由雙節(jié)點構(gòu)成的Master/Slave架構(gòu),其中一個是NameNode節(jié)點,負(fù)責(zé)維護整個并行程序的元數(shù)據(jù),是平臺文件系統(tǒng)運行的基礎(chǔ)保證;另一個為DataNode節(jié)點,主要負(fù)責(zé)建立起整個數(shù)據(jù)單元的文件儲存模塊,它在平臺中的主要意義是充當(dāng)工作節(jié)點,由NameNode節(jié)點的指令控制,并定期以“心跳機制”的形式向上游DataNode節(jié)點發(fā)送工作數(shù)據(jù)塊的信息[5]。除此以外,為了實現(xiàn)Hadoop平臺在數(shù)據(jù)挖掘算法并行化任務(wù)執(zhí)行過程中的高可用性目標(biāo),在它的基礎(chǔ)框架中還增設(shè)了一個Secondary DataNode節(jié)點作為備份,當(dāng)DataNode節(jié)點發(fā)生故障時,可以隨時從本地數(shù)據(jù)庫中調(diào)取Namespaceimage(命名空間鏡像)與Edit Log(編輯日志)文件,替代其重新成為新的元數(shù)據(jù)維護節(jié)點。
表1:Hadoop子項目與主要包列表
分析規(guī)則關(guān)聯(lián)算法的需求,可以采用基于單層單維與布爾關(guān)聯(lián)規(guī)則的Apriori算法,將兩階數(shù)集分別在構(gòu)建器與過濾器中進(jìn)行迭代,而后再以k項集為頻繁項,不斷生成新的k+1項集。這樣的算法步驟如表2所示,通過剪枝與連接的過程,使不同階段輸出的Lk與Lk-1進(jìn)行連接。在Apriori算法模式下,若頻繁項集的非空子集是連續(xù)生成的,那么只需要對Ck+1與Lk的歸屬關(guān)系進(jìn)行檢驗,即可獲知算法并行化的輸出結(jié)果是否滿足支持度要求。
基于Apriori規(guī)則關(guān)聯(lián)算法并行化的步驟流程如下:
(1)輸入。D:事務(wù)庫數(shù)據(jù),Min_support:支持度的最小閾值。
(2)步驟。L1=find_frequent_1-itemstes(D);//挖掘頻繁項集。for(k=2;Lk≠0;k+=){//初始值輸入}。Ck= aprior_gen(Lk-1,min_support),//調(diào)用aprior_gen(),生成k-1的頻繁項集。Foreach transactions t in D{//事務(wù)數(shù)據(jù)庫D掃描}。Ct=subset(Ck,t),{//以t的子集為候選集}。Foreach candidates c in Ct。c.count++;//統(tǒng)計候選k-1的計數(shù)。Lk={c?C|kc.count>Min_support}//最小支持度的滿足條件,即輸出的k-1項集結(jié)果}。ReturnL=UkLk;//頻繁項k項集合并。
若事務(wù)T中包含著A項集,可以記作“A?T”,若A項集中包含K項數(shù)集,那么就可以稱K為A的數(shù)據(jù)項集,簡稱為K項集。而這樣的事務(wù)T又屬于包含所有項的I集合,記作“I={i1、i2、i3....in},T?I”,而事務(wù)T中又有n項數(shù)據(jù),記作“T={t1、t2、t3....in}”。此時就可以將事務(wù)T看做在全部項集D中,以某項數(shù)據(jù)間的線索為標(biāo)識符的關(guān)聯(lián)集合,記作“T|D”。在這樣的關(guān)聯(lián)規(guī)則體系下,事務(wù)T中所有的元素都相當(dāng)于交易環(huán)節(jié)的商品列表,而i1t1、t2、t3....in等集合元素,則可以被視為在“x→y”標(biāo)識規(guī)則下,從全集合D中提取出的所有符合元素。
在Hadoop平臺上,首先為分類算法匹配一個算法PFP作為分布式數(shù)據(jù)處理環(huán)節(jié),例如FP-growth算法??梢詾椴煌挠嬎銠C服務(wù)器分別配置獨立的數(shù)據(jù)分類挖掘任務(wù),這樣的數(shù)據(jù)挖掘結(jié)果,每個子部算法輸出結(jié)果之間是互相平行割裂的,互相之間并不存在依賴關(guān)系。
而后采用MapReduce組件將數(shù)據(jù)進(jìn)行分片處理,并使用“mapper()->reduce()”指令求得分類數(shù)據(jù)項集的所有支持度結(jié)果計數(shù)。再單獨將每個mapper的數(shù)據(jù)分片輸入本地的頻繁項文件列表“F_List”中,在某個工作節(jié)點上將“F_List”項集按照輸入數(shù)綱規(guī)則劃分為g個分組,使每個列表分組中均包含至少一個gid樣本數(shù)據(jù),構(gòu)成新的分組集合“G_List”。
接著再根據(jù)不同的數(shù)據(jù)業(yè)務(wù)需求,以不同分組單位構(gòu)成的FP-Tree(樹狀文件列表),此時只需要將事務(wù)集合轉(zhuǎn)換至歸集多個組的數(shù)據(jù)分片中,就可以在遞歸構(gòu)建條件的要求下,使新集成數(shù)據(jù)被多個組間節(jié)點加工為中間結(jié)果數(shù)據(jù)了。
最后是算法并行化的實現(xiàn)關(guān)鍵,當(dāng)“G_List”列表以組為單位生成數(shù)據(jù)集事務(wù)時,需要啟動“mapper()”實例,將一組中間結(jié)果讀入至hashmap中,并且會同步映射生成一個group_id數(shù)據(jù),此時每個mapper()指令的工作對象都與唯一的一個數(shù)據(jù)分片相對應(yīng)。在將數(shù)據(jù)輸出結(jié)果的格式調(diào)整為“key,value=Ti”形式后,將每個被包含于事務(wù)集合中的樣本Ti,輸入如下操作流程:一是使用“group_id”來取締滿足“Tj?Ti”條件的輸出數(shù)值;二是將出現(xiàn)在Ti中的“group_id”數(shù)據(jù)記為“gid”,并將離散性最大的出現(xiàn)位置記作L,使輸出鍵與算法指令“key=gid,value={Ti[1]、Ti[2]、Ti[3]......Ti[L]}”相契合[5];三是需要在分類算法并行化模型構(gòu)建完成后,從一組已知類別數(shù)據(jù)中抽取若干預(yù)先定義的分類數(shù)據(jù),建立起訓(xùn)練樣本,不斷檢驗分類算法并行化模型的預(yù)測準(zhǔn)確率。
聚類算法的并行化主要是采用統(tǒng)計學(xué)辦法,用葉貝斯定理來建立起多個相對獨立的屬性類簇Ci,將海量數(shù)據(jù)項集D中的數(shù)據(jù)按照如下公式進(jìn)行處理:
式中C表示為聚類的某種假設(shè)前提,代表著聚類數(shù)據(jù)簇中心的臨時特征值;P(X|C)表示為聚類條件為X時,所有由C篩選出的后驗概率;P(C)是數(shù)據(jù)簇的先驗概率。
應(yīng)用該定理時首先需要先為其描述n個基本屬性描述,用A1、A2、A3....An來表示;當(dāng)假設(shè)數(shù)據(jù)挖掘的聚類簇存在m個時,用C1、C2、C3....Cm來表示;為了度量出數(shù)據(jù)與簇中心的距離,再用X1、X2.......Xo來表示聚類的中心簇定元組。
其次是對每個聚類后驗概率的輸出值P(C|X)進(jìn)行驗證,只有當(dāng)P(C|X)滿足條件“P(C|Xo)>P(Cm|X)[o>m>1]”時,才可以將預(yù)測的定元組X作為數(shù)據(jù)簇中心的特征值,此時將P(C|X)所對應(yīng)的簇Ci輸出[6]。
而它的工作過程則分為如下:第一步是在全項集D中隨機抽取n個樣本作為取樣區(qū)C,再在集合C中繼續(xù)抽取k個樣本組成集合K,我們將這樣的集合K稱作“初始簇中心”,此后每形成一個簇中心都用其來表示一個數(shù)據(jù)簇。
第二部是為每個樣本集合中心匹配一個可供參照的數(shù)據(jù)樣本,根據(jù)數(shù)據(jù)與中心簇可度量的屬性值來計算它們的相似度,并將該樣本暫時歸集至該簇中。此后每出現(xiàn)一個新的數(shù)據(jù)簇,都與中心簇的樣本進(jìn)行相似度比較,一旦出現(xiàn)高于中心簇的新簇時,再將樣本歸聚至這個與中心簇特征值最相似的新簇中,作為該類樣本的聚類簇輸出結(jié)果。
第三部每新增一個簇后,都需要將每個簇中樣本均值作為衡量基準(zhǔn),重新計算聚類簇中心的特征值。并重復(fù)如上步驟,采用標(biāo)準(zhǔn)測度函數(shù)與均方差的方法對簇中心的特征值進(jìn)行收斂處理。
第四部是將簇內(nèi)樣本的相似度S1、S2.....Sn,與簇間樣本的相似度I1、I2、I3...In輸出,若采用密度度量法計算聚類簇的樣本均值,則是將每個簇抽象處理為以簇中心為圓心的,以距離簇中心最遠(yuǎn)樣本的偏差距離為半徑作圓。再次以簇中心為圓心,以任意距離n(n小于最遠(yuǎn)樣本距離)為半徑,逐漸增加簇半徑的距離,將兩個圓在同一平面內(nèi)形成的圓環(huán)作為參考量,計算出環(huán)形區(qū)域內(nèi)的數(shù)據(jù)點個數(shù)與圓環(huán)面積的比值,即為數(shù)據(jù)聚類樣本密度。
預(yù)測算法的并行化則主要是依靠LSTM時間序列的處理工作流程,LSTM是一種可以用于深度學(xué)習(xí)領(lǐng)域的人工遞歸神經(jīng)網(wǎng)絡(luò),它與以往前饋式的神經(jīng)網(wǎng)絡(luò)不同,在整個網(wǎng)絡(luò)節(jié)點中還包含有反饋連接功能單元,因此它除了可以用于挖掘圖像、數(shù)據(jù)表等單一數(shù)據(jù)點的預(yù)測信息以外,還可以挖掘帶有“數(shù)據(jù)序列”屬性的數(shù)據(jù),例如視頻、音頻以及語音文件。
需要先為LSTM創(chuàng)建一個床柜的分布式數(shù)據(jù)架構(gòu),以Hadoop平臺組件HDFS為例,這樣的平臺架構(gòu)由一個TensorFLow分布式集群,與若干個TensorFlow子服務(wù)器構(gòu)成[7]。而在執(zhí)行數(shù)據(jù)預(yù)測算法的并行化任務(wù)時,除了需要根據(jù)數(shù)據(jù)業(yè)務(wù)需求匹配相應(yīng)的數(shù)據(jù)挖掘算法以外,還要執(zhí)行如下幾種主要的算法并行策略:
多工鏡像策略,通常情況下為了確保數(shù)據(jù)預(yù)測分析的準(zhǔn)確性,在整個數(shù)據(jù)模型中可能布置存在一個預(yù)測算法,因此需要針對多Worker情景的算法調(diào)用需求,通過跨Worker的同步分布式算法訓(xùn)練,使每個Worker對應(yīng)的服務(wù)器組都可以調(diào)用資源參與程序計算。它的基本原理就是在所有程序Worker的計算機設(shè)備上分別創(chuàng)建一組包含數(shù)據(jù)變量信息的副本,構(gòu)成與Worker調(diào)用算法數(shù)據(jù)模型對應(yīng)的鏡像,為中央存儲策略實例的語句調(diào)用提供架構(gòu)環(huán)境。
TPU策略,它的主包路徑應(yīng)當(dāng)設(shè)置為“tf.distribute.experimental.TPUStragy”,該策略的主要作用是使預(yù)測算法并行化執(zhí)行程序以及算法訓(xùn)練流程可以在Tensor處理單元,即TPU上運行。與鏡像策略最大的不同之處在于它不是以調(diào)用多組Worker計算機的形式實現(xiàn)同步分布式培訓(xùn)的,而是將算法訓(xùn)練形式轉(zhuǎn)換為TensorFlow后,使其可以在TPU單元運行。
參數(shù)服務(wù)器策略,主包路徑應(yīng)當(dāng)設(shè)置為“tf.distribute.experimental.ParameterServerStrategy”,在該策略模式下整個用于數(shù)據(jù)預(yù)測挖掘的云網(wǎng)絡(luò)中,部分計算機會被指定為WorkerServer,即工作服務(wù)器組;而另外一部分則會被指定為ParameterServer,即參數(shù)服務(wù)器組。將預(yù)測算法的數(shù)據(jù)模型中的頻繁變量文件統(tǒng)一放置于一個參數(shù)服務(wù)器組中,再由工作服務(wù)器組通過工作程序以復(fù)制的形式進(jìn)行調(diào)用,實現(xiàn)在多個服務(wù)器對預(yù)測算法數(shù)據(jù)模型進(jìn)行分布式訓(xùn)練的需求。
綜上所述,如何在合理的時間內(nèi)攫取、管理以及加工處理更龐大的數(shù)據(jù)量,一直以來都是大數(shù)據(jù)時代網(wǎng)絡(luò)應(yīng)用所追求的首要目標(biāo),在這種背景下“大數(shù)據(jù)云計算”技術(shù)應(yīng)運而生。而云環(huán)境下數(shù)據(jù)挖掘算法的并行化就是指利用多種不同的數(shù)據(jù)模型策略,實現(xiàn)數(shù)據(jù)關(guān)聯(lián)規(guī)則、分類、聚類與預(yù)測四種數(shù)據(jù)挖掘方法的并行化執(zhí)行功能。若待處理的計算數(shù)據(jù)規(guī)模繼續(xù)增加,就需要由多臺計算機處理機共同執(zhí)行并行計算,而此時再配置計算任務(wù)時,就需要考慮到數(shù)據(jù)通信、數(shù)據(jù)段間同步以及算法選取的問題。