【文章內(nèi)容簡介】 性將示例集分解成子集后，系統(tǒng)的熵值最小。期望該非葉節(jié)點 到達各后代葉節(jié)點的平均路徑最短，是生成的決策樹平均深度較小，提高分類速度和準確率。 ID3 方法驗證所有的特征，選擇信息增益率最大的特征屬性產(chǎn)生決策樹節(jié)點，由該特征的不同取值建立分支，對各分支的實例子集遞歸，用該方法建立決策樹節(jié)點和分支，直到某一子集中的例子屬于同一類。 ID3 算法描述 ID3 算法的形式化描述如下： 輸入 :樣本 samples,由離散的屬性值表示，候選屬性集合 attribute_list 輸出：一棵決策樹 算法： （ 1）創(chuàng)建節(jié)點 N； （ 2） If samples 都在同一個類 C， then （ 3）返回 N作為葉節(jié)點，以類 C 標記； （ 4） If attribute_list 為空 then （ 5）返回 N作為葉節(jié)點，標記為 samples 中最普遍的類； （ 6）選擇 attribute_list 中具有最高信息增益的屬性 branch_attribute。 （ 7）標記節(jié)點 N為 branch_attribute； （ 8）對于 branch_attribute 中每一個已知值 a。 （ 9）由節(jié)點 N 生成一個條件為 branch_attribute=a 的分支。 算法的流程圖如下所示： 圖 21 ID3算法流程圖 ID3 算法的優(yōu)劣勢 ID3 通過不斷的循環(huán)處理，直至找到一棵完全正確的決策樹，并從頂向下歸納形成了一組類似 IFTHEN 的規(guī)則，允許多于兩個類別，其屬性值可以是整數(shù)或實數(shù)。 ID3 算法有很多的優(yōu)點，總結如下： （ 1）搜索空間是完全的假設空間，目標函數(shù)必在搜索空間只能，不存在無解的危險； （ 2）全部使用訓練數(shù)據(jù)，而不是像候選剪除算法逐個考慮訓練例子，這樣做可以利用全部的訓練例子的統(tǒng)計性質進行決策，從而抵抗噪聲； （ 3）可以生成容易理解的 IFTHEN 分類規(guī)則，即使建立一 棵包含幾百個屬性的大規(guī)模復雜決策，也可以較清晰地理解每一條從根節(jié)點到葉子節(jié)點路徑所描述的含義； （ 4）擅長處理非數(shù)值型數(shù)據(jù)。 ID3 算法也存在著許多的缺點： （ 1） ID3 偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不是最優(yōu)的屬性。關于這個問題，后續(xù)會用增益比率的方法，它將每個屬性取值的概率都考慮在內(nèi) （ 2）當訓練集增加時， ID3 決策樹也隨之變化，決策樹對訓練集變化的敏感性引起了決策樹算法的不穩(wěn)定性問題，這種不穩(wěn)定性的現(xiàn)象也使分類中知識發(fā)現(xiàn)的過程更加復雜； （ 3）同多數(shù)決策樹模型一樣，隨著重復地將 數(shù)據(jù)劃分成越來越小的部分，ID3 決策樹模型面臨著較為嚴重的碎片問題（碎片是指一個給定分支中的樣本數(shù)太小而失去統(tǒng)計意義引）。碎片問題帶來的最直接的影響就是決策樹模型的健壯性降低，并最終降低分類的準確性。一棵健壯的決策樹所表現(xiàn)出來的特征之一是較少的葉子節(jié)點，即每個葉子節(jié)點都有較多的樣本數(shù)。 （ 4）對噪音比較敏感，不容易取出噪聲，也就是特征值錯誤或類別錯誤 （ 5）缺乏伸縮性。由于要進行深度優(yōu)先搜索，所以算法受到內(nèi)存大小的限制，難以處理大訓練集。 ID3 算法分析 算法實現(xiàn)中一般的處理方法是掃描一遍數(shù)據(jù)庫（實 際中保存在本地文件中），直接復制數(shù)據(jù)集到內(nèi)存，這種做法對內(nèi)存的消耗很大。若一棵樹的深度 k,原始數(shù)據(jù)集數(shù)據(jù)量為 n， 每個數(shù)據(jù)的維數(shù)為 m,當數(shù)據(jù)本身為大數(shù)據(jù)時， m 可能很大，則整棵決策樹總的空間復雜度為 O(n*k*m)（最壞情況為深度為 k 的滿樹，即所有葉子節(jié)點都在最下面一層，此時每一層為整個數(shù)據(jù)集的一個劃分）。 算法在構建決策樹的時候，每一個節(jié)點都需要對剩余的實例集進行一次掃描，設 n 為屬性個數(shù)，在樹的每一層中，這些被遍歷子集的并集中的所有實例數(shù)剛好等于整個訓練集中的實例數(shù)目 m，所有對樹中每一層而言，遍歷以時間復雜度 O(mn) 實現(xiàn)，這樣標準決策樹學習算法所具有的時間復雜度即為 O(mn^2 )。在對決策樹進行搜索時，雖然絕大部分情況下為多叉樹，但是近似可用 O(logk)表示。 本章小結 通過 對該算法的核心思想進行分析，主要數(shù)據(jù)結構的解釋以及優(yōu)缺點描述，算法空間時間復雜度等幾個方面來全面總結整個算法 第三章 ID3 算法實現(xiàn) 實驗開發(fā)環(huán)境 （ 1）系統(tǒng)開發(fā)工具： Visual Studio 2021 Visual Studio 是微軟公司推出的開發(fā)環(huán)境，是目前最流行的 Windows 平臺應用程序開發(fā)環(huán)境。相對于其他開發(fā)環(huán)境，使用 VS 開發(fā)有幾個顯著優(yōu)勢：多語言開發(fā)、精簡代碼、直觀代碼風格、快速開發(fā)周期、調(diào)試方便。 （ 2）系統(tǒng)開發(fā)語言： C++ 實驗使用的數(shù)據(jù)結構 為了使整棵決策樹能夠建成并且完成后續(xù)的分類操作，需要自定義樹的節(jié)點信息。經(jīng)過對數(shù)據(jù)集的分析以及對實驗的思考后，自定義的樹結構體如下： 圖 31 自定義樹節(jié)點類圖 其中 attribute 是 string 類型值，記錄需要分類的屬性標簽值；arrived_value 也是 string 類型值，實際中記代的是已經(jīng)到達的分枝 ,，即分 裂的屬性值；向量 childs 裝的是 node 類型的，即分叉節(jié)點的具體信息，提供下一步的搜索起點。 因為需要更好的保存實驗中的每一條記錄，因此構造了如下的數(shù)據(jù)結構： vector vector string state, teststate。 用于保存整個實例集 vector string item(MAXLEN),testitem(MAXLEN)。 對應實例集中的某一行 vector string attribute_row。 保存首行即屬性行數(shù)據(jù) mapstring,vector string map_attribute_values。 存儲屬性對應的所有的值 程序模塊介紹 為了使程序具有更好的可閱讀性以及可維護性，將其所包含的功能包裝成若干函數(shù)，現(xiàn)對各函數(shù)的功能做一個簡單的描述。 數(shù)據(jù)初始化函數(shù) DataInit() 該函數(shù)的主要功能是以文件流的方式將數(shù)據(jù)讀入到內(nèi)存中，向量 vector vector string state 保 存 整 個 數(shù) 據(jù) 集 ， 向 量 vector string attribute_row 保存要分類的屬性，為下一步的決策樹建立做準備。 屬性值映射 函數(shù) MapAttributeValue() 該函數(shù)作用是將讀入的不同屬性值對應到其屬性上。因為在實際的過程中我們往往并不知道屬性對應幾個屬性值以及每個屬性值分別是什么，采用MapAttributeValue()函數(shù)可以很好保障程序的靈活性。此外，在這個函數(shù)中保存的是屬性值的索引值 (int 類型 )，這樣也可以減少對內(nèi)存的需要。 判斷是否到達葉節(jié)點函數(shù) IsReachLeaveNode() 在決策樹構建時判斷某節(jié)點上屬性是否正負性都一致 ,即是否到達葉子節(jié)點，若子集只含有單個屬性，則分支為葉子節(jié)點。 獲取樣例中占多數(shù) 的正 /負性函數(shù) MostCommonLabel() 對剩下實例集的正負性進行掃描投票機制確定最后的葉節(jié)點的屬性值。這個函數(shù)稍加改動也可以變?yōu)楹罄m(xù)的后剪枝操作的可用函數(shù)。 計算熵值函數(shù) Entropy() 信息熵就是一組數(shù)據(jù)包含的信息，概率的度量。一組數(shù)據(jù)越有序信息熵也就越低，極端時如果一組數(shù)據(jù)中只有一個非 0，其它都是 0，那么熵等于 0，因為只有可能是這個非 0的情況發(fā)生，它給人們的信息已經(jīng)確定了，或者說不含有任何信息了，因為信息熵含量為 0。一組數(shù)據(jù)越無序信息熵也就越高，極端時如果一組數(shù)據(jù)均勻分布，則它的熵最大。假如 一組數(shù)據(jù)由 {d1,d2,...,dn}構成，其和是 sum,那么求信息熵的公式是： sumdisumdiDH ni 21 log)( ???? 計算熵值函數(shù) Gain() 已經(jīng)有了熵作為衡量訓練樣例集合純度的標準，