戴龍平+戴莉萍+劉麗珍

摘要：決策樹算法的實現(xiàn)往往采用面向?qū)ο笳Z言工具來實現(xiàn)，與數(shù)據(jù)庫中的結(jié)構(gòu)通常存在一定的差異，需要進行大量的數(shù)據(jù)轉(zhuǎn)換?，F(xiàn)在充分利用數(shù)據(jù)庫中表結(jié)構(gòu)特點和存儲過程中PL/SQL語法的強大性及靈活性，采用一個動力計量計費系統(tǒng)中的數(shù)據(jù)，快速、有效且非遞歸地實現(xiàn)了決策樹C4.5算法中的節(jié)點生成、擴展與剪枝主要過程；并進行了規(guī)則抽取。應用結(jié)果表明，該算法的實現(xiàn)方法具有一定的高效性、穩(wěn)定性和普適性。

關鍵詞： C4.5算法； 信息增益； 存儲過程； 動力計量計費系統(tǒng)

中圖分類號： TN919?34； TP391.77 文獻標識碼： A 文章編號： 1004?373X（2014）08?0091?04

Application of nonrecursive decision tree in power metrology?billing system

DAI Long?ping1, DAI Li?ping2, LIU Li?zhen3

（1. Jiangxi Branch, China Unicom, Nanchang 330096, China; 2. Software School, Jiangxi Normal University, Nanchang 330022, China;

3. Jiangxi Hongdu Aviation Industry Group Co., Ltd., AVIC, Nanchang 330024, China）

Abstract： The oriented?object program?developing tools are usually used to implement the algorithms of decision tree. Since the data structures in the programming languages are different from these in a database， massive data conversion is needed. With the data from a power metrology?billing system， the critical steps of node generation， node extension and pruning in C4.5 algorithm of decision tree can be implemented quickly， efficiently and non?recursively by making full use of the features of table object and the flexibility of PL/SQL in stored procedure， and the corresponding rules can be abstracted easily. Experimental results demonstrate that this method is effective， stable and adaptable.

Keyword： C4.5 Algorithm； information gain； stored procedure； power metrology?billing system

0引 言

決策樹是用于分類和預測的主要技術(shù)，它著眼于從一組無規(guī)律的事例中推理出決策樹表示形式的分類規(guī)則，采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點進行屬性值的比較，并根據(jù)不同屬性判斷從該節(jié)點向下分支，在決策樹的葉節(jié)點得到結(jié)論。決策樹的主要優(yōu)點包括易于用戶理解，只要訓練事例能夠用屬性的方式表達出來，就可以使用其進行學習；并且易于轉(zhuǎn)換為規(guī)則，從根節(jié)點到葉節(jié)點就對應著一條合理規(guī)則，整棵樹就對應著一組表達式規(guī)則。而且許多實驗及應用也說明了其良好的有效性[1?2]。近年來，決策樹方法在機器學習、知識發(fā)現(xiàn)等領域得到了廣泛的應用。

在決策樹方法中，有2個基本步驟：構(gòu)造樹并將樹應用于數(shù)據(jù)庫。一般情況下，決策樹的構(gòu)造基本使用面向?qū)ο蟮母呒壵Z言完成，再調(diào)用數(shù)據(jù)庫中的數(shù)據(jù)。這樣的做法往往使得數(shù)據(jù)結(jié)構(gòu)多樣、算法處理復雜、實現(xiàn)難度加大等。而隨著現(xiàn)代數(shù)據(jù)庫技術(shù)的發(fā)展，其語言支持功能愈發(fā)強大，例如PL/SQL和存儲過程。存儲過程是一種子程序，實際存放在數(shù)據(jù)庫的數(shù)據(jù)字典中，應用程序可通過它來訪問關系型數(shù)據(jù)庫系統(tǒng)。存儲過程的典型應用有結(jié)合數(shù)據(jù)庫的數(shù)據(jù)有效性驗證和訪問控制機制。而且，存儲過程可以統(tǒng)一并加強原本只在應用程序中實現(xiàn)的復雜邏輯過程，從而應用程序可以調(diào)用該存儲過程[3?4]。而且存儲過程可以接受參數(shù)并回傳值，靈活性和運行效率都有所提高。

因此本文中將這兩個步驟全部放在SQL Server數(shù)據(jù)庫中完成，利用存儲過程完成了C4.5算法的快速實現(xiàn)，并把其應用在一個動力計量計費系統(tǒng)中。

1C4.5算法基本原理

C4.5是Ross Quinlan為改進ID3算法而提出來的一種決策樹生成算法。它根據(jù)給定的樣本集，以樹的形式給出分類規(guī)則。其生成過程如下[5?6]。

假設類別表示為{C1，C2，…，Ck}，T表示為訓練集。針對決策樹給定節(jié)點中T的內(nèi)容，在構(gòu)造決策樹時一般會有以下3種可能的情況：

（1） 當T包含的一個或多個樣本都屬于某個類別Cj，那么針對T的決策樹則是指向類別Cj的葉節(jié)點；

（2） 當T不包含任何樣本時，此時決策樹仍是葉節(jié)點，但與此節(jié)點關聯(lián)的類別則是其父節(jié)點中出現(xiàn)頻率最高的類別；

（3） 當T包含的樣本屬于不同的類別時，提出相應的設定，即基于單個屬性確定一個結(jié)果集{O1，O2，…，On}，T被分成若干個子集{T1，T2，…，Tn}，其中Ti包含了產(chǎn)生Oi的所有樣本。此時決策樹包含了一個指向該設定的決策點，該決策點的每條分支對應到每個可能的結(jié)果。

對于每個子節(jié)點都可以繼續(xù)進行判斷，重復上述操作，直到滿足決策樹的終止條件為止，這個終止條件可以是：節(jié)點對應的所有樣本屬于同一類；或者不存在可以再分割的屬性。

以下是決策樹生成算法的一般描述。其中T為訓練集，A為條件屬性集，Y為目標屬性，最終生成Tree。

Function Tree=Decision_Tree_Create（T，A，Y）

{

If 訓練集為空，則返回值為Failure的單個節(jié)點Tree；

If訓練集是由相同類別屬性值的記錄所組成，則返回一個帶有該值的單個節(jié)點Tree；

If 沒有可分的屬性，則返回單個節(jié)點Tree，其值在訓練集的記錄中找出頻率最高的類別屬性值；

//對于A中屬性，基于信息理論進行特征選擇，從而確定最佳的分裂特性。其中X為分類屬性，Values為分裂點；

（X，Values）=Attribute_Selection（T，A，Y）；

//根據(jù)分裂特性進行樣本集的劃分，生成相應的子節(jié)點，并對一直遞歸下去，最終形成一個分支并將其加入到Tree中；

for each V in Values do

subT=滿足X的測試條件V的樣本子集；

Node=Decision_Tree_Create（subT，A?{X}，Y）

Create_Branch（Tree， Node）；

end for

返回Tree；

}

其中節(jié)點如何進行分裂是決策樹生成過程中的重要步驟。只有根據(jù)不同的屬性將節(jié)點分開，方能形成多個類別。因此，整個問題的核心就是如何選擇分裂的屬性。通常的做法是測試所有的屬性，對每個屬性分類的好壞做出相應的量化評價，選擇其中一個最好的分類方式。特征選擇策略提供了這種量化的指標，這主要依賴于對集合不純度的度量方法，信息增益就是其中一種，它衡量每個屬性對分類后的數(shù)據(jù)子集的信息量的貢獻[7]。

假設訓練集T包含n個樣本，這些樣本分別屬于m個類，其中第i個類在T中出現(xiàn)的比例為pi，那么T的信息熵為[3，8]：

[I(T)=i=1m-pilog2pi] （1）

如果m=1，也就是T的樣本都屬于一個類，那么I（T）=0，達到最小值；如果p1=p2=…=pm，也就是每類樣本的個數(shù)相同，那么I（T）=log m，達到最大值。

假設屬性A把集合T劃分成V個子集{T1，T2，…，Tv}，其中Ti所包含的樣本數(shù)為ni，那么劃分后的熵就是：

[E(A)=i=1vninI(Ti)] （2）

那么，分裂后的信息增益為Gain（A）=I（T）-E（A）。

2決策樹的節(jié)點生成

首先選取訓練樣本集，本文中使用的是某公司動力分廠中各種動力用量和費用作為數(shù)據(jù)集，如圖1所示。構(gòu)造決策樹的目的就是希望能夠知道一個時間段內(nèi)各個單位各種動力用量高低對于其最終動力費用的影響程度。為描述簡單，這里僅僅使用四種動力：綜合電ZHD、高峰電GFD、低谷電DGD和平峰電PFD來描述整個決策樹算法的快速實現(xiàn)與應用。

圖1 各個動力用量費用顯示

在構(gòu)造決策樹之前，已經(jīng)使用樸素Bayes算法將各個動力用量按照高、中、低進行了分類。而后為決策樹實現(xiàn)確定數(shù)據(jù)結(jié)構(gòu)，圖2是節(jié)點的主體結(jié)構(gòu)。

圖2 節(jié)點的主體結(jié)構(gòu)

其中Type表示的是某種電量如綜合電ZHD，H表示高，M表示中，L表示低。HH表示當ZHD用量分類為高時，總費用分類為高；HM表示當ZHD用量分類為高時，總費用為分類中，其他類推。NodeID是該節(jié)點編號，ParentID是其父節(jié)點編號，Ancestor保存了其祖輩信息。圖3是一個節(jié)點的具體實例。

圖3 節(jié)點表的數(shù)據(jù)顯示

以根節(jié)點為例說明一個節(jié)點的具體生成過程，算法描述如下：

輸入：訓練樣本集

輸出：節(jié)點表新增一條節(jié)點記錄

處理：主要使用T_DTVALUE表，該表中存放了確定分裂結(jié)點所需要的各種數(shù)值，例如動力類型、費用高中低各自的個數(shù)及總個數(shù)、信息量值、熵值以及信息增益值

（1） 生成屬性取值和類別分布：使用的存儲過程是PRC_CREDVALUE，傳遞一個字符串型的輸入?yún)?shù)，即動力類型的名稱，進而生成費用高中低的個數(shù)及其總個數(shù)，其T_DTVALUE中的部分數(shù)值如圖4所示。

EXEC PRC_CREDTVALUE ′ZHD′

EXEC PRC_CREDTVALUE ′GFD′

EXEC PRC_CREDTVALUE ′DGD′

EXEC PRC_CREDTVALUE ′PFD‘

圖4 屬性取值與類別分布

（2） 計算訓練樣本的信息量：變量@H、@M和@L分別是目標屬性高中低的樣本個數(shù)，變量@TOTAL是總個數(shù)，根據(jù)公式（1）得到信息量值，這里取小數(shù)點后4位。

SET @H=（SELECT TOP 1 SUM（ZFYHIGH） FROM T_DTVALUE GROUP BY TYPE）

SET @M=（SELECT TOP 1 SUM（ZFYMIDDLE） FROM T_DTVALUE GROUP BY TYPE）

SET @L=（SELECT TOP 1 SUM（ZFYLOW） FROM T_DTVALUE GROUP BY TYPE）

SET @TOTAL=@H+@M+@L

SET @IT=?@H/@TOTAL*LOG（@H/@TOTAL）?@M/@TOTAL*LOG（@M/@TOTAL）?@L/@TOTAL*LOG（@L/@TOTAL）

（3） 計算每個屬性的信息增益：根據(jù)式（1），（2），編寫存儲過程PRC_ ComputeEntropy，通過輸入?yún)?shù)靈活求取各個動力類型的熵值。即先求取每個屬性值的各個樣本子集的信息量，而后信息量之和就是熵值，再用訓練樣本的信息量減去熵值得到信息增益。表T_DTVALUE中的信息增益值如圖5所示。

EXEC PRC_ComputeEntropy ′ZHD′

EXEC PRC_ComputeEntropy ′GFD′

EXEC PRC_ComputeEntropy ′DGD′

EXEC PRC_ComputeEntropy ′PFD′

UPDATE T_DTVALUE SET GAIN=@IT?ENTROPY

圖5 信息增益值

（4） 確定分裂結(jié)點，插入到結(jié)點表中：選取信息增益最大的屬性作為分裂的節(jié)點，因為這里使用的是倒序排列，因此取第1位；因為是根節(jié)點，因此無父節(jié)點，賦值為0；因為根節(jié)點的所有直接子節(jié)點沒有產(chǎn)生完畢，因此ISOK賦值為0。

SET @TYPE=（ SELECT TOP 1 TYPE FROM T_DTVALUE ORDER BY GAIN DESC）

INSERT INTO T_DTNODES （TYPE，PARENTID，ISOK） VALUES （@TYPE，0，0）

3決策樹節(jié)點擴展與剪枝

分裂節(jié)點確定之后，需要生成其下屬子節(jié)點。本文中采用了非遞歸式廣度優(yōu)先來生成決策樹，即產(chǎn)生一個節(jié)點所有的直接子節(jié)點，而后根據(jù)這些子節(jié)點的順序再依次產(chǎn)生其所有的直接子節(jié)點。為實現(xiàn)非遞歸方式，同時保證過程的靈活性，除了表結(jié)構(gòu)需要特別仔細的設計外，還大量地使用了MSSQL動態(tài)指令執(zhí)行語句：EXECUTE和SP_ExecuteSQL[9?10]。

為了使得到的決策樹所蘊含的規(guī)則具有普遍意義，必須對決策樹進行修剪。樹枝修剪的任務主要是刪除一個或更多的樹枝，并用葉替換這些樹枝，使決策樹簡化，以提高今后分類識別的速度和分類識別新數(shù)據(jù)的能力。通常采用兩種方法進行樹枝的修剪，即事前修剪和事后修剪。本文中采用了事前修剪，為每個節(jié)點擴展設置了一個閥值，一旦有結(jié)果超過閥值，該子樹就停止生長。本系統(tǒng)中根據(jù)經(jīng)驗值和生產(chǎn)要求設置當前閥值為80%，當綜合電用量為高時，總費用為高的比例超過80%，那就不需要進行子節(jié)點擴展了。這種剪枝方式比較簡單直接而且有效，但是難點就通常在于閥值的確定。

節(jié)點表中的HH，HM等字段的賦值表明該節(jié)點是否需要進行子節(jié)點擴展，例如HH為?1表示規(guī)則已經(jīng)產(chǎn)生；為0表示該節(jié)點不需要擴展；為?2表示繼續(xù)生長；為1時表示沒有這類情況出現(xiàn)。以根節(jié)點的子節(jié)點生成為例，描述節(jié)點擴展與剪枝的算法過程。

輸入：根節(jié)點結(jié)構(gòu)的初始值和訓練樣本集

輸出：根節(jié)點的擴展子節(jié)點

處理：當綜合電ZHD用量分類為高時

（1） 計算各種情況下的數(shù)值比例。例如下段代碼就是求取綜合電ZHD用量分類為高且總費用分類為高時的比例@HRATE。首先把賦值語句SELECT以字符串的形式賦給變量@STR，而后使用系統(tǒng)存儲過程SP_EXECUTESQL執(zhí)行該條語句，@FLAG的賦值為H，以獲取到各個計數(shù)值， @NODEID是當前擴展節(jié)點的編號。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，還需要計算總費用分類為中和低時的比例，即@MRATE和@LRATE。

（2） 回寫擴展標識以確定是否在后續(xù)過程中得到相應的處理。下段代碼是判斷綜合電ZHD用量分類為高時的子節(jié)點生成情況。這里利用到了CASE語句，把求取到的@HRATE，@MRATE和@LRATE和確定好的閥值做比較，來決定不同的結(jié)果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ?1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ?2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，還需要回寫當總費用分類為中和為低時的擴展標識。

4規(guī)則的生成

當決策樹生成之后，就可以從中推導出分類規(guī)則，這個步驟稱為規(guī)則抽取。每個葉節(jié)點表示為一條規(guī)則，規(guī)則的條件是從根節(jié)點出發(fā)到該葉節(jié)點路徑上的所有中間節(jié)點構(gòu)成的一個“與”判斷，規(guī)則的結(jié)論是葉節(jié)點的類別。在對新樣本進行分類時，如果樣本滿足某條分類規(guī)則的條件判斷，那么它的類別就是規(guī)則右邊的值。這部分算法比較簡單，大致的流程描述如下。

輸入：節(jié)點表T_DTNODES，主要使用到的字段就是節(jié)點編號nodeid，父節(jié)點編號parentid，ancestor是該節(jié)點的所有父輩節(jié)點的文字描述；部分數(shù)據(jù)如圖6所示。

輸出：規(guī)則表T_DTRULES，部分數(shù)據(jù)如圖7所示。

處理：由于在生成樹的過程中就較好地保存了各個節(jié)點相對應的祖父信息，因此只需要根據(jù)nodeid和parentid進行相應的遍歷，把這些信息轉(zhuǎn)換成對應的文字表示即可。規(guī)則生成比較簡單，主要在存儲過程中使用了游標，逐行處理。最后還要進行規(guī)則的適當調(diào)整。

圖6 節(jié)點表的父子信息

圖7 規(guī)則表

5結(jié)語

本文利用SQL Server數(shù)據(jù)庫中的表結(jié)構(gòu)和存儲過程實現(xiàn)了一個決策樹算法。其中數(shù)據(jù)結(jié)構(gòu)簡單，基本就是二維表，易于處理；全部算法過程放置在幾個存儲過程中，非遞歸式層層調(diào)用，增強了靈活性，易于理解；而且應用中由于對數(shù)據(jù)的訪問都是通過存儲過程來進行的，可以在不改動存儲過程接口的情況下對數(shù)據(jù)庫進行任何改動，使得更新對應用程序而言具有透明性，增強適應性和可維護性。在實際應用中，算法能夠正確運行，對于大量的數(shù)據(jù)具有較好的執(zhí)行能力，其規(guī)則也體現(xiàn)了一定的準確性。不過訓練數(shù)據(jù)由于受到人員錄入方式、樸素Bayes分類結(jié)果等因素的影響，使得閥值的確定難度加大，進而使得生成的決策樹會存在一定的偏差，希望在下一步的工作中調(diào)整。

參考文獻

[1] 馮少榮.決策樹算法的研究與改進[J].廈門大學學報：自然科學版，2007，46（4）：496?500.

[2] DUNHAM M H.數(shù)據(jù)挖掘教程[M].郭崇慧，田鳳占，靳曉明，等譯.北京：清華大學出版社，2005.

[3] 徐人鳳，曾建華.SQL Server 2005數(shù)據(jù)庫及應用[M].北京：高等教育出版社，2007.

[4] 王珊.數(shù)據(jù)庫系統(tǒng)概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數(shù)據(jù)挖掘技術(shù)及應用[M].北京：科學出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測評中的應用[J].濟南大學學報：自然科學版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認定中的應用[J].河南教育學院學報：自然科學版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學生心理健康評測中的應用[J].計算機應用與軟件，2011，28（10）：240?244.

[9] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數(shù)據(jù)挖掘[J].計算機工程，2010，36（1）：40?42.

[10] 姚亞夫，邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進及其應用[J].中南大學學報：自然科學版，2011，42（12）：3772?3776.

（1） 計算各種情況下的數(shù)值比例。例如下段代碼就是求取綜合電ZHD用量分類為高且總費用分類為高時的比例@HRATE。首先把賦值語句SELECT以字符串的形式賦給變量@STR，而后使用系統(tǒng)存儲過程SP_EXECUTESQL執(zhí)行該條語句，@FLAG的賦值為H，以獲取到各個計數(shù)值， @NODEID是當前擴展節(jié)點的編號。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，還需要計算總費用分類為中和低時的比例，即@MRATE和@LRATE。

（2） 回寫擴展標識以確定是否在后續(xù)過程中得到相應的處理。下段代碼是判斷綜合電ZHD用量分類為高時的子節(jié)點生成情況。這里利用到了CASE語句，把求取到的@HRATE，@MRATE和@LRATE和確定好的閥值做比較，來決定不同的結(jié)果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ?1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ?2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，還需要回寫當總費用分類為中和為低時的擴展標識。

4規(guī)則的生成

當決策樹生成之后，就可以從中推導出分類規(guī)則，這個步驟稱為規(guī)則抽取。每個葉節(jié)點表示為一條規(guī)則，規(guī)則的條件是從根節(jié)點出發(fā)到該葉節(jié)點路徑上的所有中間節(jié)點構(gòu)成的一個“與”判斷，規(guī)則的結(jié)論是葉節(jié)點的類別。在對新樣本進行分類時，如果樣本滿足某條分類規(guī)則的條件判斷，那么它的類別就是規(guī)則右邊的值。這部分算法比較簡單，大致的流程描述如下。

輸入：節(jié)點表T_DTNODES，主要使用到的字段就是節(jié)點編號nodeid，父節(jié)點編號parentid，ancestor是該節(jié)點的所有父輩節(jié)點的文字描述；部分數(shù)據(jù)如圖6所示。

輸出：規(guī)則表T_DTRULES，部分數(shù)據(jù)如圖7所示。

處理：由于在生成樹的過程中就較好地保存了各個節(jié)點相對應的祖父信息，因此只需要根據(jù)nodeid和parentid進行相應的遍歷，把這些信息轉(zhuǎn)換成對應的文字表示即可。規(guī)則生成比較簡單，主要在存儲過程中使用了游標，逐行處理。最后還要進行規(guī)則的適當調(diào)整。

圖6 節(jié)點表的父子信息

圖7 規(guī)則表

5結(jié)語

本文利用SQL Server數(shù)據(jù)庫中的表結(jié)構(gòu)和存儲過程實現(xiàn)了一個決策樹算法。其中數(shù)據(jù)結(jié)構(gòu)簡單，基本就是二維表，易于處理；全部算法過程放置在幾個存儲過程中，非遞歸式層層調(diào)用，增強了靈活性，易于理解；而且應用中由于對數(shù)據(jù)的訪問都是通過存儲過程來進行的，可以在不改動存儲過程接口的情況下對數(shù)據(jù)庫進行任何改動，使得更新對應用程序而言具有透明性，增強適應性和可維護性。在實際應用中，算法能夠正確運行，對于大量的數(shù)據(jù)具有較好的執(zhí)行能力，其規(guī)則也體現(xiàn)了一定的準確性。不過訓練數(shù)據(jù)由于受到人員錄入方式、樸素Bayes分類結(jié)果等因素的影響，使得閥值的確定難度加大，進而使得生成的決策樹會存在一定的偏差，希望在下一步的工作中調(diào)整。

參考文獻

[1] 馮少榮.決策樹算法的研究與改進[J].廈門大學學報：自然科學版，2007，46（4）：496?500.

[2] DUNHAM M H.數(shù)據(jù)挖掘教程[M].郭崇慧，田鳳占，靳曉明，等譯.北京：清華大學出版社，2005.

[3] 徐人鳳，曾建華.SQL Server 2005數(shù)據(jù)庫及應用[M].北京：高等教育出版社，2007.

[4] 王珊.數(shù)據(jù)庫系統(tǒng)概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數(shù)據(jù)挖掘技術(shù)及應用[M].北京：科學出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測評中的應用[J].濟南大學學報：自然科學版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認定中的應用[J].河南教育學院學報：自然科學版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學生心理健康評測中的應用[J].計算機應用與軟件，2011，28（10）：240?244.

[9] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數(shù)據(jù)挖掘[J].計算機工程，2010，36（1）：40?42.

[10] 姚亞夫，邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進及其應用[J].中南大學學報：自然科學版，2011，42（12）：3772?3776.

（1） 計算各種情況下的數(shù)值比例。例如下段代碼就是求取綜合電ZHD用量分類為高且總費用分類為高時的比例@HRATE。首先把賦值語句SELECT以字符串的形式賦給變量@STR，而后使用系統(tǒng)存儲過程SP_EXECUTESQL執(zhí)行該條語句，@FLAG的賦值為H，以獲取到各個計數(shù)值， @NODEID是當前擴展節(jié)點的編號。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，還需要計算總費用分類為中和低時的比例，即@MRATE和@LRATE。

（2） 回寫擴展標識以確定是否在后續(xù)過程中得到相應的處理。下段代碼是判斷綜合電ZHD用量分類為高時的子節(jié)點生成情況。這里利用到了CASE語句，把求取到的@HRATE，@MRATE和@LRATE和確定好的閥值做比較，來決定不同的結(jié)果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ?1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ?2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，還需要回寫當總費用分類為中和為低時的擴展標識。

4規(guī)則的生成

當決策樹生成之后，就可以從中推導出分類規(guī)則，這個步驟稱為規(guī)則抽取。每個葉節(jié)點表示為一條規(guī)則，規(guī)則的條件是從根節(jié)點出發(fā)到該葉節(jié)點路徑上的所有中間節(jié)點構(gòu)成的一個“與”判斷，規(guī)則的結(jié)論是葉節(jié)點的類別。在對新樣本進行分類時，如果樣本滿足某條分類規(guī)則的條件判斷，那么它的類別就是規(guī)則右邊的值。這部分算法比較簡單，大致的流程描述如下。

輸入：節(jié)點表T_DTNODES，主要使用到的字段就是節(jié)點編號nodeid，父節(jié)點編號parentid，ancestor是該節(jié)點的所有父輩節(jié)點的文字描述；部分數(shù)據(jù)如圖6所示。

輸出：規(guī)則表T_DTRULES，部分數(shù)據(jù)如圖7所示。

處理：由于在生成樹的過程中就較好地保存了各個節(jié)點相對應的祖父信息，因此只需要根據(jù)nodeid和parentid進行相應的遍歷，把這些信息轉(zhuǎn)換成對應的文字表示即可。規(guī)則生成比較簡單，主要在存儲過程中使用了游標，逐行處理。最后還要進行規(guī)則的適當調(diào)整。

圖6 節(jié)點表的父子信息

圖7 規(guī)則表

5結(jié)語

本文利用SQL Server數(shù)據(jù)庫中的表結(jié)構(gòu)和存儲過程實現(xiàn)了一個決策樹算法。其中數(shù)據(jù)結(jié)構(gòu)簡單，基本就是二維表，易于處理；全部算法過程放置在幾個存儲過程中，非遞歸式層層調(diào)用，增強了靈活性，易于理解；而且應用中由于對數(shù)據(jù)的訪問都是通過存儲過程來進行的，可以在不改動存儲過程接口的情況下對數(shù)據(jù)庫進行任何改動，使得更新對應用程序而言具有透明性，增強適應性和可維護性。在實際應用中，算法能夠正確運行，對于大量的數(shù)據(jù)具有較好的執(zhí)行能力，其規(guī)則也體現(xiàn)了一定的準確性。不過訓練數(shù)據(jù)由于受到人員錄入方式、樸素Bayes分類結(jié)果等因素的影響，使得閥值的確定難度加大，進而使得生成的決策樹會存在一定的偏差，希望在下一步的工作中調(diào)整。

參考文獻

[1] 馮少榮.決策樹算法的研究與改進[J].廈門大學學報：自然科學版，2007，46（4）：496?500.

[2] DUNHAM M H.數(shù)據(jù)挖掘教程[M].郭崇慧，田鳳占，靳曉明，等譯.北京：清華大學出版社，2005.

[3] 徐人鳳，曾建華.SQL Server 2005數(shù)據(jù)庫及應用[M].北京：高等教育出版社，2007.

[4] 王珊.數(shù)據(jù)庫系統(tǒng)概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數(shù)據(jù)挖掘技術(shù)及應用[M].北京：科學出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測評中的應用[J].濟南大學學報：自然科學版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認定中的應用[J].河南教育學院學報：自然科學版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學生心理健康評測中的應用[J].計算機應用與軟件，2011，28（10）：240?244.

[9] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數(shù)據(jù)挖掘[J].計算機工程，2010，36（1）：40?42.

[10] 姚亞夫，邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進及其應用[J].中南大學學報：自然科學版，2011，42（12）：3772?3776.