數(shù)據(jù)挖掘中決策樹(shù)算法的探討

1、數(shù)據(jù)挖掘中決策樹(shù)算法的探討唐華松, 姚耀文(華南理工大學(xué)計(jì)算機(jī)系, 廣東廣州510640)摘要: 決策樹(shù)算法是DM的一個(gè)活躍的研究領(lǐng)域。首先給出了DM中決策樹(shù)算法的基本思想,然后討論了決策樹(shù)算法中的難點(diǎn)問(wèn)題,提出了利用熵與加權(quán)和的思想來(lái)選擇取值的算法。關(guān)鍵詞: 數(shù)據(jù)挖掘;決策樹(shù);熵中圖分類(lèi)號(hào): TP301. 6 文獻(xiàn)標(biāo)識(shí)碼: A 文章編號(hào): 100123695 (2001) 0820018202Research on Decision Tree in Data MiningTANG Hua2song , YAO Yao2wen( Dept . of Computer Science , Sou

2、th China 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 divi

3、sion in Decision Tree , and put forward analgorithm using the thoughts of entropy and weighted entropy to solve the problem with the examples.Key words : DM;Decision tree ;Entropy1 引言數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫(kù)管理系統(tǒng)的廣泛應(yīng)用,導(dǎo)致人們積累了越來(lái)越多的數(shù)據(jù)。巨增的數(shù)據(jù)背后蘊(yùn)藏著豐富的知識(shí),而目前的數(shù)據(jù)庫(kù)技術(shù)雖可以高效地實(shí)現(xiàn)數(shù)據(jù)的查詢、統(tǒng)計(jì)等功能,但卻無(wú)法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則,無(wú)法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測(cè)未來(lái)的

4、發(fā)展趨勢(shì)。數(shù)據(jù)庫(kù)中存在著大量的數(shù)據(jù),卻缺乏挖掘數(shù)據(jù)背后隱藏的知識(shí)的手段,出現(xiàn)了“數(shù)據(jù)爆炸而知識(shí)貧乏”的現(xiàn)象。在此背景下,數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)(KDD) 及其核心技術(shù)數(shù)據(jù)挖掘(DM) 便應(yīng)運(yùn)而生了。KDD 的研究?jī)?nèi)容是,能自動(dòng)地去處理數(shù)據(jù)庫(kù)中大量的原始數(shù)據(jù),從中挖掘搜索出具有規(guī)律、富有意義的模式。它的發(fā)現(xiàn)過(guò)程主要有三個(gè)步驟:定義要發(fā)現(xiàn)的問(wèn)題;根據(jù)問(wèn)題進(jìn)行數(shù)據(jù)搜索、模式抽取; 評(píng)價(jià)所發(fā)現(xiàn)的知識(shí)的好壞。三者之中,核心技術(shù)是第二步,即數(shù)據(jù)搜索及模式抽取方法。KDD = 問(wèn)題處理+ DM+ 解釋評(píng)價(jià)。由于問(wèn)題處理和解釋評(píng)價(jià)的研究較成熟,所以目前KDD 的研究和實(shí)現(xiàn)難點(diǎn)重點(diǎn)都集中在核心的DM上。DM的核心技術(shù)算

5、法主要有統(tǒng)計(jì)分析方法、神經(jīng)元網(wǎng)絡(luò)、決策樹(shù)方法,遺傳算法等。其中,決策樹(shù)是一種常用于預(yù)測(cè)模型的算法,它通過(guò)將大量數(shù)據(jù)有目的地分類(lèi),從中找到一些具有商業(yè)價(jià)值的,潛在的信息。2 決策樹(shù)的基本思想決策樹(shù)的結(jié)構(gòu),顧名思義,就像一棵樹(shù)。它利用樹(shù)的結(jié)構(gòu)將數(shù)據(jù)記錄進(jìn)行分類(lèi),樹(shù)的一個(gè)葉結(jié)點(diǎn)就代表某個(gè)條件下的一個(gè)記錄集,根據(jù)記錄字段的不同取值建立樹(shù)的分支;在每個(gè)分支子集中重復(fù)建立下層結(jié)點(diǎn)和分支,便可生成一棵決策樹(shù)。例如,我們要分析一個(gè)網(wǎng)站的用戶接受某項(xiàng)新服務(wù)的情況,可以從中選取100 個(gè)用戶,其中50 個(gè)接受這項(xiàng)新服務(wù)的,50 個(gè)拒絕這項(xiàng)新服務(wù)的,然后通過(guò)建立決策樹(shù)來(lái)分析用戶的情況,尋找一些潛在的規(guī)則信息。圖1

6、網(wǎng)站某項(xiàng)新服務(wù)的決策樹(shù)結(jié)構(gòu)利用決策樹(shù)進(jìn)行分析,可以容易地找到一些具有商業(yè)價(jià)值的潛在的規(guī)則信息。如在上例中,從決策樹(shù)結(jié)構(gòu)圖可以看出:在接受這項(xiàng)新服務(wù)的用戶中有60 %是使用新帳號(hào)的,在拒絕這項(xiàng)新服務(wù)的用戶中有100 %是使用舊帳號(hào)的;也就是說(shuō),如果用戶是使用新帳號(hào)的,那么他就有60 %的可能接受這項(xiàng)新服務(wù),如果用戶是使用舊帳號(hào)的,那么他就有100 %的可能拒絕這項(xiàng)新服務(wù)。當(dāng)然,還可以從決策樹(shù)中找到其它的規(guī)則信息,這里就不再舉例說(shuō)明了。3 決策樹(shù)的技術(shù)難點(diǎn)建決策樹(shù),就是根據(jù)記錄字段的不同取值建立樹(shù)的分支,以及在每個(gè)分支子集中重復(fù)建立下層結(jié)點(diǎn)和分支。建決策樹(shù)的關(guān)鍵在于建立分支時(shí)對(duì)記錄字段不同取值的選

7、擇。選擇不同的字段值,會(huì)使劃分出來(lái)的記錄子集不同,影響決策樹(shù)生長(zhǎng)的快慢以及決策樹(shù)結(jié)· 8 1 · 計(jì)算機(jī)應(yīng)用研究2001 年© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.構(gòu)的好壞,從而導(dǎo)致找到的規(guī)則信息的優(yōu)劣。可見(jiàn),決策樹(shù)算法的技術(shù)難點(diǎn)也就是選擇一個(gè)好的分支取值。利用一個(gè)好的取值來(lái)產(chǎn)生分支,不但可以加快決策樹(shù)的生長(zhǎng),而且最重要的是,產(chǎn)生的決策樹(shù)結(jié)構(gòu)好,可以找到較好的規(guī)則信息。相反,如果根據(jù)一個(gè)差的取值來(lái)產(chǎn)生分支,不但減慢決策樹(shù)的生長(zhǎng)速度,而且會(huì)使產(chǎn)生的決策樹(shù)分支過(guò)細(xì)

8、,結(jié)構(gòu)性差,從而難以發(fā)現(xiàn)一些本來(lái)可以找到的有用的規(guī)則信息。怎樣的取值才算一個(gè)好的取值呢? 一個(gè)好的取值,就是決策樹(shù)根據(jù)此值來(lái)分裂時(shí),產(chǎn)生的分支子集中的記錄在預(yù)測(cè)內(nèi)容上盡可能一致。何謂子集中的記錄在預(yù)測(cè)內(nèi)容上盡可能一致呢? 舉個(gè)例子,我們對(duì)學(xué)生的思想品德情況進(jìn)行分析,預(yù)測(cè)內(nèi)容是在思想品德上是優(yōu)或良,抽取10 個(gè)學(xué)生記錄,其中5 個(gè)學(xué)生的思想品德是優(yōu),另5 個(gè)的是良,那么我們可以得到以下兩個(gè)不同的劃分:學(xué)號(hào)成績(jī)學(xué)號(hào)成績(jī)學(xué)號(hào)成績(jī)學(xué)號(hào)成績(jī)01 優(yōu)03 良01 優(yōu)02 優(yōu)02 優(yōu)05 良03 良04 優(yōu)04 優(yōu)06 良05 良06 良07 優(yōu)08 良07 優(yōu)08 良10 優(yōu)09 良09 良10 優(yōu)(A)

9、 (B)圖2 學(xué)生思想品德情況的兩個(gè)劃分在(A) 方案中,劃分后的左分支子集的記錄的思想品德都是優(yōu),右分支子集的記錄的思想品德都是良,即左分支100 %優(yōu)、0 %良,右分支100 %良、0 %優(yōu),子集中的記錄在預(yù)測(cè)內(nèi)容上已盡可能一致。我們就可以從兩個(gè)分支中尋找記錄的共性,以得到和學(xué)生思想品德情況有關(guān)的信息。在(B) 方案中,劃分后的左分支子集中3 條記錄的思想品德是優(yōu),2 條記錄的思想品德是良,右分支子集中2 條記錄的思想品德是優(yōu),3 條記錄的思想品德是良,即左分支60 %優(yōu)、40 %良,右分支60 %良、40 %優(yōu),子集中的記錄在預(yù)測(cè)內(nèi)容上的一致性差,還不能有效地總結(jié)出和學(xué)生思想品德情況有關(guān)

10、的信息。怎樣找到好的取值呢? 從上例,可以看出,好的取值分支后子集的記錄的一致性好,也就是記錄的有序性好。通常,在系統(tǒng)學(xué)上,經(jīng)常使用“熵”來(lái)表示事物的無(wú)序度。所以在這里,也可以引用“熵”來(lái)估量分支后子集有序性的好壞。熵H =(2Pi) ×lg(Pi)其中Pi 是指分支子集中記錄取某值的可能性。如果子集的熵值越小,則子集記錄的有序性越好;如果熵值越大,則有序性越差。因此,我們可以對(duì)根據(jù)不同取值進(jìn)行分裂后的左右分支的子集分別計(jì)算各自的熵值,選擇熵值最小所對(duì)應(yīng)的記錄字段的取值,這就是好的取值。如上例中,Ha左,右= (25/ 5) ×lg(5/ 5) + (20/ 5) 

11、5;lg(0/ 5) = 0. 0Hb左,右= (23/ 5) ×lg(3/ 5) + (22/ 5) ×lg(2/ 5) = 0. 3要提出注意的是,如果左右分支子集的記錄數(shù)相差太遠(yuǎn),則可能導(dǎo)致新的情況,此時(shí)只用熵值來(lái)判斷可能選擇不到好的取值。如上例,也可以得到以下兩個(gè)劃分:(C) 左分支:優(yōu)右分支:優(yōu),優(yōu),優(yōu),優(yōu),良,良,良,良,良(D) 左分支:優(yōu),優(yōu),優(yōu),優(yōu),良右分支:優(yōu),良,良,良,良Hc左= (21/ 1) ×lg(1/ 1) + (20/ 1) ×(0/ 1) = 0. 00Hc右= (24/ 9) ×lg(4/ 9) + (25

12、/ 9) ×(5/ 9) = 0. 99Hd左= (24/ 5) ×lg(4/ 5) + (21/ 5) ×(1/ 5) = 0. 72Hd右= (24/ 5) ×lg(4/ 5) + (21/ 5) ×(1/ 5) = 0. 72取左右分支的和平均值,則Hc平= (0 + 0. 99) / 2 = 0. 50Hd平= (0. 72 + 0. 72) / 2 = 0. 72選擇小值,可能就選擇(C) 方案,但從例子可以看出, (D) 方案才是較好的,因?yàn)樗淹?lèi)的基本劃分到一起了,而且如果像(C) 方案那樣,每次都只把一個(gè)數(shù)據(jù)劃分出去,只會(huì)導(dǎo)致

13、決策樹(shù)結(jié)構(gòu)的層次變得復(fù)雜,同類(lèi)型的記錄無(wú)法有效地歸到一起,不利于從中發(fā)掘潛在的信息。要解決這個(gè)問(wèn)題,可以利用“加權(quán)和”的思想,根據(jù)分支子集所占的比重來(lái)給它一個(gè)權(quán)值,然后計(jì)算加權(quán)熵,通過(guò)比較加權(quán)熵的大小來(lái)選擇取值。加權(quán)熵H加=Xi ×Hi其中Xi 是指分支子集所占的比重,Hi 是指分支子集的熵,則Hc加= 9/ 10 ×0. 99 + 1/ 10 ×0. 0 = 0. 89Hd加= 1/ 2 ×0. 72 + 1/ 2 ×0. 72 = 0. 724 實(shí)驗(yàn)事例在實(shí)驗(yàn)事例中,我們構(gòu)造一個(gè)包括10 條記錄的學(xué)生總評(píng)成績(jī)的模型,以分析學(xué)生總評(píng)成績(jī)?cè)?5

14、 分以上與何因素有關(guān)。我們提出兩個(gè)方案, ( ) 方案每次選擇第一個(gè)取值來(lái)產(chǎn)生分支; ( ) 方案利用加權(quán)熵算法選擇取值來(lái)產(chǎn)生分支。通過(guò)對(duì)兩個(gè)方案產(chǎn)生的決策樹(shù)進(jìn)行比較,可以了解加權(quán)熵算法的優(yōu)點(diǎn)。學(xué)號(hào)01 02 03 04 05 06 07 08 09 10性別F M M F M M M F F M年齡21 20 21 22 23 20 21 23 20 21體育成績(jī)A A B A A A B B B A思想品德優(yōu)良優(yōu)優(yōu)良優(yōu)良優(yōu)優(yōu)良發(fā)表論文2 0 0 1 0 2 0 0 1 0平時(shí)成績(jī)95 90 80 80 75 85 95 80 70 80總評(píng)成績(jī)95 85 80 85 70 85 90 75

15、 70 75圖3 學(xué)生總評(píng)成績(jī)的情況在圖4 中,Y表示學(xué)生的總評(píng)成績(jī)?cè)?5 分以上;N表示學(xué)生的總評(píng)成績(jī)?cè)?5 分以下。由圖4 可見(jiàn),方案( ) 構(gòu)造的決策樹(shù)結(jié)構(gòu)好,基本上將總評(píng)成績(jī)?cè)?5 分以上或以下的同類(lèi)學(xué)生劃分到一起,容易得出“如果學(xué)生的平時(shí)成績(jī)?cè)?5 分以上,他的總評(píng)成績(jī)就有100 %的可能在85 分以上”、“如果學(xué)生的平時(shí)成績(jī)?cè)?5 分以下,他的總評(píng)成績(jī)就有5/ 6 即83. 3 %的可能在85 分以下”等規(guī)則信息。(下轉(zhuǎn)第22 頁(yè))· 9 1 · 第8 期唐華松等:數(shù)據(jù)挖掘中決策樹(shù)算法的探討© 1995-2004 Tsinghua Tongfang O

16、ptical Disc Co., Ltd. All rights reserved.和即插即用,共同協(xié)作,形成最終的GIS 應(yīng)用。對(duì)于非GIS 專(zhuān)業(yè)人員而言,可以容易地通過(guò)對(duì)GIS 組件的利用,將GIS 功能嵌入應(yīng)用程序中,大大提高了開(kāi)發(fā)的效率及GIS 應(yīng)用。GIS 的互操作組件特別有利于GIS 專(zhuān)業(yè)人員的是,他們不必要再開(kāi)發(fā)支持專(zhuān)用的開(kāi)發(fā)軟件或數(shù)據(jù)庫(kù),而是將更多的精力集中于GIS 的“G”(地學(xué)應(yīng)用) ,從而使GIS 產(chǎn)品達(dá)到更高的層次。4 討論與展望地理信息及其應(yīng)用是復(fù)雜的。要將現(xiàn)實(shí)世界復(fù)雜的事物、過(guò)程、現(xiàn)象映射到計(jì)算機(jī)中,并依據(jù)人們的需要對(duì)其進(jìn)行處理,并不是一件容易的事情。雖然GIS 界

17、及IT界早已認(rèn)識(shí)到信息共享與互操作的重要性,并做了大量工作致力于它們的實(shí)現(xiàn)。到目前為止,獲得的成果離人們的目標(biāo)還很遠(yuǎn)。在異構(gòu)分布環(huán)境中,GIS 互操作適應(yīng)網(wǎng)絡(luò)化和社會(huì)化的需求,以分布式計(jì)算、面向?qū)ο蠹夹g(shù)、互聯(lián)網(wǎng)絡(luò)技術(shù)、開(kāi)放式數(shù)據(jù)庫(kù)技術(shù)等為支撐,通過(guò)組件技術(shù)來(lái)實(shí)現(xiàn)互操作。而在互操作的實(shí)現(xiàn)過(guò)程中,由于GIS 技術(shù)本身及計(jì)算機(jī)技術(shù)的某些方面的不成熟,目前還不能完全實(shí)現(xiàn)。GIS 技術(shù)本身的局限表現(xiàn)在:只對(duì)復(fù)雜現(xiàn)實(shí)世界的簡(jiǎn)單對(duì)象的特征有清晰的定義和描述,而對(duì)復(fù)雜對(duì)象,如三維、四維、多維的討論較少;地理數(shù)據(jù)具有多重性的特征,在地理數(shù)據(jù)內(nèi)部交換及轉(zhuǎn)換中語(yǔ)義難免有不兼容,用來(lái)實(shí)現(xiàn)數(shù)據(jù)無(wú)損轉(zhuǎn)換的語(yǔ)義轉(zhuǎn)換器在具體

18、實(shí)現(xiàn)中工作難度很大。來(lái)自計(jì)算機(jī)技術(shù)方面的限制主要表現(xiàn)在:作為支撐技術(shù)的分布式計(jì)算技術(shù)和面向?qū)ο蠹夹g(shù)自身尚未完全成熟;OGC 用于互操作規(guī)范組件的連接與通訊的實(shí)現(xiàn)規(guī)范CORBA ,DCOM, SQL 彼此之間不能直接訪問(wèn)。目前對(duì)GIS 互操作研究的基本單位是過(guò)程或?qū)ο?而對(duì)粒度更大的應(yīng)用間的互操作考慮得較少等。目前還沒(méi)有商業(yè)化的GIS 軟件能完全支持GIS 互操作。而在OGC 成員之間已有GIS 互操作實(shí)現(xiàn)的成功實(shí)例。GIS 互操作的實(shí)現(xiàn)將增進(jìn)GIS 與IT 界的協(xié)作能力,這種協(xié)作無(wú)疑給GIS 界造就了新的機(jī)遇、更廣闊的市場(chǎng)、更多的收入。前景是美好的,而地理信息共享和GIS 的互操作的完全實(shí)現(xiàn),

19、由于存在的種種障隘涉及計(jì)算機(jī)領(lǐng)域和GIS 領(lǐng)域的疑難問(wèn)題,需要IT 界和GIS 界的共同努力,還需要很長(zhǎng)時(shí)間。我國(guó)目前在這個(gè)領(lǐng)域的研究還不是很多,有必要對(duì)國(guó)內(nèi)GIS 軟件的互操作進(jìn)行研究,同時(shí)跟蹤OpenGIS 的國(guó)際最新技術(shù)和熱點(diǎn),力爭(zhēng)將我國(guó)的地理信息和GIS 軟件融入到國(guó)際大舞臺(tái)中。參考文獻(xiàn):1 李德仁. 論地理信息學(xué)的形成及其在跨世紀(jì)中的發(fā)展C . 中國(guó)地理信息系統(tǒng)協(xié)會(huì)第二屆年會(huì)論文集,1996 ,10.2 黃裕霞,陳常松,何建邦. GIS 的互操作C . 中國(guó)地理信息系統(tǒng)協(xié)會(huì)、中國(guó)海外地理信息系統(tǒng)協(xié)會(huì)1998 年年會(huì)論文集,1998.3 滿曉麟,王書(shū)慶,石洞. 軟件組件化技術(shù)及其在橋梁CAD中的應(yīng)用J . 計(jì)算機(jī)應(yīng)用研究,2000 ,17(9) :72274.4 Zhong Ershun ,Song Guanfu ,Wang Erqi . Development ofComponents GIS Based on Applications. Proceedings of IEAS97& IWGIS 97C1 1997 , 1.作者簡(jiǎn)介:駱成鳳(19762) ,女,現(xiàn)為南京大學(xué)城市與資源學(xué)系地圖學(xué)與地理信息系統(tǒng)專(zhuān)業(yè)碩士研究生,主要研究方向?yàn)榛ゲ僮餍訥IS ,組件式地理信