計算機云計算的SLIQ并行算法實踐研究

孫 娟

（江海職業(yè)技術(shù)學(xué)院，江蘇 揚州 225101）

計算機云計算的SLIQ并行算法實踐研究

孫 娟

（江海職業(yè)技術(shù)學(xué)院，江蘇 揚州 225101）

隨著云計算的出現(xiàn)，當(dāng)前的數(shù)據(jù)分析和存儲變得更加方便和高效。在傳統(tǒng)的SLIO計算方式之中有著許多的缺陷，在計算機云計算環(huán)境之中需要對這些缺陷進行有效的改進。文章對計算機云計算與SLIQ的并行算法展開了實際性的研究。

計算機；云計算；SLIQ并行算法；數(shù)據(jù)分析；數(shù)據(jù)存儲

在數(shù)據(jù)挖掘的過程中必然會遇到海量的數(shù)據(jù)處理和計算，而在傳統(tǒng)的SLIQ計算方式中更傾向于小規(guī)模的數(shù)據(jù)處理與計算，一旦數(shù)據(jù)量過大就會使得運算的速度等影響到最終的挖掘效率，甚至?xí)層嬎愠霈F(xiàn)無法進行的問題，這也是傳統(tǒng)SLIO計算方式的一大瓶頸。計算機云計算的出現(xiàn)正好能夠改變這種現(xiàn)狀，云計算更傾向于大數(shù)據(jù)的處理和計算，如果將其與SLIO計算方式相結(jié)合，通過并行計算將會有效地改變挖掘計算困難的問題，從而實現(xiàn)海量數(shù)據(jù)的處理與運算。下面根據(jù)筆者自身的經(jīng)驗，對計算機云計算的SLIQ并行算法展開探討。

1 SLIQ算法的概述

SLIQ算法最早于1996年被提出，是一種高速的可調(diào)整的數(shù)據(jù)挖掘分類模式計算方法。SLIQ算法在計算設(shè)計上面采用的是預(yù)排列思路，當(dāng)數(shù)據(jù)量較大的時候，又不能將所有的數(shù)據(jù)全部放入內(nèi)存駐留磁盤，此時會將這些數(shù)據(jù)進行排序，同時處理離散和連續(xù)的字段。SLIQ算法是基于此點之上采取廣度優(yōu)先的方式完成決策樹的構(gòu)建，其在計算的過程中會對每層節(jié)點的屬性表進行掃描，然后根據(jù)掃描的結(jié)果找出當(dāng)前的最優(yōu)分裂方式。在形成新的節(jié)點之中進行取值，并對列表的類型進行節(jié)點信息更新。

2 云計算的SLIQ計算改進

2.1 決策樹中的Gini指標

在通常的情況下，決策樹中會選用信息量來作為評價節(jié)點分裂質(zhì)量的參數(shù)，在SLIQ算法之中則對此做出了改變，利用Gini指標來代替信息量的位置，其應(yīng)用起來性能相對更好，讓整個計算變得更加的簡便、高效。在Gini指標之中，主要是用來度量數(shù)據(jù)劃分或者訓(xùn)練元祖級的純度。當(dāng)Gini指標出現(xiàn)變小的情況時則預(yù)示著信息增益量變大，對于節(jié)點分裂的質(zhì)量也就越好。在此過程之中也可以對數(shù)據(jù)集進行分裂，從而形成二元劃分，如果其中存在著一些連續(xù)值屬性和離散值屬性則存在著一定的不同。在面對離散值屬性時，需要選擇該離散值屬性產(chǎn)生最小指標的子集作為分裂子集。

SLIQ算法與傳統(tǒng)算法在決策樹的形式上也有著很大的不同，SLIQ使用的是二分查找樹結(jié)構(gòu)，對于該種結(jié)構(gòu)在計算上要求更高，需要先對其中的每個節(jié)點進行計算，并從計算結(jié)果之中找到分裂的方式，然后進行分裂?？赡苤苯舆@樣說理解起來較為困難，現(xiàn)以實際距離進行分析：在一個字段之中，如果發(fā)生分裂通常都會是在其中點的位置，將該字段進行排序，一共具有N個節(jié)點，分裂發(fā)生時只會是在兩節(jié)點的中間，也就是說在N個節(jié)點中會出現(xiàn)N-1個可能性，然后從小到大依次取其中不同的分裂節(jié)點，從中可以找出Gini指標最小的分裂點。但是其中也存在著特殊的情況，如離散字段可能的分割則是屬性值中的所有子集，在展開分裂測試的時候就需要將其中存在可能的所有子集都取出來。

SLIQ算法中重要的技術(shù)優(yōu)勢在于事先排序和廣度優(yōu)先者兩種技術(shù)思路上面，也正是這兩種技術(shù)的運用使得SLIQ算法變得更加的高效。對于事先排序技術(shù)而言主要是為了消除在決策樹中每個節(jié)點對數(shù)據(jù)集進行排序的過程，從而實現(xiàn)性能上的優(yōu)化。對于廣度優(yōu)化技術(shù)主要是為了節(jié)省對每個節(jié)點掃描的時間和占用的資源，從而有效地提升SLIQ算法的運算速度。

2.2 SLIQ最佳分裂

在SLIQ計算中，Gini index通常表示的是可伸縮指標，這個指標通常被用來替代信息量，在生成新的決策樹中起到非常重要的作用。對其定義為在數(shù)據(jù)集中包含多個記錄，則Gini index可以用下面式子來進行表示：

如果在上式之中的集合D被分成兩個部分，分別用D1和D2來進行表示，則關(guān)于Gini index可以用下面的式子來進行表達。

在上面的公式之中Pj指的是在該集合之中出現(xiàn)j類數(shù)據(jù)的頻率。而對于Gini index來說最大的特征之處在于計算過程中需要考慮其中的數(shù)值在被劃分之后的分布情況。

對于其中出現(xiàn)數(shù)值連續(xù)型連續(xù)字段的時候，查找其中最合理點的方法為：首先假設(shè)有字段a為數(shù)值連續(xù)字段，對其進行預(yù)排序操作，然后得到R1、R2、R3、……、Rn的排序結(jié)果，在分裂的過程中沒有一定的規(guī)律，經(jīng)常會出現(xiàn)在兩個相鄰節(jié)點內(nèi)，也就是存在著n-1種分裂的可能性。按照正常的運算方式選取分裂的候選節(jié)點，通常會選擇中間的節(jié)點，因此分裂形式可以表示為a≤Ri和a＞Ri，然后按照從小到大的順序排列分裂點，將其中最小的分裂點定位最佳的候選節(jié)點。

在針對離散字段進行處理的時候，其情況同連續(xù)字段有著極大的相似之處。首先將分裂測試數(shù)集字段b分為兩個集合，分別為b1和b－b1，然后對這兩個部分分別進行計算得出Gini index數(shù)值，取Gini index數(shù)值之中的最小值，則該值對應(yīng)的分裂點就是最佳的分裂點。

2.3 對SLIQ的適應(yīng)性改進

在實際應(yīng)用過程中為了能夠讓SLIQ算法適用于當(dāng)前的海量數(shù)據(jù)處理和運算，需要對SLIQ算法做出適當(dāng)?shù)牟⑿谢脑欤拍軌蜃屗谠朴嬎阒蝎@得良好的處理效果。SLIQ算法并行化改造的方法為：將整個類表復(fù)制到每個處理器的內(nèi)存之上。并行算法又稱為Generate decision tree，因為數(shù)據(jù)劃分D的訓(xùn)練元組產(chǎn)生出決策樹。在輸入上面：數(shù)據(jù)劃分D是訓(xùn)練元組對應(yīng)類型標號的集合；attribute list，候選屬性集合attribute selection method，作為劃分最合理的數(shù)據(jù)元組，并作為個體類數(shù)據(jù)的分類準則的過程。這個準則是由分裂屬性和分裂點、分裂子集構(gòu)成。在輸出上面：首先將一個決策樹作為此次的輸出目標，具體操作如下：創(chuàng)建一個數(shù)據(jù)節(jié)點；將d集合之中的相同類型數(shù)據(jù)都歸于c集合中；返回并對c進行標記；如果其中的attribute list是一個空的集合，則需要再次返回并標記d集合中的多數(shù)情況，然后使用attribute selection method和d集合中的attribute list找出最佳的節(jié)點分裂位置。將SLIQ算法進行改進之后，取得的最大優(yōu)勢在于類表輸入到內(nèi)存的速度將會被提高，這也就使得這個過程被極大簡化，讓其在較短的時間內(nèi)就能夠完成，而且生成出來的目標數(shù)也較小。

2.4 在Map Reduce中SLIQ的改進

當(dāng)然改進的方式還可以采用Map Reduce編程的方式來實現(xiàn)，其操作的具體步驟可以按照下面的方式實行：

第一，將所有收集到的根節(jié)點數(shù)據(jù)記錄運用Map Reduce函數(shù)來進行劃分，形成m個子數(shù)據(jù)集合，它們的規(guī)?；鞠嗤缓髮?shù)據(jù)塊劃分為Input Splito。

第二，將上述劃分得到的m個子數(shù)據(jù)集合采取格式化操作，會產(chǎn)生出＜key，value＞對，格式化為＜Sn，＜idn，tn，val-Ue，則此時格式化中的Sn表示的含義是m個子數(shù)據(jù)集合中的第n個表格的第s列；to表示的是第n個表格所對應(yīng)的屬性值；idn則表示的是第n個表格之中的數(shù)據(jù)單元索引值；val-uel表示的是記錄的類別。

第三，Map Reduce操作實質(zhì)上可以分為兩個操作的過程，首先是Map操作：通過該操作會將輸入進來的相關(guān)記錄進行仔細的掃描，然后按照特定的程序進行分類整理，把其中key相同的數(shù)據(jù)放在一起存儲到相應(yīng)的文件之中，然后才是將文件配置到Reduce之中，執(zhí)行接下來的操作。

第四，針對其中的連續(xù)行數(shù)據(jù)段首先按照特定的順序進行排序，生成與之相對應(yīng)的直方圖，并將初始階段設(shè)置為0，極端分裂點Gini rode值就是Reduce所對應(yīng)的任務(wù)，然后在操作過程中只需要實時更新類對應(yīng)直方圖，不需要對直方圖進行更新，然后利用類直方圖就可以準確地計算出相對應(yīng)的Gini index值。

3 結(jié)語

綜上所述，云計算在處理和計算海量的數(shù)據(jù)時表現(xiàn)出來的優(yōu)勢是無法替代的，而要想在數(shù)據(jù)挖掘中實現(xiàn)海量數(shù)據(jù)處理和計算，將SLIQ算法并行改進是一種十分可行的方式。因此，在本文中分析了云計算環(huán)境下的MapReduce的改進算法，說明在云計算的環(huán)境下決策規(guī)則和并行化是十分重要的基礎(chǔ)，在實現(xiàn)的過程中可以通過對SLIQ算法的改進，從而獲得對其高速運算的支持。

[1]賀?。骄坑嬎銠C云計算的SLIQ并行算法分析[J]．無線互聯(lián)科技，2014，（2）.

[2]崔學(xué)敏，張傳勇．云計算技術(shù)中計算機海量數(shù)據(jù)SLIQ算法的應(yīng)用[J]．電子技術(shù)與軟件工程，2015，（18）.

[3]何元．基于云計算的海量數(shù)據(jù)挖掘分類算法研究[D]．電子科技大學(xué)，2011.

[4]杜亞光．大跨度自錨式懸索橋結(jié)構(gòu)并行計算算法與主梁恒載狀態(tài)研究[D]．西南交通大學(xué)，2013.

[5]張敏．云計算環(huán)境下的并行數(shù)據(jù)挖掘策略研究[D]．南京郵電大學(xué)，2011.

[6]高華．計算機海量數(shù)據(jù)處理SLIQ算法研究[J]．長春工業(yè)大學(xué)學(xué)報，2016，（4）.

[7]李筱．面向異構(gòu)多核系統(tǒng)的并行計算模型和調(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é)院講師，碩士，研究方向：計算機應(yīng)用技術(shù)。

A