1、數據挖掘中 決礙樹算法的 探討唐華松，姚翅文(華南理工大學計算機系，廣東廣州510640)摘 要：決策樹算法是dm的一個活販的研究領域。首先給出了dm中決策樹算法的基 本思想，然后討論了決策樹算法中的難點問題，提出了利用小商與加權和的思想來選擇取值的算法。關鍵詞：數據挖掘；決策樹；炳中圖分類號：tp301. 6文獻標識碼：a文章編號：100123695 (2001)0820018202research on decision tree in data miningtang iiua2song , yao yao2wen(dept . of computer science , south ch

2、ina university of technology , guangzhou guangdong 510640 , china)abstract : decision tree is one of heated fields in data mining in recent years. this paper first gives the main thoughts of algorithmofdecision tree in data mining , then discusses the difficult problemof selecting value on division

3、in decision tree , and put forward an algorithm using the thoughts of entropy and weighted entropy to solve the problem with the exampleskey words : dm;decision tree ;entropy1 弓i言數據庫技術的迅速發展以及數據庫管理系統的廣 泛應用，導致人們積累了越來越多的數據。巨增的數 據背后蘊藏著豐富的知識，而目前的數據庫技術雖可 以高效地實現數據的查詢、統計等功務匕但卻無法發現 數據中存在的關系和規貝！j,無法根據現有的數據預測

4、未來的發展趨勢。數據庫中存在著大量的數據，卻缺 乏挖掘數據背后隱藏的知識的手段，出現了 “數據爆炸 而知識貧乏”的現象。在此背景下，數據庫知識發現(kdd)及其核心技術-數據挖掘(dm) 便應運而生了。kdd的研究內容是， 能自動地去處理數據庫中大量的原始數據，從中挖掘 搜索出具有規律、富有息義的模式。它的發現過程主 要有三個步驟:定義要發現的問題；根據問題進行數據 搜索、模式抽取；評價所發現的知識的好壞。三者之 中，核技術是第二步，即數據搜索及模式抽取方法。kdd = 問題處理+ dm+ 解釋評價。由于問題處理和解 釋評價的研究較成熟，所以目前kdd 的研究和實現難 點重點都集中在核心的dm

5、上。dm的核心技術算法主要有統計分析方法、神經元網絡、決策樹方法，遺傳算法等。其中，決策樹是一種常用于預測模型的算法，它通過將大量數據有目的地 分類，從中找到一些具有商業價值的，潛在的信息。2 決策樹的基本思想決策樹的結構，顧名思義，就像一棵樹。它利用樹 的 結構將數據記錄進行分類，樹的一個葉結點就代農 某個條件下的一個記錄集，根據記錄字段的不同取值 建立樹的分支;在每個分支子集中重復建立下層結點和分支，便可生成一棵決策樹。例如，我們要分析一個網站的用戶接受某項新服務的情況，可以從中選取100 個用戶，其中50 個接受這 項新服務的，50 個拒絕這項新服務的，然后通過理立決 策樹來分析用戶的情

6、況，尋找一些潛在的規則信息。圖1網站某項新服務的決疏樹結構便用時何-1'偎用i年用戶年齡az 、用戶弧許二 25|20桜受刀護廠|5聶受拒笛2,樓受5怔暫5襪受.40帝絕1田i網站臬項新服務的決策樹緒構 利用決策樹進行分析，可以容易地找到一些具有商業價值的潛在的規則信息。如在上例中，從決策樹 結構圖可以看出：在接受這項新服務的用戶中有60 %是使用新帳號的，在拒絕這項新服務的用戶中 有100 % 是使用舊帳號的；也就是說，如果用戶是使用 新帳號 的，那么他就有60 %的可能接受這項新服務，如果用戶 是使用舊 帳號的，那么 他就有100 %的可能拒絕這項新 服務。當然，還可以從決策樹中找

7、到其它的規則信息， 這里就不再舉例說明了。3 決策樹的技術堆點建決策樹，就是根據記錄字段的不同取值建立樹的分支，以及在每個分支子集中重復建立下層結點和分支。建決策樹的關鍵在于建立分支時對記錄字段不同取值的選擇。選擇不同的字段值，會使劃分出來的記錄子集不同，影響決策樹生長的快慢以及決策樹結 8 1 計算機應用研究2001年© 1995-2004 tsinghua tongfang optical disc co., ltd. all rights reserved.構的好壞，從而導致找到的規則信息的優劣。可見，決策樹算法的技術難點也就是選擇一個好的分支取值。利用一個好的取值來產生分支，

8、不但可以加快決策樹的生長，而且最重要的是，產生的決策樹結構好，可以找到較好的規則信息。相反，如果根據一個差的取值來產生分支，不但減慢決策樹的生長速度， 而且會使產生的決策樹分支過細，結構性差，從而難以 發現一些本來可以找到的有用的規則信息。怎樣的取值才算一個好的取值呢？ 一個好的取值，就是決策樹根據此值來分裂時，產生的分支子集中 的記錄在預測內容上盡可能一致。何謂子集中的記錄 在預測內容上盡可能一致呢？ 舉個例子，我們對學生 的思想品德情況進行分析，預測內容是在思想品德上 是優或良，抽取10 個學生記錄，其中5 個學生的思想品 德是優，另5 個的是良，那么我們可以得到以下兩個不 同的劃分：學號

9、成績學號01020407成績學號成績學號成績10優03優05優06優08優09m01 良03 良05 良07良09優02良04良06優08良10(a)(b)杓0102040710料03050608094艮艮艮19.艮030507w如<優良良優 櫛02c406懵 呦til良良悅良2學生思想品徳怡況的兩個劃分在(a) 方案中，劃分后的左分支子集的記錄的思想 品德都是優，右分支子集的記錄的思想品德都是良，即 左分支100 %優、0 %更，右分支100 %良、0 %優，子集中 的記錄在預測內容上已盡可能一致。我們就可以從兩 個分支中尋找記錄的共性，以謁到利學生思想品德情 況有關的信息。在(b)

10、方案中，劃分后的左分支子集中3 條記錄的 思想品德是優，2 條記錄的思想品德赴良，右分支子集 中2 條記錄的思想品徳是優，3 條記錄的思想品徳是 良，即左分支60 %優.40 %良，右分支60 %良.40 %優， 子集中的記錄在預測內容上的一致性差，還不能有效 地總結出和學生思想品德情況有關的信息。怎樣找到好的取值呢？ 從上例，可以看出，好的取 值分支后子集的記錄的一致性好，也就是記錄的有序 性好。通常，在系統學上，經常使用“炳”來表示事物的 無序度。所以在這里，也可以弓i用 “炳” 來估量分支后 子集有序性的好壞。煩h二工(2pi) x lg(pi)其中pi是指分支子集中記錄取某值的可能性。

11、如果子集的炳值越小，則子集記錄的有序性越好;如果癇值越大，則有序性越差。因此，我們可以對根據 不同取值進行分裂后的左右分支的子集分別計算各自 的蜩值，選擇煩值最小所對應的記錄字段的取值，這就 是好的取值。如上例中，ha左，右二(25/5)xlg(5/ 5) + (20/ 5)xlg(0/5)二 0.0hb左，右二(23/5)xlg(3/ 5) + (22/ 5)xlg(2/5) = 0.3要提出注意的是，如果左右分支子集的記錄數相差太遠，則可另豈導致新的情況，此時只用炳值來判斷可矣豈選擇不到好的取值。如上例，也可以得到以下兩個劃分：(0左分支：優右分支：優，優，優，優，気，m, 気(d) 左分

12、支：優，優，優，優，良右分支：優，良，良，良，良he左二(21/ 1)xlg(l/ 1)+ (20/ 1)x (0/ 1)=0.00he右二(24/ 9)xlg(4/ 9)+ (25/ 9)x (5/ 9)=0.99hd左二(24/ 5)xlg(4/ 5)+ (21/ 5)x (1/ 5)=0.72hd右二(24/ 5)xlg(4/ 5)+ (21/ 5)x (1/ 5)=0.72取左右分支的和平均值，則he平二(0 + 0. 99)/ 2=0. 50hd平二(0. 72 + 0.72)/ 2 = 0. 72選擇小值，可能就選擇(c) 方案，但從例子可以舌 出，(d)方案才是較好的，因為它把同

13、類的基本劃分到 一起了，而且如果像(c) 方案那樣，每次都只把一個數 據劃分出去，只會導致決策樹結構的層次變得復雜，同 類型的錄無法有效地歸到一起，不利于從中發掘潛 在的佶息。要解決這個問題，可以利用 “加權和”的思想，根據 分支子集所占的比重來給它一個權值，然后計算加權 癇，通過比較加權小商的大小來選擇取值。加權炳h加二xi x hi其中xi是指分支子集所占的比董，hi是指分支子集的 m,貝!jhe加二 9/ 10 x0. 99 + 1/ 10 x0. 0 = 0. 89hd加二 1/ 2 x0. 72 + 1/ 2 x0. 72 = 0. 724 實驗事例在實驗事例中，我們構造一個包括10

14、 條記錄的學 生總評成績的模型，以分析學生總評成績在85分以上 與何因素有關。我們提出兩個方案，(i ) 方案每次選擇第一個取值來產生分支；（n） 方案利用加權煩卑法 選擇取值來產生分支。通過對兩個方案產生的決策樹學號01 0203 04 05 0607 08 09 10進行比較，可以了解加權煩算法的優點。學號0102co(h0606070910性別fmmfmmmffm213021222330212j3021aabaaapdba優ft優優ft優便優ttft發表倫文20010200i0959030758595wt)95858085708590757)75田3學生總評成績的怡況性別f m m年齡2

15、1 2021 22 23 2021 23 20 21體育成績a aba思想品德優良優優良優良優優良發表論文2 0 0 1 0 20 0 10平時成績95 90 80 8075 8595807080總評成績95 85 80 8570 8590757075圖3學生總評成績的情況在圖4中，y表示學生的總評成績在85 分以上；n表示學生的總評成績在85 分以下。由圖4 可見，方案（ii）構造的決策樹結構好，基本上將總評成績在85分以上或以下的同類學生劃分到一起，容易得出“如果學生的平時成績在85分以上，他的總評成績就有100 %的可能在85分以上”、“如果學生的平時成績在85分以下，他的總評成績就有5

16、/ 6即83. 3 %的可能在85分以下”等規則信息。（下轉第22頁） 9 1 第8 期唐華松等：數據挖掘中決策樹葬法的探討© 1995-2004 tsinghua tongfang optical disc co., ltd. all rights reserved. 和即插即用，共同協作，形成最終的gts 應用。對于非gis 專業人員而言，可以容易地通過對gis 組件的利用，將gis 功能嵌入應用程序中，大大提高了開發的效 率及gis應用。gis的互操作組件特別有利于gis專業 人員的是，他們不必要再開發支持專用的開發軟件或 數據庫，而是將更多的精力集中于gis 的（地學應用），

17、從而使gis 產品達到更高的層次。4討論與展盥地理信息及其應用是復雜的。要將現實世界復雜的事物、過程、現象映射到計算機中，并依據人們的需要對其進行處理，并不是一件容易的事情。雖然gis界及it界早已認識到信息共享與互操作的重要性，并做 了大量工作致力于它們的實現。到 目 前為止，獲得的 成果離人們的 目標還很遠。在異構分布環境中，gis 互操作適應網絡化和社會 化的需求，以分布式計算. 面向對象技術. 互聯網絡技 術.開放式數據庫技術等為支撐，通過組件技術來實現 互操作。而在互操作的實現過程中，由于gis技術本身 及計算機技術的某些方面的不成熟，目前還不能完全 實現。g1s 技術本身的局限表現

18、在：只對復雜現實世界的 簡單對象的特征有清晰的定義和描述，而對復雜對象， 如三維、四維、多維的討論較少；地理數據兵冇多重性 的特征，在地理數據內部交換及轉換中語義難免有不 兼容，用來實現數據無損轉換的語義轉換器在具體實 現中工作難度很大。來自計算機技術方面的限制主要表現在：作為支撐技術的分布式計算技術和面向對象技術自身尚未完 全成熟；ogc 用于互操作規范組件的連接與通訊的實 現規范c0r13a , dcom, sql彼此之間不能直接訪問。 目前對gjls 互操作研究的基本單位是過程或對象，而對 粒度更大的應用間的互操作考慮彳導較少等。目前還沒有商業化的gis 軟件能完全支持gis 互 操作。

19、而在ogc 成員之間已有gis 互操作實現的成功 實例。gis 互操作的實現將增進gis 與it 界的協作能 力，這種協作無疑給gis 界造就了新的機遇、更廣闊的 市場、更多的收入。前景是美好的，而地理信息共享和 gis 的互操作的完全實現，由于存在的種種障隘涉及計 算機領域和gis 領域的疑難問題，需要it 界和gis 界 的共同努力，還需要很長時間。我國目 前在這個領域 的研究還不是很多，冇必要對國內gts 軟件的互操作進 行研究，同 時跟蹤opengis 的國際最新技術和熱點，力 爭將我國的地理信息和gis 軟件砂入到國際大舞臺中。 參考文獻：1 李德仁. 論地理信息學的形成及其在跨世紀

20、中的發展c 中國地理信息系統協會第二屆年會論文集,1996 ,10.2 黃裕霞，陳常松，何理邦.g1s的互操作c 中國地理借 息系統協會、中國海外地理信息系統協會1998 年年會論 文集,1998.3 滿曉麟，王書慶，石洞. 軟件組件化技術及其在橋梁cad 中的應用j .計算機應用研究,2000 , 17 (9) : 72274.4 zhong ershun , song guanfu , wang erqi . development of componcnts gis based on applications. procccdings of ieas' 97& iwgis ' 97c 1 1997 , 1.作者簡介：駱成鳳(19762),女，現為南京大學城市與資源學系地圖學與地 理信息系統專業碩士研究生，主要研究方向為互操作性gis , 組件式地理信息 系統