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

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

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

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

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

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

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

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

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

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

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

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

2 基于Tree-3決策樹模型的改進算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Tree-3決策樹模型及其改進方法的挖掘結果對比

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

表2 Tree-3 決策樹模型及其改進方法的試驗結果對比

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

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

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

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

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

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

4 結語

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