孫 娟
(江海職業(yè)技術(shù)學(xué)院,江蘇 揚(yáng)州 225101)
計(jì)算機(jī)云計(jì)算的SLIQ并行算法實(shí)踐研究
孫 娟
(江海職業(yè)技術(shù)學(xué)院,江蘇 揚(yáng)州 225101)
隨著云計(jì)算的出現(xiàn),當(dāng)前的數(shù)據(jù)分析和存儲(chǔ)變得更加方便和高效。在傳統(tǒng)的SLIO計(jì)算方式之中有著許多的缺陷,在計(jì)算機(jī)云計(jì)算環(huán)境之中需要對(duì)這些缺陷進(jìn)行有效的改進(jìn)。文章對(duì)計(jì)算機(jī)云計(jì)算與SLIQ的并行算法展開了實(shí)際性的研究。
計(jì)算機(jī);云計(jì)算;SLIQ并行算法;數(shù)據(jù)分析;數(shù)據(jù)存儲(chǔ)
在數(shù)據(jù)挖掘的過程中必然會(huì)遇到海量的數(shù)據(jù)處理和計(jì)算,而在傳統(tǒng)的SLIQ計(jì)算方式中更傾向于小規(guī)模的數(shù)據(jù)處理與計(jì)算,一旦數(shù)據(jù)量過大就會(huì)使得運(yùn)算的速度等影響到最終的挖掘效率,甚至?xí)層?jì)算出現(xiàn)無法進(jìn)行的問題,這也是傳統(tǒng)SLIO計(jì)算方式的一大瓶頸。計(jì)算機(jī)云計(jì)算的出現(xiàn)正好能夠改變這種現(xiàn)狀,云計(jì)算更傾向于大數(shù)據(jù)的處理和計(jì)算,如果將其與SLIO計(jì)算方式相結(jié)合,通過并行計(jì)算將會(huì)有效地改變挖掘計(jì)算困難的問題,從而實(shí)現(xiàn)海量數(shù)據(jù)的處理與運(yùn)算。下面根據(jù)筆者自身的經(jīng)驗(yàn),對(duì)計(jì)算機(jī)云計(jì)算的SLIQ并行算法展開探討。
SLIQ算法最早于1996年被提出,是一種高速的可調(diào)整的數(shù)據(jù)挖掘分類模式計(jì)算方法。SLIQ算法在計(jì)算設(shè)計(jì)上面采用的是預(yù)排列思路,當(dāng)數(shù)據(jù)量較大的時(shí)候,又不能將所有的數(shù)據(jù)全部放入內(nèi)存駐留磁盤,此時(shí)會(huì)將這些數(shù)據(jù)進(jìn)行排序,同時(shí)處理離散和連續(xù)的字段。SLIQ算法是基于此點(diǎn)之上采取廣度優(yōu)先的方式完成決策樹的構(gòu)建,其在計(jì)算的過程中會(huì)對(duì)每層節(jié)點(diǎn)的屬性表進(jìn)行掃描,然后根據(jù)掃描的結(jié)果找出當(dāng)前的最優(yōu)分裂方式。在形成新的節(jié)點(diǎn)之中進(jìn)行取值,并對(duì)列表的類型進(jìn)行節(jié)點(diǎn)信息更新。
2.1 決策樹中的Gini指標(biāo)
在通常的情況下,決策樹中會(huì)選用信息量來作為評(píng)價(jià)節(jié)點(diǎn)分裂質(zhì)量的參數(shù),在SLIQ算法之中則對(duì)此做出了改變,利用Gini指標(biāo)來代替信息量的位置,其應(yīng)用起來性能相對(duì)更好,讓整個(gè)計(jì)算變得更加的簡(jiǎn)便、高效。在Gini指標(biāo)之中,主要是用來度量數(shù)據(jù)劃分或者訓(xùn)練元祖級(jí)的純度。當(dāng)Gini指標(biāo)出現(xiàn)變小的情況時(shí)則預(yù)示著信息增益量變大,對(duì)于節(jié)點(diǎn)分裂的質(zhì)量也就越好。在此過程之中也可以對(duì)數(shù)據(jù)集進(jìn)行分裂,從而形成二元?jiǎng)澐?,如果其中存在著一些連續(xù)值屬性和離散值屬性則存在著一定的不同。在面對(duì)離散值屬性時(shí),需要選擇該離散值屬性產(chǎn)生最小指標(biāo)的子集作為分裂子集。
SLIQ算法與傳統(tǒng)算法在決策樹的形式上也有著很大的不同,SLIQ使用的是二分查找樹結(jié)構(gòu),對(duì)于該種結(jié)構(gòu)在計(jì)算上要求更高,需要先對(duì)其中的每個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算,并從計(jì)算結(jié)果之中找到分裂的方式,然后進(jìn)行分裂??赡苤苯舆@樣說理解起來較為困難,現(xiàn)以實(shí)際距離進(jìn)行分析:在一個(gè)字段之中,如果發(fā)生分裂通常都會(huì)是在其中點(diǎn)的位置,將該字段進(jìn)行排序,一共具有N個(gè)節(jié)點(diǎn),分裂發(fā)生時(shí)只會(huì)是在兩節(jié)點(diǎn)的中間,也就是說在N個(gè)節(jié)點(diǎn)中會(huì)出現(xiàn)N-1個(gè)可能性,然后從小到大依次取其中不同的分裂節(jié)點(diǎn),從中可以找出Gini指標(biāo)最小的分裂點(diǎn)。但是其中也存在著特殊的情況,如離散字段可能的分割則是屬性值中的所有子集,在展開分裂測(cè)試的時(shí)候就需要將其中存在可能的所有子集都取出來。
SLIQ算法中重要的技術(shù)優(yōu)勢(shì)在于事先排序和廣度優(yōu)先者兩種技術(shù)思路上面,也正是這兩種技術(shù)的運(yùn)用使得SLIQ算法變得更加的高效。對(duì)于事先排序技術(shù)而言主要是為了消除在決策樹中每個(gè)節(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行排序的過程,從而實(shí)現(xiàn)性能上的優(yōu)化。對(duì)于廣度優(yōu)化技術(shù)主要是為了節(jié)省對(duì)每個(gè)節(jié)點(diǎn)掃描的時(shí)間和占用的資源,從而有效地提升SLIQ算法的運(yùn)算速度。
2.2 SLIQ最佳分裂
在SLIQ計(jì)算中,Gini index通常表示的是可伸縮指標(biāo),這個(gè)指標(biāo)通常被用來替代信息量,在生成新的決策樹中起到非常重要的作用。對(duì)其定義為在數(shù)據(jù)集中包含多個(gè)記錄,則Gini index可以用下面式子來進(jìn)行表示:
如果在上式之中的集合D被分成兩個(gè)部分,分別用D1和D2來進(jìn)行表示,則關(guān)于Gini index可以用下面的式子來進(jìn)行表達(dá)。
在上面的公式之中Pj指的是在該集合之中出現(xiàn)j類數(shù)據(jù)的頻率。而對(duì)于Gini index來說最大的特征之處在于計(jì)算過程中需要考慮其中的數(shù)值在被劃分之后的分布情況。
對(duì)于其中出現(xiàn)數(shù)值連續(xù)型連續(xù)字段的時(shí)候,查找其中最合理點(diǎn)的方法為:首先假設(shè)有字段a為數(shù)值連續(xù)字段,對(duì)其進(jìn)行預(yù)排序操作,然后得到R1、R2、R3、……、Rn的排序結(jié)果,在分裂的過程中沒有一定的規(guī)律,經(jīng)常會(huì)出現(xiàn)在兩個(gè)相鄰節(jié)點(diǎn)內(nèi),也就是存在著n-1種分裂的可能性。按照正常的運(yùn)算方式選取分裂的候選節(jié)點(diǎn),通常會(huì)選擇中間的節(jié)點(diǎn),因此分裂形式可以表示為a≤Ri和a>Ri,然后按照從小到大的順序排列分裂點(diǎn),將其中最小的分裂點(diǎn)定位最佳的候選節(jié)點(diǎn)。
在針對(duì)離散字段進(jìn)行處理的時(shí)候,其情況同連續(xù)字段有著極大的相似之處。首先將分裂測(cè)試數(shù)集字段b分為兩個(gè)集合,分別為b1和b-b1,然后對(duì)這兩個(gè)部分分別進(jìn)行計(jì)算得出Gini index數(shù)值,取Gini index數(shù)值之中的最小值,則該值對(duì)應(yīng)的分裂點(diǎn)就是最佳的分裂點(diǎn)。
2.3 對(duì)SLIQ的適應(yīng)性改進(jìn)
在實(shí)際應(yīng)用過程中為了能夠讓SLIQ算法適用于當(dāng)前的海量數(shù)據(jù)處理和運(yùn)算,需要對(duì)SLIQ算法做出適當(dāng)?shù)牟⑿谢脑?,才能夠讓它在云?jì)算之中獲得良好的處理效果。SLIQ算法并行化改造的方法為:將整個(gè)類表復(fù)制到每個(gè)處理器的內(nèi)存之上。并行算法又稱為Generate decision tree,因?yàn)閿?shù)據(jù)劃分D的訓(xùn)練元組產(chǎn)生出決策樹。在輸入上面:數(shù)據(jù)劃分D是訓(xùn)練元組對(duì)應(yīng)類型標(biāo)號(hào)的集合;attribute list,候選屬性集合attribute selection method,作為劃分最合理的數(shù)據(jù)元組,并作為個(gè)體類數(shù)據(jù)的分類準(zhǔn)則的過程。這個(gè)準(zhǔn)則是由分裂屬性和分裂點(diǎn)、分裂子集構(gòu)成。在輸出上面:首先將一個(gè)決策樹作為此次的輸出目標(biāo),具體操作如下:創(chuàng)建一個(gè)數(shù)據(jù)節(jié)點(diǎn);將d集合之中的相同類型數(shù)據(jù)都?xì)w于c集合中;返回并對(duì)c進(jìn)行標(biāo)記;如果其中的attribute list是一個(gè)空的集合,則需要再次返回并標(biāo)記d集合中的多數(shù)情況,然后使用attribute selection method和d集合中的attribute list找出最佳的節(jié)點(diǎn)分裂位置。將SLIQ算法進(jìn)行改進(jìn)之后,取得的最大優(yōu)勢(shì)在于類表輸入到內(nèi)存的速度將會(huì)被提高,這也就使得這個(gè)過程被極大簡(jiǎn)化,讓其在較短的時(shí)間內(nèi)就能夠完成,而且生成出來的目標(biāo)數(shù)也較小。
2.4 在Map Reduce中SLIQ的改進(jìn)
當(dāng)然改進(jìn)的方式還可以采用Map Reduce編程的方式來實(shí)現(xiàn),其操作的具體步驟可以按照下面的方式實(shí)行:
第一,將所有收集到的根節(jié)點(diǎn)數(shù)據(jù)記錄運(yùn)用Map Reduce函數(shù)來進(jìn)行劃分,形成m個(gè)子數(shù)據(jù)集合,它們的規(guī)模基本相同,然后將數(shù)據(jù)塊劃分為Input Splito。
第二,將上述劃分得到的m個(gè)子數(shù)據(jù)集合采取格式化操作,會(huì)產(chǎn)生出<key,value>對(duì),格式化為<Sn,<idn,tn,val-Ue,則此時(shí)格式化中的Sn表示的含義是m個(gè)子數(shù)據(jù)集合中的第n個(gè)表格的第s列;to表示的是第n個(gè)表格所對(duì)應(yīng)的屬性值;idn則表示的是第n個(gè)表格之中的數(shù)據(jù)單元索引值;val-uel表示的是記錄的類別。
第三,Map Reduce操作實(shí)質(zhì)上可以分為兩個(gè)操作的過程,首先是Map操作:通過該操作會(huì)將輸入進(jìn)來的相關(guān)記錄進(jìn)行仔細(xì)的掃描,然后按照特定的程序進(jìn)行分類整理,把其中key相同的數(shù)據(jù)放在一起存儲(chǔ)到相應(yīng)的文件之中,然后才是將文件配置到Reduce之中,執(zhí)行接下來的操作。
第四,針對(duì)其中的連續(xù)行數(shù)據(jù)段首先按照特定的順序進(jìn)行排序,生成與之相對(duì)應(yīng)的直方圖,并將初始階段設(shè)置為0,極端分裂點(diǎn)Gini rode值就是Reduce所對(duì)應(yīng)的任務(wù),然后在操作過程中只需要實(shí)時(shí)更新類對(duì)應(yīng)直方圖,不需要對(duì)直方圖進(jìn)行更新,然后利用類直方圖就可以準(zhǔn)確地計(jì)算出相對(duì)應(yīng)的Gini index值。
綜上所述,云計(jì)算在處理和計(jì)算海量的數(shù)據(jù)時(shí)表現(xiàn)出來的優(yōu)勢(shì)是無法替代的,而要想在數(shù)據(jù)挖掘中實(shí)現(xiàn)海量數(shù)據(jù)處理和計(jì)算,將SLIQ算法并行改進(jìn)是一種十分可行的方式。因此,在本文中分析了云計(jì)算環(huán)境下的MapReduce的改進(jìn)算法,說明在云計(jì)算的環(huán)境下決策規(guī)則和并行化是十分重要的基礎(chǔ),在實(shí)現(xiàn)的過程中可以通過對(duì)SLIQ算法的改進(jìn),從而獲得對(duì)其高速運(yùn)算的支持。
[1]賀?。骄坑?jì)算機(jī)云計(jì)算的SLIQ并行算法分析[J].無線互聯(lián)科技,2014,(2).
[2]崔學(xué)敏,張傳勇.云計(jì)算技術(shù)中計(jì)算機(jī)海量數(shù)據(jù)SLIQ算法的應(yīng)用[J].電子技術(shù)與軟件工程,2015,(18).
[3]何元.基于云計(jì)算的海量數(shù)據(jù)挖掘分類算法研究[D].電子科技大學(xué),2011.
[4]杜亞光.大跨度自錨式懸索橋結(jié)構(gòu)并行計(jì)算算法與主梁恒載狀態(tài)研究[D].西南交通大學(xué),2013.
[5]張敏.云計(jì)算環(huán)境下的并行數(shù)據(jù)挖掘策略研究[D].南京郵電大學(xué),2011.
[6]高華.計(jì)算機(jī)海量數(shù)據(jù)處理SLIQ算法研究[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào),2016,(4).
[7]李筱.面向異構(gòu)多核系統(tǒng)的并行計(jì)算模型和調(diào)度算法研究[D].湖南大學(xué),2012.
(責(zé)任編輯:黃銀芳)
TP393
1009-2374(2017)12-0011-02
10.13535/j.cnki.11-4406/n.2017.12.006
孫娟(1977-),女,江蘇江都人,江海職業(yè)技術(shù)學(xué)院講師,碩士,研究方向:計(jì)算機(jī)應(yīng)用技術(shù)。
A