模式識(shí)別——決策樹算法-文庫吧
2024-12-24 09:24 本頁面
【正文】 一般情況下，訓(xùn)練樣本 數(shù)據(jù)集 是根據(jù)實(shí)際需要有歷史的、有一定綜合程度的，用于數(shù)據(jù)分析處理的數(shù)據(jù)集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策 樹進(jìn)行檢驗(yàn)、校正和修下的過程，主要是用新的樣本數(shù)扼集（稱為測試數(shù)據(jù)集）中的數(shù)據(jù)校驗(yàn)決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準(zhǔn)確性的分枝剪除。 二 ID3 算法描述 ID3算法是由 Quinlan 首先提出的。該算法是以 信息論 為基礎(chǔ)，以 信息熵 和 信息增益 度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對數(shù)據(jù)的歸納分類。 ID3算法主要針對屬性選擇問題，是決策樹學(xué)習(xí)方法中最具影響和最為典型的算法。 ID3采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造。 大多數(shù)決策樹歸納算法都沿用 這種自頂向下的方法，從訓(xùn)練元組集和它們的相關(guān)聯(lián)的類標(biāo)號開始構(gòu)造決策樹。隨著樹的構(gòu) 建，訓(xùn)練集遞歸地劃分成較小的子集。 ID3算法中關(guān)鍵的一步是屬性選擇度量，即選擇分裂準(zhǔn)則。其中的三種度量方法分別是 信息增益、增益率和 Gini指標(biāo)。 (示例算法選擇了第一種方法 )。當(dāng)獲取信息時(shí)，將不確定 的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。 算法的基本策略如下： 算法： Generate_decision_tree。由數(shù)據(jù)劃分 D 的訓(xùn)練元組產(chǎn)生決策樹。 輸入： D 是訓(xùn)練元組和對應(yīng)類標(biāo)號的集合 ，候選屬性的集合 ，一個(gè)確定 “ 最好 ” 地劃分?jǐn)?shù)據(jù)元組為個(gè)體類的分裂準(zhǔn)則的過程。這個(gè)準(zhǔn)則由分裂屬性和分裂點(diǎn)或分裂子集組成。 輸出：一棵決策樹 模式識(shí)別 —— 決策樹算法 第 3 頁 共 14 頁 方法： 創(chuàng)建一個(gè)節(jié)點(diǎn) N； if D 中的元組都是同一類 C， then 返回 N 作為葉節(jié)點(diǎn)，以類 C 標(biāo)記； if attribute_list 為空 then 返回 N 作為葉節(jié)點(diǎn)，標(biāo)記為 D 中的多數(shù)類； //多數(shù)表決 使用 Attribute_selection_method（ D， attribute_list），找出“最 好”的splitting_criterion； 7 用 splitting_criterion 標(biāo)記節(jié)點(diǎn) N； if splitting_ attribute 是離散值的并且允許多路劃分 then //不限于二叉樹 attribute_list ? attribute_list splitting_ attribute ； //刪除劃分屬性 for splitting_criterion 的每個(gè)輸出 j // 劃分元組并對每個(gè)劃分產(chǎn)生子樹 設(shè) Dj 是 D 中滿足輸出 j 的數(shù)據(jù)元組的集合； //一個(gè)劃分 if Dj 為空 then 加一個(gè)樹葉到節(jié)點(diǎn) N，標(biāo)記為 D 中的多數(shù)類； else 加一個(gè)由 Generate_decision_tree（ Dj， attribute_list）返回的節(jié)點(diǎn)到節(jié)點(diǎn) N； end for 返回 N； 上述算法基本策略中，用到三個(gè)參數(shù) D、 attribute_list和 Attribute_selection_method調(diào)用該算法。其中， D為數(shù)據(jù)劃分； attribute_list是描述元組的屬性列表；Attribute_selection_method指定選擇屬性的啟發(fā)式過程，所選擇的屬性按類“最 好”地區(qū)分元組。該過程使用一種屬性選擇度量，如 信息增益和 Gini指標(biāo) 。 屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定的類標(biāo)記的訓(xùn)練元組的數(shù)據(jù)劃分 D“最好”地分成個(gè)體類的啟發(fā)式方法。如果我們要根據(jù)分裂準(zhǔn)則的輸出將 D劃分成較小的劃分，理想地，每個(gè)劃分是“純”的，即，落在給定劃分的所有元組都屬于相同的類。從概念上講，最好的劃分準(zhǔn)則是導(dǎo)致最接近這種情況的劃分。本文主要介紹一種流行的屬性選擇度量 —— 信息增益。 信息增益度量基于 Claude Shannon在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作。設(shè)節(jié)點(diǎn) N代表或存放 劃分 D的元組。選擇具有最高信息增益的屬性作為節(jié)點(diǎn) N的分裂屬性。該屬性使結(jié)果劃分中的元組分類所需的信息量最小，并反映這些劃分中的最小隨機(jī)性或“不純性”。這種方法使對給定元組分類所需的期望測試數(shù)目最小，并確保找到一棵簡單的樹。 對于 D中的元組分類所需的期望信息由下式給出： 21( ) lo g ( )miiiIn fo D p p??? ? （ 1） 其中， pi是 D中任意元組屬于類 Ci的概率，并用 |Ci,D|/|D|估計(jì)。使用以 2為底的對數(shù)函數(shù)，因?yàn)樾畔⒂枚M(jìn)位編碼。 Info(D)是識(shí)別 D中的元組的類標(biāo)號所需的平均信息量。 這里，我們所具有的信息只是每個(gè)類的元組所占的百分比。 Info(D)又稱 D的熵。 模式識(shí)別 —— 決策樹算法 第 4 頁 共 14 頁 假設(shè)按屬性 A劃分 D中的元組，其中屬性 A根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v個(gè)不同值{a1,a2,… ,av}?？梢杂脤傩?A將 D劃分為 v個(gè)子集 {D1D2,… ,Dv }，其中 Dj包含 D中的元組，它們在 A上具有值 Aj。這些劃分將對應(yīng)于從節(jié)點(diǎn) N生長出來的分枝。理想地，我們希望該劃分產(chǎn)生元組的準(zhǔn)確分類，即，每個(gè)劃分都是純的。為了得到準(zhǔn)確的分類我們還需要多少信息？這個(gè)量由下式度量： 1||( ) ( )||v jAjjDIn fo D In fo DD???? （ 2） 項(xiàng) ||||jDD充當(dāng)?shù)?j個(gè)劃分的權(quán)重。 ()AInfo D 是基于按 A劃分對 D的元組分類所需要的期望信息。所需要的信息越小，劃分的純度越高。 信息增益定義為原來的信息需求（即僅基于類比例）與新的需求（即對 A劃分之后得到的）之間的差。即是： ( ) ( ) ( )AGai n A Inf o D Inf o D?? （ 3） Gain(A)告訴我們通過 A的劃分我們得到了多少。選擇具有最高信息增益的屬性作為節(jié)點(diǎn) N的分裂屬性。這等價(jià)于按能做“最佳劃分” 的屬性 A劃分，使得完成元組分類還需要的信息最少。 三 ID3 算法 java 實(shí)現(xiàn) 1 實(shí)例 假定某推銷員根據(jù)經(jīng)驗(yàn)得知，學(xué)生是否會(huì)由家長接送，與學(xué)生的年齡、性別和家庭收入關(guān)系最大。于是，她收集了某一學(xué)校學(xué)生由家長接送的信息，得到了表如下的數(shù)據(jù)，這就是
公司管理相關(guān)推薦
鄂ICP備17016276號-1