【海量數(shù)據(jù)挖掘/數(shù)據(jù)分析】之 決策樹模型（決策樹模型、決策樹構(gòu)成、決策樹常用算法、決策樹性能要求、信息增益、信息增益計(jì)算公式、決策樹信息增益計(jì)算實(shí)例）
目錄
【海量數(shù)據(jù)挖掘/數(shù)據(jù)分析】之 決策樹模型（決策樹模型、決策樹構(gòu)成、決策樹常用算法、決策樹性能要求、信息增益、信息增益計(jì)算公式、決策樹信息增益計(jì)算實(shí)例）
一、決策樹模型
1、常用算法
2、屬性劃分策略
3、其他算法
三、決策樹算法性能要求
四、 決策樹模型創(chuàng)建 ( 遞歸創(chuàng)建決策樹 )
1 、 決策樹模型創(chuàng)建
2 、 決策樹創(chuàng)建算法 ( 遞歸 )
3 、 遞歸操作
4 、 遞歸停止的條件
五、 決策樹 樹根屬性 選擇
六、信息增益 說明
1、 熵 和 信息 的數(shù)據(jù)組成
2 、 信息增益分析
3、信息增益計(jì)算步驟
4、信息增益 計(jì)算使用的數(shù)據(jù)集 S
七、信息增益 計(jì)算公式
1 、 已知條件 ( 變量聲明 ) : 聲明一些計(jì)算公式中使用的變量 說明
2、信息增益 總熵 計(jì)算公式
?3、信息增益 每個 屬性的熵 計(jì)算公式
4、信息增益 計(jì)算公式
八、 信息增益計(jì)算 實(shí)例
1 、 已知數(shù)據(jù)
2 、總熵計(jì)算 :
3、 計(jì)算 年齡 屬性的熵 :
?4、計(jì)算 年齡屬性 不同樣本取值的熵 :
?5、 計(jì)算年齡屬性的信息增益
6、 依次計(jì)算 各個屬性的 熵 :
?九、信息增益計(jì)算 遞歸確定 劃分屬性
一、決策樹模型
1 、決策樹 : 決策時基于 “樹” 結(jié)構(gòu) , 這也是模擬人在進(jìn)行決策時采用的策略 ;
2、決策樹組成 : 根節(jié)點(diǎn) , 內(nèi)部節(jié)點(diǎn) , 葉子節(jié)點(diǎn) , 這些節(jié)點(diǎn)都是數(shù)據(jù)的 屬性 ( 特征 ) ;
- ?根節(jié)點(diǎn) : 最初始判定的屬性 , 判定區(qū)域是全局的數(shù)據(jù)集 ;
- ?內(nèi)部節(jié)點(diǎn) : 中間的判定屬性 , 判定區(qū)域是符合某些特征的子數(shù)據(jù)集 ;
- ?葉子節(jié)點(diǎn) : 決策結(jié)果 , 位于決策樹的最底層 , 每個葉子節(jié)點(diǎn)都是一個決策結(jié)果 ;
?
3、 決策樹模型過程
① 訓(xùn)練過程 : 使用訓(xùn)練集數(shù)據(jù)確定決策時使用的屬性 , 確定根節(jié)點(diǎn) , 內(nèi)部節(jié)點(diǎn) , 葉子節(jié)點(diǎn) 的屬性劃分 , 訓(xùn)練決策樹模型 ;
② 預(yù)測過程 : 從根節(jié)點(diǎn)特征開始 , 根據(jù)決策樹中的判定序列依次從根節(jié)點(diǎn)向下判定 , 直到一個葉子節(jié)點(diǎn) ;
4、實(shí)例說明
1 ） 需求場景 :
① 需求 : 電商網(wǎng)站為用戶進(jìn)行分類 , 目的是確定該用戶是否有可能購買某件商品 , 然后為其推送指定商品的廣告 ;
② 決策樹使用 : 如何對用戶進(jìn)行分類 , 這里就用到了決策樹模型 , 將用戶分成不同的類別 ;
2 ） 數(shù)據(jù)集 : 決策過程中 , 根據(jù)每個節(jié)點(diǎn)所處理的數(shù)據(jù)集的特征 , 將其劃分到不同的子節(jié)點(diǎn)中進(jìn)行處理 ; 如數(shù)據(jù)集中是 100 個用戶的信息 ;
3 ） 決策樹構(gòu)成 :
① 根節(jié)點(diǎn)決策 : 根節(jié)點(diǎn) 處理年齡特征 , 小于 30 歲的用戶劃分到一組 , 大于 30 歲的用戶劃分到另一組 ;
② 內(nèi)部節(jié)點(diǎn)決策 : 然后在 小于 30 歲的用戶中繼續(xù)判定 , 學(xué)生劃分成一組 , 非學(xué)生劃分成一組 ;
③ 葉子節(jié)點(diǎn)決策結(jié)果 : 學(xué)生會買電腦 , 非學(xué)生不會買電腦 ;
二、常用的決策樹算法?
1、常用算法
- ?CLS 算法 : 這是第一個決策樹算法 , 1966 年提出 ;
- ?ID3 算法 : 該算法使決策樹稱為機(jī)器學(xué)習(xí)主流技術(shù) , 1979 年提出 ;
- ?C4.5 算法 : 最常用的決策樹算法 ; 1993 年提出 ;
?區(qū)別 : 上述三個算法五個組件基本一致 , 唯一的區(qū)別是確定屬性劃分時的策略不同 , 即將哪個屬性放在樹根 , 將哪個屬性放在內(nèi)部節(jié)點(diǎn)上 , 內(nèi)部節(jié)點(diǎn)的屬性所在層級如何設(shè)置 ;
2、屬性劃分策略
① ID3 算法屬性劃分策略 : ID3 使用信息增益策略 ;
② C4.5 算法屬性劃分策略 : C4.5 使用的是增益率策略 ;
3、其他算法
1) CART 算法 : 既可以用于分類任務(wù) ( 結(jié)果是離散值 ) , 也可以用于回歸任務(wù) ( 結(jié)果是連續(xù)值 ) ;
2) FR 算法 : 隨機(jī)森林算法 ; 使用了數(shù)據(jù)挖掘 , 機(jī)器學(xué)習(xí)中的集成思想 ; 有很多差的分類器 , 準(zhǔn)確率都很低 , 但是多個分類器集成起來 , 準(zhǔn)確率就很高 ;
?
三、決策樹算法性能要求
1 、 決策樹的高度 :
① 決策樹最大高度 : 決策屬性的個數(shù) ; ( 每個屬性都要決策一次 , 才能預(yù)測出結(jié)果 )
② 決策時最小高度 : 1 ; ( 只需要決策一次 , 就可以預(yù)測出結(jié)果 )
2 . 決策樹性能 : 決策樹越矮越好 , 即預(yù)測某特征 , 進(jìn)行的決策次數(shù)越少越好 ;
3 . 樹根屬性 : 越重要的屬性 , 其越能將數(shù)據(jù)最大可能拆分開 , 將重要的屬性放在樹根 ;
四、 決策樹模型創(chuàng)建 ( 遞歸創(chuàng)建決策樹 )
1 、 決策樹模型創(chuàng)建
決策樹模型創(chuàng)建的核心就是選擇合適的樹根 , 將重要的屬性放在樹根 , 然后子樹中 , 繼續(xù)選擇子樹中重要的屬性放在子樹的樹根 , 依次遞歸 , 最終得到?jīng)Q策結(jié)果 ( 葉子節(jié)點(diǎn) ) ;
2 、 決策樹創(chuàng)建算法 ( 遞歸 )
使用遞歸算法 , 遞歸算法分為遞歸操作 和 遞歸停止條件 ;
3 、 遞歸操作
每個步驟先選擇屬性 , 選擇好屬性后 , 根據(jù) 總樹 ( 子樹 ) 的樹根屬性劃分訓(xùn)練集 ;
① 選擇屬性 : 遞歸由上到下決定每一個節(jié)點(diǎn)的屬性 , 依次遞歸構(gòu)造決策樹 ;
② 數(shù)據(jù)集劃分 : 開始決策時 , 所有的數(shù)據(jù)都在樹根 , 由樹根屬性來劃分?jǐn)?shù)據(jù)集 ;
③ 屬性離散化 : 如果屬性的值是連續(xù)值 , 需要將連續(xù)屬性值離散化 ; 如 : 100 分滿分 , 將 60 分以下分為不及格數(shù)據(jù) , 60 分以上分為及格數(shù)據(jù) ;
4 、 遞歸停止的條件
① 子樹分類完成 : 節(jié)點(diǎn)上的子數(shù)據(jù)集都屬于同一個類別 , 該節(jié)點(diǎn)就不再向下劃分 , 稱為葉子節(jié)點(diǎn) ;
② 屬性 ( 節(jié)點(diǎn) ) 全部分配完畢 : 所有的屬性都已經(jīng)分配完畢 , 決策樹的高度等于屬性個數(shù) ;
③ 所有樣本分類完畢 : 所有的樣本數(shù)據(jù)集都分類完成 ;
五、 決策樹 樹根屬性 選擇
1 . 屬性選擇方法 : 樹根屬性選擇的方法很多 , 這里介紹一種常用的方法 , 信息增益 ;
2 . 信息增益 : 信息增益 效果越大 , 其作為樹根屬性 , 劃分的數(shù)據(jù)集分類效果越明顯 ;
3 . 信息 和 熵
① 信息 與 熵 的關(guān)系 : 信息 會 消除 熵 , 熵 代表了不確定性 , 信息用來消除不確定性 ;
② 信息增益 : 信息增益大的屬性 , 能最大消除熵的不確定性 ;
4 . 決策樹中的信息增益 : 屬性的 信息增益 越大 , 就越能將分類效果達(dá)到最大 ;
如 : 想要從用戶數(shù)據(jù)集中找到是否能買奢侈品的用戶 , 先把高收入群體劃分出來 , 將低收入者從數(shù)據(jù)集中去除 , 這個收入水平的屬性 ( 特征 ) , 信息增益就很大 ;
六、信息增益 說明
1、 熵 和 信息 的數(shù)據(jù)組成
① 數(shù)據(jù)集 ( 熵 ) : 給定一個總的數(shù)據(jù)集如 100 個用戶數(shù)據(jù) , 要從里面選擇購買奢侈品的 1 個用戶 ( 高收入 , 30 歲以下 ) ;
② 年齡屬性 ( 信息 ) : 30 歲以上的 50 個 , 30 歲以下的 50 個 ;
③ 收入屬性 ( 信息 ) : 高收入 10 個 , 低收入 90 個 ;
2 、 信息增益分析
① 收入屬性的信息增益 : 熵是 100 個用戶數(shù)據(jù) , 代表不確定性 ; 根據(jù)收入屬性來劃分 , 將高收入者 10 個用戶劃分出來 , 買奢侈品的用戶從這 10 個中選擇 ; 由 100 個用戶中選 1 個用戶 , 變?yōu)?10 個用戶中選擇 1 個用戶 ; 消除了 90 個用戶的不確定性 ;
② 年齡屬性的信息增益 : 熵是 100 個用戶數(shù)據(jù) , 代表不確定性 ; 根據(jù)收入屬性來劃分 , 將30 歲以下的 50 個用戶劃分出來 , 買奢侈品的用戶從這 50 個中選擇 ; 由 100 個用戶中選 1 個用戶 , 變?yōu)?50 個用戶中選擇 1 個用戶 ; 消除了 50 個用戶的不確定性 ;
③ 信息增益分析 : 明顯 收入屬性 的信息增益要高于 年齡屬性 的信息增益 ;
3、信息增益計(jì)算步驟
1 ） 總熵 : 不考慮 輸入變量 ( 屬性 / 特征 ) , 為數(shù)據(jù)集 S 中的某個數(shù)據(jù)樣本進(jìn)行分類 , 計(jì)算出該過程的熵 ( 不確定性 ) , 用 Entropy(S) 表示 ;
2 ）引入屬性后的熵 : 使用 輸入變量 ( 屬性 / 特征 ) X 后 , 為數(shù)據(jù)集 S 中的某個數(shù)據(jù)樣本進(jìn)行分類 , 計(jì)算出該過程的熵 ( 不確定性 ) , 用 Entropy(X , S) 表示 ;
3 ）信息增益 : 上面 Entropy(X , S) - Entropy(S) 的差 , 就是 X 屬性 ( 特征 ) 帶來的信息增益 , 用 Gain(X , S) 表示 ;
4、信息增益 計(jì)算使用的數(shù)據(jù)集 S
數(shù)據(jù)集 : 根據(jù) 年齡 , 收入水平 , 是否是學(xué)生 , 信用等級 , 預(yù)測該用戶是否會購買商品 ;如下圖
① 是否會購買商品 : 9 個 會購買 , 5 個不會購買 ;
② 年齡 ( 屬性 ) :
5 個小于 30 歲的人中 , 3 個不會買電腦 , 有 2 個會買商品 ;
4 個 31 ~ 39 歲的人中 , 0 個不會買電腦 , 有 4 個會買商品 ;
5 個 大于 40 歲的人中 , 2 個不會買電腦 , 有 3 個會買商品 ;
?
七、信息增益 計(jì)算公式
數(shù)據(jù)集如下圖：
1 、 已知條件 ( 變量聲明 ) : 聲明一些計(jì)算公式中使用的變量 說明
① 總的數(shù)據(jù)集 : S
② 最終分類個數(shù) : m , 最終分成 m 個類別 , 如 是否購買商品 ( 是 , 否 ) , 就是分成 2 類 , m = 2 ;
③ 分類表示 : C i ( i = 1 , ? , m ) , 如 : 是否購買商品 ( 是 , 否 ) ,? C1? 表示 是 ,? C2? 表示 否 ;
④ 分類樣本個數(shù) : s i ( i = 1 , ? , m )? , 如 : 是否購買商品 , 會購買的 ( C1? ) 的樣本個數(shù)是 9 人 , 表示為 s1?=9 ;
?
2、信息增益 總熵 計(jì)算公式
① 加和式 : 這是一個 1 到 m 加和式 ;
② 比值權(quán)重 :? s/si?? 表示第i 個樣本 數(shù) ( si? ) 與 總樣本數(shù) ( s) 比值 ;
示例 說明
① 需求 : 判定 14 個用戶是否會購買某商品 , 9 個會購買 , 5 個不購買 ;
② 計(jì)算過程 :
?3、信息增益 每個 屬性的熵 計(jì)算公式
1 ） 計(jì)算熵的屬性 : 屬性 A? 的值為 {a1?,a2?,?,av?} ;
2 ） 引入 屬性 ( 特征 ) A 后 的熵計(jì)算公式 :
3）公式解析 :
① 剩余的熵 : 引入屬性 A 后 , 屬性 A 是信息 , 信息會消除熵 , 這里計(jì)算消除后剩余的熵是多少 ;
② 屬性解析 : 這是一個? 1 到? v 的加和式 ,? v 表示 A 屬性的取值個數(shù) ,
如 :? A 表示年齡 , 有 : 30歲以下( a1? ) 有 5 個樣本 , 31 ~ 39 歲 ( a2? ) 有 4 個樣本 , 40 歲以上(? a3? ) 有 5 個樣本 , 所以 v = 3? ;
③ 系數(shù)說明 : 其中 Sj / S ?? 系數(shù) 表示 , 屬性 A ( 年齡特征 ) 的第? j 個版本的比例 , 這個比例越高 , 樣本對多 , 越重要 ;
4）屬性的熵 示例 說明
?簡單說明計(jì)算過程解析
- ① 5/14*?Entropy(2,3) 在 5 個 小于 30 歲的人中 , 有 2 個會買商品 , 3 個不會買商品 ;
- ② 4/14?*Entropy(4,0) 在 4 個 31 ~ 39 歲的人中 , 有 4 個會買商品 , 0 個不會買商品 ;
- ③ 5/14?*Entropy(3,2) 在 5 個 大于 40 歲的人中 , 有 3 個會買商品 , 2 個不會買商品 ;
?
4、信息增益 計(jì)算公式
計(jì)算 A A A 屬性的信息增益 :
八、 信息增益計(jì)算 實(shí)例
數(shù)據(jù)列表如下：
1 、 已知數(shù)據(jù)
① 數(shù)據(jù)集 : 計(jì)算 上述數(shù)據(jù)集? S 的信息增益 , 該數(shù)據(jù)集? S 有 14 個樣本數(shù)據(jù) ;
② 數(shù)據(jù)集屬性 : 數(shù)據(jù)集? S 有? 5 個屬性 , 年齡 , 收入 , 是否是學(xué)生 , 信用等級 , 是否購買商品 ;
③ 預(yù)測屬性 : 根據(jù) 年齡 , 收入 , 是否是學(xué)生 , 信用等級? 4 個屬性 , 預(yù)測 是否購買商品 這個屬性 ;
2 、總熵計(jì)算 :
① 總熵 : 計(jì)算每個屬性的信息增益 , 先要使用 Entropy(S) 公式計(jì)算出總熵 ;
① 預(yù)測屬性分析 : 最后預(yù)測的屬性是 是否購買電腦 , 有兩個取值 , 是 或 否 , 2 個取值 , 計(jì)算總熵時 , 需要計(jì)算兩項(xiàng) , 分別計(jì)算 取值 會買電腦 和 不會買電腦的 熵 ;
③ 屬性的具體分類 : 判定 14 個用戶是否會購買某商品 , 9 個會購買 , 5 個不購買 ;
④ 計(jì)算過程 :
3、 計(jì)算 年齡 屬性的熵 :
① 引入屬性 : 引入 年齡 屬性 后 , 年齡 屬性 是信息 , 信息會消除熵 , 這里計(jì)算引入 年齡 屬性 之后的熵是多少 ;
② 年齡屬性分析 : 年齡屬性有 3 種取值 : 30歲以下有 5 個樣本 , 31 ~ 39 歲有 4 個樣本 , 40 歲以上有 5 個樣本 ;
③ 計(jì)算內(nèi)容 :
需要分別計(jì)算 3 種取值的熵各是多少 ,
30歲以下有 5 個樣本 , 需要計(jì)算這 5 個樣本的熵是多少 , 5 個樣本 , 有 3 個人買商品 , 2 個人不買商品 ,
④ 計(jì)算示例 :
- 5/14? * ?Entropy(2,3) 在 5 個 小于 30 歲的人中 , 有 2 個會買商品 , 3 個不會買商品 ;
- 4 /14 * ?Entropy(4,0) 在 4 個 31 ~ 39 歲的人中 , 有 4 個會買商品 , 0 個不會買商品 ;
- 5/ 14 * Entropy(3,2) 在 5 個 大于 40 歲的人中 , 有 3 個會買商品 , 2 個不會買商品 ;
?4、計(jì)算 年齡屬性 不同樣本取值的熵 :
① 計(jì)算? Entropy(2 , 3) : 5 個人 , 有 2 個人買商品 , 3 個人沒有買商品 ;
?② 計(jì)算? Entropy(4,0) : 4 個人 , 有 4 個人買商品 , 0 個人沒有買商品 ;
?③ 計(jì)算? Entropy(3 , 2)? : 5 個人 , 有 3 個人買商品 , 2 個人沒有買商品 ;
?5、 計(jì)算年齡屬性的信息增益
6、 依次計(jì)算 各個屬性的 熵 :
① 年齡 屬性的信息增益 : Gain ( 年齡 ) = 0.246
② 收入 屬性的信息增益 :? Gain ( 收入 ) = 0.029
③ 是否是學(xué)生 屬性的信息增益 :? Gain ( 是否是學(xué)生 ) = 0.151
④ 信用等級 屬性的信息增益 :? Gain ( 信用等級 ) = 0.048
⑤ 樹根 屬性選擇: 年齡屬性的 信息增益 最大 , 選擇年齡屬性作為樹根 ;
?后續(xù)工作 ( 重要 ) : 選擇完樹根后 , 樹根屬性將數(shù)據(jù)分為不同的子集 , 每個子集再計(jì)算剩余的 3 個屬性 , 哪個屬性的信息增益最大 , 就選那個屬性作為子樹的樹根屬性 ;
?
?九、信息增益計(jì)算 遞歸確定 劃分屬性
1 . 計(jì)算公式使用 : 根據(jù)上述公式 , 計(jì)算出每個屬性的信息增益 , 遞歸選取信息增益最大的作為樹根
2 . 決策樹創(chuàng)建算法 ( 遞歸 ) : 使用遞歸算法 , 遞歸算法分為遞歸操作 和 遞歸停止條件 ;
3 . 遞歸操作 : 每個步驟先選擇屬性 , 選擇好屬性后 , 根據(jù) 總樹 ( 子樹 ) 的樹根屬性劃分訓(xùn)練集 ;
① 選擇屬性 : 遞歸由上到下決定每一個節(jié)點(diǎn)的屬性 , 依次遞歸構(gòu)造決策樹 ;
② 數(shù)據(jù)集劃分 : 開始決策時 , 所有的數(shù)據(jù)都在樹根 , 由樹根屬性來劃分?jǐn)?shù)據(jù)集 ;
③ 屬性離散化 : 如果屬性的值是連續(xù)值 , 需要將連續(xù)屬性值離散化 ; 如 : 100 分滿分 , 將 60 分以下分為不及格數(shù)據(jù) , 60 分以上分為及格數(shù)據(jù) ;
4 . 遞歸停止的條件 :
① 子樹分類完成 : 節(jié)點(diǎn)上的子數(shù)據(jù)集都屬于同一個類別 , 該節(jié)點(diǎn)就不再向下劃分 , 稱為葉子節(jié)點(diǎn) ;
② 屬性 ( 節(jié)點(diǎn) ) 全部分配完畢 : 所有的屬性都已經(jīng)分配完畢 , 決策樹的高度等于屬性個數(shù) ;
③ 所有樣本分類完畢 : 所有的樣本數(shù)據(jù)集都分類完成 ;
5 . 下圖是最終的決策樹樣式 :
?參考博文：
【數(shù)據(jù)挖掘】決策樹算法簡介 ( 決策樹模型 | 模型示例 | 決策樹算法性能要求 | 遞歸創(chuàng)建決策樹 | 樹根屬性選擇 )_討論決策樹屬性選擇的原則和要求文章來源：http://www.zghlxwxcb.cn/news/detail-534406.html
【數(shù)據(jù)挖掘】決策樹中根據(jù) 信息增益 確定劃分屬性 ( 信息與熵 | 總熵計(jì)算公式 | 每個屬性的熵計(jì)算公式 | 信息增益計(jì)算公式 | 劃分屬性確定 )_數(shù)據(jù)挖掘 決策樹劃分信息熵信息增益文章來源地址http://www.zghlxwxcb.cn/news/detail-534406.html
到了這里，關(guān)于【海量數(shù)據(jù)挖掘/數(shù)據(jù)分析】之 決策樹模型（決策樹模型、決策樹構(gòu)成、決策樹常用算法、決策樹性能要求、信息增益、信息增益計(jì)算公式、決策樹信息增益計(jì)算實(shí)例）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
