【導(dǎo)讀】論文中沒有抄襲他人研究成果和偽造數(shù)據(jù)等行為。與我一同工作的同志。對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。（設(shè)計(jì)）的復(fù)印件和磁盤，允許畢業(yè)論文（設(shè)計(jì)）被查閱和借閱。業(yè)論文（設(shè)計(jì)）。

　　

【正文】 每一個(gè)訓(xùn)練實(shí)例的距離函數(shù)。這又是一項(xiàng)復(fù)雜的計(jì)算。 （ 4）建樹步驟 3中：若要選擇距離函數(shù)最小的訓(xùn)練實(shí)例就要進(jìn)行排序。這個(gè)雖然可以用上面問題（ 2）中的排序算法解決。但也需要花費(fèi)計(jì)算機(jī)的時(shí)間來做。 （ 5）循環(huán)遞歸調(diào)用也需要大量的時(shí)間。 海南師范大學(xué)本科畢業(yè)論文 19 數(shù)理統(tǒng)計(jì)論和條件概率在計(jì)算機(jī)行業(yè)是一門基礎(chǔ)課程，相信大家都學(xué)過這里不做介紹。下面的算法主要是運(yùn)用數(shù)理統(tǒng)計(jì)論和條件概率的基本概念來勾畫出 ID3的改進(jìn)算法的。 借用概率統(tǒng)計(jì)知識(shí)并 由此延伸出以下定義 : 定義 :設(shè) A、 B是事件 ,稱 P(B|A)為事件 A 發(fā)生時(shí)事件 B會(huì)發(fā)生的條件概率 ,并稱這個(gè)條件概率P(B|A)為訓(xùn)練實(shí)例集 A發(fā)生后 ,事件 B對(duì)訓(xùn)練集中某例別的影響度 。 P(B|A) = ()()PABPA 對(duì)于實(shí)例集中的各個(gè)屬性 ,首先計(jì)算所有屬性值的影響度 ,然后進(jìn)行比較 ,可以知道影響度越大的屬性值相對(duì)應(yīng)的屬性提供給分類的信息量就越大 ,依次比較 ,就可以確定屬性對(duì)分類的影響程度大小 ,因此可以根據(jù)此大小來構(gòu)造決策樹的生成算法 。 從前面的理論分 析知 ,條件概率決策樹算法是直接把實(shí)例各屬性與類別結(jié)果相聯(lián)系 ,計(jì)算在分類為某例條件下 ,屬性不同取值對(duì)分類條件的概率 ,通過比較概率的大小判斷屬性對(duì)分類所提供的信息大小 。 下面通過 上述 ID3算法中所列舉 實(shí)例集的手動(dòng)計(jì)算來驗(yàn)證此算法思想 ， 并通過與 ID3算法的比較得出其改進(jìn)性以及其優(yōu)缺點(diǎn) 。 例子一： 表 1 ID age ine student credit_rating Class 1 youth high no fair N 2 youth high no excellent N 3 Middleaged high no fair Y 4 old medium no fair Y 5 old low yes fair Y 海南師范大學(xué)本科畢業(yè)論文 20 6 old low yes excellent N 7 Middleaged low yes excellent Y 8 youth medium no fair N 9 youth low yes fair Y 10 old medium yes fair Y 11 youth medium yes excellent Y 12 Middleaged medium no excellent Y 13 Middleaged high yes fair Y 14 old medium no excellent N 表 1的樣本數(shù)據(jù)集實(shí)例按人員所屬類別分為 N、 Y兩個(gè)類別 ,并利用基于條件概率的決策樹算法建立決策樹 ,對(duì)表 1的實(shí)例集進(jìn)行分類 。 表 1中所給的數(shù)據(jù)集中決定人員類別有四個(gè)屬性 :age、 ine、student、 creditrating,其中 age的屬性值分為 youth、 Middleaged和 old兩個(gè)屬性值 ； ine屬性有 high、 medium和 low三個(gè)屬性值 ； student的屬性有 no和 yes兩個(gè)屬性值； creditrating屬性有fair和 excellent兩個(gè)屬性值。 對(duì)于類別字段 ,將人員所屬類別 (Class)分為 N和 Y兩個(gè)類別集 。 下面分別計(jì)算各屬性值相對(duì)于 Y的影響度 。 在表 1的數(shù)據(jù)集中 ,實(shí)例集大小為 14,age取值為 youth的記錄有 5條 ,取值為 Middleaged的記錄有 4條，取值為 old的有 5條 ； ine取值為 high的記錄有 4條 ,取值為 medium的記錄有 6條， 取值為 low的記錄有 4條 ； student取值為 no的記錄有 7條，取 值為 yes的記錄有 7條； creditrating取值為 fair的記錄有 8條，取值為 excellent的記錄有 6條。 把人員所屬類別 (Class)看作一個(gè)隨機(jī)變量 X,以youth、 Middleaged (old)表示 age為 youth、 Middleaged (old)的事件 ； 以 high、 medium (low)表示 ine為 high、 medium (low)的事件 ；以 no（ yes）表示 student為 no（ yes）的事件；以 fair（ excellent）表示 creditrating為 fair（ excellent）的事件。 設(shè) P (youth|old)表示年齡屬于 youth的事件發(fā)生的概率 。P(N ,youth|age)為年齡屬于 youth且類別為 N的事件發(fā)生的概率 。 P( Nyouth|年齡 )為年齡屬于 youth 人員所屬類別 (Class)為 N的條件概率 ,其余類推 ,由條件概率的概念可知 : 海南師范大學(xué)本科畢業(yè)論文 21 P(youth|age) = 514； P(Middleaged|age) = 414 P(old|age) = 514； P(high|ine) = 414； P(medium|ine) = 614 P(low|ine) = 414 ； P(no|student) = 714 ； P(yes|student) = 714 ； P(fair|creditrating) = 814 ； P(excellent|creditrating) = 614 ； P(N ,youth|age) = 314 ； P(N , Middleaged|age) = 0； P(N ,old|age) = 214 ； P(N,high|ine) = 214 ； P(N , medium | ine) = 214 P(N,low|ine)= 114 海南師范大學(xué)本科畢業(yè)論文 22 P(N ,no|student) = 414； P(N ,yes|student) = 114； P(N,fair|creditrating) = 214； P(N,excellcent|creditrating)= 314 根據(jù)公式： P(B|A) = ()()PABPA有 : P(+|正 ) = ( , )()PP?正正, 可以知道每個(gè)屬性對(duì)分類為 N的影響度 : P( Nhigh|ine) = P( N ,hig h| in e)P( hig h| in e) = 12 ； 同理 : P( diNme um |ine) = 12 ； P( Nlow |ine) = 14 ； P( Nyouth|age) = 35 ； P(MiddleagedN|age) = 0； P( Nold |age) = 25 ； P(Nno |student) = 47 ； P( Nyes|student) = 17 ； 海南師范大學(xué)本科畢業(yè)論文 23 P( Nfair|creditrating) = 14； P( Nexcellent|creditrating) = 12。 比較可得 : P( Nyouth|age) Nno|student) P( Nexcellcent|creditrating) P( Nhigh|ine) 由上面的分析可知 :age為 youth時(shí)提供分類的信息量大 ,其次是 ine,接著是 creditrating，最后是 student。 故必須先選 age屬性對(duì)實(shí)例集進(jìn)行分類 ,接著才是 ine、 creditrating、 student?？傻贸鰶Q策樹如下圖所示 ,圖中的數(shù)字表示表 1中的 ID號(hào) 。 根 結(jié) 點(diǎn) （ 1 ，2 ， . . . ， 1 4 ） a g e結(jié) 點(diǎn) 3（ 4 , 5 , 6 , 1 0 , 1 4 ）c r e d i t r a t i n g結(jié) 點(diǎn) 1（ 1 , 2 , 8 , 9 , 1 1 , ）s t u d e n tyoutholdMiddleaged結(jié) 點(diǎn) 2（ 3 , 7 , 1 2 , 1 3 ）s t u d e n tnoyes結(jié) 點(diǎn) 4（ 1 , 2 , 8 ）結(jié) 點(diǎn) 5（ 9 , 1 1 , ）noyes結(jié) 點(diǎn) 6（ 4 , 5 , 1 0 ）結(jié) 點(diǎn) 7（ 6 , 1 4 ）NYYNY 生成如下決策樹分類規(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)向 良 女生 好 海南師范大學(xué)本科畢業(yè)論文 24 外向 外向 內(nèi)向 外向 內(nèi)向 外向 外向 外向 內(nèi)向 內(nèi)向 內(nèi)向 良 中 差 中 良 差 差 良 中 中 差 男生 女生 女生 男生 男生 女生 男生 女生 女生 男生 男生 好 差 差 好 好 好 差 好 差 差 差 表 2的樣本數(shù)據(jù)集實(shí)例按人員所屬類別分為 好 、 差 兩個(gè)類別 ,并利用基于條件概率的 決策樹算法建立決策樹 ,對(duì)表 2的實(shí)例集進(jìn)行分類 。 表 2中所給的數(shù)據(jù)集中決定人員類別有四個(gè)屬性 :性格 、 父母教育程度 、性別 ,其中 性格 的屬性值分為 內(nèi)向和外向 兩個(gè)屬性值 ； 父母教育程度 屬性有良 、中 和差三個(gè)屬性值 ；性別的屬性有男生和女生兩個(gè)屬性值。 對(duì)于類別字段 ,將人員所屬類別 (學(xué)習(xí)成績 )分為 好 和 差 兩個(gè)類別集 。 下面分別計(jì)算各屬性值相對(duì)于 好 的影響度 。 在表 2的數(shù)據(jù)集中 ,實(shí)例集大小為 12,性格 取值為 內(nèi)向 的記錄有 6條 ,取值為 外向 的記錄有 6條 ； 父母教育程度 取值為 良 的記錄有 4條 ,取值為 中 的記錄有 4條， 取值為 差 的記錄有 4條 ； 性別 取值為 男 生的記錄有 6條，取值為 女生 的記錄有 6條。 把人員所屬類別 (學(xué)習(xí)成績 )看作一個(gè)隨機(jī)變量 X,以 內(nèi)向 (外向 )表示 性格 為 內(nèi)向 (外向 )的事件 ； 以 良 、 中 (差 )表示 父母教育程度 為 良 、 中 (差 )的事件 ；以 男生（ 女生 ）表示 性別 為 男生 （ 女生 ）的事件。 設(shè) P (內(nèi)向 |外向 )表示性格 屬于 內(nèi)向 的事件發(fā)生的概率 。P(好 ,內(nèi)向 |外向 )為 性格 屬于 內(nèi)向 且類別為 +的事件發(fā)生的概率 。 P( 好內(nèi) 向|性格 )為性格 屬于 內(nèi)向 人員所屬類別 (學(xué)習(xí)成績 )為 好 的條件概率 ,其余類推 ,由條件概率的概念可知 : P(內(nèi) 向 |性格 ) = 612 ； P(外向 |性格 ) = 612 P(良 |父母教育程度 ) = 412 ； 海南師范大學(xué)本科畢業(yè)論文 25 P(中 |父母教育程度 ) = 412； P(差 |父母教育程度 ) = 412； P(男生 |性別 ) = 612； P(女生 |性別 ) = 612； P(好 ,內(nèi)向 |性格 ) = 212 ； P(好 ,外向 |性格 ) = 412 ； P(好 , 良 |家庭背景 ) = 412 ； P(好 , 中家庭背景 ) = 112 ； P(好 , 差 |家庭背景 ) = 112 ； P(好 ， 男生 |性別 )= 312 P(好 ,女生 |性別 ) = 312 ； 根據(jù)公式： P(B|A) = ()()PABPA有 : P(+|正 ) = ( , )()PP?正正, 可以知道每個(gè)屬性對(duì)分類為 +影響度 : P( 好內(nèi) 向|性格 ) = P( , | )P( | )好 內(nèi) 向 性 格內(nèi) 向 性 格 = 13 ； 同理 : P( 好外 向|性格 ) = P( , | )P( | )好 外 向 性 格外 向 性 格 = 23 ； 海南師范大學(xué)本科畢業(yè)論文 26 P(好良|父母教育程度 ) = P( , | )P( | )好 良 父 母 教 育 程 度良 父 母 教 育 程 度 = 1； P(好中|父母