【正文】 把人員所屬類別 (學習成績 )看作一個隨機變量 X,以 內向 (外向 )表示 性格 為 內向 (外向 )的事件 ； 以 良 、 中 (差 )表示 父母教育程度 為 良 、 中 (差 )的事件 ；以 男生（ 女生 ）表示 性別 為 男生 （ 女生 ）的事件。 比較可得 : P( Nyouth|age) Nno|student) P( Nexcellcent|creditrating) P( Nhigh|ine) 由上面的分析可知 :age為 youth時提供分類的信息量大 ,其次是 ine,接著是 creditrating，最后是 student。 表 1中所給的數據集中決定人員類別有四個屬性 :age、 ine、student、 creditrating,其中 age的屬性值分為 youth、 Middleaged和 old兩個屬性值 ； ine屬性有 high、 medium和 low三個屬性值 ； student的屬性有 no和 yes兩個屬性值； creditrating屬性有fair和 excellent兩個屬性值。 （ 5）循環(huán)遞歸調用也需要大量的時間。 （ 2）建樹步驟 1中：要將歸一化后的數據進行從小到大的升序排序，這又要選擇一種排序方法。 4)對不含同一類樣本的子集 ,遞歸調用建樹算法 。 總離散度 ST 定義為： 211 ( ) ( )NT i iiS X XN ???? ? ?? （ 4） 根據離散度的概念 ,推導出樣本類內離散度定義 :樣本與樣本均值的方差 ,若考慮先驗概率 ,可以定義如下： 2,11( ( ) )iSn kw j i i jikS P x ??????? （ 5） ip 表示第 i類的先驗概率 ,即 ii sp s? ,S表示訓練集的總的樣本數 。 我們按照下式對離散 的數據進行歸一化處理 ,歸一化后的結果將限制在 [0 ,1 ] 范圍之內。 但在一般情況下不能保證相同 ,因而計算訓練集的互信息就有偏差 。對于給定的描述語言，如果決策樹是單變量（ univariate）的，那么決策樹的復雜程度主要由樹的結點個數決定；如果是多變量海南師范大學本科畢業(yè)論文 15 （ multivariare）的，則主要是由結點中屬性的總個數決定。所以一般并不采用這種方法，而是采取用訓練實例集本身來估計訓練算法的有效性。他們提出，當一個算法過高估計增加樹的復雜性對于分類的正確性的貢獻，那么就會出現(xiàn)過學習現(xiàn)象。所以，也可以如下定義過學習。如果預先字段所要學習的函數屬于整個假設空間中一個很小子集，那么即使在訓練實例不完整的情況下，我們也有可能從訓練實例集喪鐘學習有用的假設，來使得它能夠對未知的實例進行正確分類。 這樣經過重組、變異算子運算得到的新的決策樹需要進行結構上的完整性和一致性處理。 (2) 同一棵樹的兩個結點互相交換。由于適者生存的特點 ,使得適應性較優(yōu)的 決策樹能盡量保留 ,又由于它提供了對決策樹的調整和重新組合的機制 ,使得有更優(yōu)適應性的決策樹在進發(fā)過程中出現(xiàn)。每一個方案的優(yōu)劣程度即為適應性 (fit2ness),根據自然界進化的“優(yōu)勝劣汰”的原則 ,逐步產生出它們的后代 ,使后 代具有更強的適應性。但是 CN 如下 不足 之處 : 海南師范大學本科畢業(yè)論文 12 第一 , ,在構造樹的內部結點的時候是局部最優(yōu)的搜索方式。它采用的具體方法是 :計算規(guī)則對其使用的各個訓練例分類的精度 a ,然后計算這個精度的二項分布的標準差 s ,最后對給定信任度 (95 %)， 取下界 ()為該規(guī)則的性能度量 pa； 在有大量數據的情況下 ,s接近于 0,pa接近于 a ； 隨著數據量的減少 ,pa與 a的差別將會增大。其搜索無回溯它可能收斂于局部最優(yōu)解而丟失全局最優(yōu)解 ,因為一個一個地考慮訓練例 ,不容易象剪除算法那樣使用新例步進式地改進決策樹。 這是 ID3算法的最大缺點。 對“性別”來說 :Gain( Es,性別 ) = 0 。例子集中共有 12 名學生 ,如表 2所示。由此可知 age在屬性中的信息增益最高，故選它做為測試屬性。 age的取值為 youth、 Middleaged、 old； Ine的取值為 high、 medium和 low；海南師范大學本科畢業(yè)論文 6 student的取值為 no和 yes； creditrating的取值為 fair和 excellent。有的對生成的決策樹進行剪枝處 理 。若以屬性 A 作為決策樹的根 , A 具有 V 個值 1V ,2V ,? ,nV ,它將 E 分成 V 個子集 [ 1E , 2E ,? , vE ] ,假設 iE 中含有 j類樣本的個數為 ijp ,j = 1,2,? ,c那么 ,子集 jE 的信息量是 I( iE )。 ID3 的基本原理如下 :設 E = F1 F2 ? Fn 是 n 維有窮向量空間 ,其中 jF 是有窮離散符號集 , E中的元素 e = 1V , 2V ,? ,nV 叫做例子 ,其中 jV ∈ jF , j = 1 ,2 , ? , n。 ID3 算法的關鍵是確定屬性表As中可對訓練實例集 Es進行的最佳分類的屬性 A ,即在樹的每一個節(jié)點上確定一個候選屬性 ,它的測試對訓練例的分類最有利。也可能是多變量的。它代表一個假設 ,可以寫成邏輯公式。 （ 2）信息熵。它的一般操作是泛化（ generalization）和特化（ specialization）。同時，還存在數據的 “ 缺值 ” 處理問題。數據挖掘有廣義和狹義之分，廣義的數據挖掘，指從大量的數據中發(fā)現(xiàn)隱藏的、內在的和有用的知識或信息的過程。 Improvement 隨著現(xiàn)代信息技術的 飛速 發(fā)展，在全球 范圍 內掀起了信息化 （ Information） 浪潮。 本論文主要對決策樹的常見算法做初步的研究與探討，并給出決策樹的評價標準。 論文（設計）作者簽名： 日期： 2021年 5 月 21日 本科生畢業(yè)論文（設計）使用授權聲明 海南師范大學有權保留并向國家有關部門或機構送交畢業(yè)論文（設計）的復印件和磁盤，允許畢業(yè)論文（設計）被查閱和借閱。s thought, finally proposes a Propose his viewpoint and the view. Key words: Data Mining。 自 數據挖掘技術誕生以來，關于數據挖掘技術的研究也就開始了。決策樹方法的最大優(yōu)點就是可理解性，比較直觀。 歸納學習 (induction Learning) 是符號學習中研究最為廣泛的一種方法。他提出了一系列概念： 海南師范大學本科畢業(yè)論文 3 （ 1）自信息量。設 X對應信源符號，Y對應信源符號，為當 Y為時 X為的概率，則有： H（ X/Y） = 11 ( ) lo g ( / )rsi j i jij p a b a b???? （ 4）平均互信息量。因此 ,一棵決策樹可以看作是 — 個對目標分類的劃分和獲取策略。 因為決策樹有不同的等價表示形式，所以會有不同的算法來實現(xiàn)與決策樹學習相同的功能。該算法是根據屬性集的取值選擇實例的類別。對 的不同的取值對應的 E 的 v個子集 iE 遞歸調用上述過程 ,生成的子結點 , 12,BB ? ， VB 。因而許多學者致力于尋找更優(yōu)的啟發(fā)式函數和評價函數 ,洪家榮、 Pei Lei Tu等人分別證明了要找到這種最優(yōu)的決策樹是 NP難題。盡管作者用一個實驗證明能建立理想的決策樹 ,但算法有較大的弱點 :時間開銷太大 ,因為每選擇一個新的屬性 ,算法都需要建立 3 棵決策樹 ,從中選優(yōu)。需要觀察 age的每個樣本值的 Y和 N的分布。性格的取 值為外向、內向。當 v =“外向”時 ,有 4 名“外向”小學生是“學習成績好”的 ,有 2 名“外向”小學生是“學習成績差”的。 父 母 教 育 程 度良差中內 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內 向 ， 中 ， 女 生 ： 差內 向 ， 中 ， 男 生 ： 差內 向 ， 差 ， 女 生 ： 差內 向 ， 差 ， 男 生 ： 差性 格內 向外 向外 向 ， 中 ， 男 生 ： 好外 向 ， 中 ， 女 生 ： 差性 格內 向外 向外 向 ， 差 ， 女 生 ： 好外 向 ， 差 ， 男 生 ： 差 海南師范大學本科畢業(yè)論文 10 按“性格”作第二次劃分后的決策樹 現(xiàn)在只有“ 父母教育程度 ”為“中”和“差”的“外向”小學生還沒有明確類別 ,它們要用屬性“性別”來進一步劃分。全盤使用訓海南師范大學本科畢業(yè)論文 11 練數據 ,而不是像候選剪除算法一個一個地考慮訓練例。根據放在結點的信息 ,就可以判斷出哪個屬性的訓練例集 Es值最小 ,從而確定當前用哪一個屬性來進行劃分。 例如 “窗口”( Windows ) 的概念 ,先從所有的事例中選取一部分用做構造決策樹 ,再利用剩余的事例測試決策樹并對它進行調整。 GA(Geic Algorithm) 遺傳算法是一種通用搜索算法。 群體搜索策略和個體之間的信息交換是遺傳算法的兩大特點 ,主要表現(xiàn)在全局最優(yōu)性和潛在的并行性。 復制算子的定義與常用的復制算子的定義一致。 (2) 改變屬性值的分組情況。下面，給出評價決策樹的一些標準。當有過多的假設與訓練實例集相一致的時候，則成為過學習。()Derror h 一般將 ()trainerror h 成為重替換（ resubstitution）錯 誤率，在本書中將其簡記為 r錯誤率。Cohen和 Jensen利用事后剪枝的方法驗證了他們的理論。 4．余一有效性（ leaveoneout validation） 這種有效性的度量與交叉有效性類似，不同之處在于將每個 iT 的大小定為 1。 目前決策樹技術的主要研究方向 [8]有以下幾點 : 1 決策樹算法的并行性研究 2 尋找新的構造決策樹的方法 3 尋找更好的簡化決策樹的方法 4 研究產生決策樹的訓練和檢驗數據的大小及特性與決策樹特性之間的關系 5 不確定環(huán)境下決策樹研究 6 將決策樹用于多智能體控制并不多見 7 決策樹時間復雜度與準確性之間的矛盾 8 決策樹技術的軟件實現(xiàn) 由以上討論可知： ID3算法存在種種缺陷，如：算法的計算時間是例子個數、特征個數、節(jié)點個數 之積的線性函數 。 其中 ,Si表示第 i類總的樣本數 , kijX 表示第 i類第 k個樣本在第 j維特征處的取值 。 設 a 是 d維空間中所選的中心點 ,從聚類的 N個點中取出 d個點 ,以a 為引點 ,作一個超平行四邊形 。 海南師范大學本科畢業(yè)論文 18 根據上述特征選擇方法 ,在 ID3算法的基礎上 ,提出一種改進的決策樹建樹算法 ,算法步驟如下 : 1)將訓練集窗口中的全部數據 ,選擇一種歸一化方法 ,歸一化到 [0 ,1 ]區(qū)間 ,形成訓練集 D。 （ 2）分類的錯誤率 :這種基于離散度的改進算法分類的錯誤率要低于 ID3算法分類的錯誤率 。 （ 4）建樹步驟 3中：若要選擇距離函數最小的訓練實例就要進行排序。 從前面的理論分 析知 ,條件概率決策樹算法是直接把實例各屬性與類別結果相聯(lián)系 ,計算在分類為某例條件下 ,屬性不同取值對分類條件的概率 ,通過比較概率的大小判斷屬性對分類所提供的信息大小 。 設 P (youth|old)表示年齡屬于 youth的事件發(fā)生的概率 。 對于類別字段 ,將人員所屬類別 (學習成績 )分為 好 和 差 兩個類別集 。 P( 好內 向|性格 )為性格 屬于 內向 人員所屬類別 (學習成績 )為 好 的條件概率 ,其余類推 ,由條件概率的概念可知 : P(內 向 |性格 ) = 612 ； P(外向 |性格 ) = 612 P(良 |父母教育程度 ) = 412 ； 海南師范大學本科畢業(yè)論文 25 P(中 |父母教育程度 ) = 412； P(差 |父母教育程度 ) = 412； P(男生 |性別 ) = 612； P(女生 |性別 ) = 612； P(好 ,內向 |性格 ) = 212 ； P(好 ,外向 |性格 ) = 412 ； P(好 , 良 |家庭背景 ) = 412 ； P(好 , 中家庭背景 ) = 112 ； P(好 , 差 |家庭背景 ) = 112 ； P(好 ， 男生 |性別 )= 312 P(好 ,女生 |性別 ) = 312 ； 根據公式： P(B|A) = ()()PABPA有 : P(+|正 ) = ( , )()PP?正正, 可以知道每個屬性對分類為 +影響度 : P( 好內 向|性格 ) = P( , | )P( | )好 內 向 性 格內 向 性 格 = 13 ； 同理 : P( 好外 向|性格 ) = P( , | )P( |