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