基于Tree-3決策樹模型的大數(shù)據(jù)挖掘算法

褚福洋 馬文輝 張文晶 閆繼偉

（齊齊哈爾醫(yī)學(xué)院，黑龍江 齊齊哈爾 161006）

大數(shù)據(jù)時代為人們提供了信息量十分龐大的數(shù)據(jù)集合，為人們找到更有用、更有效的信息提供了可能[1]。但是，如何從海量數(shù)據(jù)中檢索自己所需要的有價值的信息也成為一項技術(shù)難題。數(shù)據(jù)挖掘算法就是解決該問題的有效技術(shù)途徑[2]。數(shù)據(jù)挖掘算法具備對數(shù)據(jù)進(jìn)行整理、歸類、分析和提取等作用，其實質(zhì)是在機器學(xué)習(xí)的基礎(chǔ)上進(jìn)行聚類、關(guān)聯(lián)分析的方法[3]。基于決策樹的數(shù)據(jù)挖掘方法在數(shù)據(jù)挖掘領(lǐng)域具有十分重要的地位。其中，Tree-3 決策樹模型在這類方法中具有重要意義。該文在Tree-3 決策樹模型下，針對其存在的不足進(jìn)行改進(jìn)，構(gòu)建更適合大數(shù)據(jù)挖掘的算法。

1 Tree-3決策樹模型及其挖掘算法流程

Tree-3 決策樹模型在各種決策樹挖掘算法模型中是最經(jīng)典的一種模型。在常規(guī)的決策樹的構(gòu)建過程中，Tree-3 決策樹模型使用了一種新的名為信息熵濃度增加-判定的機制，沿著決策樹路徑按節(jié)點進(jìn)行搜索，搜索依據(jù)就是信息熵濃度更高的節(jié)點被保留，當(dāng)搜索遍歷整個決策樹時，搜索過程被執(zhí)行完畢，所需的檢索結(jié)果被找出。

假定參數(shù)是 一個論域，并且對它隨機執(zhí)行一個劃分{M1，點，這個根節(jié)點的信息熵計算如公式（4）所示。M2，…，Mn}，可以得到的概率分布Pi=P（Mi），這樣M的信息熵計算如公式（1）所示。

在大數(shù)據(jù)挖掘的過程中，可以采用T和F表示符合要求和不符合要求的數(shù)據(jù)樣本，，據(jù)此可以得出有關(guān)2 類樣本分類的信息熵，如公式（3）所示。

在數(shù)據(jù)挖掘過程中，用戶特別要求的屬性A將成為根節(jié)

包括屬性A的根節(jié)點信息熵濃度的增加部分可以按照這樣的方式進(jìn)行計算，如公式（5）所示。

Tree-3 決策樹模型構(gòu)建的數(shù)據(jù)挖掘算法的目標(biāo)就是在整個決策樹中找到符合用戶屬性要求并且信息熵濃度增益最大的那個節(jié)點作為根節(jié)點?；赥ree-3 決策樹模型的數(shù)據(jù)挖掘算法流程如圖1 所示。

圖1 基于Tree-3 決策樹模型的數(shù)據(jù)挖掘算法流程

由圖1 可知，執(zhí)行的各個環(huán)節(jié)如下：1）根據(jù)用戶的檢索需求，在大數(shù)據(jù)全部樣本中確定符合要求的樣本集合和不符合要求的樣本集合。2）根據(jù)用戶的檢索需求，設(shè)定檢索過程中的關(guān)鍵屬性，關(guān)鍵屬性可能是1 個，也可能是多個，根據(jù)這些屬性構(gòu)建關(guān)鍵屬性集合，從而制定屬性信息熵濃度增加的計算規(guī)則。3）根據(jù)Tree-3 決策樹模型的信息熵濃度增加規(guī)則進(jìn)行計算，并由此構(gòu)建決策樹。4）每執(zhí)行1 個關(guān)鍵屬性元素進(jìn)行信息熵濃度增加計算就得到1 個決策樹，得到全部屬性決策樹后，比較各個決策樹的根節(jié)點信息熵濃度的大小，信息熵濃度最大的為最終勝出者，其檢索路徑和結(jié)果作為數(shù)據(jù)挖掘結(jié)果輸出。

2 基于Tree-3決策樹模型的改進(jìn)算法

基于Tree-3 決策樹模型構(gòu)建的數(shù)據(jù)挖掘算法原理簡單、執(zhí)行思路清晰且算法硬件計算量消耗小，對很多領(lǐng)域的數(shù)據(jù)挖掘都具有較高的適用性。但是，基于Tree-3決策樹模型構(gòu)建的數(shù)據(jù)挖掘算法在關(guān)鍵屬性確定出現(xiàn)偏差時，就會出現(xiàn)無法得到全局最佳結(jié)果的問題，即最終推送給用戶的挖掘結(jié)果可能是次優(yōu)的或者是局部最優(yōu)的結(jié)果。

因此，該文對基于Tree-3 決策樹模型建構(gòu)過程進(jìn)行改進(jìn)，以期得到準(zhǔn)確推送全局最優(yōu)挖掘結(jié)果的數(shù)據(jù)挖掘方法。Tree-3決策樹模型的挖掘依賴信息熵濃度增加的判定，并由此確定關(guān)鍵屬性。因此，要解決Tree-3 決策樹模型的問題，就需要改進(jìn)信息熵濃度的計算方法。而用戶的檢索要求可能涉及多個屬性，為了更準(zhǔn)確地確定關(guān)鍵屬性，該文結(jié)合各屬性概率特征，重新修定Tree-3 決策樹模型的信息熵計算過程。

如果一個屬性A包括m個子值，并且這些屬性子值的概率分別為p1、p2、…、pm，那么Tree-3 決策樹依托屬性A構(gòu)建就可以為包括m個子節(jié)點的集合{θ1，θ2，…，θm}，進(jìn)一步用G（θ1）、G（θ2）、…、G（θm）表示各屬性子值的信息熵，就可以計算屬性A的信息熵，如公式（6）所示。

基于Tree-3 決策樹模型的改進(jìn)算法的流程如下：1）如果用戶檢索要求的一個屬性為Ai，并且其包括mi個子值，那么子值屬性集合為{θ1，θ2，…，θm i}，集合中各元素對應(yīng)的概率為p1、p2、…、pm i，那么可以得到集合中一個子值的信息熵，如公式（7）所示。2）根據(jù)公式（6）并結(jié)合全部子值信息熵計算Ai的信息熵。3）重復(fù)上面2 個步驟，得到用戶檢索要求的全部屬性的信息熵，并以信息熵濃度增加最大的屬性為該節(jié)點的屬性。4）根據(jù)前3 個環(huán)節(jié)遍歷決策樹所有節(jié)點，確定各個節(jié)點的屬性，并得到每個節(jié)點的屬性信息熵增益濃度。5）將信息熵濃度最大的節(jié)點確定為根節(jié)點，并將其輸出作為挖掘結(jié)果。

3 基于Tree-3決策樹模型的改進(jìn)算法的數(shù)據(jù)挖掘試驗

3.1 大數(shù)據(jù)集合的選取

在大數(shù)據(jù)挖掘算法的驗證試驗中，領(lǐng)域內(nèi)的常規(guī)做法是用國際公認(rèn)的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行挖掘算法驗證試驗，這樣便于形成橫向比對。該文從國際通用的UCI 數(shù)據(jù)集合中選擇6 個數(shù)據(jù)子集進(jìn)行挖掘試驗。這6 類數(shù)據(jù)子集分布領(lǐng)域如圖2 所示。

圖2 6 類數(shù)據(jù)子集的分布領(lǐng)域

3.1.1 UCI-Wine 數(shù)據(jù)子集

在UCI-Wine 數(shù)據(jù)子集中，全部是有關(guān)白酒行業(yè)的各種數(shù)據(jù)，包括白酒的各種關(guān)鍵參數(shù)。在UCI-Wine 數(shù)據(jù)子集中，納入了全球180 多 個知名品牌的白酒，涉及的關(guān)鍵參數(shù)包括這些品牌白酒中的酒精參數(shù)、果酸參數(shù)以及黃酮參數(shù)等信息。

3.1.2 UCI-Heart 數(shù)據(jù)子集

UCI-Heart 數(shù)據(jù)子集全部是心臟掃描圖像的各種數(shù)據(jù)，包括心臟是否患病的判斷規(guī)則參數(shù)。在UCI-Heart 數(shù)據(jù)子集中，涉及270 多 個心臟類疾病的檢索樣本，涉及的關(guān)鍵參數(shù)包括對應(yīng)疾病的各種體質(zhì)性指標(biāo)。

3.1.3 UCI-Balance 數(shù)據(jù)子集

UCI-Balance 數(shù)據(jù)子集全部是心理學(xué)意義上的心態(tài)是否平衡的樣本數(shù)據(jù)，包括630 多 個各種可能情況下被測人員可能發(fā)生心理失衡的樣本，這些樣本中也涉及被測人員心理學(xué)意義上的各種指標(biāo)。

3.1.4 UCI-Vehicle 數(shù)據(jù)子集

UCI-Vehicle 數(shù)據(jù)子集全部是有關(guān)汽車行業(yè)的各類數(shù)據(jù)，包括汽車的各種關(guān)鍵參數(shù)。在UCI-Vehicle 數(shù)據(jù)子集中，納入了全球820 多 個知名品牌的汽車，涉及的關(guān)鍵參數(shù)包括這些品牌汽車中的發(fā)動機參數(shù)、排放參數(shù)以及穩(wěn)定性參數(shù)等。

3.1.5 UCI-Valley 數(shù)據(jù)子集

UCI-Valley 數(shù)據(jù)子集全部是多頂點曲線連接的相關(guān)數(shù)據(jù)，包括頂點信息和連線信息。在UCI-Valley 數(shù)據(jù)子集中，納入了1 200 多 個樣本，為多頂點曲線連接集合形狀的分類判別提供了依據(jù)。

3.1.6 UCI-Yeast 數(shù)據(jù)子集

UCI-Yeast 數(shù)據(jù)子集全部是細(xì)胞內(nèi)蛋白質(zhì)含量的各種數(shù)據(jù)，包括細(xì)胞是否正常的判斷規(guī)則參數(shù)。在UCI-Yeast 數(shù)據(jù)子集中，涉及1 500 多 個細(xì)胞類疾病的檢索樣本，涉及的關(guān)鍵參數(shù)包括對應(yīng)疾病的各種體質(zhì)性指標(biāo)。

上述6 個數(shù)據(jù)子集在樣本數(shù)量、屬性各屬以及分類類別等各方面的基本情況對比見表1。

表1 數(shù)據(jù)挖掘試驗中6 個數(shù)據(jù)子集的基本情況

3.2 Tree-3決策樹模型及其改進(jìn)方法的挖掘結(jié)果對比

根據(jù)表1 中提供的6 個數(shù)據(jù)集合，該文分別采用Tree-3決策樹模型數(shù)據(jù)挖掘方法、基于Tree-3 決策樹模型的改進(jìn)數(shù)據(jù)挖掘方法進(jìn)行試驗，從而得到2 種挖掘方法得到的決策樹的節(jié)點與最終的挖掘精度方面的對比，結(jié)果見表2。

表2 Tree-3 決策樹模型及其改進(jìn)方法的試驗結(jié)果對比

由表2 可知，2 種方法得到的決策樹節(jié)點總數(shù)柱狀圖對例如圖3 所示。

圖3 Tree-3 決策樹模型及其改進(jìn)方法的決策樹節(jié)點總數(shù)對比

在圖3 中，2 個顏色的柱狀圖分別表示基于Tree-3 決策樹模型的大數(shù)據(jù)挖掘算法和該文提出的基于Tree-3 決策樹模型的改進(jìn)大數(shù)據(jù)挖掘算法。6 組試驗結(jié)果的柱狀圖逐次降低，這也體現(xiàn)了6 個數(shù)據(jù)集的復(fù)雜程度的改變。其中，第一組數(shù)據(jù)集構(gòu)建的決策樹節(jié)點為338 個，對應(yīng)的改進(jìn)算法構(gòu)建的決策樹節(jié)點為249 個。到了最后一組數(shù)據(jù)集，決策樹節(jié)點為57 個，而對應(yīng)的改進(jìn)算法構(gòu)建的決策樹節(jié)點為34 個。根據(jù)對比可以明顯看出，經(jīng)過該文的改進(jìn)處理，Tree-3 決策樹模型的結(jié)構(gòu)更精簡。而從挖掘精度上來看，如果決策樹的模型復(fù)雜，那么Tree-3 決策樹模型的挖掘精度就會明顯降低。而該文改進(jìn)的Tree-3 決策樹模型的挖掘精度不會隨著決策樹模型的結(jié)構(gòu)出現(xiàn)明顯的改變。由圖3 可知，對6 個UCI 數(shù)據(jù)子集來說，該文提出的改進(jìn)方法比原有的Tree-3 決策樹模型挖掘方法所構(gòu)建的決策樹的節(jié)點更少，結(jié)構(gòu)更精簡。

根據(jù)表2 中的試驗結(jié)果可知，2 種方法得到的挖掘精度節(jié)曲線圖對例如圖4 所示。

從圖4 可以看出，對6 個UCI 數(shù)據(jù)子集來說，該文提出的改進(jìn)方法比原有的Tree-3 決策樹模型挖掘方法的數(shù)據(jù)挖掘精度更高，可以為用戶提供更準(zhǔn)確的挖掘結(jié)果。

圖4 Tree-3 決策樹模型及其改進(jìn)方法的挖掘精度對比

4 結(jié)語

大數(shù)據(jù)時代在為用戶提供便利的同時，也帶來了數(shù)據(jù)檢索速度慢、檢索準(zhǔn)確率低的問題。因此，該文在Tree-3 決策樹模型的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種新的數(shù)據(jù)挖掘算法。首先，給出了Tree-3 決策樹模型的建構(gòu)方法。其次，針對Tree-3 決策樹模型有時無法給出全局最優(yōu)結(jié)果的問題，提出了信息熵改進(jìn)計算方案，并給出了改進(jìn)方法的具體流程。最后，對6 個UCI 數(shù)據(jù)子集進(jìn)行挖掘試驗，該文提出的改進(jìn)方法可以得到更精簡的決策樹，還可以得到更高的挖掘精度。