計(jì)算機(jī)云計(jì)算的SLIQ并行算法實(shí)踐研究

孫 娟

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

1 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ì)算的過(guò)程中會(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 云計(jì)算的SLIQ計(jì)算改進(jìn)

2.1 決策樹中的Gini指標(biāo)

在通常的情況下，決策樹中會(huì)選用信息量來(lái)作為評(píng)價(jià)節(jié)點(diǎn)分裂質(zhì)量的參數(shù)，在SLIQ算法之中則對(duì)此做出了改變，利用Gini指標(biāo)來(lái)代替信息量的位置，其應(yīng)用起來(lái)性能相對(duì)更好，讓整個(gè)計(jì)算變得更加的簡(jiǎn)便、高效。在Gini指標(biāo)之中，主要是用來(lái)度量數(shù)據(jù)劃分或者訓(xùn)練元祖級(jí)的純度。當(dāng)Gini指標(biāo)出現(xiàn)變小的情況時(shí)則預(yù)示著信息增益量變大，對(duì)于節(jié)點(diǎn)分裂的質(zhì)量也就越好。在此過(guò)程之中也可以對(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)行分裂?？赡苤苯舆@樣說(shuō)理解起來(lái)較為困難，現(xiàn)以實(shí)際距離進(jìn)行分析：在一個(gè)字段之中，如果發(fā)生分裂通常都會(huì)是在其中點(diǎn)的位置，將該字段進(jìn)行排序，一共具有N個(gè)節(jié)點(diǎn)，分裂發(fā)生時(shí)只會(huì)是在兩節(jié)點(diǎn)的中間，也就是說(shuō)在N個(gè)節(jié)點(diǎn)中會(huì)出現(xiàn)N-1個(gè)可能性，然后從小到大依次取其中不同的分裂節(jié)點(diǎn)，從中可以找出Gini指標(biāo)最小的分裂點(diǎn)。但是其中也存在著特殊的情況，如離散字段可能的分割則是屬性值中的所有子集，在展開分裂測(cè)試的時(shí)候就需要將其中存在可能的所有子集都取出來(lái)。

SLIQ算法中重要的技術(shù)優(yōu)勢(shì)在于事先排序和廣度優(yōu)先者兩種技術(shù)思路上面，也正是這兩種技術(shù)的運(yùn)用使得SLIQ算法變得更加的高效。對(duì)于事先排序技術(shù)而言主要是為了消除在決策樹中每個(gè)節(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行排序的過(guò)程，從而實(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)通常被用來(lái)替代信息量，在生成新的決策樹中起到非常重要的作用。對(duì)其定義為在數(shù)據(jù)集中包含多個(gè)記錄，則Gini index可以用下面式子來(lái)進(jìn)行表示：

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

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

對(duì)于其中出現(xiàn)數(shù)值連續(xù)型連續(xù)字段的時(shí)候，查找其中最合理點(diǎn)的方法為：首先假設(shè)有字段a為數(shù)值連續(xù)字段，對(duì)其進(jìn)行預(yù)排序操作，然后得到R1、R2、R3、……、Rn的排序結(jié)果，在分裂的過(guò)程中沒(méi)有一定的規(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)用過(guò)程中為了能夠讓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)則的過(guò)程。這個(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è)過(guò)程被極大簡(jiǎn)化，讓其在較短的時(shí)間內(nèi)就能夠完成，而且生成出來(lái)的目標(biāo)數(shù)也較小。

2.4 在Map Reduce中SLIQ的改進(jìn)

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

第一，將所有收集到的根節(jié)點(diǎn)數(shù)據(jù)記錄運(yùn)用Map Reduce函數(shù)來(lái)進(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è)操作的過(guò)程，首先是Map操作：通過(guò)該操作會(huì)將輸入進(jìn)來(lái)的相關(guān)記錄進(jìn)行仔細(xì)的掃描，然后按照特定的程序進(jìn)行分類整理，把其中key相同的數(shù)據(jù)放在一起存儲(chǔ)到相應(yīng)的文件之中，然后才是將文件配置到Reduce之中，執(zhí)行接下來(lái)的操作。

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

3 結(jié)語(yǔ)

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

[1]賀?。骄坑?jì)算機(jī)云計(jì)算的SLIQ并行算法分析[J]．無(wú)線互聯(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