1樓：搗蛋哥
比如在我們的記錄中，有一列為使用者ID，乙個使用者ID必然對應乙個唯一的類別，因此當決策樹在嘗試選擇特徵降低整體的不確定程度時，必然優先選擇使用者ID（高資訊增益），因為根據ID劃分，只需要劃分一次就可以完全確定類別。但是這樣的劃分是沒有意義的。
2樓：flower
最近也在看決策樹相關的問題，回答一下。
首先這個結論是基於乙個假設的：特徵的有效性
所謂特徵的有效性，也就是說特徵的不同取值下，最終結果取正例或者反例的比率是不同的。
舉個 ：
假設我們有這樣乙個資料集，資料總量4000，其中正例和反例各2000，然後現在面臨首先是使用A特徵還是B特徵還是C特徵
首先資料的原始資訊墒為
特徵A劃分後的資訊增益
特徵B劃分後的資訊增益
特徵C劃分後的資訊增益
(公式太難打遂只給了計算結果.......)
通過對比我們發現
A特徵和B特徵的資訊增益是相同的，因為其實b1和b2等價，b3和b4等價，（所以b1,b2這種劃分其實並不是有效特徵，完全可以合併），也就是ID3演算法並不是什麼情況下都傾向於選擇特徵取值更多的特徵
C特徵的資訊增益是高於A特徵的，我們可以簡單理解為C特徵是對A特徵的進一步細分，那麼自然是消除了更多的不確定性，有更高的資訊增益
結論：ID3演算法傾向於選擇特徵取值更多的特徵是說，在特徵有效性的前提下，特徵取值更多，相當於對資料集的進一步細分，那麼自然是消除了更多的資料的不確定性，獲得了更大的資訊增益，這其實是沒有問題的
而為什麼要消除ID3演算法的這種傾向性，主要是基於下面這個原因：
所以具體的任務中，如果資料量相對於特徵取值足夠多，或者是對特徵的有效性有足夠的先驗知識可以作為保證，那麼就不會發生類似的過擬合情況，ID3演算法的有效性會得到保障，也就沒有必要使用什麼資訊增長率的指標了，也就是C4.5演算法
3樓：WastonYuan
ID3 特徵值太多的話要是一分成N叉會直接到葉子節點(葉子節點節點資料量到閾值) 而效果不好。
其實更多的是要做一下特徵值合併。
如果是CART樹就沒這個問題了因為人家只是二叉（合併了特徵值）。
4樓：
下邊用盡可能簡單的方式來解釋這個問題，不涉及具體的公式。
幾種水果混合在一起了，示例資料集中給出了「唯一號碼」、「顏色」、「重量」、「硬度」、「含水量」五個屬性，使用決策樹對示例資料集進行分類。
示例資料集
如果乙個決策樹分支節點包含的樣本都是屬於同乙個類別的（例如都是蘋果），那麼這個節點純度就高；反之，如果包含的樣本並不屬於同一類別（不同種類的水果混合在一起了），那麼節點純度就低。
一般來說，通過一種劃分方式帶來的純度提公升越大，資訊增益就越高。ID3演算法以資訊增益為準則來選擇決策樹劃分屬性。值多的屬性更有可能會帶來更高的純度提公升（參見下一段），所以資訊增益的比較偏向選擇取值多的屬性。
這會帶來乙個漏洞的：在示例資料集中，如果選擇唯一號碼作為劃分屬性，那麼會得到十個類別，每個類別都只包含乙個樣本，每個節點的純度都是最高的（都只有一種水果），純度提公升也是最大的，帶來的資訊增益也是最高的。但是這樣的劃分是沒有意義的。
所以，為了避免ID3演算法的選擇偏好可能帶來的不利影響，C4.5演算法不直接使用資訊增益為準則來選擇劃分屬性，而是使用增益率（gain ratio）來劃分。C4.
5演算法並不是直接選擇增益率最大的候選劃分屬性，而是使用了乙個啟發式：先從候選劃分屬性中找出資訊增益高於平均水平的屬性，再從中選擇增益率最高的。
5樓：李磊
最近在上這方面的課程，簡單說下我自己的理解吧！
覺得內容太多，可以直接看最後面部分。
首先分析一下熵和決策樹中的純的關係
熵的理解
熵反映的是系統的不確定性，舉個簡單的例子，總共有十個樣本：
(1). 正負各5個
(2).正樣本9個，負樣本1個
我們可以看出明顯(2)的樣本集的熵小，我自己的理解是如果從(1)的樣本集中隨機取出乙個樣本，有可能為正(50%)，也很有可能為負(50%)，但從(2)中隨機取乙個樣本，很大概率(90%)為正的，更穩定些。
那麼為何要用熵作為決策樹的節點擊擇的重要依據呢？
決策樹實際上就機器學習的乙個演算法，任何演算法最關鍵的是算得快(time cost)和佔空間少(memory cost)。
2. 算得快及佔空間少
現在先看看這個例子，屬性為有錢(0或1)和帥不帥(0或者1), 分類為嫁還是不嫁(0或1)。
我們考慮一下可能出現的資料有哪些：
表1. 所有可能出現的資料，紅色為雜訊資料，出現次數極少，大部分的資料為黑色的模式，藍色可能發生，並且出現了產生爭端的資料。(雖然沒有收集過此方面的資料，但是一般情況下，兩個屬性的二分類通常都會出現這種情形的資料分布)
此時，考慮所有的情形，以帥或者有錢作為初始節點的樹的結構為：
及考慮到出現矛盾的情況，根據資料出現的次數，刪掉出現次數極少的情形(001,110,見表1)，得到以帥或者有錢作為初始節點的樹的結構:
及對於(011,010;101,100,見表1)可能出現衝突的請況，根據出現次數多少進行刪減(提高accuracy)，不妨假設011的次數多於010, 100的次數多於101(其他情況的分析也一樣的), 以帥或者有錢作為初始節點的決策樹結構:
及此時，從計算時間和儲存空間來看，無論用有錢作為初始節點還是帥作為初始節點，都一樣。
但考慮到當
(1).屬性大於2
(2).收集的資料不夠
(3).(010,011)這種模式根本不存在
的時候，會出現以下的情形:
資料只有:
表2在這種情況下，很顯然，用有錢作為初始節點更好，通過有錢直接可以判斷嫁不嫁，而如果把帥作為初始節點，如果不帥，還要考慮是否有錢。
以及左右一致
顯然下面的模型計算量少，儲存空間少，以有錢作為初始節點優於帥作為初始節點。
3. 熵和純
現在我們從熵的角度和純的角度來分析這個模型：
(1). 熵
那麼， " eeimg="1"/>
用錢作為初始node,資訊增益大於用帥作為初始node。
(2). 純
以帥作為初始節點，其帥節點下面只有嫁，而不帥的節點下有嫁和不嫁兩種情況。
以有錢作為初始節點，其有錢節點下只有嫁，沒錢節點下只有不嫁。
總體而言
以有錢為初始節點，"純"高或者說該節點(有錢)的子節點(有或沒)只出現以一種情況(也就是純淨，單一)；
以帥作為初始節點，"純"低或者說該節點(帥)的子節點(帥不帥)出現(混合)多種情況(也就是不純，混合)。
4. 整體分析
(1). 表2可以作為乙個很有代表性的例子。正常情況下，屬性數目多，資料量較少時，資料不可能涵蓋所有的情形( )。而且當出現衝突資料時，為保證精度，往往刪掉出現次數少的資料。
(2). 從純度而言，純度越高，越快得到出分類結果，模型越淺，計算速度快，時間消耗少(見2)。當條件概率 確定之後，為了保證純度，資料越少，純度越高(見3)。
(3). 從熵而言，熵低，模型穩定，體現在分布上就是分布不均勻(見1)。
此處利用1的例子說明，分布越不均勻(比如1/10和9/10)，那麼會得到資料量很少的乙個分類(1/9)，從數量上來說，數量少(1/9)往往純度(乾淨程度)可能更低。而當資料達到一定程度(9/10和1/2)後，純度不變。
結論：任何演算法的分析都離不開Performance，Time Cost和Memory Cost。此處不考慮過擬合等問題，分析最基礎的決策樹演算法。
其實資訊增益演算法的核心是熵越低=>分布不均勻=>某些分類資料量少=> 出現不同類的少=>純度高=>計算時間少。
建議讀完上面部分再看
回答：資訊增益率的引進則是解決記憶體空間大小，如果出現這種情形
資訊增益演算法會傾向於先將Day作為初始節點，因為該分類下每類的資料量少，而且都只有一類(Y或者N)，純度高。然而得到的圖結構就是：
整個樹結構十分龐大，雖然也很淺，計算速度快，但是佔記憶體空間大，才引入資訊增益率這個概念。
6樓：weizier
回到公式本身來吧
當極限情況下A將每乙個樣本都分到乙個節點當中去的時候，後面的括號部分為0.也就是條件熵部分為0，而條件熵的最小值為0，這意味著該情況下的資訊增益達到了最大值，故ID3演算法一定會選擇特徵A。然而，我們知道這個特徵A顯然不是最佳選擇。
7樓：方圓七里
我覺得題主的問題是在問取值越多是否就一定會導致資訊增益越大？這個是不一定的，樓上舉的例子比較極端，我再舉個例子：
Humidity的值有兩種，High和Normal，Temperature的值有三種，Hot、Mild和Cool，而Day的值多達14種，如果按照資訊增益的公式來算：
對於PlayTennis，各個屬性的資訊增益值：
可以看出Temperature所帶來的資訊增益不如Humidity，也就是說取值越多不一定會導致資訊增益越大。
參考文獻： 《Machine Learning》 Tom M. Mitchell
8樓：
對於取值多的屬性，尤其一些連續型數值，比如兩條地理資料的距離屬性，這個單獨的屬性就可以劃分所有的樣本，使得所有分支下的樣本集合都是「純的」（最極端的情況是每個葉子節點只有乙個樣本）。
乙個屬性的資訊增益越大，表明屬性對樣本的熵減少的能力更強，這個屬性使得資料由不確定性變成確定性的能力越強。
所以如果是取值更多的屬性，更容易使得資料更「純」（尤其是連續型數值），其資訊增益更大，決策樹會首先挑選這個屬性作為樹的頂點。結果訓練出來的形狀是一棵龐大且深度很淺的樹，這樣的劃分是極為不合理的。
C4.5使用了資訊增益率，在資訊增益的基礎上除了一項split information,來懲罰值更多的屬性。
c 中為什麼不提倡使用vector bool ？
陌歸 作為乙個 STL 容器，vector 確實只有兩個問題 1.它不是乙個STL容器 2.它並不容納 bool 因為vector 打包 bool 以節省空間，每個儲存在 vector 中的 bool 占用乙個單獨的bit，而禁止有指向單個位元的指標，所以vector不能編譯下式 vector v ...
C 未包含 string 為什麼可使用string？
d41d8c 需要用到std ios base型別，std ios base有個成員類叫failure，std ios base failure有個建構函式接受std string 現在這被認為是個錯誤 我個人希望standard library module unit能消除這個問題。 馬小刀 編譯...
為什麼我這樣使用C 中的initializer list，在g 可以得到輸出而在msvc中不可以？
機犬 std initializer list 這東西雖然是在庫里提供的，但實現完全看編譯器怎麼開洞，大部分情況下值都在棧上，G 可能會直接指向靜態儲存區，我就遇到過 VC 爆棧 G 沒事的情況，就當成有型別的 va list 用好了，常量或是比較大的容器初始化資料還是選 std array 吧。 ...