【算法】決策樹與ID3算法

2021-02-13 數據科學與人工智慧

小編邀請您，先思考：

1 如何構建決策樹？

2 決策樹適合解決什麼問題？

1. 什麼是決策樹/判定樹（decision tree）？

決策樹(Decision Tree)算法是機器學習(Machine Learning)中分類算法中的一個重要算法，屬於監督學習(Supervised Learning)算法。決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。

2. 決策樹構造

決策樹學習的算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行分割，使得對各個子數據集有一個最好的分類的過程。決策樹構造可以分三步進行：特徵選擇、決策樹的生成、決策樹的修剪。

3. 熵（entropy）概念：

信息和抽象，如何度量？

1948年，香農提出了 「信息熵(entropy)」的概念

一條信息的信息量大小和它的不確定性有直接的關係，要搞清楚一件非常非常不確定的事情，或者是我們一無所知的事情，需要了解大量信息==>信息量的度量就等於不確定性的多少

例子：猜世界盃冠軍，假如一無所知，猜多少次？每個隊奪冠的機率不是相等的 比特(bit)來衡量信息的多少

變量的不確定性越大，熵也就越大.

4. 決策樹歸納算法 （ID3）

決策樹方法最早產生於上世紀60年代，到70年代末。由J.Ross.Quinlan提出了ID3算法，此算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進，對於預測變量的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。

決策樹的典型算法有ID3，C4.5，CART等。數據挖掘領域的十大經典算法中，C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法產生的分類規則易於理解，準確率較高。

選擇屬性判斷節點

信息獲取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)

通過A來作為節點分類獲取了多少信息

電腦銷售客戶的訓練數據集：

根據年齡、收入、是否為學生，信用度判斷是否買電腦

類似，Gain(income) = 0.029,

Gain(student) = 0.151,

Gain(credit_rating)=0.048

所以，選擇age作為第一個根節點

重複上面的操作。

算法：

樹以代表訓練樣本的單個結點開始（步驟1）。

如果樣本都在同一個類，則該結點成為樹葉，並用該類標號（步驟2 和3）。

否則，算法使用稱為信息增益的基於熵的度量作為啟發信息，選擇能夠最好地將樣本分類的屬性（步驟6）。該屬性成為該結點的「測試」或「判定」屬性（步驟7）。在算法的該版本中，

所有的屬性都是分類的，即離散值。連續屬性必須離散化。

對測試屬性的每個已知的值，創建一個分枝，並據此劃分樣本（步驟8-10）。

算法使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。一旦一個屬性出現在一個結點上，就不必該結點的任何後代上考慮它（步驟13）。

遞歸劃分步驟僅當下列條件之一成立停止：

(a) 給定結點的所有樣本屬於同一類（步驟2 和3）。

(b) 沒有剩餘屬性可以用來進一步劃分樣本（步驟4）。在此情況下，使用多數表決（步驟5）。

這涉及將給定的結點轉換成樹葉，並用樣本中的多數所在的類標記它。替換地，可以存放結

點樣本的類分布。

(c) 分枝

test_attribute = a i 沒有樣本(步驟11)。在這種情況下，以 samples 中的多數類

創建一個樹葉（步驟12）

5 .決策樹/判定樹（decision tree)

判定樹：根據條件判定是否去play

7. 決策樹優點：

直觀、生成的模式簡單，便於理解，小規模數據集有效

分類精度高

缺點：

親愛的讀者朋友們，您們有什麼想法，請點擊【寫留言】按鈕，寫下您的留言。


數據人網（http://shujuren.org）誠邀各位數據人來平臺分享和傳播優質數據知識。


公眾號推薦：

好又樂書屋，專注分享有思想的人物，身心健康，自我教育，閱讀寫作和有趣味的生活等內容，傳播正能量。

閱讀原文，更多精彩！

分享是收穫，傳播是價值！


相關焦點

  • 決策樹分類算法之ID3算法與C4.5算法
    而K均值(K-means clustering)聚類則是最典型的聚類算法(當然，除此之外，還有很多諸如屬於劃分法K-MEDOIDS算法、CLARANS算法；屬於層次法的BIRCH算法、CURE算法、CHAMELEON算法等；基於密度的方法：DBSCAN算法、OPTICS算法、DENCLUE算法等；基於網格的方法：STING算法、CLIQUE算法、WAVE-CLUSTER算法)。
  • 決策樹-ID3算法和C4.5算法
    它通過對已有樣本的學習生成一顆決策樹(可看成if-then規則集合)，從而能對新樣本作出相應分類。本文重點闡述如何選擇特徵建立決策樹，並給出理解算法的具體實例。什麼是決策樹？ID3算法詳解2.1 什麼是熵2.2 ID3算法2.3 ID3算法的缺點C4.5算法詳解3.1 第一個問題的改進辦法3.2 第二個問題的改進辦法決策樹：通過對已知樣本的學習，一步一步將特徵進行分類，從而將整個特徵空間進行劃分，進而區分出不同類別的算法
  • 決策樹算法--ID3
    決策樹是機器學習方法中的一種監督學習算法，表示根據特徵對樣本進行分類的樹形結構，可以用於分類和回歸。這個問題可以通過決策樹來實現。那決策樹有哪些特點？決策樹在sklearn中如何使用？帶著這個問題請繼續往下看,決策樹怎麼幫助我們解決現實生活中的問題的。
  • 決策樹學習筆記(三):CART算法,決策樹總結
    ，旨在從最簡單的決策樹開始學習，循序漸進，最後理解並掌握複雜模型GBDT，Xgboost，為要想要深入了解機器學習算法和參加數據挖掘競賽的朋友提供幫助。：CART算法，它可以說是學習決策樹的核心了。也就是說，CART樹的剪枝算法可以概括為兩步：1）是從原始決策樹生成各種剪枝效果的決策樹序列。2）是用交叉驗證來檢驗剪枝後的預測能力，選擇泛化預測能力最好的剪枝後的數作為最終的CART樹。
  • Machine Learning -- ID3算法
    決策樹的基本認識    決策樹是一種依託決策而建立起來的一種樹。在機器學習中，決策樹是一種預測模型，代表的是一種對象屬性與對象值之間的一種映射關係，每一個節點代表某個對象，樹中的每一個分叉路徑代表某個可能的屬性值，而每一個葉子節點則對應從根節點到該葉子節點所經歷的路徑所表示的對象的值。
  • 【分類算法】基於 R 語言決策樹算法介紹及應用
    常見的強化學習算法有時間差學習。算法類似性決策樹學習：根據數據的屬性採用樹狀結構建立決策模型。決策樹模型常常用來解決分類和回歸問題。常見的算法包括 CART (Classification And Regression Tree)、ID3、C4.5、隨機森林 (Random Forest) 等。
  • 決策樹分類算法
    二、決策樹分類決策樹算法藉助於樹的分支結構實現分類。下圖是一個決策樹的示例，樹的內部結點表示對某個屬性的判斷，該結點的分支是對應的判斷結果；葉子結點代表一個類標。上表是一個預測一個人是否會購買購買電腦的決策樹，利用這棵樹，我們可以對新記錄進行分類，從根節點（年齡）開始，如果某個人的年齡為中年，我們就直接判斷這個人會買電腦，如果是青少年，則需要進一步判斷是否是學生；如果是老年則需要進一步判斷其信用等級，直到葉子結點可以判定記錄的類別。
  • 詳解決策樹 C4.5 算法
    決策樹（decision tree）算法基於特徵屬性進行分類，其主要的優點：模型具有可讀性，計算量小，分類速度快。上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：1、對於二叉決策樹而言，可以看作是if-then規則集合，由決策樹的根節點到葉子節點對應於一條分類規則;2、分類規則是互斥並且完備的，所謂互斥即每一條樣本記錄不會同時匹配上兩條分類規則，所謂完備即每條樣本記錄都在決策樹中都能匹配上一條規則。
  • 決策樹與隨機森林(4)—— 決策樹C5.0算法
    C5.0算法通過加入自適應增強（Adaboost）算法對C4.5進行改進。這是許多決策樹構建的一個過程，然後這些決策樹通過投票表決的方法為每個案例選擇最優的分類。Question 2: 什麼叫做 Adaboost ？
  • AI產品經理必懂算法:決策樹
    決策樹（Decision Tree）是一種以樹形數據結構來展示決策規則和分類結果的模型，它是將看似無序、雜亂的已知實例，通過某種技術手段將它們轉化成可以預測未知實例的樹狀模型。時隔半月，已近年關。AI產品經理必懂算法的第三篇終於來了，今天想和大家聊的是決策樹，閒言少敘，切入正題。
  • IBM SPSS Modeler算法系列-----決策樹CHAID算法
    （包括C5.0、CHAID、QUEST、C&R和決策列表）的區別，這可以幫助大家在選用算法的時候有一些參考。      接下來我們回到CHAID算法，我們在IBM SPSS Modeler構建這個模型，得到的決策樹結果如下（部分截圖）：
  • IBM SPSS Modeler算法系列-----決策樹C5.0算法
    在之前的文章《IBM SPSS Modeler算法系列決策樹CHAID算法》,我們介紹是CHAID算法，今天我們介紹另外一種用得非常廣泛的決策樹算法
  • 關於「樹」的算法:現實生活中的決策樹
    圖源：unsplash就像樹木是人類生活的重要組成部分一樣，基於樹的算法也是機器學習的重要組成部分。樹的結構給了我們開發算法的靈感，並再將其反饋到機器，讓它們學習我們希望它們學習的東西，以解決現實生活中的問題。這些基於樹的學習算法被認為是最好和最常用的監督學習方法之一：決策樹、隨機森林、梯度提升等方法在各種數據科學問題中得到了廣泛應用。對於每一個機器學習的初學者來說，學習這些算法並將其用於建模非常重要。
  • ID3算法
    上一篇介紹了可以用「信息增益」來對決策樹進行特徵分類，而ID3算法恰好使用了這種方式。這一篇我主要介紹一個例子，來說明ID3算法的應用。 ID3算法核心 首先，我們來看下該算法的原理。
  • 關於人工智慧領域ID3算法分析
    今天我們重點探討一下ID3算法。  Hunt、Marin、和 Stone於1966年研製了一個概念學習系統CLS， 可以學習單個概念，並用此學到的概念分類新的實例。John Ross Quinlan（雪梨大學）於1983年研製了ID3算法。 ID3算法是決策樹的一種，它是基於奧卡姆剃刀原理的，即用儘量用較少的東西做更多的事。
  • 機器學習中決策樹的原理與算法 | 科普
    從名字來看，決策的的意思就是在眾多類別中我們需要決策出我們分類的東西是屬於哪一個類別，決策離散型的值的叫決策樹，決策連續型值的叫回歸樹。用學術一點的語言就是決策樹的輸出是離散型隨機變量，回歸樹的輸出是連續型隨機變量，這篇文章的重點是講解輸出是離散型隨機變量的決策樹，當你明白決策樹的運行機理後，回歸樹也就觸類旁通了。
  • ID3、C4.5、CART決策樹介紹
    決策樹同時也是隨機森林的基本組成部分，後者是現今最強大的機器學習算法之一。1. 簡單了解決策樹舉個例子，我們要對」這是好瓜嗎？」這樣的問題進行決策時，通常會進行一系列的判斷：我們先看"它是什麼顏色的"，如果是"青綠色"， 我們再看"它的根蒂是什麼形態"，如果是"蜷縮"，我們再判斷"它敲起來是什麼聲音"，最後我們判斷它是一個好瓜。決策過程如下圖所示。
  • 決策樹之ID3和C4.5
    一、決策樹       一種樹狀分類結構模型，是一種通過對變量值拆分建立起來的分類規則，又利用樹形圖分割形成的概念路徑的數據分析技術。二、決策樹的兩個關鍵步驟三、決策樹的構建步驟②數據是在一直持續劃分直至在一個分區中特徵無區別，因此決策樹很容易出現過度擬合的現象。③對於大規模的數據量，可以使用預剪枝的方法，來對決策樹進行剪枝。什麼叫過度擬合？來複習一下。在學習期間，它可能包含了訓練數據中的某些特定的異常，這些異常不會在一般數據集中出現。⑶第四步中：可以利用混淆矩陣、ROC曲線、AUC值等等模型評估指標來對我們的模型進行評估。
  • 從決策樹到隨機森林:樹型算法的原理與實現
    基於樹（Tree based）的學習算法在數據科學競賽中是相當常見的。這些算法給預測模型賦予了準確性、穩定性以及易解釋性。和線性模型不同，它們對非線性關係也能進行很好的映射。常見的基於樹的模型有：決策樹（decision trees）、隨機森林（random forest）和提升樹（boosted trees）。
  • 幹活 | 從決策樹學習談到貝葉斯分類算法、EM、HMM及其應用
    常用的分類算法包括：決策樹分類法，樸素的貝葉斯分類算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網絡法，k-最近鄰法(k-nearest neighbor，kNN)，模糊分類法等等(所有這些分類算法日後在本blog內都會一一陸續闡述)。