基于云邊協(xié)同的決策樹(shù)并行化設(shè)計(jì)

姚躍

摘要：隨著海量數(shù)據(jù)的分析任務(wù)越來(lái)越重，數(shù)據(jù)挖掘工作需要進(jìn)一步推進(jìn)和優(yōu)化。文章首先提出了基于云邊協(xié)同的決策樹(shù)并行化設(shè)計(jì)，根據(jù)連續(xù)屬性離散化判斷分裂屬性，在屬性確認(rèn)之后建立決策樹(shù)；其次對(duì)并行化設(shè)計(jì)內(nèi)的數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)建決策樹(shù)整體并行流程；最終實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)分析與智能處理。對(duì)比試驗(yàn)表明，基于云邊協(xié)同的決策樹(shù)算法連續(xù)屬性離散化的優(yōu)化，在保證準(zhǔn)確率的基礎(chǔ)上，能有效地縮短運(yùn)算時(shí)間，提高算法的運(yùn)算速度。

關(guān)鍵詞：云邊協(xié)同；決策樹(shù)；并行化；邊緣算法；屬性相似度；數(shù)據(jù)處理

中圖分類(lèi)號(hào)：TP3? 文獻(xiàn)標(biāo)志碼：A

0 引言

網(wǎng)絡(luò)的數(shù)據(jù)挖掘一般使用決策樹(shù)算法進(jìn)行數(shù)據(jù)處理，傳統(tǒng)的決策樹(shù)算法在連續(xù)屬性離散化和屬性選擇中存在效果偏弱，算法低效，因此決策樹(shù)算法需要進(jìn)行并行化的設(shè)計(jì)及優(yōu)化［1］。云邊協(xié)議的優(yōu)勢(shì)在于擁有更為高效的任務(wù)分配模式，將“云計(jì)算”和“邊緣計(jì)算”進(jìn)行互補(bǔ)，強(qiáng)大的調(diào)度機(jī)制可以增強(qiáng)決策樹(shù)算法在處理各項(xiàng)數(shù)據(jù)時(shí)的性能和效率［2］。根據(jù)連續(xù)屬性離散化判斷分裂屬性，在屬性確認(rèn)之后建立決策樹(shù)［3］。之后再根據(jù)相似度進(jìn)行決策樹(shù)并行化計(jì)算，數(shù)據(jù)需要在初次預(yù)處理后實(shí)現(xiàn)決策樹(shù)的并行化，最后確定基于云邊協(xié)作的決策樹(shù)并行化算法的流程［4］。在此基礎(chǔ)上，以試驗(yàn)數(shù)據(jù)為研究對(duì)象，實(shí)現(xiàn)決策樹(shù)算法數(shù)據(jù)的實(shí)時(shí)分析與智能處理，提高了數(shù)據(jù)處理的效率和安全性。

1 基于云邊協(xié)同的決策樹(shù)屬性相似度

1.1 連續(xù)屬性離散化

在決策樹(shù)算法的測(cè)試屬性選取中，將信息理論內(nèi)的信息增益加以引入；隨即遞歸每個(gè)分支下的訓(xùn)練事例，利用這種層層遞進(jìn)的方法可構(gòu)造出層次邏輯清晰的決策樹(shù)分支，直至所有子集的實(shí)例數(shù)據(jù)屬性都顯示相同的狀態(tài)。為了解決決策樹(shù)算法中存在的多值偏好問(wèn)題，本文將屬性相似性作為判斷屬性選取的準(zhǔn)則。解決連續(xù)屬性的離散化問(wèn)題，因遵循的定義如下所示。

定義1：屬性相似性代表用不同的測(cè)試屬性來(lái)替代決策的結(jié)果。

定義2：在完整的電子計(jì)算機(jī)信息構(gòu)架中，L=（U，Q）內(nèi)的U為論域范圍，Q為條件屬性集C和決策屬性集D所構(gòu)成的集合，定義特性A∈C，與其相似程度用式（1）表示。

S（D，A）=|D∪{A}||D|*|{A}|（1）

式（1）中，S為相似度，D為決策屬性，A為定義屬性。相似度S越大，則定義屬性A與決策屬性 D越接近，尤其在S=1時(shí)，A和D就會(huì)非常接近；反之，S愈低，A就愈不接近D。按照知識(shí)的粒度，可以知道，在完整的電子計(jì)算機(jī)信息構(gòu)架中L=（U，Q）內(nèi)的U為論域范圍，Q為條件屬性集C和決策屬性D所構(gòu)成的集合，定義屬性A∈C與D的相似度可用粒度來(lái)表示，即式（2）所示。

S（D，A）=GD|D∪｛A｝|GD（D）*GD（｛A｝）（2）

GD（D）表示D的粒度值為式（3）所示。

GD（D）=∑ni=1|Di|2（3）

根據(jù)上述方程，可以得到條件屬性A和判定屬性D的屬性相似性公式（4）。

S（D，A）=∑ni=1∑mj=1ai，j2∑ni=1ai，m+12∑mj=1an+1，j2（4）

其中：ai，j表示在屬性A中，取ai記錄下屬于類(lèi)Di的記數(shù)式，式（3）對(duì)判定屬性D與A的相似度進(jìn)行了測(cè)度，其數(shù)值愈大，屬性相似度愈高。在決策樹(shù)算法中，屬性相似性是判斷屬性選擇的準(zhǔn)則，而與決策屬性越相近則是越好的選擇。從理論上可以看出，這種決策樹(shù)并行方法能有效地解決多值傾向問(wèn)題，且分類(lèi)的正確性也較高。

1.2 分裂屬性選擇

連續(xù)屬性離散化的下一步數(shù)據(jù)處理需在云邊協(xié)作中完成，邊緣算法主要針對(duì)需要進(jìn)行實(shí)時(shí)處理的數(shù)據(jù)為云邊協(xié)同做出服務(wù)；而云技術(shù)主要負(fù)責(zé)數(shù)據(jù)的非實(shí)時(shí)、長(zhǎng)周期數(shù)據(jù)的采集，以及對(duì)邊緣應(yīng)用進(jìn)行全周期的管理。在基于邊緣協(xié)作的基礎(chǔ)上，建立基于云邊協(xié)作的信息增益率，以此來(lái)選取最優(yōu)的特征。設(shè)A為訓(xùn)練樣本合集，此合集包含Ai元組，i=｛1，2，3...m｝，則期望信息為式（5）所示。

I（A1，A2...Am）=-∑mi=1AiAlog2AiA（5）

式中，Ai為包含i個(gè)對(duì)象的樣本集。設(shè)Aj為包含j個(gè)對(duì)象的樣本集，根據(jù)劃分的期望信息計(jì)算A的熵為下列式（6）所示。

E（A）=∑vj=1AjSI（A1j+...+Amj）（6）

由試驗(yàn)屬性A進(jìn)行分割的信息增益是以下公式（7）。

Gain（A）=I（A1，A2...Am）-E（A）（7）

對(duì)應(yīng)于屬性A劃分的訓(xùn)練集合S的信息量是公式（8）。

SplitInfo（A）=I|a1||a|，|a2||a|...|ay||a|（8）

式中，｛a1，a2...ay｝是按照A的值將S分開(kāi)而得到的所有子集合，而A的屬性所對(duì)應(yīng)的信息增值是決定分裂屬性的重要因素。對(duì)符合要求的分裂屬性進(jìn)行計(jì)算后，便可以開(kāi)始決策樹(shù)的整體建立過(guò)程。

1.3 決策樹(shù)并行化實(shí)現(xiàn)

決策樹(shù)采用并行算法時(shí)，必須突出平行化，在此基礎(chǔ)上進(jìn)行橫向平行分割，同時(shí)考慮在多個(gè)計(jì)算節(jié)點(diǎn)上進(jìn)行高效的分布，并對(duì)不同屬性信息熵進(jìn)行有針對(duì)性的計(jì)算。邊緣節(jié)點(diǎn)提供了計(jì)算存儲(chǔ)、網(wǎng)絡(luò)虛擬化等資源，還接受和執(zhí)行云端資源的調(diào)度管理。云平臺(tái)上提供了資源計(jì)劃管理的策略，其中包括設(shè)備管理、資源管理和網(wǎng)絡(luò)連接管理。由于決策樹(shù)中的信息熵被分割的越多，其運(yùn)算能力就越弱，因此，并行任務(wù)的調(diào)度就會(huì)變得非常困難，需要對(duì)決策樹(shù)并行算法進(jìn)行進(jìn)一步的優(yōu)化，其流程如圖1所示。

改進(jìn)的決策樹(shù)并行算法稱(chēng)為SIPDT執(zhí)行過(guò)程，其流程主要由以下內(nèi)容組成：初始化Spark環(huán)境，讀入初始數(shù)據(jù)集并完成RDD轉(zhuǎn)換，并對(duì)數(shù)據(jù)集完成標(biāo)準(zhǔn)化判斷，判斷屬性中是否存在連續(xù)屬性值。若有，則先轉(zhuǎn)到第5步再依次完成第6步；若無(wú)，則直接轉(zhuǎn)到第5步；通過(guò)map函數(shù)利用改進(jìn)的連續(xù)屬性離散化（FG-CAD）方法，找到連續(xù)屬性的最佳分割點(diǎn)；通過(guò)map函數(shù)，利用改進(jìn)的信息增益率計(jì)算公式，對(duì)各個(gè)屬性進(jìn)行并行計(jì)算，在此基礎(chǔ)上將信息增益系數(shù)最大的特征作為決策樹(shù)的劃分結(jié)點(diǎn)；然后使用返回功能通過(guò)reduce函數(shù)，執(zhí)行決策樹(shù)算法進(jìn)行遞歸計(jì)算，直到將屬性全部劃分完，構(gòu)造出一個(gè)完整的決策樹(shù)模型，最后進(jìn)行決策樹(shù)剪枝，決策樹(shù)整體并行構(gòu)建徹底完成。

2 對(duì)比實(shí)驗(yàn)

2.1 實(shí)驗(yàn)準(zhǔn)備

本文先通過(guò)一些數(shù)據(jù)集在Matlab平臺(tái)上對(duì)基于云邊協(xié)同的決策樹(shù)并行化設(shè)計(jì)進(jìn)行實(shí)驗(yàn)驗(yàn)證，從UCI中選用了5個(gè)常用的公開(kāi)數(shù)據(jù)集，數(shù)據(jù)的范圍較為廣泛。Hadoop是一個(gè)Java的MapReduce框架，是本文運(yùn)用的主要算法。首先建立兩種服務(wù)器集群的模擬試驗(yàn)平臺(tái)，一種是JobTracker節(jié)點(diǎn)，一種是任務(wù)跟蹤節(jié)點(diǎn)；從平臺(tái)中挑選5個(gè)可以用作年度計(jì)算和數(shù)據(jù)存儲(chǔ)的結(jié)點(diǎn)作為實(shí)驗(yàn)對(duì)象。同時(shí)，采用Xen的虛擬化技術(shù)，實(shí)現(xiàn)多個(gè)MapReduce的并行運(yùn)行。其次，將Hadoop-0.20.0和JDK安裝在服務(wù)器上，在Eclipse的集成開(kāi)發(fā)環(huán)境下，實(shí)現(xiàn)該平臺(tái)的程序運(yùn)行。最后，與傳統(tǒng)的決策樹(shù)算法作對(duì)比，比較基于云邊緣協(xié)同和串行特征相似度的決策樹(shù)算法在計(jì)算精度、效率等方面的應(yīng)用，具體實(shí)驗(yàn)數(shù)據(jù)集如表1所示。

由表1可以計(jì)算出5個(gè)數(shù)據(jù)集在連續(xù)型屬性數(shù)中占總屬性數(shù)的比值，A=1，B=0.7，C=0.36，D=0.6，E=1;從大到小進(jìn)行排序，得到數(shù)據(jù)集A=數(shù)據(jù)集E>數(shù)據(jù)集B>數(shù)據(jù)集D>數(shù)據(jù)集C。

2.2 實(shí)驗(yàn)結(jié)果

2.2.1 有效性

根據(jù)實(shí)驗(yàn)準(zhǔn)備中表1的數(shù)據(jù)可以得知，其連續(xù)屬性離散化改進(jìn)決策樹(shù)算法的運(yùn)行時(shí)間如圖2所示。

在運(yùn)行時(shí)間上，本文對(duì)決策樹(shù)算法在連續(xù)屬性離散化的改進(jìn)與傳統(tǒng)算法對(duì)比，運(yùn)行時(shí)間顯著縮短，減少程度幾乎與數(shù)據(jù)集的連續(xù)屬性占總屬性比值的大小趨勢(shì)保持一致。同時(shí)，算法的準(zhǔn)確率在一個(gè)穩(wěn)定的范圍內(nèi)波動(dòng)。由此可知連續(xù)屬性占總屬性比值越大則減少的時(shí)間越多，且本文在保證準(zhǔn)確率的基礎(chǔ)上對(duì)連續(xù)屬性離散化進(jìn)行優(yōu)化，結(jié)果表明，該方法能有效地縮短運(yùn)算時(shí)間，提高算法的運(yùn)算速度。

2.2.2 準(zhǔn)確性

為了驗(yàn)證基于云邊協(xié)同的決策樹(shù)并行優(yōu)化設(shè)計(jì)準(zhǔn)確性，對(duì)采集到的數(shù)據(jù)集A重新進(jìn)行數(shù)據(jù)節(jié)點(diǎn)的劃分，其中60%為訓(xùn)練數(shù)據(jù)集，40%為測(cè)試數(shù)據(jù)集，其實(shí)驗(yàn)結(jié)果如表2所示。

用同一個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，采用云邊協(xié)同策略的決策樹(shù)并行化算法運(yùn)算在相同的時(shí)間內(nèi)，精確度得到了改善。同時(shí)，從并行化的角度來(lái)看，節(jié)點(diǎn)數(shù)量的增多，使得算法的計(jì)算復(fù)雜度降低，且保持一定的精度，從而證明了基于云邊協(xié)同的決策樹(shù)并行設(shè)計(jì)是切實(shí)可行的。

3 結(jié)語(yǔ)

本文討論了基于云邊協(xié)同的決策樹(shù)并行化設(shè)計(jì)，為解決決策樹(shù)算法中存在的多個(gè)偏倚問(wèn)題，采用屬性相似性作為判定屬性選取的準(zhǔn)則，將其離散化做出分裂屬性選擇。從邊緣端和云端進(jìn)行云邊協(xié)作決策樹(shù)構(gòu)建，實(shí)現(xiàn)有效的決策樹(shù)并行化設(shè)計(jì)。隨著決策樹(shù)算法的不斷改進(jìn)，其準(zhǔn)確性和有效性越來(lái)越高，不斷融入云邊協(xié)同的方法使該算法的應(yīng)用領(lǐng)域更加廣泛，使設(shè)計(jì)切實(shí)可行。

參考文獻(xiàn)

［1］招景明，張捷，宋鵬，等.一種高效的基于云邊端協(xié)同的電力數(shù)據(jù)采集系統(tǒng)［J］.電網(wǎng)與清潔能源，2022（5）：49-55.

［2］郭祥富，劉昊，毛萬(wàn)登，等.面向云邊協(xié)同的配變短期負(fù)荷集群預(yù)測(cè)［J］.電力系統(tǒng)保護(hù)與控制，2022（9）：84-92.

［3］聶麗霞，劉輝，鄒凌.基于異構(gòu)網(wǎng)絡(luò)特征與梯度提升決策樹(shù)的協(xié)同藥物預(yù)測(cè)［J］.計(jì)算機(jī)應(yīng)用與軟件，2020（4）：48-52.

［4］常昊，楊盛泉.基于協(xié)同過(guò)濾決策樹(shù)的商品推薦算法的研究［J］.價(jià)值工程，2020（9）：127-129.

（編輯 沈 強(qiáng)）

Parallel design of decision tree based on cloud side collaboration

Yao? Yue

（Changsha Vocational &Technical College， Changsha 410217， China）

Abstract：? With the increasingly heavy task of analyzing massive data， data mining needs to be further promoted and optimized. Therefore， this paper firstly proposes a parallel design of decision tree based on cloud edge collaboration; secondly， according to the discretization of continuous attributes， the split attributes are judged， and the decision tree is established after the attributes are confirmed. Preprocess the data in the parallel design， construct the overall parallel process of the decision tree， and finally realize the real-time analysis and intelligent processing of the data. Comparative experiments show that the optimization of continuous attribute discretization of decision tree algorithm based on cloud edge collaboration can effectively shorten the operation time and improve the operation speed of the algorithm on the basis of ensuring the accuracy.

Key words： cloud edge collaboration; decision tree; parallelization; edge algorithm; attribute similarity; data processing