Decision Trees 決策樹(shù)

什么是決策樹(shù) —— 基本概念

• 非葉節(jié)點(diǎn)：一個(gè)屬性上的測(cè)試，每個(gè)分枝代表該測(cè)試的輸出
• 葉節(jié)點(diǎn)：存放一個(gè)類標(biāo)記
• 規(guī)則：從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條屬性取值路徑
  

建立決策樹(shù)分類模型的流程

• 模型訓(xùn)練：從已有數(shù)據(jù)中生成一棵決策樹(shù)
• 分裂數(shù)據(jù)的特征，尋找決策類別的路徑
• 相同的數(shù)據(jù)，根據(jù)不同的特征順序，可以建立多種決策樹(shù)

如何建立決策樹(shù)?

基本的決策樹(shù)學(xué)習(xí)過(guò)程，可以歸納為以下三個(gè)步驟：

1. 特征選擇：選取對(duì)于訓(xùn)練數(shù)據(jù)有著較強(qiáng)區(qū)分能力的特征
2. 生成決策樹(shù)：基于選定的特征，逐步生成完整的決策樹(shù)
3. 決策樹(shù)剪枝：簡(jiǎn)化部分枝干，避免過(guò)擬合因素影響
   

決策樹(shù)學(xué)習(xí)

問(wèn)題：基于以下屬性，決定是否在餐廳等待桌子：

1. Alternate：附近是否有其他選擇的餐廳？
2. Bar：是否有一個(gè)舒適的酒吧區(qū)等待？
3. Fri/Sat：今天是星期五還是星期六？
4. Hungry：我們餓了嗎？
5. Patrons：餐廳里的人數(shù)（無(wú)人、有些人、滿座）
6. Price：價(jià)格范圍（$、$$、$$$）
7. Raining：外面是否下雨？
8. Reservation：我們是否預(yù)約了？
9. Type：餐廳類型（法國(guó)、意大利、泰國(guó)、漢堡）
10. WaitEstimate：等待時(shí)間的預(yù)估值（0-10、10-30、30-60、>60）
    
    假設(shè)的一種可能表示
    例如，在上述餐廳等待桌子的問(wèn)題中，我們可以使用決策樹(shù)來(lái)表示假設(shè)，該決策樹(shù)定義了在不同屬性值下等待桌子的決策。以下是一個(gè)可能的假設(shè)樹(shù)示例：
    

表達(dá)能力

決策樹(shù)可以表示任何輸入屬性的函數(shù)，但使用單條路徑來(lái)表示每個(gè)訓(xùn)練示例的決策樹(shù)可能會(huì)過(guò)度擬合數(shù)據(jù)，無(wú)法很好地推廣到新的未見(jiàn)過(guò)的數(shù)據(jù)示例。

決策樹(shù)可以表達(dá)輸入屬性的任何函數(shù)。例如，對(duì)于布爾函數(shù)，函數(shù)真值表的每行對(duì)應(yīng)于樹(shù)中 的一條路徑:
簡(jiǎn)單來(lái)說(shuō)，針對(duì)每個(gè)訓(xùn)練示例，可以創(chuàng)建一條路徑到葉子節(jié)點(diǎn)的一致性決策樹(shù)（除非函數(shù)在輸入屬性上是非確定性的），但這種決策樹(shù)可能會(huì)過(guò)度擬合數(shù)據(jù)，無(wú)法很好地泛化到新的未見(jiàn)過(guò)的數(shù)據(jù)示例。因此，更傾向于找到更緊湊的決策樹(shù)來(lái)提高泛化性能。

決策樹(shù)學(xué)習(xí)

目的：找到一個(gè)與訓(xùn)練示例一致的小樹(shù)
想法：（遞歸）選擇“最重要”屬性作為（子）樹(shù)的根

想法：一個(gè)好的屬性將示例拆分為（理想情況下）“全正”或“全負(fù)”的子集

根據(jù)Patron分類是一個(gè)更好的選擇

信息論在決策樹(shù)學(xué)習(xí)中的應(yīng)用

信息熵：計(jì)算數(shù)據(jù)的不確定性

$$\text{Entropy}(t)=?\sum _{j=1}^{m}p(j|t){\log }_{2}p(j|t)$$
此時(shí)：表示某個(gè)節(jié)點(diǎn)?? （即某個(gè)特征）的信息不確定性
$p(j|t)$是節(jié)點(diǎn)特征??的屬于類別??的樣本的比例

• 特點(diǎn)：對(duì)于該節(jié)點(diǎn)特征t
  • 當(dāng)樣本均勻地分布在各個(gè)類別時(shí)，熵達(dá)到最大值$log(n_c)$, 此時(shí)包含的信息最少
  • 當(dāng)樣本只屬于一個(gè)類別時(shí)，熵達(dá)到最小值 0, 此時(shí)包含的信息最多

對(duì)于包含 $p$ 個(gè)正例和 $n$ 個(gè)反例的訓(xùn)練集，其熵可以用以下公式計(jì)算：

$$I(\frac{p}{p+n},\frac{n}{p+n})=?\frac{p}{p+n}{\log }_2\frac{p}{p+n}?\frac{n}{p+n}{\log }_2\frac{n}{p+n}$$

其中，第一項(xiàng)和第二項(xiàng)分別表示正例和反例的占比，${\log }_2$ 表示以 2 為底的對(duì)數(shù)。熵的值越高，表示數(shù)據(jù)集越不確定。

特征選擇準(zhǔn)則一：信息增益

信息增益: 按某個(gè)特征劃分之后，數(shù)據(jù)不確定性降低的程度

$$\text{Gain}(m)=\text{Entropy}(p)?(\sum _{i=1}^k\frac{|n_i|}{n}\text{Entropy}(i))$$

1. 第一項(xiàng)$\text{Entropy}(p)$表示數(shù)據(jù)未劃分時(shí)的信息熵
2. 第二項(xiàng)${\sum }_{i=1}^k\frac{|n_i|}{n}\text{Entropy}(i)$表示按特征m劃分后，數(shù)據(jù)的信息熵
   1. 按特征$m$劃分后，父節(jié)點(diǎn)分裂成$k$個(gè)子節(jié)點(diǎn)
   2. ??表示父節(jié)點(diǎn)的樣本個(gè)數(shù)
   3. ???? 表示子節(jié)點(diǎn)??的樣本個(gè)數(shù)
      選擇準(zhǔn)則：選擇最大的??????N 對(duì)應(yīng)的特征m

舉例

結(jié)論

信息增益能夠較好地體現(xiàn)某個(gè)特征在降低信息不確定性方面的貢獻(xiàn)
信息增益越大，說(shuō)明信息純度提升越快，最后結(jié)果的不確定性越低

不足

信息增益的局限性，尤其體現(xiàn)在更偏好可取值較多的特征
取值較多，不確定性相對(duì)更低，因此得到的熵偏低，但不一定有實(shí)際意義
特征Customer ID有最大的信息增益，因?yàn)槊總€(gè)子節(jié)點(diǎn)的熵均為0

回到餐廳的例子

對(duì)于訓(xùn)練集，$p=n=6$，信息熵為 $I(\frac{6}{12},\frac{6}{12})=1$ bit。
考慮屬性Patrons和Type（以及其他屬性）
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-600524.html

從12個(gè)例子中學(xué)到的決策樹(shù)：

到了這里，關(guān)于【人工智能】監(jiān)督學(xué)習(xí)、分類問(wèn)題、決策樹(shù)、信息增益的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！