基于云邊協同的決策樹并行化設計

姚躍

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

關鍵詞：云邊協同；決策樹；并行化；邊緣算法；屬性相似度；數據處理

中圖分類號：TP3? 文獻標志碼：A

0 引言

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

1 基于云邊協同的決策樹屬性相似度

1.1 連續屬性離散化

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

定義1：屬性相似性代表用不同的測試屬性來替代決策的結果。

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

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

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

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

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

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

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

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

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

1.2 分裂屬性選擇

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

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

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

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

由試驗屬性A進行分割的信息增益是以下公式（7）。

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

對應于屬性A劃分的訓練集合S的信息量是公式（8）。

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

式中，｛a1，a2...ay｝是按照A的值將S分開而得到的所有子集合，而A的屬性所對應的信息增值是決定分裂屬性的重要因素。對符合要求的分裂屬性進行計算后，便可以開始決策樹的整體建立過程。

1.3 決策樹并行化實現

決策樹采用并行算法時，必須突出平行化，在此基礎上進行橫向平行分割，同時考慮在多個計算節點上進行高效的分布，并對不同屬性信息熵進行有針對性的計算。邊緣節點提供了計算存儲、網絡虛擬化等資源，還接受和執行云端資源的調度管理。云平臺上提供了資源計劃管理的策略，其中包括設備管理、資源管理和網絡連接管理。由于決策樹中的信息熵被分割的越多，其運算能力就越弱，因此，并行任務的調度就會變得非常困難，需要對決策樹并行算法進行進一步的優化，其流程如圖1所示。

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

2 對比實驗

2.1 實驗準備

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

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

2.2 實驗結果

2.2.1 有效性

根據實驗準備中表1的數據可以得知，其連續屬性離散化改進決策樹算法的運行時間如圖2所示。

在運行時間上，本文對決策樹算法在連續屬性離散化的改進與傳統算法對比，運行時間顯著縮短，減少程度幾乎與數據集的連續屬性占總屬性比值的大小趨勢保持一致。同時，算法的準確率在一個穩定的范圍內波動。由此可知連續屬性占總屬性比值越大則減少的時間越多，且本文在保證準確率的基礎上對連續屬性離散化進行優化，結果表明，該方法能有效地縮短運算時間，提高算法的運算速度。

2.2.2 準確性

為了驗證基于云邊協同的決策樹并行優化設計準確性，對采集到的數據集A重新進行數據節點的劃分，其中60%為訓練數據集，40%為測試數據集，其實驗結果如表2所示。

用同一個數據集進行測試，采用云邊協同策略的決策樹并行化算法運算在相同的時間內，精確度得到了改善。同時，從并行化的角度來看，節點數量的增多，使得算法的計算復雜度降低，且保持一定的精度，從而證明了基于云邊協同的決策樹并行設計是切實可行的。

3 結語

本文討論了基于云邊協同的決策樹并行化設計，為解決決策樹算法中存在的多個偏倚問題，采用屬性相似性作為判定屬性選取的準則，將其離散化做出分裂屬性選擇。從邊緣端和云端進行云邊協作決策樹構建，實現有效的決策樹并行化設計。隨著決策樹算法的不斷改進，其準確性和有效性越來越高，不斷融入云邊協同的方法使該算法的應用領域更加廣泛，使設計切實可行。

參考文獻

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

［2］郭祥富，劉昊，毛萬登，等.面向云邊協同的配變短期負荷集群預測［J］.電力系統保護與控制，2022（9）：84-92.

［3］聶麗霞，劉輝，鄒凌.基于異構網絡特征與梯度提升決策樹的協同藥物預測［J］.計算機應用與軟件，2020（4）：48-52.

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

（編輯 沈 強）

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