【正文】 ting) P(|ine) 由上面的分析可知:age為youth時(shí)提供分類的信息量大,其次是ine,接著是creditrating，最后是student。故必須先選age屬性對(duì)實(shí)例集進(jìn)行分類,接著才是ine、creditrating、student。可得出決策樹(shù)如下圖所示,圖中的數(shù)字表示表1中的ID號(hào)。 　 生成如下決策樹(shù)分類規(guī)則： IF age=“youth” AND student = “no” THEN Class=“N”IF age=“Middleaged” THEN Class=“Y”IF age=“youth” AND student = “yes” THEN Class=“Y”IF age=“old” AND creditrating=“fair” THEN Class=“Y”IF age=“old” AND creditrating=“excellent” THEN Class=“N”例子二：表2性格父母教育程度性別類別內(nèi)向外向外向內(nèi)向外向內(nèi)向外向外向外向內(nèi)向內(nèi)向內(nèi)向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差表2的樣本數(shù)據(jù)集實(shí)例按人員所屬類別分為好、差兩個(gè)類別,并利用基于條件概率的決策樹(shù)算法建立決策樹(shù),對(duì)表2的實(shí)例集進(jìn)行分類。表2中所給的數(shù)據(jù)集中決定人員類別有四個(gè)屬性:性格、父母教育程度、性別,其中性格的屬性值分為內(nèi)向和外向兩個(gè)屬性值；父母教育程度屬性有良、中和差三個(gè)屬性值；性別的屬性有男生和女生兩個(gè)屬性值。對(duì)于類別字段,將人員所屬類別(學(xué)習(xí)成績(jī))分為好和差兩個(gè)類別集。下面分別計(jì)算各屬性值相對(duì)于好的影響度。在表2的數(shù)據(jù)集中,實(shí)例集大小為12,性格取值為內(nèi)向的記錄有6條,取值為外向的記錄有6條；父母教育程度取值為良的記錄有4條,取值為中的記錄有4條，取值為差的記錄有4條；性別取值為男生的記錄有6條，取值為女生的記錄有6條。把人員所屬類別(學(xué)習(xí)成績(jī))看作一個(gè)隨機(jī)變量X,以內(nèi)向(外向)表示性格為內(nèi)向(外向)的事件；以良、中 (差)表示父母教育程度為良、中(差)的事件；以男生（女生）表示性別為男生（女生）的事件。設(shè)P (內(nèi)向|外向)表示性格屬于內(nèi)向的事件發(fā)生的概率。P(好 ,內(nèi)向|外向)為性格屬于內(nèi)向且類別為+的事件發(fā)生的概率。 P(|性格)為性格屬于內(nèi)向人員所屬類別(學(xué)習(xí)成績(jī))為好的條件概率,其余類推,由條件概率的概念可知: P(內(nèi)向|性格) = ；P(外向|性格) = P(良|父母教育程度) = ；P(中|父母教育程度) = ；P(差|父母教育程度) = ；P(男生|性別) = ；P(女生|性別) = ；P(好 ,內(nèi)向|性格) = ；P(好,外向|性格) = ； P(好, 良|家庭背景) = ；P(好, 中家庭背景) = ；P(好, 差|家庭背景) = ；P(好，男生|性別)= P(好,女生|性別) = ；根據(jù)公式：P(B|A) = 有: P(+|正) = ,可以知道每個(gè)屬性對(duì)分類為+影響度:P(|性格) = = ；同理: P(|性格) = = ；P(|父母教育程度) = = 1；P(|父母教育程度) = = ；P(|父母教育程度) = = ；P(|性別) = = ；P(|性別) = = 。比較可得:P(|父母教育程度) P(|性格) P(|性別)由上面的分析可知:父母教育程度為良時(shí)提供分類的信息量大,其次是性格,最后是性別。故先選父母教育程度屬性對(duì)實(shí)例集進(jìn)行分類,接著才是性格、性別。可得出決策樹(shù)如下圖所示。 生成如下決策樹(shù)分類規(guī)則： IF 父母教育程度=“良” THEN 學(xué)習(xí)成績(jī) =“好”IF 父母教育程度=“中”AND 性格=“內(nèi)向” THEN學(xué)習(xí)成績(jī) =“差”IF 父母教育程度=“差”AND 性格=“內(nèi)向” THEN學(xué)習(xí)成績(jī) =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性別=“女生” THEN學(xué)習(xí)成績(jī) =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性別=“男生” THEN學(xué)習(xí)成績(jī) =“好”IF 父母教育程度=“差”AND 性格=“外向”AND 性別=“女生” THEN學(xué)習(xí)成績(jī) =“好”IF 父母教育程度=“差”AND 性格=“外向”AND 性別=“男生” THEN學(xué)習(xí)成績(jī) =“差”由前述研究部分可以看出：ID3算法是一個(gè)很有實(shí)用價(jià)值的學(xué)習(xí)算法,它的基礎(chǔ)理論清晰,算法相對(duì)較簡(jiǎn)單,但也存在著一些缺點(diǎn):(1) 算法往往偏向于選擇取值較多的屬性,而在很多情況下取值較多的屬性并不總是最優(yōu)的屬性,即按照熵值最小的原則被ID3算法列為應(yīng)該首先判斷的屬性在現(xiàn)實(shí)情況中卻并不那么重要。例如:在股票市場(chǎng)中個(gè)股的選擇。而利用基于條件概率決策樹(shù)算法是按從小到大的順序排列的，因此就有畢業(yè)計(jì)算所有屬性的條件概率。(2) 在建樹(shù)時(shí),每個(gè)結(jié)點(diǎn)僅含一個(gè)特征,是一種單變?cè)乃惴?特征間的相關(guān)性不夠緊。雖然在一棵樹(shù)上連在一起,但聯(lián)系還是松散的。(3) ID3對(duì)燥聲比較敏感,不容易除去燥聲,也就是特征值取錯(cuò)或類別給錯(cuò)。通過(guò)精密的設(shè)計(jì)基于條件概率決策樹(shù)算法可以出去燥聲，即一般不會(huì)取錯(cuò)特征值。(4) 當(dāng)訓(xùn)練集增加時(shí),ID3 決策樹(shù)隨之變化。在建樹(shù)過(guò)程中,各特征的相互信息會(huì)隨例子的增加而改變,決策樹(shù)也隨之變化,這對(duì)變化的數(shù)據(jù)集的學(xué)習(xí)是不適合的。(5) ID3 算法雖然理論清晰,但它的計(jì)算比較復(fù)雜,在學(xué)習(xí)和訓(xùn)練數(shù)據(jù)集的過(guò)程中機(jī)器內(nèi)存占用率比較大,比較耗費(fèi)資源,影響數(shù)據(jù)挖掘的時(shí)間和成本。以上實(shí)例證明,在分類問(wèn)題中采用條件概率決策樹(shù)算法能夠極大地降低計(jì)算復(fù)雜性,快速生成決策樹(shù),可以很直觀地得到?jīng)Q策規(guī)則,達(dá)到簡(jiǎn)化決策過(guò)程,它是直接把屬性值和類別結(jié)果相聯(lián)系,通過(guò)比較某一屬性的取值對(duì)分類結(jié)果的影響大小,再比較所有的屬性對(duì)分類結(jié)果的影響大小,很直觀地構(gòu)造出決策樹(shù),在這個(gè)計(jì)算過(guò)程中,計(jì)算的復(fù)雜性很大程度上得到了緩解,對(duì)計(jì)算機(jī)的硬件要求也相應(yīng)降低,同時(shí)也使得決策樹(shù)思想在數(shù)據(jù)挖掘等領(lǐng)域的發(fā)展受計(jì)算機(jī)硬件的限制較小。另外上述實(shí)例也展示了該算法的簡(jiǎn)潔、計(jì)算效率高等特性。從而可以在計(jì)算機(jī)硬件配置較低、資源消耗較少的條件下來(lái)快速生成決策樹(shù),得到相應(yīng)的決策規(guī)則。這較ID3算法又是一個(gè)進(jìn)步。以上討論了利用條件概率的思想來(lái)改進(jìn)決策樹(shù)算法的一些優(yōu)點(diǎn)，但該算法思想還存在一些不足之處：雖然此算法較ID3算法減少了計(jì)算量，但它并沒(méi)有降低ID3算法計(jì)算過(guò)程中的循環(huán)調(diào)用量，相反還有所增加；此算法思想同ID3算法一樣適合小數(shù)量的挖掘，但與挖掘的概念相沖突。因?yàn)橥诰蚓褪菑暮Ａ康臄?shù)據(jù)中提取有用信息。當(dāng)數(shù)據(jù)量較大時(shí)，該算法耗時(shí)與ID3過(guò)憂而無(wú)不及。由上述決策樹(shù)算法的研究和改進(jìn)可知：在一般情況下算法的改進(jìn)都是以犧牲算法的空間復(fù)雜度為代價(jià)的。時(shí)間復(fù)雜度越小，其空間復(fù)雜度相對(duì)來(lái)說(shuō)就高；雖然隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展空間已成為即將被忽略的概念，數(shù)據(jù)也可以不用常駐內(nèi)存，但占有大量空間的算法給程序員帶來(lái)了工作上的負(fù)擔(dān)；給讀者帶來(lái)了極大的困惑，其可讀性較差，有些甚至難以理解；對(duì)算法的有限性要求也是一種挑戰(zhàn)。因此考慮折中的方法來(lái)改進(jìn)決策樹(shù)算法的趨勢(shì)是勢(shì)在必行的。本次畢業(yè)設(shè)計(jì)是對(duì)自己以前所學(xué)知識(shí)的總結(jié)，也是對(duì)新的知識(shí)的探討與研究，在本次畢業(yè)設(shè)計(jì)中使我深刻地體會(huì)到?jīng)Q策樹(shù)在數(shù)據(jù)挖掘應(yīng)用中的作用，也深刻體會(huì)到了算法復(fù)雜性設(shè)計(jì)的重要性，數(shù)據(jù)挖掘改進(jìn)性研究的發(fā)展趨勢(shì)已經(jīng)來(lái)到的，它的前景是不可光明的。此算法中的有關(guān)圖形均由本人以微軟公司的office軟件中的microsoft visio軟件來(lái)制作；數(shù)學(xué)公式有數(shù)學(xué)軟件Mathtype制作。在本次畢業(yè)論文的整個(gè)過(guò)程中我得到了指導(dǎo)老師徐冬老師的精心指導(dǎo)與熱情幫助，在此深表謝意；同時(shí)我也要感謝魏夏鵬同學(xué)能夠借電腦給我做畢業(yè)設(shè)計(jì)；這里還要感謝考研朋友所送的數(shù)學(xué)軟件，在整個(gè)論文過(guò)程中意義重大。參考文獻(xiàn)[1]. 史忠植《知識(shí)發(fā)現(xiàn)》，北京：清華大學(xué)出版社。[2]. 邵峰晶、于忠清《數(shù)據(jù)挖掘原理與算法》，北京：中國(guó)水利水電出版社，2003。[3]. 楊清、楊岳湘《基于決策樹(shù)的學(xué)習(xí)算法》，長(zhǎng)沙：國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院。[4]. 朱紹文、胡宏銀、王泉德、張大斌、黃浩、陸玉昌《決策樹(shù)采掘技術(shù)及發(fā)展趨勢(shì)》，北京、武漢：華中師范大學(xué)電子與計(jì)算機(jī)研究所、清華大學(xué)計(jì)算機(jī)系。[5]. 陳京民《數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)》，北京：電子工業(yè)出版社。[6]. 郭玉濱,《一種基于離散度的決策樹(shù)改進(jìn)算法》，山東菏澤：菏澤學(xué)院計(jì)算機(jī)與信息工程學(xué)系。[7].劉慧巍, 張　雷, 翟軍昌《數(shù)據(jù)挖掘中決策樹(shù)算法的研究及其改進(jìn)》，遼寧錦州：渤海大學(xué)。[8]. 房祥飛,劉希玉《決策樹(shù)在數(shù)據(jù)挖掘中的新進(jìn)展和發(fā)展前景》，山東濟(jì)南：山東師范大學(xué)信息科學(xué)與工程學(xué)院。[9]. (加) Jiawei Han, Micheline Kamber著；范明, 孟小峰等譯《數(shù)據(jù)挖掘：概念與技術(shù)》，北京：機(jī)械工業(yè)出版社，2001。 [10]. (美)Jiawei Han, Micheline Kamber《Data mining,Concepts and techniques》,北京：高等教育出版社，2001。[11]. Richard , Michael 《Data mining a tutoralbased primer》，北京：清華大學(xué)出版社，2003。[12]. 張維東、張凱、董青、孫維華《利用決策樹(shù)進(jìn)行數(shù)據(jù)挖掘中的信息熵計(jì)算》，上海：同濟(jì)大學(xué)計(jì)算機(jī)系。[13]. 黃解軍、潘和平、萬(wàn)幼川《數(shù)據(jù)挖掘技術(shù)的應(yīng)用研究》，武漢：武漢大學(xué)遙感信息工程學(xué)院數(shù)字智能研究中心。[14]. 劉小虎、李生《決策樹(shù)的優(yōu)化算法》，哈爾濱：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)系。[15]. 郭景峰、米浦波、劉國(guó)華《決策樹(shù)算法的并行性研究》，秦皇島：燕山大學(xué)。[16]. 楊名、張載鴻《決策樹(shù)學(xué)習(xí)算法ID3的研究》，北京：北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院, 。[17]. 譚旭、王麗珍、卓明《利用決策樹(shù)發(fā)掘分類規(guī)則的算法研究》，云南：云南大學(xué)計(jì)算機(jī)科學(xué)與工程系，2002。