區(qū)塊鏈框架下基于優(yōu)化決策樹模型的大數(shù)據(jù)分類算法研究

楊薇薇，曾凌靜

（福建船政交通職業(yè)學院 信息與智慧交通學院，福建 福州 350007）

在互聯(lián)網(wǎng)、信息產(chǎn)業(yè)和通信技術的推動下，每天都會產(chǎn)生海量的數(shù)據(jù)，據(jù)國際權威大數(shù)據(jù)研究機構Statista 預測，到2020 年底全球的數(shù)據(jù)總量有望突破50 ZB 大關［1-2］。大數(shù)據(jù)是人類社會進步的主要推動力之一，大數(shù)據(jù)資源也是世界各國參與國際競爭所必備的最主要資源之一［3］。由于大數(shù)據(jù)的規(guī)模巨大、格式多樣，且具有多源異構性，要深度挖掘出大數(shù)據(jù)內(nèi)部蘊藏的關鍵信息具有較大的難度，需要借助大數(shù)據(jù)框架和云計算工具［4-5］。大數(shù)據(jù)分類是數(shù)據(jù)挖掘處理的基礎步驟與核心任務之一，數(shù)據(jù)分類的精度將影響到最終的大數(shù)據(jù)處理效果。在當前商品經(jīng)濟的社會背景下，大數(shù)據(jù)分類還具有更多的商業(yè)價值和產(chǎn)業(yè)附加值。因此，大數(shù)據(jù)分類處理還需要面對各行各業(yè)中的數(shù)據(jù)壟斷問題。區(qū)塊鏈技術作為一種分布式的數(shù)據(jù)存儲模式，能夠在數(shù)據(jù)分類中兼容數(shù)據(jù)加密，并有效解決行業(yè)中的數(shù)據(jù)壟斷問題，所以在區(qū)塊鏈框架下的數(shù)據(jù)分類具有更多的實踐意義和價值［6-7］。

區(qū)塊鏈技術體系框架下現(xiàn)有的大數(shù)據(jù)分類算法，主要以人工智能和機器學習為基礎。文獻［8］提出基于樸素貝葉斯模型的大數(shù)據(jù)分類方案，該算法在處理多分類樣本時具有較高效率，但算法的應用需要基于樣本分布獨立的假設條件，實用性較差；文獻［9］提出基于k-means 的數(shù)據(jù)分類算法，該算法的復雜度較低且容易實現(xiàn)，但在實際應用過程中k值的找尋較為困難，且在迭代過程中容易陷入局部最優(yōu)解，該算法的并行運算能力也較差；苗紅等［10］提出一種基于LDA-SVM 的大數(shù)據(jù)分類算法，作為一種二值分類器，LDA-SVM 算法擁有較快的分類速度，但當樣本規(guī)模擴大以后分類器的性能會快速衰減，導致總的數(shù)據(jù)訓練時間和測試時間延長，分類準確率不斷降低。本文根據(jù)區(qū)塊鏈框架的特征，并針對現(xiàn)有大數(shù)據(jù)分類算法的不足，提出基于優(yōu)化的決策樹模型分類算法，通過梯度提升的方式提升經(jīng)典決策樹模型的性能，獲取更好的數(shù)據(jù)分類效果。

1 區(qū)塊鏈框架下的大數(shù)據(jù)加密處理

在通信、金融、電商等領域，大數(shù)據(jù)具有明顯的碎片化分布特征。數(shù)據(jù)碎片化一方面增加了大數(shù)據(jù)分類處理的難度，另一方面碎片化數(shù)據(jù)中更容易隱藏具有惡意攻擊性數(shù)據(jù)，危及用戶的隱私安全。在區(qū)塊鏈框架下對數(shù)據(jù)明文采用同態(tài)加密的方式處理，并將密鑰分別存儲于各利益相關者數(shù)據(jù)節(jié)點，同時將信息同步到云端服務器，在聯(lián)盟供應鏈網(wǎng)絡中選取記賬節(jié)點，使每個節(jié)點都有屬于自己的ID、公鑰與私鑰。區(qū)塊鏈框架下不僅可以實現(xiàn)數(shù)據(jù)的加密功能，節(jié)點之間還能夠互相監(jiān)督，避免出現(xiàn)行業(yè)數(shù)據(jù)壟斷的現(xiàn)象，區(qū)塊鏈架構下的大數(shù)據(jù)加密過程如圖1所示。

區(qū)塊鏈采用一種分布式方式和密碼學技術原理，將不同的服務器連接起來，每一個區(qū)塊記錄不同的對應信息。分布式記賬方式有效地去除了過度依賴特定服務器的弊端，去中心化的思想可以有效避免出現(xiàn)行業(yè)數(shù)據(jù)壟斷的現(xiàn)象。區(qū)塊鏈的賬本中存儲了全部企業(yè)的相關信息、下載地址及數(shù)據(jù)共享的路徑，使用哈希函數(shù)和哈希值加密數(shù)據(jù)的完整性。在數(shù)據(jù)存儲方面，云端存儲是主流的存儲方式，具有安全性和容量大的雙重優(yōu)勢，云存儲降低了用戶數(shù)據(jù)存儲成本，保護更多普通用戶數(shù)據(jù)的安全和隱私。由于采用了分布式的記賬方式，區(qū)塊鏈中的每個個體都被視為一個節(jié)點，節(jié)點分布式排布能夠起到相互監(jiān)督的作用。此外，去中心化的方式也使整個系統(tǒng)框架具有更強的分類計算能力。

2 決策樹模型的構建及優(yōu)化

在大數(shù)據(jù)分類計算過程中，如何在全局尋優(yōu)的基礎上兼顧數(shù)據(jù)分類效率、分類精度，是需要解決的核心問題。決策樹算法是人工智能和機器學習最基礎、最有效的算法之一。決策樹算法先通過對無規(guī)則、無次序樣本數(shù)據(jù)的訓練和規(guī)則挖掘，構建數(shù)學分析模型，并得到基礎的分類規(guī)則，再對目標數(shù)據(jù)集做預測分類。區(qū)塊鏈框架下可以根據(jù)節(jié)點的分布特征，構建多個決策樹模型同步分類以提高數(shù)據(jù)分類處理的效率。決策樹模型的構建首先要生成候選分裂點，并選擇每個節(jié)點的最佳分裂時機；其次，以最佳分裂點為基礎進行大數(shù)據(jù)分類；最后，通過不斷迭代更新分類模型的性能。節(jié)點的分裂以大數(shù)據(jù)樣本屬性的信息熵和信息增益率為基礎，節(jié)點分裂及決策樹模型的構建過程如圖2所示。

圖2 決策樹模型構建過程

待分類的大數(shù)據(jù)集訓練樣本總數(shù)為M，與區(qū)塊鏈創(chuàng)建的節(jié)點數(shù)量一致，訓練集的類別總數(shù)為S，各樣本集記作M1、M2、…、Ms。設訓練集中所包含的任意一個屬性為τ，該屬性包含p個屬性值，記作τ1、τ2、…、τp，與屬性值為τi對應的樣本數(shù)量為，屬性取值為j的樣本數(shù)量為，i的取值區(qū)間為[1,p]。區(qū)塊鏈框架下大數(shù)據(jù)集中的訓練樣本集的信息熵H(P)可以表示為

將屬性τ融入特征數(shù)據(jù)集：

融入特征屬性τ之后，信息增益率κ(τ,P)表示為

分類屬性的選擇問題是決定決策樹模型效率的核心要素，如果在利用信息熵和信息增益效率構建模型過程中出現(xiàn)了屬性缺失的情況，會直接增加分類的錯誤率，決策樹算法原有的泛化能力強的優(yōu)勢也無法充分發(fā)揮出來。為保證在局部節(jié)點分裂受阻的情況下不影響其他節(jié)點的分裂工作，對經(jīng)典的決策樹算法進行優(yōu)化，在區(qū)塊鏈體系內(nèi)預留出用于緩沖的空節(jié)點。如果在當前的決策樹模型中，可以用于分裂的節(jié)點屬性個數(shù)為k，那么優(yōu)化后的當前節(jié)點可以分裂為k+1個子節(jié)點。當屬性缺失時，該子節(jié)點可以基于已知屬性進入空節(jié)點，避免分裂終止的情況發(fā)生。算法改進后的部分偽代碼如下所示：

信息熵放大了系統(tǒng)的混淆層尺度，而信息增益值可用于度量信息熵在概率分布上的差異。在區(qū)塊鏈框架體系下，采用分布式的計算方式能夠進一步提升決策樹模型的分類能力。由于區(qū)塊鏈體系內(nèi)預留出了用于分裂緩沖的空節(jié)點，在分類過程中應先計算每個信息特征值節(jié)點的增益值，并將信息增益值做排序處理。決策樹的深度dj及非子葉節(jié)點數(shù)IN，都依據(jù)待分類數(shù)據(jù)的規(guī)模指定，兩者之間的關系表示為

由于預留了至少一個備選節(jié)點，即使在信息增益中出現(xiàn)了個別特征缺失的情況，也能夠避免節(jié)點分裂停止的情況發(fā)生。

3 基于優(yōu)化決策樹模型大數(shù)據(jù)分類的實現(xiàn)

區(qū)塊鏈框架體系下按照預設好的樹形結構訓練數(shù)據(jù)集，經(jīng)過優(yōu)化后的決策樹模型在分裂處理樣本目標值、預測值時，可以采用批量處理的方式，分類計算過程中的損失函數(shù)模型L(H,κ)表示為

在類似于優(yōu)化決策樹分類模型的后饋網(wǎng)絡學習系統(tǒng)中，每一次分裂僅會修改一個葉子節(jié)點權重，此時第t顆樹的分類損失函數(shù)Lt表示為

其中，τp 表示優(yōu)化決策樹分類模型第t棵樹之外的決策樹，模型通過不斷更新信息熵H(P)的值來確保損失函數(shù)保持最小化趨勢。數(shù)據(jù)訓練中要獲得更準確的數(shù)據(jù)分類效果，需要計算損失函數(shù)Lt的偏導數(shù)，計算結果表示為

式中，λ是損失函數(shù)Lt的一階導數(shù)。

從第t棵樹到第t+1 棵樹的分裂和更新過程，描述如下：

式中，χ是優(yōu)化決策樹模型的學習率。

當均方根誤差最小時，λ的推倒過程可以描述為

式中，yt是分類結果輸出的累加值。

從決策樹整體最優(yōu)化的角度來考慮，樣本分類輸出目標值的擬合程度越高，大數(shù)據(jù)的分類效果越好。由于區(qū)塊鏈框架下每個節(jié)點都單獨匹配一組服務器，所以優(yōu)化決策樹算法還要考慮到復合樣本的情況，即將優(yōu)化決策樹模型從一個節(jié)點復制到整個區(qū)塊鏈體系。這樣，一方面能夠發(fā)揮出區(qū)塊鏈框架體系并行計算的優(yōu)勢，同時數(shù)據(jù)分類過程中各節(jié)點之間互相監(jiān)督，避免出現(xiàn)數(shù)據(jù)壟斷的現(xiàn)象。對于任意一個區(qū)塊在更新葉子節(jié)點時，依據(jù)被劃分到上一級葉子節(jié)點的樣本索引，訓練和更新本批次梯度，損失函數(shù)的更新過程可以描述為

在不斷地迭代更新中，以批次訓練的方式更新決策樹結構的網(wǎng)絡權重值，引入網(wǎng)絡化的分層運算方式，并用全部樣本的平均梯度更新子節(jié)點權重比例，就能夠在整個區(qū)塊鏈范圍內(nèi)大規(guī)模地分類處理原始數(shù)據(jù)集，提升了整個算法的效率，全局的訓練過程步驟如下：

step1：輸入樣本集并設定迭代次數(shù)，初始化模型框架并以區(qū)塊鏈的節(jié)點為基礎劃分數(shù)據(jù)的批次。

step2：統(tǒng)計原始數(shù)據(jù)中特征元素的個數(shù)、長度等基礎信息，形成訓練樣本。

step3：計算損失函數(shù)值及決策樹函數(shù)模型的梯度值，并預測下一層次的葉子節(jié)點，優(yōu)化后的決策樹模型已經(jīng)預留出了用于緩沖的空節(jié)點，避免了節(jié)點分裂情況的發(fā)生。

step4：最后更新網(wǎng)絡權重值，在區(qū)塊鏈全局范圍內(nèi)更新分類數(shù)據(jù)。

在優(yōu)化決策樹模型訓練過程中，確保目標函數(shù)值始終處于最優(yōu)狀態(tài)，并保證損失函數(shù)降到最低，這樣既能保證葉子節(jié)點之間相互獨立，也能夠確保模型函數(shù)具有良好的收斂性能。

4 實驗與仿真

為了驗證所提出的基于優(yōu)化決策樹模型在大數(shù)據(jù)分類方面的效果，在實驗室環(huán)境下，模擬區(qū)塊鏈工作情況構建了一個擁有10 個節(jié)點的Hadoop集群。各節(jié)點硬件配備intel core i7處理器，工作主頻為3.6 GHz，各節(jié)點主機配備16 G 運行內(nèi)存和2 TB 的固態(tài)閃存存儲器。軟件系統(tǒng)部分運行win‐dow10 專業(yè)版系統(tǒng)和Hadoop2.6.5 版本。Hadoop集群中包含9 個slave 節(jié)點和1 個master節(jié)點：slave節(jié)點負責對每個區(qū)塊的數(shù)據(jù)進行采集、歸類和存儲；master 節(jié)點負責對整個區(qū)塊鏈網(wǎng)絡進行數(shù)據(jù)綜合管理和調(diào)度。首先驗證算法的數(shù)據(jù)分類處理能力，具體考核指標包括數(shù)據(jù)的吞吐能力和并行計算能力。經(jīng)過優(yōu)化的決策樹算法能夠連續(xù)地選擇最佳的分裂節(jié)點，并保持算法對輸入大數(shù)據(jù)的分類性能。

實驗中以相對復雜的Nursery 數(shù)據(jù)集和Mush‐room 數(shù)據(jù)集為研究對象，對比文中提出的優(yōu)化決策樹算法及文獻［8］、文獻［9］和文獻［10］3 種傳統(tǒng)算法在數(shù)據(jù)吞吐量方面的差異，數(shù)據(jù)統(tǒng)計結果如圖3和圖4所示。

圖3 Nursery數(shù)據(jù)集各算法數(shù)據(jù)吞吐量變化

圖4 Mushroom數(shù)據(jù)集各算法數(shù)據(jù)吞吐量變化

數(shù)據(jù)仿真結果顯示，無論是針對Nursery 數(shù)據(jù)集還是Mushroom 數(shù)據(jù)集，文中算法經(jīng)過優(yōu)化后的數(shù)據(jù)吞吐量在統(tǒng)計執(zhí)行時間點上都要優(yōu)于3 種傳統(tǒng)分類算法。數(shù)據(jù)吞吐量是驗證分類算法絕對性能的重要指標，統(tǒng)計結果表明，經(jīng)過優(yōu)化后的決策樹模型具有更強的算法連續(xù)性、泛化能力和全局迭代尋優(yōu)能力。

在區(qū)塊鏈框架下，由于各節(jié)點都采取了分布式的網(wǎng)絡結構設計，算法的并行計算能力會影響到大數(shù)據(jù)分類的總體效率。仍以Nursery 數(shù)據(jù)集和Mush‐room數(shù)據(jù)集為研究對象，判斷各算法隨線程數(shù)增加并行度的變化情況，仿真結果如圖5和圖6所示。

圖6 Mushroom數(shù)據(jù)集并行計算能力結果統(tǒng)計

數(shù)據(jù)統(tǒng)計結果顯示，當數(shù)據(jù)并行度發(fā)生改變時，文中算法的線程數(shù)波動要更小、更為穩(wěn)定，這表明提出的優(yōu)化決策樹算法具有更強的數(shù)據(jù)并行計算能力，在區(qū)塊鏈框架體系內(nèi)能夠幫助各節(jié)點完成區(qū)塊范圍內(nèi)大數(shù)據(jù)的分類處理。

最后驗證各分類算法在區(qū)塊鏈框架體系內(nèi)，針對大數(shù)據(jù)分類的準確率，在Nursery 數(shù)據(jù)集和Mushroom 數(shù)據(jù)集的基礎上擴充測試樣本集，引入MINST、CIFAR10、Oxford-IIIT Pet、Food-101、Wiki‐text-2、Amazon reviews、DBPedia ontology、Yelp re‐views 等不同類別的故障數(shù)據(jù)集，驗證在多種不同數(shù)據(jù)集條件下各算法的性能。準確率指標Acc的計算公式為

最終的統(tǒng)計分析結果如表1所示。

表1 各算法的大數(shù)據(jù)分類準確率對比 %

表1 （續(xù)）

針對不同的大數(shù)據(jù)集，3種傳統(tǒng)算法在分類準確率上出現(xiàn)明顯波動：文獻［9］算法在Oxford-IIIT Pet數(shù)據(jù)集上的分類準確率可達到91.26%，但在Wiki‐text-2數(shù)據(jù)集上的分類準確率僅為74.85%。從對各大數(shù)據(jù)集分類的平均值來看，文中算法達到了97.75%，3種傳統(tǒng)算法的平均準確率均未達到85%。

5 結論

區(qū)塊鏈框架的優(yōu)勢在于采用了分布式、去中心化的結構設計，避免在大數(shù)據(jù)分類中發(fā)生數(shù)據(jù)壟斷情況。本文在區(qū)塊鏈框架下對經(jīng)典的決策樹模型進行優(yōu)化，提升了節(jié)點分裂性能，仿真實驗結果也表明提出算法具有更高的數(shù)據(jù)分類準確率，相對于傳統(tǒng)大數(shù)據(jù)分類算法優(yōu)勢較為明顯。