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