陳 健

（福建商學(xué)院 信息工程學(xué)院，福建 福州350012）

大規(guī)模數(shù)據(jù)庫和互聯(lián)網(wǎng)的迅速發(fā)展，使人們對數(shù)據(jù)庫的應(yīng)用提出更多新要求，僅使用查詢檢索的方法已經(jīng)不能滿足用戶提取有用數(shù)據(jù)實現(xiàn)其目標(biāo)的結(jié)論性信息的要求。數(shù)據(jù)庫中所包含的大量知識無法得到充分的挖掘和使用，造成極大的信息浪費，并產(chǎn)生大量的數(shù)據(jù)垃圾［1］。另外，從領(lǐng)域?qū)＜耀@得知識是非常復(fù)雜的個人到個人之間的交互過程，具有很強的個性及隨機性［2］。因此，人們開始考慮用數(shù)據(jù)庫作為知識源，通過數(shù)據(jù)挖掘可以自動處理數(shù)據(jù)庫中的大量原始數(shù)據(jù)，挖掘出具有必然的、富有意義的規(guī)則和模式，成為有助于人們實現(xiàn)目標(biāo)的知識［1］，找出人們需要解決問題的答案。

決策樹是建立在信息論上解決分類問題比較常用的一種方法，用樹形的結(jié)構(gòu)來表示分類規(guī)則，構(gòu)造決策樹的過程就是分類規(guī)則形成的過程。它根據(jù)各變量對目標(biāo)變量的影響情況產(chǎn)生效應(yīng)的不同而進(jìn)行預(yù)測，通過這個分類規(guī)則就可以比較容易的對未知數(shù)據(jù)事例進(jìn)行分類識別和預(yù)測，這種方法容易實現(xiàn)可視化，其輸出結(jié)果的效率也較高，規(guī)則也容易理解，所以得到廣泛的應(yīng)用［3］。

1 PEP 剪枝算法

PEP 后剪枝算法是在ID3 算法的基礎(chǔ)上，采用自上而下的剪枝算法，對訓(xùn)練事例集的錯誤估計進(jìn)行，比較剪枝前后的錯分樣本數(shù)來進(jìn)行剪枝，在采用同一訓(xùn)練事例集來生成決策樹同時又用它來進(jìn)行剪枝，這樣進(jìn)行剪枝的速度將比較快。正是因為沒有使用剪枝事例集，使得對錯分樣本率R（t）的估計具有較大偏離，因而不能得到最優(yōu)的剪枝樹。所以追加了一個可以對錯分樣本率R（t）進(jìn)行校正的連續(xù)校正公式，通過校正后可以得到一個較為合理的錯分樣本率。

用Ni表示決策樹的內(nèi)部節(jié)點，Nl表示樹的葉節(jié)點，N 表示決策樹的所有節(jié)點，則N=Ni∪Nl，Tt表示以節(jié)點t 為根節(jié)點的子樹。樹T 的葉子節(jié)點的個數(shù)用│Nl│表示。到達(dá)節(jié)點t 且屬于類i 的實例個數(shù)用Ni（t）表示，節(jié)點t 覆蓋的實例總個數(shù)用N（t）表示，假設(shè)節(jié)點t 的實例共有k 類，則N（t）=N1（t）+N2（t）+…+Ni（t）+…+Nk（t）。節(jié)點t 覆蓋的例外實例個數(shù)用E（t）表示：E（t）=N（t）-Max（Ni（t）），其中Max（Ni（t））表示到達(dá)節(jié)點t 的包含最多實例的類的實例數(shù)，即Max（Ni（t））=Max（N1（t）+N2（t）+…+Ni（t）+…+Nk（t））。

令單個節(jié)點t 上的錯誤分類率為

由于使用PEP 后剪枝算法進(jìn)行決策樹的遍歷，訪問決策樹T 的每個子樹最多一次，比較其他剪枝算法，PEP 剪枝算法的優(yōu)點在于剪枝的速度更快。

2 醫(yī)療系統(tǒng)的設(shè)計

醫(yī)療系統(tǒng)是在基于病案數(shù)據(jù)的醫(yī)療數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘，首先對醫(yī)療數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，得到離散化的手術(shù)診斷決策信息表并存放在數(shù)據(jù)庫中。如何利用決策樹數(shù)據(jù)挖掘技術(shù)對手術(shù)診斷決策信息表進(jìn)行挖掘，發(fā)現(xiàn)他們之間隱含的關(guān)系是該系統(tǒng)的研究重點。以下將介紹具體的系統(tǒng)設(shè)計框架，挖掘出手術(shù)診斷的決策規(guī)則，并介紹實現(xiàn)該系統(tǒng)具體的程序結(jié)構(gòu)和軟件包。

2.1 數(shù)據(jù)預(yù)處理

該系統(tǒng)是在基于病案的醫(yī)療數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘的，在使用前必須對相關(guān)的醫(yī)療數(shù)據(jù)進(jìn)行相應(yīng)的處理，數(shù)據(jù)預(yù)處理的目的在于可以提供進(jìn)行數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的數(shù)據(jù)。對相關(guān)醫(yī)療數(shù)據(jù)進(jìn)行預(yù)處理的任務(wù)是明確條件屬性和決策屬性，建立醫(yī)療數(shù)據(jù)信息表，并存放在數(shù)據(jù)庫中，為下一步的決策樹挖掘做準(zhǔn)備。

院方提供的數(shù)據(jù)字典和部分醫(yī)療數(shù)據(jù)表包含：病人基本信息表（病例號，性別，年齡，婚否，職業(yè)，出生地，民族，家庭地址，住院日期，出院日期）、疾病診斷信息表（病例號，疾病代碼，治療情況，發(fā)病日期，住院日期，出院日期）、手術(shù)診斷信息表（病例號，手術(shù)時間，切口，手術(shù)名稱，麻醉情況，診斷類別，主刀醫(yī)生）、醫(yī)生基本信息表（姓名編碼，姓名，職稱，工作時間，畢業(yè)院校，年齡，科室編碼）、門診用藥信息表（病例號，所用藥物編號）、疾病列表（疾病代碼，…）等，考慮在進(jìn)行數(shù)據(jù)挖掘之前，需要對原始的醫(yī)療數(shù)據(jù)表中的屬性字段進(jìn)行如下處理：對于如姓名、聯(lián)系人等與數(shù)據(jù)挖掘無關(guān)的屬性進(jìn)行刪除；對于與決策屬性強相關(guān)的屬性也要去除；對于如主刀醫(yī)生和麻醉情況等字段，有利于進(jìn)行決策分析的屬性可考慮細(xì)化處理；對于如年齡取值為連續(xù)的屬性轉(zhuǎn)化為離散取值，如幼兒、兒童、少年、青年、中年、老年等；對于如發(fā)病日期、住院日期、出院日期取值過多的離散值的屬性，進(jìn)行合并和歸類，歸納為手術(shù)季節(jié)等。

由于手術(shù)診斷信息表中部分記錄有比較嚴(yán)重的缺損，還有一些對診斷決策不產(chǎn)生影響的冗余的屬性，可以考慮把這些記錄和屬性刪除，最終將獲得一個比較完備的手術(shù)診斷信息表，包含7 個條件屬性為{手術(shù)類別，病人性別，病人年齡，麻醉情況，主刀職稱，手術(shù)環(huán)境，手術(shù)季節(jié)}，1 個決策屬性為{術(shù)后情況}）［4］。

2.2 系統(tǒng)設(shè)計框圖

根據(jù)如上所述，設(shè)計了一個可視化的基于決策樹PEP 剪枝算法挖掘技術(shù)的決策系統(tǒng)。該系統(tǒng)設(shè)計框圖如圖1 所示。

圖1 系統(tǒng)設(shè)計框圖

2.3 程序結(jié)構(gòu)及軟件包內(nèi)組織關(guān)系

在構(gòu)建可視化決策系統(tǒng)時考慮使用B/S 架構(gòu)，當(dāng)客戶訪問系統(tǒng)時，客戶端可以通過Applet 與服務(wù)器交互，這時是用瀏覽器自動下載服務(wù)器上的Applet 進(jìn)行訪問的。在設(shè)計的過程中可以將類分為兩類，分別是客戶端類和服務(wù)器端類。另外由于該系統(tǒng)是圖形化決策樹挖掘算法系統(tǒng)，分別獨立出兩個類作為決策樹算法和圖形繪制方面的應(yīng)用類。根據(jù)以上分析，最終把整個系統(tǒng)分為以下5 個類包：本系統(tǒng)的頂級包為decisiontree。服務(wù)器端和客戶端通信的數(shù)據(jù)傳輸類為decisiontree.info?？蛻舳说念惣习鼮閐ecisiontree.client。服務(wù)器端的類集合包為decisiontree.server。決策樹圖構(gòu)建包即圖形繪制相關(guān)類為decisiontree.wldata。決策樹算法相關(guān)類為decisiontree.id3。

定義了軟件包結(jié)構(gòu)間的調(diào)用關(guān)系后，通過具體的數(shù)據(jù)流圖詳細(xì)說明訓(xùn)練集與測試集的采集、信息從客戶端到服務(wù)器端的傳輸及反饋、服務(wù)器端決策樹的生成和客戶端決策樹的顯示整個過程，如圖2所示。

圖2 系統(tǒng)整體架構(gòu)圖

客戶端處理模塊（Client）的主要功能：接收客戶端的指令流（包括打開決策表或決策樹圖命令、提取服務(wù)器端文件列表命令、由數(shù)據(jù)表生成決策樹命令、保存增刪改后的決策樹命令和用訓(xùn)練集或測試集優(yōu)化決策樹命令等），并向下傳送；向下發(fā)送與指令流相對應(yīng)的數(shù)據(jù)流信息（包括決策表參數(shù)信息和編輯后的決策樹結(jié)構(gòu)信息）；接收服務(wù)器端反饋的數(shù)據(jù)流信息（包括構(gòu)造決策樹結(jié)構(gòu)信息、訓(xùn)練集與測試集記錄信息和經(jīng)過服務(wù)器端處理的反映決策樹決策能力的指標(biāo)信息等），經(jīng)過客戶端處理模塊的處理后向客戶端IE 提交顯示。

信息封裝拆封模塊（Info）的主要功能：接收客戶端的指令編碼進(jìn)行分析，判斷數(shù)據(jù)信息對應(yīng)的數(shù)據(jù)結(jié)構(gòu)對象類（WlData），用該對象類加載數(shù)據(jù)信息，然后將指令編碼和數(shù)據(jù)信息封裝為可序列化的信息流，通過網(wǎng)絡(luò)向服務(wù)器端傳送；接收服務(wù)器端反饋的序列化信息流，拆封后進(jìn)行分析，按照指令編碼類型確定數(shù)據(jù)信息的裝載對象類，然后用該對象類還原為決策樹的數(shù)據(jù)結(jié)構(gòu)信息或決策表記錄信息，并向客戶端處理模塊發(fā)送。

在圖2 中將信息封裝拆封模塊分為Client 端和Server 端是為了說明問題的方便，實際上在Client端和Server 端實現(xiàn)的功能是對稱的，因此在程序設(shè)計中只需要一個模塊就足夠了。

網(wǎng)絡(luò)傳輸模塊（HTTP）的主要功能：基于java 的Servlet 技術(shù)，對無論上傳或下傳的序列化流都是用Servlet Stream 進(jìn)行封裝后在網(wǎng)絡(luò)中傳輸。由于該模塊只用于數(shù)據(jù)傳輸，并且與服務(wù)器端耦合緊密，因此在實際設(shè)計中，將該模塊并入服務(wù)器端模塊中。

服務(wù)器端處理模塊（Server）的主要功能：根據(jù)負(fù)載平衡的需要，為了減輕客戶端的負(fù)載，把繁重的處理任務(wù)盡量放在服務(wù)器端執(zhí)行?？蛻舳酥贿M(jìn)行指令流、數(shù)據(jù)流的傳輸和信息的可視化。服務(wù)器端處理模塊接收指令信息和數(shù)據(jù)信息后，根據(jù)指令類別調(diào)用相應(yīng)的模塊進(jìn)行處理。服務(wù)器端處理模塊通過接口連接決策樹生成模塊（ID3）、決策樹訓(xùn)練模塊（Training）、決策樹測試模塊（Testing）以及其他一些處理模塊。服務(wù)器端和XML 文件是可以交互的：接收要保存的數(shù)據(jù)信息，經(jīng)過處理后存入服務(wù)器端XML 文件；請求要編輯的XML 文件，經(jīng)過封裝后向客戶端發(fā)送。

決策樹生成模塊（ID3）、決策樹訓(xùn)練模塊（Training）、決策樹測試模塊（Testing）的主要功能：決策樹生成模塊（ID3）根據(jù)具體的決策表記錄信息和字段信息用ID3 算法生成一棵原始的決策樹；決策樹訓(xùn)練模塊（Training）用訓(xùn)練集對原始的決策樹進(jìn)行訓(xùn)練，修剪枝葉，使得決策樹在決策能力不發(fā)生大的落差情況下樹的深度盡可能??；決策樹測試模塊（Testing）用來測試經(jīng)過上面兩個模塊處理后的決策樹的實際決策能力，得出正確率和錯誤率的信息。

2.4 實驗結(jié)果

從醫(yī)院獲得基于病案的醫(yī)療數(shù)據(jù)庫中，經(jīng)過前期的數(shù)據(jù)預(yù)處理，得到一個術(shù)后情況信息決策表。包含7 個條件屬性為{手術(shù)類別，病人性別，病人年齡，麻醉情況，主刀職稱，手術(shù)環(huán)境，手術(shù)季節(jié)}，1 個決策屬性為{術(shù)后情況}）［5］。通過與醫(yī)院醫(yī)生的溝通，了解到醫(yī)生比較關(guān)注的是手術(shù)后不理想的情況，所以主要篩選出術(shù)后情況都是乙等或丙等的記錄［6］。取40%的數(shù)據(jù)記錄來生成決策樹，并將全部記錄用來測試。在實驗中，分別進(jìn)行生成決策樹和測試后剪枝算法，具體結(jié)果如表1 所示。

表1 決策樹后剪枝及其數(shù)據(jù)集測試結(jié)果列表

3 結(jié)語

本文介紹了基于決策樹PEP 剪枝算法可視化系統(tǒng)，并且得出了手術(shù)診斷決策的規(guī)則。生成決策樹并進(jìn)行剪枝以及規(guī)則歸納和測試的過程都可以利用該系統(tǒng)來完成，并且實現(xiàn)了可視化。但是，由于其他客觀因素得到的數(shù)據(jù)有限，可能還存在其他因素影響手術(shù)質(zhì)量，條件字段集內(nèi)容還不夠，使得決策表中存在許多矛盾的數(shù)據(jù)，對于最后決策規(guī)則的生成產(chǎn)生了一定的負(fù)面影響。把產(chǎn)生的規(guī)則集和醫(yī)院的醫(yī)生進(jìn)行探討，醫(yī)生認(rèn)為產(chǎn)生的大部分規(guī)則客觀反映了影響手術(shù)的諸多因素，有些規(guī)則對他們還是有借鑒意義的，取得了比較滿意的結(jié)果。