戴龍平+戴莉萍+劉麗珍

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

關(guān)鍵詞： C4.5算法； 信息增益； 存儲(chǔ)過程； 動(dòng)力計(jì)量計(jì)費(fèi)系統(tǒng)

中圖分類號(hào)： TN919?34； TP391.77 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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引 言

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

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

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

1C4.5算法基本原理

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

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

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

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

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

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

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

Function Tree=Decision_Tree_Create（T，A，Y）

{

If 訓(xùn)練集為空，則返回值為Failure的單個(gè)節(jié)點(diǎn)Tree；

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

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

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

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

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

for each V in Values do

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

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

Create_Branch（Tree， Node）；

end for

返回Tree；

}

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

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

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

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

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

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

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

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

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

圖1 各個(gè)動(dòng)力用量費(fèi)用顯示

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

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

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

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

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

輸入：訓(xùn)練樣本集

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

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

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

EXEC PRC_CREDTVALUE ′ZHD′

EXEC PRC_CREDTVALUE ′GFD′

EXEC PRC_CREDTVALUE ′DGD′

EXEC PRC_CREDTVALUE ′PFD‘

圖4 屬性取值與類別分布

（2） 計(jì)算訓(xùn)練樣本的信息量：變量@H、@M和@L分別是目標(biāo)屬性高中低的樣本個(gè)數(shù)，變量@TOTAL是總個(gè)數(shù)，根據(jù)公式（1）得到信息量值，這里取小數(shù)點(diǎn)后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ì)算每個(gè)屬性的信息增益：根據(jù)式（1），（2），編寫存儲(chǔ)過程PRC_ ComputeEntropy，通過輸入?yún)?shù)靈活求取各個(gè)動(dòng)力類型的熵值。即先求取每個(gè)屬性值的各個(gè)樣本子集的信息量，而后信息量之和就是熵值，再用訓(xùn)練樣本的信息量減去熵值得到信息增益。表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é)點(diǎn)，插入到結(jié)點(diǎn)表中：選取信息增益最大的屬性作為分裂的節(jié)點(diǎn)，因?yàn)檫@里使用的是倒序排列，因此取第1位；因?yàn)槭歉?jié)點(diǎn)，因此無父節(jié)點(diǎn)，賦值為0；因?yàn)楦?jié)點(diǎn)的所有直接子節(jié)點(diǎn)沒有產(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é)點(diǎn)擴(kuò)展與剪枝

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

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

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

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

輸出：根節(jié)點(diǎn)的擴(kuò)展子節(jié)點(diǎn)

處理：當(dāng)綜合電ZHD用量分類為高時(shí)

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

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

同理，還需要計(jì)算總費(fèi)用分類為中和低時(shí)的比例，即@MRATE和@LRATE。

（2） 回寫擴(kuò)展標(biāo)識(shí)以確定是否在后續(xù)過程中得到相應(yīng)的處理。下段代碼是判斷綜合電ZHD用量分類為高時(shí)的子節(jié)點(diǎn)生成情況。這里利用到了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

同理，還需要回寫當(dāng)總費(fèi)用分類為中和為低時(shí)的擴(kuò)展標(biāo)識(shí)。

4規(guī)則的生成

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

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

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

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

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

圖7 規(guī)則表

5結(jié)語

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

參考文獻(xiàn)

[1] 馮少榮.決策樹算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，46（4）：496?500.

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

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

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

[5] 陳安，陳寧，周龍?bào)J.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京：科學(xué)出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測(cè)評(píng)中的應(yīng)用[J].濟(jì)南大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認(rèn)定中的應(yīng)用[J].河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學(xué)生心理健康評(píng)測(cè)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（10）：240?244.

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

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

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

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

同理，還需要計(jì)算總費(fèi)用分類為中和低時(shí)的比例，即@MRATE和@LRATE。

（2） 回寫擴(kuò)展標(biāo)識(shí)以確定是否在后續(xù)過程中得到相應(yīng)的處理。下段代碼是判斷綜合電ZHD用量分類為高時(shí)的子節(jié)點(diǎn)生成情況。這里利用到了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

同理，還需要回寫當(dāng)總費(fèi)用分類為中和為低時(shí)的擴(kuò)展標(biāo)識(shí)。

4規(guī)則的生成

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

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

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

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

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

圖7 規(guī)則表

5結(jié)語

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

參考文獻(xiàn)

[1] 馮少榮.決策樹算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，46（4）：496?500.

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

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

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

[5] 陳安，陳寧，周龍?bào)J.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京：科學(xué)出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測(cè)評(píng)中的應(yīng)用[J].濟(jì)南大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認(rèn)定中的應(yīng)用[J].河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學(xué)生心理健康評(píng)測(cè)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（10）：240?244.

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

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

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

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

同理，還需要計(jì)算總費(fèi)用分類為中和低時(shí)的比例，即@MRATE和@LRATE。

（2） 回寫擴(kuò)展標(biāo)識(shí)以確定是否在后續(xù)過程中得到相應(yīng)的處理。下段代碼是判斷綜合電ZHD用量分類為高時(shí)的子節(jié)點(diǎn)生成情況。這里利用到了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

同理，還需要回寫當(dāng)總費(fèi)用分類為中和為低時(shí)的擴(kuò)展標(biāo)識(shí)。

4規(guī)則的生成

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

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

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

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

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

圖7 規(guī)則表

5結(jié)語

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

參考文獻(xiàn)

[1] 馮少榮.決策樹算法的研究與改進(jìn)[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，46（4）：496?500.

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

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

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

[5] 陳安，陳寧，周龍?bào)J.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京：科學(xué)出版社，2006.

[6] 曲守寧，盧健.C4.5分類算法在碩士研究生智育測(cè)評(píng)中的應(yīng)用[J].濟(jì)南大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，23（3）：253?256．

[7] 馬偉杰.C4.5決策樹法在高校貧困生認(rèn)定中的應(yīng)用[J].河南教育學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，21（3）：27?30.

[8] 吳小剛，周萍，彭文惠.決策樹算法在大學(xué)生心理健康評(píng)測(cè)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（10）：240?244.

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

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