查道貴

(宿州職業(yè)技術(shù)學(xué)院計算機信息系,安徽 宿州 234101)

0 引 言

隨著信息技術(shù)的迅猛發(fā)展，大數(shù)據(jù)時代的到來以及各行業(yè)對速度與運營成本要求的提高，分布式計算框架由此而生。分布式計算框架可以將多個計算任務(wù)進行分步驟計算，對拆分之后的若干個子任務(wù)進行精細計算，使得計算結(jié)果也更加精確[1]。分布式計算框架技術(shù)應(yīng)用范圍廣闊，目前最常用的兩種機器學(xué)習(xí)分布式框架主要為Mahout，GraphLab以及MLIib[2]。盡管目前的MLIib還處于起步階段，相關(guān)研究尚未成熟，但MLIib的運用工具是最方便、計算效率最高的，具有非常大的發(fā)展?jié)摿3]。機器學(xué)習(xí)中最常見的問題為聚類與分類，聚類分析的應(yīng)用范圍廣泛，多見于物流、交通以及圖像處理行業(yè)，聚類分析中用得最多的為K-均值算法，而分類分析則主要運用于電商、醫(yī)學(xué)信息處理以及網(wǎng)站運營分類等，其最常用的算法為隨機森林算法，這種算法具有較高的計算性能與數(shù)據(jù)處理能力[4]。研究提出了自適應(yīng)改進的K-均值算法(Adaptive K-means，AKM)和隨機森林算法(Adaptive Random Forests，ARF)，建立了基于Spark平臺技術(shù)的AMLF(Adaptive Machine Learning Framework on Spark)機器學(xué)習(xí)應(yīng)用框架以便于提升機器學(xué)習(xí)的應(yīng)用效率。

1 算法優(yōu)化與機器學(xué)習(xí)框架設(shè)計

1.1 K-均值聚類算法與隨機森林分類算法

K-均值算法的主要目標是實現(xiàn)待處理數(shù)據(jù)的分簇，按照各數(shù)據(jù)距簇類中心的距離，對其進行相應(yīng)的聚類[5]。雖然K-均值算法的計算過程復(fù)雜，但不可否認是一種有效的聚類算法，常利用快速收斂以獲取局部最優(yōu)解。假定存在數(shù)據(jù)集合X，X={X1,X2,...,Xn}，集合X中的元素均為d階向量。K-均值算法劃分數(shù)據(jù)對象的依據(jù)為對象屬性特征，按照不同的屬性值，將其劃分至不同簇中。若k≤n，促使各群組元素的總體均方誤差降至最小，可將此群組記為V，若出現(xiàn)k個群組Si，皆有i=1,2...,k,μi，可設(shè)定為群組Si內(nèi)元素的中心值。V適用的計算模型如式(1)：

(1)

K-均值算法的主要流程為輸入輸出，輸入包括群組以及數(shù)據(jù)對象個數(shù)。輸出則包含數(shù)據(jù)對象集合的劃分，劃分結(jié)束之后重新計算簇族中每個數(shù)據(jù)點距中心的距離是否符合距離最小原則。若不符合，則重新劃分；若符合，則循環(huán)結(jié)束。

隨機森林實質(zhì)為集成分類器，依據(jù)隨機原則建立彼此間相互獨立且各異的決策樹。隨機森林算法可以表示為{h(x,θk),k=1,...,L},其中的θk為算法中的隨機向量參數(shù)，x表示數(shù)據(jù)信息。各決策樹的參數(shù)都是隨機向量，隨機選取樣本屬性特征，并隨機分配樣本數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集。隨機森林算法中需要構(gòu)建決策樹數(shù)量，用k表示；同時構(gòu)建各決策樹訓(xùn)練集中的樣本數(shù)目，用n表示；另外還需對樣本特征數(shù)量與分割特征數(shù)進行設(shè)定，分別用M，m表示，其中有m≤M。使用隨機森林算法對多個數(shù)據(jù)點依照數(shù)據(jù)特點進行分類時，首先在所有數(shù)據(jù)樣本中隨機劃分，形成k組訓(xùn)練數(shù)據(jù)集(k顆決策樹)，未歸入訓(xùn)練數(shù)據(jù)集的樣本數(shù)據(jù)則為袋外數(shù)據(jù)。接著隨機選取m個決策樹節(jié)點特征，依據(jù)此特征進行最佳分割特征值的計算。讓各決策樹自由生長，并利用生成的決策樹構(gòu)建隨機森林模型，通過隨機森林模型判別分類未知數(shù)據(jù)。

1.2 Spark框架

Spark是一種通過Scala語言構(gòu)建的新型分布式計算框架技術(shù)，可以對分布計算中涉及到的重用數(shù)據(jù)集進行工作負載設(shè)計。Spark框架中包含RDD數(shù)據(jù)集，這種數(shù)據(jù)集為彈性分布式，可以進行多節(jié)點分區(qū)、也可以實現(xiàn)多計算共享，不僅可以應(yīng)用至數(shù)據(jù)集，還可以進行局部調(diào)度。RDD實際上也是一個Scala對象，大大提高了數(shù)據(jù)的訪問速度，省去了繁瑣的磁盤讀寫操作。為了能夠進行大數(shù)據(jù)處理，Spark中不僅建立了MapReduce編程模型，且能夠提供多樣化的配套工具集，便于不同應(yīng)用下的大數(shù)據(jù)處理。驅(qū)動程序會開啟工作結(jié)點，工作結(jié)點獲取本地文件系統(tǒng)的數(shù)據(jù)后，本地內(nèi)存即時完成對RDD數(shù)據(jù)集的緩存。執(zhí)行過程中，驅(qū)動程序主要用于代碼信息傳遞，使得工作結(jié)點合理處理分區(qū)數(shù)據(jù)。數(shù)據(jù)計算完成后，程序就執(zhí)行結(jié)束，結(jié)果通過工作結(jié)點返回到驅(qū)動程序。

1.3 基于AMLF框架的機器學(xué)習(xí)算法優(yōu)化

為了克服上文提出的兩聚類算法的缺點以及機器學(xué)習(xí)對使用者要求較高的問題，研究中將建立基于Spark平臺技術(shù)的機器學(xué)習(xí)應(yīng)用框架(AMLF)。設(shè)計了框架可提供學(xué)習(xí)算法接口，將算法底層細節(jié)進行隱藏，從而實現(xiàn)推廣機器學(xué)習(xí)使用，降低應(yīng)用門檻的目的。AMLF框架對待析原始數(shù)據(jù)集進行標準化處理，并檢測以及刪除待析原數(shù)據(jù)集中的孤立點，根據(jù)原始數(shù)據(jù)集的屬性特征，自動計算簇類中心點的個數(shù)K[6]。按照機器學(xué)習(xí)的處理過程，原始數(shù)據(jù)集預(yù)處理、算法與模型學(xué)習(xí)以及評估等過程均在AMLF框架上進行，優(yōu)化后的隨機森林算法統(tǒng)一用ARF算法表示。此外，AMLF框架的主要設(shè)計目標還包括便于應(yīng)用、提供多類型的數(shù)據(jù)訪問接口。使用者需要對算法的相關(guān)參數(shù)進行設(shè)定，并且對原始數(shù)據(jù)集進行預(yù)先處理，這些都不是易事，因而這嚴重阻礙了機器學(xué)習(xí)的應(yīng)用。AMLF框架的技術(shù)基礎(chǔ)為Spark平臺技術(shù)，根據(jù)AMLF的設(shè)計目標，可以得到圖1所示的框架結(jié)構(gòu)圖。

圖1 AMLF框架結(jié)構(gòu)圖

2 實驗驗證

研究以數(shù)據(jù)庫中的4個數(shù)據(jù)集進行算法檢測，命名其為DS1，DS2，DS3以及DS4。其中DS1中的數(shù)據(jù)元素分布較為均勻且各群組大小相近；DS2中的數(shù)據(jù)元素分布不均，各群組距離較近；DS3中的數(shù)據(jù)元素分布散亂，各群組間相差較大；而DS4為高階數(shù)據(jù)集，群組內(nèi)的數(shù)據(jù)元素分布較為散亂。算法優(yōu)化效果主要從準確性、可升級性兩方面進行評估。研究中在所有數(shù)據(jù)集中均添加了部分孤立點，孤立點特征值的選取主要依據(jù)原始數(shù)據(jù)的特征范圍。有關(guān)處理后利用AKM算法得到了DS1數(shù)據(jù)集的分布與聚類結(jié)果，如圖2(a)所示。DS1數(shù)據(jù)集中群組數(shù)目的取值范圍為[2，11]，最優(yōu)群組數(shù)為2。AKM算法能夠精確識別出DS1數(shù)據(jù)集中的群組數(shù)量，并進行聚類，聚類效果較好，準確率近乎100%。同理，經(jīng)數(shù)據(jù)標準化處理后，利用對應(yīng)算法得到了DS2數(shù)據(jù)集的分布與聚類結(jié)果，如圖2(b)所示。由圖2(b)可知，DS2數(shù)據(jù)集中群組數(shù)目的取值范圍為[2，13]，最優(yōu)群組數(shù)為4。AKM算法能夠精確識別出DS2中的群組數(shù)量，并進行聚類，聚類效果較好，準確率為96%。類似可得到DS3的分布與聚類結(jié)果，如圖2(c)所示。

(a) 基于AKM算法的DS1數(shù)據(jù)分布與聚類結(jié)果

由圖2(c)可知，DS3中群組數(shù)目的取值范圍為[2，25]，最優(yōu)群組數(shù)為4。AKM算法能夠精確識別出DS3中的群組數(shù)量，并進行聚類，且聚類效果較好，準確率為91%。DS4由于為高階數(shù)據(jù)組，因而其分布與聚類結(jié)果不能以圖展現(xiàn)。利用AKM算法對DS4數(shù)據(jù)集進行聚類，經(jīng)相關(guān)處理后，得到數(shù)據(jù)集的取值區(qū)間為[2，17]，最優(yōu)群組數(shù)量為3，聚類準確率為87%。綜合可知，AKM算法的聚類準確率較高，不僅擁有良好的抗干擾力，而且能夠獨立處理數(shù)據(jù)集。此外，為了驗證AKM算法的可升級性，根據(jù)集群的不同數(shù)量，對AKM算法的運行時間以及算法加速比進行統(tǒng)計。統(tǒng)計結(jié)果表明，AKM算法具有較高的可升級性，是一種適用性極強的應(yīng)用型算法。

對ARF算法的準確性與可升級性進行驗證。實驗開始前對各數(shù)據(jù)集進行預(yù)處理，即將數(shù)據(jù)對象添加對應(yīng)的噪聲特征以及冗余特征。其中的噪聲特征選取具有隨機性，冗余特征取值則與數(shù)據(jù)對象的特征取值密切相關(guān)。研究中將決策樹原始算法、原始隨機森林原始算法與ARF算法進行對比，對比結(jié)果見圖3(a)。

由圖3(a)可知，同決策樹算法相比，ARF算法準確率為其1.5倍；同隨機森林算法相比，ARF算法準確率為其1.2倍。此外ARF算法具有較強的噪聲刪除與冗余刪除能力。綜合可知，ARF算法不僅具有較高的穩(wěn)定性，還具有較強的聚類分析能力。類似可得到ARF算法的升級驗證效果，如圖3(b)所示。由圖3(b)可知，最小的數(shù)據(jù)集中所含機群結(jié)點數(shù)為2，最大的數(shù)據(jù)集中所含機群結(jié)點數(shù)為12，數(shù)據(jù)集1的加速比最高，數(shù)據(jù)集2的加速比最低，數(shù)據(jù)集3、數(shù)據(jù)集4與數(shù)據(jù)集5則適中。且無論應(yīng)用于何種數(shù)據(jù)集，ARF算法的可升級性都較高，具有極強的適用性。

(a) 三種算法的數(shù)據(jù)分類準確率對比

3 結(jié) 語

在分析機器學(xué)習(xí)常用算法的基礎(chǔ)上，構(gòu)建了基于Spark框架的AMLF機器學(xué)習(xí)應(yīng)用框架，并利用此框架對機器學(xué)習(xí)聚類分析算法提出了AKM與ARF優(yōu)化算法，最后從分類準確率以及可升級性兩方面對AKM算法與ARF算法進行評估。結(jié)果顯示，AKM算法在四個數(shù)據(jù)集中的分類準確率均較高，近乎于100%，聚類效果較好。AKM算法具有較高的可升級性，是一種適用性極強的應(yīng)用型算法；ARF算法準確率為決策樹算法的1.5倍；為隨機森林算法的1.2倍，且ARF算法具有較強的噪聲刪除與冗余刪除能力。其可升級性驗證表明，ARF算法在5個數(shù)據(jù)集中的測試加速比均較高，具有較高的可升級性。