ID3算法

2021-01-08 騰訊網

上一篇介紹了可以用「信息增益」來對決策樹進行特徵分類，而ID3算法恰好使用了這種方式。這一篇我主要介紹一個例子，來說明ID3算法的應用。

ID3算法核心

首先，我們來看下該算法的原理。

算法從根節點開始，對每個特徵都計算其信息增益，然後選取信息增益最大的那個特徵作為根節點的分類特徵，形成子節點；然後對子節點再計算剩餘特徵的信息增益，再次選取較大的那個特徵；重複上述步驟，直到信息增益為0或者沒有特徵選擇為止。

實戰

這裡我們舉一個《機器學習》書中的例子：

如上圖，我們給出了一天的天氣狀況以及是否出去打網球的數據集D。我們希望訓練出的模型可以根據某一天的天氣狀況，來判斷出今天是否應該去打網球。也就是說，這是一個分類問題，類別只有「yes」和「no」兩類。

那麼，我們應該如何構建一個決策樹呢？

首先，要計算數據集D中類別的熵。

可以看到，一共有14個數據，其中有9個「yes」，5個「no」。因此，信息熵為

·第1個特徵outlook

然後，我們先選擇第一個特徵outlook，計算其分類的信息熵。而outlook特徵有3個取值，分別是sunny、overcast和rain。因此，我們分別計算熵再相加即可。

先來看sunny，一共有5個數據，佔比為5/14；而在這5個當中，playtennis的類別情況是有2個「yes」，3個「no」，因此其信息熵為

第二個取值是overcast，有4個數據，而且類別全是「yes」，因此其信息熵為

第三個取值是rain，有5個數據，類別情況是有3個「yes」，2個「no」，因此其信息熵為

把公式（1）（2）（3）加起來，即可得到特徵A（outlook）總的分類信息熵為

所以，特徵A的信息增益為

g(D,A)=H(D)-H(D|A)=0.94-0.7=0.24

·第2個特徵temperature

特徵有3個取值，分別是hot、mild和cool。計算過程同上，這裡我們省略，最後可算出第二個特徵B的信息增益為

g(D,B)=0.03

·第3個特徵humidity

特徵有2個取值，分別是high和normal。經計算，特徵C的信息增益為

g(D,C)=0.15

·第4個特徵wind

特徵有2個取值，分別是strong和weak。經計算，特徵E的信息增益為

g(D,E)=0.05

對比這4個特徵的信息增益，最大的是特徵A——outlook。因此，我們用此特徵作為根節點的分類特徵。該特徵按其取值將數據分成三大類。

隨後，我們用剩餘的特徵對這三大類再次進行上述步驟，直到到達葉節點。最後劃分出的結果如下圖所示：

可以看到，我們僅用了3個特徵，就將數據完全分類了。

ID3算法暫時先介紹到這裡，那麼還有沒有其他的算法可以進行決策樹的特徵選擇呢？下一篇我將為你介紹。

相關焦點

  • 【算法】決策樹與ID3算法
    決策樹(Decision Tree)算法是機器學習(Machine Learning)中分類算法中的一個重要算法，屬於監督學習(Supervised Learning)算法。決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。
  • 決策樹算法--ID3
    四 ID3算法決策樹有三種比較經典的算法: ID3, C4.5和CART。由於ID3是這三個算法的基礎，而且其他兩個算法是ID3的改進，因此本文主要以ID3為例.輸入：m個樣本，每個樣本有n個離散特徵，特徵集合為A，樣本輸出集合為D,採用前剪枝，信息增益的閾值為ϵ輸出：決策樹T。
  • Machine Learning -- ID3算法
    對於決策樹來說，主要有兩種算法：ID3算法和C4.5算法。C4.5算法是對ID3算法的改進。今天主要先講ID3算法，之後會講C4.5算法和隨機森林等。 Contents     1.ID3算法介紹     3. 信息熵與信息增益     4. ID3算法的C++實現  1.
  • 大眾終於不再古板 id3內飾變科技時尚風
    日前，這一印象被打破，大眾終於不再古板，在純電動緊湊型兩廂車id3上面看到了簡約科技範兒十足的內飾，引領了大眾內飾的新風潮。大眾車得大眾的心，最主要是因為它經濟實惠和親民的屬性，而從曝光的圖片來看即便id3大玩兒科技風，但也沒有劍走偏鋒，依舊是走樸素的風格。內飾整體以黑色為主，在細節處加以鍍鉻元素點綴，增強了內飾的時尚感與精緻感。
  • 決策樹分類算法之ID3算法與C4.5算法
    分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類算法的要求，則代價非常大，這時候可以考慮使用聚類算法。
  • 決策樹-ID3算法和C4.5算法
    本文重點闡述如何選擇特徵建立決策樹，並給出理解算法的具體實例。什麼是決策樹？ID3算法詳解2.1 什麼是熵2.2 ID3算法2.3 ID3算法的缺點C4.5算法詳解3.1 第一個問題的改進辦法3.2 第二個問題的改進辦法決策樹：通過對已知樣本的學習，一步一步將特徵進行分類，從而將整個特徵空間進行劃分，進而區分出不同類別的算法
  • 關於人工智慧領域ID3算法分析
    ID3算法起源於概念學習系統（CLS），以信息熵的下降速度為選取測試屬性的標準，即在每個節點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標準，然後繼續這個過程，直到生成的決策樹能完美分類訓練樣例。 ID3算法核心： ID3算法核心是「信息熵」。
  • 從ID3到C5.0的故事:算法詳解及實踐應用
    在前面，我們分別概述性地介紹了決策樹的基本知識：算法|決策樹算法究竟說的是什麼？
  • 決策樹之ID3和C4.5
    四、算法的理論知識介紹     下面我們對ID3算法、C4.5算法以及CART算法進行理論上的分享。我們用用的是韓家煒老師書中的一個小案例。為了在敘述算法的時候方便，我們用A來表示age變量，用D來表示最後的類別class。
  • ID3、C4.5、CART決策樹介紹
    決策樹同時也是隨機森林的基本組成部分，後者是現今最強大的機器學習算法之一。1. 簡單了解決策樹舉個例子，我們要對」這是好瓜嗎？」這樣的問題進行決策時，通常會進行一系列的判斷：我們先看"它是什麼顏色的"，如果是"青綠色"， 我們再看"它的根蒂是什麼形態"，如果是"蜷縮"，我們再判斷"它敲起來是什麼聲音"，最後我們判斷它是一個好瓜。決策過程如下圖所示。
  • 機器學習(9)之ID3算法詳解及python實現
  • 圖的最短路徑算法-Floyd算法-弗洛伊德算法
    Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法 在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。
  • 評估算法及算法的時間複雜度
    文章導讀【對於一個給定的算法，通常要評估其正確性和運行效率的高低。算法的正確性評估不在本文範圍之內，本文主要討論從算法的時間複雜度特性去評估算法的優劣。】程序是用來解決問題的，是由多個步驟或過程組成的，這些步驟和過程就是解決問題的算法。
  • 貪心算法與近似算法
    使用這種算法能得到最優解嗎？ 答：種貪婪策略是，選擇可裝入卡車剩餘空間內的最大箱子，並重複這個過程，直到不能再裝入箱子為止。使用這種算法不能得到最優解。2.你要去歐洲旅行，總行程為7天。對於每個旅遊勝地，你都給它分配一個價值——表示你有多想去那裡看看，並估算出需要多長時間。你如何將這次旅行的價值最大化？請設計一種貪婪算法。使用這種算法能得到最優解嗎？
  • 數據挖掘算法:EM算法
    EM算法EM算法（Expectation Maximization）是在含有隱變量（latent variable）的模型下計算最大似然的一種算法。所謂隱變量，是指我們沒有辦法觀測到的變量。比如，有兩枚硬幣A、B，每一次隨機取一枚進行拋擲，我們只能觀測到硬幣的正面與反面，而不能觀測到每一次取的硬幣是否為A；則稱每一次的選擇拋擲硬幣為隱變量。
  • 算法的算法:人工神經網絡
    從Logistic回歸到支持向量機，算法層出不窮，毫不誇張的說，神經網絡成為算法的算法，為機器學習的頂峰。它也從最初不斷嘗試中成為機器學習的通用表達形式。3.決策樹諸如決策樹算法之類的基於樹的算法有些棘手。關於如何構建這種神經網絡的答案在於分析它如何劃分其特徵空間。當訓練點遍歷一系列拆分節點時，特徵空間將拆分為多個超立方體。在二維示例中，垂直線和水平線創建了正方形。
  • 經典算法—模擬退火算法
  • 【算法資源】貪婪算法
    貪婪算法(Greedy algorithm)是一種對某些求最優解問題的更簡單、更迅速的設計技術。
  • 【嵌入式經典算法介紹】DFT算法與FFT算法概述
    一、概述　　在諧波分析儀中，我們常常提到的兩個詞語，就是DFT算法與FFT算法，那麼一款功率分析儀/諧波分析儀採用DFT算法或者FFT算法，用戶往往關注的是能否達到所要分析諧波次數的目的，而並未考慮兩種算法之間有什麼不同，採用相關算法的依據。
  • 機器學習算法之K-means算法
    K-means舉例shi'li1 K-means算法簡介k-means算法是一種聚類算法，所謂聚類，即根據相似性原則2 K-means算法原理k-means算法中的k代表類簇個數，means代表類簇內數據對象的均值（這種均值是一種對類簇中心的描述），因此，k-means算法又稱為k-均值算法。