專題講座-ID3算法簡介

1、ID3 ID3 算法簡介算法簡介郭向丹 謝宗汛LOGOLOGO 隨著信息技術(shù)的飛速發(fā)展, 數(shù)據(jù)量也以驚人的速度增長, 如何從這些大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中提取隱含在其中的有用信息呢? 數(shù)據(jù)挖掘技術(shù)數(shù)據(jù)挖掘技術(shù)便應運而生。 數(shù)據(jù)挖掘是指從大量結(jié)構(gòu)化和非結(jié)構(gòu)的數(shù)據(jù)中提取有用的信息和知識的過程, 是知識發(fā)現(xiàn)的有效手段。 數(shù)據(jù)分類是數(shù)據(jù)挖掘中的一個重要問題，指的是通過分析訓練集中的數(shù)據(jù)，對類建立分類模型，利用分類模型預測類標記未知的對象類。數(shù)據(jù)分類技術(shù)主要有：決策樹決策樹歸納、貝葉斯分類和貝葉斯網(wǎng)絡、神經(jīng)網(wǎng)絡算法、遺傳算法等。 ID3ID3算法算法是決策樹構(gòu)造中的經(jīng)典算法。LOG

2、OLOGO1、ID3算法基本思想2、相關(guān)定義3、ID3應用舉例4、ID3算法缺陷和改進LOGOLOGO 算法核心思想是：檢測所有的屬性，選擇信息增益最大的屬性作為決策樹節(jié)點，由該屬性的不同取值建立分支，再對各分支的子集遞歸地調(diào)用該方法建立決策樹節(jié)點的分支，直到所有子集僅包含同一類別的數(shù)據(jù)位置。最后得出屬性和類別間的關(guān)系，得到一棵決策樹，用來對新樣本進行分類。ID3算法基本思想LOGOLOGOID3算法基本思想 在一實體世界中，每個實體用多個屬性來描述。每個屬性限于在在一實體世界中，每個實體用多個屬性來描述。每個屬性限于在一個離散集中取互斥的值。例如，設實體是某天早晨，分類任務一個離散集中取互斥

3、的值。例如，設實體是某天早晨，分類任務是關(guān)于氣候的類型，屬性如下。是關(guān)于氣候的類型，屬性如下。 某天早晨氣候描述為：天氣多云；氣溫冷；濕度正常；風無風某天早晨氣候描述為：天氣多云；氣溫冷；濕度正常；風無風 需要用某個原則來判定，這個原則來自于大量的實際例子，從例需要用某個原則來判定，這個原則來自于大量的實際例子，從例子中總結(jié)出原則。子中總結(jié)出原則。 每個實體在世界中屬于不同的類別，為簡單起見，假定僅有每個實體在世界中屬于不同的類別，為簡單起見，假定僅有兩個兩個類別，分別為類別，分別為P P、N N。在這種兩個類別的歸納任務中，。在這種兩個類別的歸納任務中，P P類和類和N N類的類的實體分別稱

4、為概念的實體分別稱為概念的正例正例和和反例反例。將一些已知正例和反例放在一。將一些已知正例和反例放在一起便得到起便得到訓練集訓練集。LOGOLOGOID3算法基本思想LOGOLOGOID3算法基本思想晴晴多云多云雨雨P(guān) P高高正常正常P PN NN NP P有風有風濕度濕度風風天氣天氣ID3ID3決策樹決策樹LOGOLOGO相關(guān)定義1、類別屬性的信息熵：設S 是s個訓練數(shù)據(jù)樣本的集合。假定類標號屬性具有m個不同值, 定義m 個不同類Ci,i=1,m,si是類Ci中的樣本數(shù)。一個給定的樣本分類所需的期望信息:2、期望熵：設屬性A 具有v個不同值a1, a2,av, 可以用屬性A 將S 劃分為v個

5、子集S1, S2,Sv。Sj 中的樣本在屬性A上具有相同的值aj,j =1,2,v,sij 是子集Sj中類Ci的樣本數(shù)，由A劃分成子集的期望信息:LOGOLOGO3、信息增益：由前面的定義得出的信息熵為：4、屬性A上分支將獲得信息增益為： ID3算法對每個節(jié)點中選擇信息增益最大的屬性A作為測試屬性。信息增益越大，說明選擇測試屬性A實德隊結(jié)果劃分的樣本分類所需信息量最小，對分類提供的信息越多，并確保得到一顆簡單的樹。相關(guān)定義LOGOLOGOID3應用舉例 一個預測貸款申請者是否會按時還貸款的實例。表1給出影響按時還款的幾個相關(guān)指標的數(shù)據(jù)集合,它有4個屬性:擁有車輛情況、婚姻情況、父母收入情況、申

6、請者收入情況, 這4個屬性被分為是(正例)和否(反例)兩類LOGOLOGOID3應用舉例 假設從樣本數(shù)據(jù)集中取100個樣本,其中類“是”有45個樣本,類“否”有55個樣本。依據(jù)公式 計算出開始時熵值為:0.9928。 依據(jù)公式 得出擁有車輛情況、婚姻情況、父母收入情況、申請者收入情況4個屬性的信息熵分別為:0.866、0.5392、0.878、0.8328。LOGOLOGOID3應用舉例 由于婚姻情況屬性具有最小信息熵, 再依據(jù)公式 可知它具有最大的信息增益,因此它被作為測試屬性,創(chuàng)建節(jié)點婚姻情況,并對每個屬性值引出一個分支,樣本數(shù)據(jù)據(jù)此劃分。每一個分支按照以上方法遞歸計算,最后得出的決策樹如圖所示。LOGOLOGOID3應用舉例LOGOLOGOID3算法缺陷和改進ID3算法缺陷: 1、不能增量地接受訓練例,使得每增加一次實例都必須廢除原有決策樹,重新計算信息增益并構(gòu)造新的決策樹,造成極大的開銷; 2、只能處理離散屬性,對于連續(xù)型的屬性,在分類前需要對其進行離散化的處理;在建樹時每個結(jié)點僅含一個特征，是一種單變元算法,特征間的相關(guān)性強調(diào)不夠; 3、對噪聲較為敏感,數(shù)據(jù)質(zhì)量差將直接導致生成的決策樹過于龐大或決策樹中很多分支的信息量很小; 4、在建樹的過程中選擇一個新屬性時,算法只考慮該屬性帶來的信