孫 娟

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

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

孫 娟

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

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

計算機；云計算；SLIQ并行算法；數據分析；數據存儲

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

1 SLIQ算法的概述

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

2 云計算的SLIQ計算改進

2.1 決策樹中的Gini指標

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

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

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

2.2 SLIQ最佳分裂

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

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

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

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

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

2.3 對SLIQ的適應性改進

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

2.4 在Map Reduce中SLIQ的改進

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

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

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

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

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

3 結語

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

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

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

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

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

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

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

[7]李筱．面向異構多核系統(tǒng)的并行計算模型和調度算法研究[D]．湖南大學，2012.

（責任編輯：黃銀芳）

TP393

1009-2374（2017）12-0011-02

10.13535/j.cnki.11-4406/n.2017.12.006

孫娟（1977-），女，江蘇江都人，江海職業(yè)技術學院講師，碩士，研究方向：計算機應用技術。

A