非遞歸式決策樹在動力計量計費系統中的應用

戴龍平+戴莉萍+劉麗珍

摘要：決策樹算法的實現往往采用面向對象語言工具來實現，與數據庫中的結構通常存在一定的差異，需要進行大量的數據轉換。現在充分利用數據庫中表結構特點和存儲過程中PL/SQL語法的強大性及靈活性，采用一個動力計量計費系統中的數據，快速、有效且非遞歸地實現了決策樹C4.5算法中的節點生成、擴展與剪枝主要過程；并進行了規則抽取。應用結果表明，該算法的實現方法具有一定的高效性、穩定性和普適性。

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

中圖分類號： 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引 言

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

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

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

1C4.5算法基本原理

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

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

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

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

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

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

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

Function Tree=Decision_Tree_Create（T，A，Y）

{

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

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

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

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

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

//根據分裂特性進行樣本集的劃分，生成相應的子節點，并對一直遞歸下去，最終形成一個分支并將其加入到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；

}

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

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

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

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

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

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

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

2決策樹的節點生成

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

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

在構造決策樹之前，已經使用樸素Bayes算法將各個動力用量按照高、中、低進行了分類。而后為決策樹實現確定數據結構，圖2是節點的主體結構。

圖2 節點的主體結構

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

圖3 節點表的數據顯示

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

輸入：訓練樣本集

輸出：節點表新增一條節點記錄

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

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

EXEC PRC_CREDTVALUE ′ZHD′

EXEC PRC_CREDTVALUE ′GFD′

EXEC PRC_CREDTVALUE ′DGD′

EXEC PRC_CREDTVALUE ′PFD‘

圖4 屬性取值與類別分布

（2） 計算訓練樣本的信息量：變量@H、@M和@L分別是目標屬性高中低的樣本個數，變量@TOTAL是總個數，根據公式（1）得到信息量值，這里取小數點后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） 計算每個屬性的信息增益：根據式（1），（2），編寫存儲過程PRC_ ComputeEntropy，通過輸入參數靈活求取各個動力類型的熵值。即先求取每個屬性值的各個樣本子集的信息量，而后信息量之和就是熵值，再用訓練樣本的信息量減去熵值得到信息增益。表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） 確定分裂結點，插入到結點表中：選取信息增益最大的屬性作為分裂的節點，因為這里使用的是倒序排列，因此取第1位；因為是根節點，因此無父節點，賦值為0；因為根節點的所有直接子節點沒有產生完畢，因此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決策樹節點擴展與剪枝

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

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

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

輸入：根節點結構的初始值和訓練樣本集

輸出：根節點的擴展子節點

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

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

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

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規則的生成

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

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

輸出：規則表T_DTRULES，部分數據如圖7所示。

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

圖6 節點表的父子信息

圖7 規則表

5結語

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

參考文獻

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

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

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

[4] 王珊.數據庫系統概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數據挖掘技術及應用[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] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數據挖掘[J].計算機工程，2010，36（1）：40?42.

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

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

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

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規則的生成

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

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

輸出：規則表T_DTRULES，部分數據如圖7所示。

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

圖6 節點表的父子信息

圖7 規則表

5結語

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

參考文獻

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

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

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

[4] 王珊.數據庫系統概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數據挖掘技術及應用[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] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數據挖掘[J].計算機工程，2010，36（1）：40?42.

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

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

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

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規則的生成

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

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

輸出：規則表T_DTRULES，部分數據如圖7所示。

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

圖6 節點表的父子信息

圖7 規則表

5結語

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

參考文獻

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

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

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

[4] 王珊.數據庫系統概論[M].4版.北京：高等教育出版社，2007.

[5] 陳安，陳寧，周龍驤.數據挖掘技術及應用[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] 郭紹慮，甄濤，賈琦.基于存儲過程的海量郵件數據挖掘[J].計算機工程，2010，36（1）：40?42.

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