|
本文旨在詳細解釋ID3算法（用于構(gòu)建決策樹的眾多算法之一）。 我們使用偽造的Covid-19樣本數(shù)據(jù)集解釋該算法。  > Image Courtesy: http:///uncategorized/hello-world/ 什么是決策樹？簡而言之，決策樹是一種包含節(jié)點（矩形框）和邊線（箭頭）的結(jié)構(gòu)，并從數(shù)據(jù)集（代表要素/屬性的列表和對應于記錄的表）構(gòu)建而成。 每個節(jié)點要么用于制定決策（稱為決策節(jié)點），要么代表結(jié)果（稱為葉節(jié)點）。 決策樹示例 上圖描繪了一個決策樹，用于對一個人是健康還是不健康進行分類。 這里的決策節(jié)點是諸如''這個人是否小于30歲？'，'這個人吃垃圾嗎？'之類的問題，葉子是兩種可能的結(jié)果之一。 適合與不適合看決策樹，我們可以說做出以下決定：如果一個人不到30歲并且不吃垃圾食品，那么他就適合了;如果一個人不到30歲并且 吃垃圾食品，然后他變得不健康，依此類推。 初始節(jié)點稱為根節(jié)點（藍色），最終節(jié)點稱為葉節(jié)點（綠色），其余節(jié)點稱為中間或內(nèi)部節(jié)點。根節(jié)點和中間節(jié)點代表決策，而中間節(jié)點代表決策。 葉節(jié)點代表結(jié)果。 ID3簡介ID3代表迭代二分器3，之所以這樣命名，是因為該算法在每個步驟中將迭代（重復）地將特征二分（劃分）為兩個或更多組。 ID3由Ross Quinlan發(fā)明，它使用自上而下的貪婪方法來構(gòu)建決策樹。 簡而言之，自上而下的方法意味著我們從頂部開始構(gòu)建樹，而貪婪的方法則意味著在每次迭代中，我們都選擇當前最好的特征來創(chuàng)建節(jié)點。 通常，ID3僅用于僅具有名義特征的分類問題。 數(shù)據(jù)集描述在本文中，我們將使用COVID-19感染的樣本數(shù)據(jù)集。 整個數(shù)據(jù)集的預覽如下所示。
這些列是不言自明的。 Y和N分別代表是和否。 '已感染'列Y和N中的值或類別分別表示'已感染'和'未感染'。 用于制作決策節(jié)點的列。 '呼吸問題'，'咳嗽'和'發(fā)燒'稱為特征列，或僅稱為特征，而用于葉節(jié)點的列（即'感染'）稱為目標列。 ID3中的指標如前所述，ID3算法在構(gòu)建決策樹時的每一步都會選擇最佳功能。 在您問之前，問題的答案是：' ID3如何選擇最佳功能？'是ID3使用信息增益或僅通過增益來找到最佳功能。 信息增益可計算熵的減少量，并衡量給定要素對目標類別的區(qū)分或分類的程度。 信息增益最高的功能被選為最佳功能。 簡而言之，熵是數(shù)據(jù)集的無序量度，數(shù)據(jù)集的熵是數(shù)據(jù)集的目標特征中無序量度。對于二進制分類（目標列只有兩種類型的類別），熵為0 如果目標列中的所有值都是同質(zhì)的（相似），并且如果目標列中兩個類的值均相等，則為1。 我們將數(shù)據(jù)集表示為S，熵的計算公式為： Entropy(S) = - ∑ p? * log?(p?) ; i = 1 to n 其中，n是目標列中類的總數(shù)（在我們的案例中，n = 2，即I和NI）p?是類' i'的概率或'目標列中具有類i的行數(shù)'的比率 到數(shù)據(jù)集中的'總行數(shù)'。 特征列A的信息增益計算為： IG(S, A) = Entropy(S) - ∑((|S?| / |S|) * Entropy(S?)) 其中S?是S中特征列A的值為v的行集合|S?| 是S?中的行數(shù)，同樣| S | 是S中的行數(shù)。 ID3步驟· 計算每個功能的信息增益。 · 考慮到所有行都不屬于同一類，請使用信息增益最大的功能將數(shù)據(jù)集S分成子集。 · 使用具有最大信息增益的功能創(chuàng)建決策樹節(jié)點。 · 如果所有行都屬于同一類，則將當前節(jié)點作為以該類為標簽的葉節(jié)點。 · 重復其余功能，直到用盡所有功能，或者決策樹具有所有葉節(jié)點。 在我們的數(shù)據(jù)集上實施如上一節(jié)所述，第一步是找到最佳功能，即具有最大信息增益（IG）的功能。 現(xiàn)在，我們將為每個功能計算IG，但為此，我們首先需要計算S的熵 在我們的數(shù)據(jù)集S中，總共有14行，其中有8行的目標值為YES，有6行的目標值為NO。 S的熵計算為： Entropy(S) = — (8/14) * log?(8/14) — (6/14) * log?(6/14) = 0.99 注意：如果目標列中的所有值都相同，則熵將為零（這意味著它沒有隨機性或隨機性為零）。 現(xiàn)在，我們計算每個功能的信息增益： 發(fā)燒的IG計算：在此（發(fā)燒）功能中，有8行的值為YES和6行的值為NO。 目標值NO
如下所示，在具有否的6行中，有2行具有目標值YES和4行具有目標值NO。 +-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| NO | NO | NO | NO |+-------+-------+------------------+----------+| NO | YES | NO | NO |+-------+-------+------------------+----------+| NO | YES | YES | YES |+-------+-------+------------------+----------+| NO | YES | NO | NO |+-------+-------+------------------+----------+| NO | YES | YES | YES |+-------+-------+------------------+----------+| NO | YES | YES | NO |+-------+-------+------------------+----------+下面的方框演示了發(fā)燒信息增益的計算。 # total rows|S| = 14For v = YES, |S?| = 8Entropy(S?) = - (6/8) * log?(6/8) - (2/8) * log?(2/8) = 0.81For v = NO, |S?| = 6Entropy(S?) = - (2/6) * log?(2/6) - (4/6) * log?(4/6) = 0.91# Expanding the summation in the IG formula:IG(S, Fever) = Entropy(S) - (|S???| / |S|) * Entropy(S???) - (|S??| / |S|) * Entropy(S??)∴ IG(S, Fever) = 0.99 - (8/14) * 0.81 - (6/14) * 0.91 = 0.13 接下來，我們計算'咳嗽'和'呼吸問題'特征的IG。您可以使用此免費的在線工具來計算信息增益。 IG(S, Cough) = 0.04 IG(S, BreathingIssues) = 0.40 由于功能``呼吸問題''具有最高的信息增益，因此可用于創(chuàng)建根節(jié)點。因此，在此初始步驟之后，我們的樹如下所示：  接下來，從剩余的兩個未使用功能（發(fā)燒和咳嗽）中，我們確定哪個最適合呼吸問題的左分支。由于呼吸問題的左分支表示是，因此我們將使用原始數(shù)據(jù)的子集 也就是說，'呼吸問題'列中值為YES的行集。 這8行如下所示：
接下來，我們使用子集S??（設(shè)置呼吸問題為是）計算發(fā)燒和咳嗽特征的IG，如上所示： 注意：對于IG計算，熵將根據(jù)子集S??而非原始數(shù)據(jù)集S計算得出。 IG(S??, Fever) = 0.20 IG(S??, Cough) = 0.09 發(fā)燒的IG大于咳嗽的IG，因此我們選擇發(fā)燒作為呼吸問題的左分支：我們的樹現(xiàn)在如下所示：  接下來，我們?yōu)?#39;呼吸問題'的右分支找到具有最大IG的特征。 但是，由于只剩下一個未使用的功能，我們別無選擇，只能使其成為根節(jié)點的右分支，所以我們的樹現(xiàn)在看起來像這樣：  沒有更多未使用的功能，因此我們在此處停止并跳至創(chuàng)建葉節(jié)點的最后一步。對于Fever的左葉節(jié)點，我們看到原始數(shù)據(jù)集中具有呼吸問題和Fever兩個值的行的子集 如是。 +-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| YES | YES | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+| YES | YES | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+| YES | NO | YES | YES |+-------+-------+------------------+----------+由于目標列中的所有值均為YES，因此我們將左側(cè)葉子節(jié)點標記為YES，但為了使其更具邏輯性，我們將其標記為Infected。 同樣，對于發(fā)燒的右側(cè)節(jié)點，我們會看到原始數(shù)據(jù)集中行的子集，其呼吸問題值為YES，發(fā)燒值為NO。 +-------+-------+------------------+----------+| Fever | Cough | Breathing issues | Infected |+-------+-------+------------------+----------+| NO | YES | YES | YES |+-------+-------+------------------+----------+| NO | YES | YES | NO |+-------+-------+------------------+----------+| NO | YES | YES | NO |+-------+-------+------------------+----------+ 在這里，不是所有值，而是所有值都是NO，因此NO或Not Infected成為我們的右葉節(jié)點。 現(xiàn)在，我們的樹如下所示：  我們對節(jié)點Cough重復相同的過程，但是此處的左右葉子都相同，即NO或Not Infected如下圖所示：  看起來很奇怪，不是嗎？ 我知道！ 呼吸問題的正確節(jié)點與'未感染'類別的葉子節(jié)點一樣好。 這是ID3的缺點之一，它不會修剪。 修剪是一種通過刪除不必要的節(jié)點來減少決策樹的大小和復雜性的機制。 有關(guān)修剪的更多信息，請參見此處。 ID3的另一個缺點是過擬合或高方差，即它很好地學習了它使用的數(shù)據(jù)集，因此無法歸納為新數(shù)據(jù)。 摘要我們詳細介紹了ID3算法的過程，并看到僅使用兩個度量標準即使用該算法創(chuàng)建決策樹是多么容易。 熵和信息增益。 希望你喜歡它，伙計們！謝謝閱讀 參考文獻：https://www.cise./~ddd/cap6635/Fall-97/Short-papers/2.htm 任何人都可以根據(jù)我們的政策在'中'上發(fā)布，但我們并沒有對每個故事進行事實檢查。 有關(guān)冠狀病毒的更多信息，請參見cdc.gov。 (本文翻譯自Yaser Sakkaf的文章《Decision Trees: ID3 Algorithm Explained》，參考： |
|
|
