云計算框架下SPRINT大數(shù)據(jù)分類算法的優(yōu)化及應(yīng)用

周雅靜

關(guān)鍵詞：云計算框架；優(yōu)化SPRINT分類算法；GiNi值；子節(jié)點

中圖分類號：TP311 文獻標(biāo)識碼：A

文章編號：1009-3044（2023）20-0093-05

0 引言

云計算是一種新型的分布式計算模式，利用信息網(wǎng)絡(luò)技術(shù)將資源發(fā)布于網(wǎng)絡(luò)中，并有償將計算服務(wù)提供給客戶。作為一種新型的分布式計算模式，云計算采用了虛擬化核心層[1]，為用戶提供開源、便捷的計算服務(wù)[2]。國內(nèi)外有部分學(xué)者對云計算框架在大數(shù)據(jù)分類領(lǐng)域的應(yīng)用進行了研究。學(xué)者Tawalbeh L等人[3]從云計算的分布式計算理念入手分析，重點研究云計算框架在處理海量大數(shù)據(jù)時的實用性；學(xué)者Banchhor等人[4]著重研究了云計算框架在數(shù)據(jù)實時存儲方面的優(yōu)勢，能夠確保數(shù)據(jù)分類時核心數(shù)據(jù)不丟失；包涵等人[5]重點介紹了云計算框架在處理不平衡大數(shù)據(jù)分類過程中的應(yīng)用情況，云計算框架有助于解決小樣本數(shù)據(jù)集的分類問題；付東杰等人[6]研究了云計算框架在遙感大數(shù)據(jù)分類中的應(yīng)用。

但現(xiàn)有研究涉及的數(shù)據(jù)集規(guī)模有限，且分類算法與云計算框架的結(jié)合度較弱，沒有發(fā)揮出云計算框架的優(yōu)勢。對基礎(chǔ)大數(shù)據(jù)進行分類是云計算的最重要分析環(huán)節(jié)之一，其中規(guī)則歸納法[7]、貝葉斯分類法[8]、決策樹法等都是較為常用的分類方法[9]。與前兩種分類算法相比，決策樹的優(yōu)勢在于結(jié)構(gòu)簡單、效率高、準(zhǔn)確率有保障，是最受歡迎的分類方法。ID3分類法[10]和SLIQ方法[11]是目前應(yīng)用最為普遍的決策樹模式，ID3分類法以信息增益最大的屬性為樹節(jié)點的判定條件，直到全部的數(shù)據(jù)分類完成。但該方法的數(shù)據(jù)計算復(fù)雜度過高，且與云計算框架的兼容性較差；SLIQ方法可以同時處理不同類型的數(shù)據(jù)屬性，但該方法分類準(zhǔn)確率有待提升，應(yīng)對大規(guī)模數(shù)據(jù)集的效率也難以滿足實際應(yīng)用的需求。

為解決現(xiàn)有分類樹模型的不足，本文在云計算框架下提出一種優(yōu)化SPRINT大數(shù)據(jù)分類算法，能夠應(yīng)對處理大規(guī)模數(shù)據(jù)集，并易于實現(xiàn)云計算框架的并行化處理。同時，使得云計算框架下SPRINT大數(shù)據(jù)分類算法的優(yōu)勢能夠得以充分發(fā)揮，算法的兼容性更好，且通過最優(yōu)分割點的選擇和數(shù)據(jù)結(jié)構(gòu)的改進，SPRINT大數(shù)據(jù)分類算法并行計算優(yōu)勢較為明顯，無論是在算法的分類效率還是分類精度方面均得到了顯著提升。

1 云計算的應(yīng)用框架

云計算框架在云端布置了多個計算機資源，基于網(wǎng)絡(luò)將計算任務(wù)分配到云端，有云計算需求的用戶可在云端申請大數(shù)據(jù)計算服務(wù)和云端存儲服務(wù)[12]。云計算按照服務(wù)類型分為軟件服務(wù)層、平臺服務(wù)層和基礎(chǔ)設(shè)施服務(wù)層，各層次的劃分如圖1所示。

軟件服務(wù)層的主要用戶是開發(fā)人員，用戶通過瀏覽器在云端操作，獲取相應(yīng)的計算服務(wù)和數(shù)據(jù)服務(wù)，節(jié)省了大量的軟硬件投入；平臺服務(wù)層通過環(huán)境運營、業(yè)務(wù)運營和業(yè)務(wù)開發(fā)等整合供應(yīng)商資源，降低數(shù)據(jù)運營的成本；基礎(chǔ)設(shè)施服務(wù)層提供了虛擬機服務(wù)[13]，主要的服務(wù)對象是系統(tǒng)管理員。

2 SPRINT 分類算法的優(yōu)化與應(yīng)用

2.1 經(jīng)典SPRINT 算法

SPRINT算法是一種含有大量類別標(biāo)識參考數(shù)據(jù)的監(jiān)督學(xué)習(xí)決策樹，該算法采用了自上而下的遞歸方案建樹，并將大數(shù)據(jù)樣本劃分為訓(xùn)練集和測試集。SPRINT算法定義了屬性列表和類直方圖，是從訓(xùn)練數(shù)據(jù)集中創(chuàng)建屬性列表，與決策樹的根節(jié)點對應(yīng)，對連續(xù)型屬性進行排序。在建樹過程中根節(jié)點不斷分裂為子節(jié)點[14-15]，對應(yīng)的屬性列表也被分割到子節(jié)點中，同時，解決了數(shù)據(jù)分類前的多次排序問題。針對離散型大數(shù)據(jù)，SPRINT算法采用類直方圖記錄屬性值的分布情況，以GiNi指數(shù)作為大數(shù)據(jù)集最優(yōu)屬性的選擇標(biāo)準(zhǔn)，再利用哈希表結(jié)構(gòu)記錄決策樹的分裂信息，將哈希表[16-17]的數(shù)值記錄于各子節(jié)省上，如表1所示（以根節(jié)點為0的哈希表為例）。

SPRINT算法既可以處理連續(xù)型數(shù)據(jù)，也可以處理離散型數(shù)據(jù)，同時支持對數(shù)據(jù)的并行處理。

2.2 對經(jīng)典SPRINT 算法的優(yōu)化與改進

SPRINT 算法作為經(jīng)典的分類算法之一，具有易于實現(xiàn)并行化及伸縮擴容性良好等優(yōu)點，但同樣存在尋找最佳分割點時計算效率較低等不足，特別對于超大型數(shù)據(jù)集。為此，文章提出一種基于云計算框架的SPRINT優(yōu)化分類算法，其方法是利用GiNi值節(jié)點的分割提升連續(xù)屬性的優(yōu)化能力和分類算法并行計算能力，然后重新劃分大數(shù)據(jù)集的子集，并依據(jù)最佳分割點完成決策樹的構(gòu)建，提升大數(shù)據(jù)分類處理能力。

1） 最佳分割點識別與數(shù)據(jù)結(jié)構(gòu)改進

SPRINT算法利用GiNi指數(shù)尋找最佳的決策樹分割點，設(shè)大數(shù)據(jù)集S 的總記錄數(shù)為n，數(shù)據(jù)總類別數(shù)為m，則GiNi指數(shù)表示如下：

經(jīng)典SPRINT算法在尋找最優(yōu)屬性分割點時需要掃描屬性列表，而本文優(yōu)化的SPRINT算法從當(dāng)前節(jié)點屬性集中隨機選擇一個屬性列表，并計算與之對應(yīng)的GiNi值；然后再選擇后補屬性列表同時計算GiNi 值，對比兩個GiNi值的大小。如果當(dāng)前屬性值較小，將當(dāng)前的屬性列表保存在內(nèi)存中，刪除其他列表信息；如果當(dāng)前屬性值較大，依然保存原有的屬性列表，該列表對應(yīng)的GiNi值即為最優(yōu)的屬性規(guī)劃。經(jīng)過改進后的SPRINT算法通過計算GiNi值和哈希表尋找最佳的屬性分割點，避免了本地內(nèi)存過度的占用并降低了資源的消耗。

2.3 優(yōu)化決策樹模型的創(chuàng)建與應(yīng)用

云計算框架中內(nèi)置了與待分類大數(shù)據(jù)集相關(guān)的Web應(yīng)用，用戶基于客戶端向服務(wù)器發(fā)送請求，并尋找對應(yīng)的云服務(wù)項目，根據(jù)對應(yīng)的配置調(diào)用合適的Servlet。選定的Servlet 內(nèi)部利用Java 反射機制加載SPRINT大數(shù)據(jù)的分類，云計算框架的具體Servlet數(shù)據(jù)分類執(zhí)行流程如圖2所示。

服務(wù)器解析用戶需求的ID，調(diào)用已有的服務(wù)器規(guī)則引擎，判斷ID是否可以本地運行。如果可執(zhí)行，直接在Servlet 中執(zhí)行；如果不可執(zhí)行，則生成對應(yīng)的IDF_DATA加以封裝，并重新到本地服務(wù)器上執(zhí)行。哈希表占用的空間較大，需要外接存儲設(shè)備拓展空間，存儲設(shè)備中的屬性列表視為子節(jié)點對應(yīng)的屬性列表。改進后的SPRINT算法不需要在拓展存儲中生成節(jié)點屬性列表，而是基于GiNi值結(jié)果比較尋找最佳子集分割點，實現(xiàn)對決策樹的構(gòu)建，決策樹的建樹過程表示如下：

Step1：先實現(xiàn)對大數(shù)據(jù)集分割屬性的劃分，同時生成對應(yīng)的哈希表。

Step2：保留當(dāng)前層的哈希表，在下一層節(jié)點上利用當(dāng)前層哈希表和拓展內(nèi)存中的屬性列表，生成新的屬性列表。

Step3：采用逐層迭代的方式類推，逐漸構(gòu)建成樹狀結(jié)構(gòu)。因為在尋找最優(yōu)分割點時會使用到列表信息，如果不在屬性列表中生成列表信息，則只能通過調(diào)用哈希列表函數(shù)并結(jié)合根節(jié)點屬性解決。

Step4：結(jié)合表1及測試數(shù)據(jù)集的片段生成的決策樹如圖3所示。

判斷數(shù)據(jù)集中的列表屬性是離散型屬性還是連續(xù)型屬性，并對列表執(zhí)行預(yù)排序，如果識別出當(dāng)前列表中的類別符合要求隨即終止迭代。對于離散型屬性比較GiNi值來確定，是否選擇當(dāng)前節(jié)點作為目標(biāo)節(jié)點；而對于連續(xù)型屬性，不僅要掃描屬性列表，還要計算出每個最優(yōu)分割節(jié)點對應(yīng)的GiNi值。當(dāng)完成屬性分割得到最優(yōu)分割節(jié)點的GiNi值后，同時生成當(dāng)前節(jié)點對應(yīng)的哈希表，實現(xiàn)對數(shù)據(jù)集全部未劃分屬性的劃分，對建樹的過程描述如圖4所示。

優(yōu)化SPRINT算法主要從屬性分類的最優(yōu)節(jié)點選擇和降低算法總體復(fù)雜度兩個方面來提升和改善經(jīng)典決策樹算法的性能。在云計算的框架下，基于GiNi 值結(jié)果比較的子節(jié)點屬性分裂過程減少了分裂屬性列表的操作，同時也減少了在本地磁盤中連續(xù)生成子列表的操作，節(jié)省了磁盤空間消耗，有效提升了大數(shù)據(jù)分裂過程中的決策樹構(gòu)建效率。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境搭建

為進一步驗證云計算框架下優(yōu)化SPRINT算法的大數(shù)據(jù)分類性能，在實驗過程中安裝了MySQL數(shù)據(jù)庫和Infobright列式數(shù)據(jù)庫，并同時創(chuàng)建了10 000條有效的大數(shù)據(jù)記錄。實驗所用的相關(guān)軟硬件設(shè)置如表2 所示。

3.2 實驗結(jié)果分析

1） 算法分類效率對比

從MySQL數(shù)據(jù)庫的記錄中隨機篩選出1 000條數(shù)據(jù)并分成10組，分別采用ID3分類法、SLIQ方法和本文改進的SPRINT算法驗證對大數(shù)據(jù)的分類效率，驗證過程分為以下3個環(huán)節(jié)，采用了交叉驗證的方法標(biāo)定特定值提取時間：首先，計算出數(shù)據(jù)表中單一記錄的個數(shù)（隨機選取一個數(shù)據(jù)記錄）。然后，篩選出標(biāo)定特定值的記錄（共標(biāo)記3個特定值）。最后，統(tǒng)計不同字段的數(shù)據(jù)總數(shù)（共選擇3個字段），統(tǒng)計結(jié)果如表3 ～表5所示，提取數(shù)值的時間越短，證明算法的效率越高。

統(tǒng)計結(jié)果顯示，借助云計算框架并基于優(yōu)化SPRINT算法能夠顯著提升對目標(biāo)數(shù)據(jù)的分類提取效率，節(jié)省數(shù)據(jù)提取和分類時間。隨著待分類數(shù)據(jù)量的持續(xù)增加，優(yōu)化的SPRINT算法穩(wěn)定性優(yōu)勢會更加明顯，能夠確保分類計算效率不衰減，數(shù)據(jù)統(tǒng)計結(jié)果如圖5所示（以篩選出的1 000條數(shù)據(jù)為例）：

圖5中的數(shù)值變化顯示，隨著待分類數(shù)據(jù)規(guī)模的增加，云計算框架的優(yōu)化SPRINT算法分類耗時短、效率高，性能不衰減。

2） 算法分類性能對比

文章從決策樹結(jié)構(gòu)的生成時間和算法的加速比兩個方面對云計算框架下優(yōu)化SPRINT算法的性能進行分析，同時引入ID3分類法、SLIQ方法參與對比。將產(chǎn)生的數(shù)據(jù)集存儲于本地硬盤中，根據(jù)數(shù)據(jù)集的規(guī)模生成屬性列表，節(jié)點數(shù)量設(shè)定為8，當(dāng)遍歷完10 000條數(shù)據(jù)后決策樹自動生成，3種算法的決策樹生成時間變化情況如圖6所示：

當(dāng)參與屬性列表構(gòu)建和決策樹形成的節(jié)點數(shù)量較少時，各分類算法下建樹時間相差較小，隨著參與建樹的節(jié)點數(shù)量不斷增加后，優(yōu)化SPRINT算法的建樹時間更短，優(yōu)勢逐漸顯現(xiàn)出來，分類算法的性能優(yōu)勢更加明顯。分類算法的加速比能夠直接地顯示出算法的性能，當(dāng)有更多的節(jié)點接入后決策樹的建樹時間會以更快的速度減少，加速比越快代表算法的性能越強。3種不同分類算法下的加速比變化情況如圖7所示。

優(yōu)化SPRINT算法的優(yōu)勢在于利用大數(shù)據(jù)框架提升了節(jié)點之間的通信效率，優(yōu)化了分類算法的細節(jié)處理能力。由圖6中數(shù)據(jù)點的變化情況可知，隨著接入節(jié)點數(shù)量的增加，優(yōu)化SPRINT算法分類加速性能的優(yōu)勢也開始顯現(xiàn)出來。統(tǒng)計各算法的分類精度，仍舊從MySQL數(shù)據(jù)庫的記錄中隨機篩選出1 000條數(shù)據(jù)并分成10組驗證，結(jié)果如表6所示（分類精度為正確分類數(shù)據(jù)值與數(shù)據(jù)總數(shù)的比值）。

隨著數(shù)據(jù)規(guī)模的增大，通過分析各算法分類精度的變化情況，可以發(fā)現(xiàn)，云計算框架下優(yōu)化SPRINT算法的數(shù)據(jù)分類精度衰減相對于相對傳統(tǒng)算法更低，算法的性能更加穩(wěn)定可靠，如圖8所示。

4 結(jié)束語

本文在云計算框架下設(shè)計了一種優(yōu)化SPRINT大數(shù)據(jù)分類算法。云計算框架采用了三層次的基礎(chǔ)設(shè)計結(jié)構(gòu)，便于用戶實時需求的傳遞和通信節(jié)點之間數(shù)據(jù)的有效傳輸。根據(jù)用戶實際訪問需求和數(shù)據(jù)集的規(guī)模，將大數(shù)據(jù)集合分割成若干數(shù)據(jù)集列表，計算出最佳的GiNi值，并優(yōu)選出最佳的分割節(jié)點。實驗結(jié)果表明，云計算框架下的優(yōu)化SPRINT大數(shù)據(jù)分類算法效率更高，性能更強。