啪啪啪精品一区二,青青99久久

決策樹是一種基本的分類與回歸方法。這里主要討論決策樹用于分類。
決策樹模型是描述對樣本進(jìn)行分類的樹形結(jié)構(gòu)。樹由結(jié)點(diǎn)和有向邊組成：

內(nèi)部結(jié)點(diǎn)表示一個特征或者屬性。
葉子結(jié)點(diǎn)表示一個分類。
有向邊代表了一個劃分規(guī)則。

決策樹從根結(jié)點(diǎn)到子結(jié)點(diǎn)的的有向邊代表了一條路徑。決策樹的路徑是互斥并且是完備的。
用決策樹分類時，對樣本的某個特征進(jìn)行測試，根據(jù)測試結(jié)果將樣本分配到樹的子結(jié)點(diǎn)上。此時每個子結(jié)點(diǎn)對應(yīng)該特征的一個取值。
遞歸地對樣本測試，直到該樣本被劃分葉結(jié)點(diǎn)。最后將樣本分配為葉結(jié)點(diǎn)所屬的類。
決策樹的優(yōu)點(diǎn)：可讀性強(qiáng)，分類速度快。
決策樹學(xué)習(xí)通常包括3個步驟：

特征選擇。
決策樹生成。
決策樹剪枝。

決策樹可以看成是一系列 if-then規(guī)則的集合，如下圖所示，圓圈代表一個特征，方框是葉節(jié)點(diǎn)，表示得到的一個分類。決策樹就是一個樹狀的流程圖，將一個樣本數(shù)據(jù)按照樹中的條件一步步判斷，就能得到最終的分類結(jié)果。

image.png

下面結(jié)合例子來詳細(xì)理解決策樹算法。

一、特征選擇

首先我們需要確定，根節(jié)點(diǎn)，也就是第一個用來比較判斷的特征是哪個特征。直覺上來講，這個特征一定是最有助于幫助該樣本進(jìn)行分類的特征。在最好的情況下，該特征的分布與最終的分類結(jié)果完全一致，那么這個決策樹就只有一個內(nèi)部節(jié)點(diǎn)。一般情況下不會出現(xiàn)這種理想的特征，所以我們需要一個準(zhǔn)則來判斷哪個特征對分類最有幫助。通常的準(zhǔn)則是信息增益或信息增益比。

在之前系列中介紹過熵的概念，熵表示一個隨機(jī)變量不確定性的度量，設(shè)X是一個取有限個值的離散隨機(jī)變量，其概率分布為： $P\left(X=x_{i}\right)=p_{i}, \quad i=1,2, \cdots, n$
則X的熵定義為： $H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

條件熵：

條件熵H(Y|X)表示在已知變量X的條件下隨機(jī)變量Y的不確定性。定義為X給定條件下Y的條件概率分布對于X的數(shù)學(xué)期望。
$H(Y | X)=\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right)$
當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)（特別是極大似然估計(jì)）得到時，所對應(yīng)的熵和條件熵被稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。

信息增益

特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即： $g(D, A)=H(D)-H(D | A)$
所以我們對一個數(shù)據(jù)集D，計(jì)算其每個特征的信息增益，并選出最大的那個特征。

先來規(guī)定一些符號的含義：

設(shè)訓(xùn)練集為D，|D|表示其樣本容量，即樣本個數(shù)。設(shè)有K個類，分別為 $C_k$ 。 $|C_k|$ 為屬于這個類的樣本數(shù)。則 $\sum_{k=1}^{K}\left|C_{k}\right|=|D|$ 。設(shè)某個特征 $A$ 有n個不同的特征： $A = \left\{a_{1}, a_{2}, \dots, a_{n}\right\}$ 。根據(jù)A的取值將D劃分成n個子集 $\mathrm{D}_{1}, \mathrm{D}_{2}, \ldots, \mathrm{D}_{\mathrm{n}}$ ， $\left|\mathrm{D}_{\mathrm{i}}\right|$ 為 $D_i$ 的樣本個數(shù)， $則\sum_{i=1}^{n}\left|D_{i}\right|=|D|$ 。記子集 $D_i$ 中屬于類 $C_k$ 的樣本的集合為 $D_{ik}$ ，即 $\mathrm{D}_{\mathrm{ik}}=\mathrm{D}_{\mathrm{i}} \cap \mathrm{C}_{\mathrm{k}}$ ${D}_{\mathrm{ik}}$ 為 $D_{ik}$ 的樣本數(shù)。

下面舉例：

貸款情況表

例5.1中，|D|=15；k=2,（標(biāo)簽類別：是or否）， $C_1=9$ (類別為是的樣本數(shù)）， $C_2=6$ (類別為否的樣本數(shù))。假設(shè)特征A是“年齡”特征，那么A有三個取值（青年，中年，老年）可以劃分成三個子集， $D_1,D_2,D_3$ 都等于5，那么 $D_{11}$ 表示年齡為青年的樣本中，類別為“是”的樣本數(shù)， $D_{11}=2$ ， $D_{12}=3$ ，同理， $D_{21}=3$ ， $D_{22}=2$ ， $D_{31}=4$ ， $D_{32}=1$ 。

信息增益的算法如下：

輸入：訓(xùn)練數(shù)據(jù)集D和特征A；
輸出：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)。
（1）計(jì)算數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)：
$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$ （2）計(jì)算特征A對數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵H(D|A)： $H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{D |} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}$ （3）計(jì)算信息增益 $g(D, A)=H(D)-H(D | A)$
下面再舉例，還是上面的數(shù)據(jù)集，計(jì)算其信息增益并選擇最優(yōu)特征。

首先計(jì)算經(jīng)驗(yàn)熵H(D): $H(D)=-\frac{9}{15} \log _{2} \frac{9}{15}-\frac{6}{15} \log _{2} \frac{6}{15}=0.971$
然后計(jì)算各特征對數(shù)據(jù)集D的信息增益。分別以A1，A2，A3，A4表示年齡、有工作、有自己的房子和信貸情況4個特征，則：
（1） $\begin{aligned} g\left(D, A_{1}\right) &=H(D)-\left[\frac{5}{15} H\left(D_{1}\right)+\frac{5}{15} H\left(D_{2}\right)+\frac{5}{15} H\left(D_{3}\right)\right] \\ &=0.971-\left[\frac{5}{15}\left(-\frac{2}{5} \log _{2} \frac{2}{5}-\frac{3}{5} \log _{2} \frac{3}{5}\right)\right. \\ & +\frac{5}{15}\left(-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5}\right)+\frac{5}{15}\left(-\frac{4}{5} \log _{2} \frac{4}{5}-\frac{1}{5} \log _{2} \frac{1}{5}\right)] \\ & = 0.971 - 0.888 \\ & = 0.083 \end{aligned}$
同理：對于A2： $\begin{aligned} g\left(D, A_{2}\right) &=H(D)-\left[\frac{5}{15} H\left(D_{1}\right)+\frac{10}{15} H\left(D_{2}\right)\right] \\ &=0.971-\left[\frac{5}{15} \times 0+\frac{10}{15}\left(-\frac{4}{10} \log _{2} \frac{4}{10}-\frac{6}{10} \log _{2} \frac{6}{10}\right)\right]=0.324 \end{aligned}$
A3： $\begin{aligned} g\left(D, A_{3}\right) &=0.971-\left[\frac{6}{15} \times 0+\frac{9}{15}\left(-\frac{3}{9} \log _{2} \frac{3}{9}-\frac{6}{9} \log _{2} \frac{6}{9}\right)\right] \\ &=0.971-0.551=0.420 \end{aligned}$
A4： $g\left(D, A_{4}\right)=0.971-0.608=0.363$
最后，比較各特征的信息增益值。由于特征A3（有自己的房子）的信息增益值最大，所以選擇特征A3作為最優(yōu)特征。

信息增益比：

信息增益值的大小是相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義。在分類問題困時，也就是說在訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時候，信息增益值會偏大。反之，信息增益值會偏小。使用信息增益比（information gain ratio）可以對這一問題進(jìn)行校正。這是特征選擇的另一準(zhǔn)則。

信息增益比：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益比gR(D,A)定義為其信息增益g(D,A)與訓(xùn)練數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)之比：
$g_{R}(D, A)=\frac{g(D, A)}{H(D)}$

二、決策樹生成

ID3算法

輸入：訓(xùn)練數(shù)據(jù)集D，特征集A，閾值；
輸出：決策樹T。
（1）若D中所有實(shí)例屬于同一類Ck，則T為單結(jié)點(diǎn)樹，并將類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T；
（2）若A＝?，則T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T；
（3）否則，按算法5.1計(jì)算A中各特征對D的信息增益，選擇信息增益最大的特征Ag；
（4）如果Ag的信息增益小于閾值，則置T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T；
（5）否則，對Ag的每一可能值ai，依Ag＝ai將D分割為若干非空子集Di，將Di中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹T，返回T；
（6）對第i個子結(jié)點(diǎn)，以Di為訓(xùn)練集，以A-{Ag}為特征集，遞歸地調(diào)用步（1）～步（5），得到子樹Ti，返回Ti。

對表5.1的訓(xùn)練數(shù)據(jù)集，利用ID3算法建立決策樹。

由于特征A3（有自己的房子）的信息增益值最大，所以選擇特征A3作為根結(jié)點(diǎn)的特征。它將訓(xùn)練數(shù)據(jù)集D劃分為兩個子集D1（A3取值為“是”）和D2（A3取值為“否”）。
由于D1（有自己的房子）可以直接得出其類別為是，所以它成為一個葉結(jié)點(diǎn)，結(jié)點(diǎn)的類標(biāo)記為“是”。

對D2則需從特征A1（年齡），A2（有工作）和A4（信貸情況）中選擇新的特征。（剔除原來的特征）計(jì)算各個特征的信息增益： $\begin{array}{l}{g\left(D_{2}, A_{1}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{1}\right)=0.918-0.667=0.251} \\ {g\left(D_{2}, A_{2}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{2}\right)=0.918} \\ {g\left(D_{2}, A_{4}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{4}\right)=0.474}\end{array}$

選擇信息增益最大的特征A2（有工作）作為結(jié)點(diǎn)的特征。由于A2有兩個可能取值，從這一結(jié)點(diǎn)引出兩個子結(jié)點(diǎn)：一個對應(yīng)“是”（有工作）的子結(jié)點(diǎn)，包含3個樣本，它們屬于同一類，所以這是一個葉結(jié)點(diǎn)，類標(biāo)記為“是”；另一個是對應(yīng)“否”（無工作）的子結(jié)點(diǎn)，包含6個樣本，它們也屬于同一類，所以這也是一個葉結(jié)點(diǎn)，類標(biāo)記為“否”。

這樣生成一個如圖5.5所示的決策樹。該決策樹只用了兩個特征（有兩個內(nèi)部結(jié)點(diǎn)）。

image.png

C4.5算法

C4.5 生成算法與 ID3 算法相似，但是 C4.5 算法在生成過程中用信息增益比來選擇特征。

決策樹實(shí)戰(zhàn)python代碼：基于機(jī)器學(xué)習(xí)實(shí)戰(zhàn)。

https://github.com/yuki9965/decision-tree

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

機(jī)器學(xué)習(xí)系列6：決策樹

機(jī)器學(xué)習(xí)系列6：決策樹