模式識別——決策樹算法-文庫吧資料
2025-01-14 09:24本頁面
【正文】 final String patternString = attribute(.*)[{](.*?)[}]。 // 存儲每個屬性的取值 private ArrayListString[] data = new ArrayListString[]()。 public class ID3 { private ArrayListString attribute = new ArrayListString()。決策樹構(gòu)建完成，如圖 (2)所示。這樣就可以分別用這兩個特征構(gòu)建下一級的決策樹 節(jié)點(diǎn)。對于女性組合男性組，用上面的相同的方法，分別考查兩組樣本上如果再采用年齡或月收入作為特征所得的不純度減少。 用同樣的方法，相關(guān)人員又分別計算了采用性別特征、月收入特征作為根節(jié)點(diǎn)所能夠帶來的信息增益 0 9 7 ( g e n d e r )I n f oI n f o ( D )r)G a i n ( g e n d e A ?? ( i n c o m e )I n f oI n f o ( D )e)G a i n ( i n c o m A ?? 相關(guān)人員發(fā)現(xiàn)，用性別作為第一個特 征能夠帶來不純度最大的減小，于是決定用性別特征作為決策樹的根節(jié)點(diǎn)，如圖 (1)所示：所有 16 個樣本被按照性別特征分成了兩組，女性組有 9 個樣本，其中 1 人需要家長接送；男性組有 7 個樣本，其中 3 個人不。對年齡特征的計算方法和結(jié)果是： 如果采用年齡作為根節(jié)點(diǎn)，則把所有樣本分為兩組， 30 歲以下組有 6 人， 1 人需要家長接送； 30 歲以上組有 10 人， 3 人需要家長接送?，F(xiàn)在希望找到一個能夠最有效地劃分買車與不買車兩類的特征 ，也就是希望引入該特征后，能夠使不純度最有效地減少。 顧客編號 年齡 性別 月收入 是否購買 1 10 男 中 否 2 10 女 中 否 3 10 女 中 否 4 10 女 低 否 5 10 男 高 否 6 10 女 低 否 7 10 女 低 否 8 10 女 高 是 9 10 男 中 是 10 10 男 高 否 11 10 女 中 否 12 10 男 低 否 13 10 女 中 否 14 10 男 低 是 15 10 男 中 是 模式識別 —— 決策樹算法 第 6 頁 共 14 頁 16 10 女 低 否 這個例子中，每個屬性都是離散值的，連續(xù)的屬性已經(jīng)被離散化。于是她查閱了有關(guān)資料，決定把年齡以 10 歲為門檻分成兩檔，把收入按照每 月3000 元以下、 30006000 元和 6000 元以上分為低、中、高三檔，這樣，她的數(shù)據(jù)就變成了表如下的形式。 顧客編號 年齡 性別 月收入 是否購買 1 9 男 4000 否 2 11 女 5000 否 3 12 女 3800 否 4 14 女 2022 否 5 8 男 7000 否 6 12 女 2500 否 7 9 女 2022 否 模式識別 —— 決策樹算法 第 5 頁 共 14 頁 8 8 女 9000 是 9 14 男 5000 是 10 9 男 7000 否 11 12 女 4800 否 12 6 男 2800 否 13 12 女 4500 否 14 12 男 2800 是 15 14 男 4000 是 16 15 女 2500 否 面對這些數(shù)據(jù)，她無從下手分析。于是，她收集了某一學(xué)校學(xué)生由家長接送的信息，得到了表如下的數(shù)據(jù)，這就是她的訓(xùn)練樣本集，她的目標(biāo)是建立能夠估學(xué)生是否會由家長接送的決策樹。這等價于按能做“最佳劃分” 的屬性 A劃分，使得完成元組分類還需要的信息最少。即是： ( ) ( ) ( )AGai n A Inf o D Inf o D?? （ 3） Gain(A)告訴我們通過 A的劃分我們得到了多少。所需要的信息越小，劃分的純度越高。為了得到準(zhǔn)確的分類我們還需要多少信息？這個量由下式度量： 1||( ) ( )||v jAjjDIn fo D In fo DD???? （ 2） 項 ||||jDD充當(dāng)?shù)?j個劃分的權(quán)重。這些劃分將對應(yīng)于從節(jié)點(diǎn) N生長出來的分枝。 模式識別 —— 決策樹算法 第 4 頁 共 14 頁 假設(shè)按屬性 A劃分 D中的元組，其中屬性 A根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v個不同值{a1,a2,… ,av}。 這里，我們所具有的信息只是每個類的元組所占的百分比。使用以 2為底的對數(shù)函數(shù)，因?yàn)樾畔⒂枚M(jìn)位編碼。這種方法使對給定元組分類所需的期望測試數(shù)目最小，并確保找到一棵簡單的樹。選擇具有最高信息增益的屬性作為節(jié)點(diǎn) N的分裂屬性。 信息增益度量基于 Claude Shannon在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作。從概念上講，最好的劃分準(zhǔn)則是導(dǎo)致最接近這種情況的劃分。 屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定的類標(biāo)記的訓(xùn)練元組的數(shù)據(jù)劃分 D“最好”地分成個體類的啟發(fā)式方法。其中， D為數(shù)據(jù)劃分； attribute_list是描述元組的屬性列表；Attribute_selection_method指定選擇屬性的啟發(fā)式過程，所選擇的屬性按類“最 好”地區(qū)分元組。這個準(zhǔn)則由分裂屬性和分裂點(diǎn)或分裂子集組成。由數(shù)據(jù)劃分 D 的訓(xùn)練元組產(chǎn)生決策樹。當(dāng)獲取信息時，將不確定 的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。其中的三種度量方法分別是 信息增益、增益率和 Gini指標(biāo)。隨著樹的構(gòu) 建，訓(xùn)練集遞歸地劃分成較小的子集。 ID3采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造。該算法是以 信息論 為基礎(chǔ)，以 信息熵 和 信息增益 度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對數(shù)據(jù)的歸納分類。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策 樹進(jìn)行檢驗(yàn)、校正和修下的過程，主要是用新的樣本數(shù)扼集（稱為測試數(shù)據(jù)集）中的數(shù)據(jù)校驗(yàn)決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準(zhǔn)確性的分枝剪除。第一步，決策樹的生成：由訓(xùn)練樣本集生成決策樹的過程。在葉節(jié)點(diǎn)上，每一個節(jié)點(diǎn)只包含純一類的樣本，不需要再劃分。最上部的節(jié)點(diǎn)是根節(jié)點(diǎn) (這里的“樹”通常是
公司管理相關(guān)推薦
鄂ICP備17016276號-1