1.為四個布爾屬性A,B,C,D的奇偶函數(shù)畫一棵完全決策樹?？梢院喕摏Q策樹嗎？

Figure 4.1.四個布爾屬性奇偶函數(shù)的決策樹。

不能簡化該決策樹。

2.考慮下表中二元分類問題的訓(xùn)練樣本。

Data set for Exercise 2.

a.計算整個訓(xùn)練樣本集的Gini指標(biāo)值。

1-2*0.5^2=0.5

b.計算屬性顧客ID的Gini指標(biāo)值。

每個客戶ID值的基尼為0。因此，客戶ID的總體基尼為0。

c.計算屬性性別的Gini值。

男性的基尼為1-0.4^2-0.6^2=0.48。女性的基尼也是0.48。因此，總體性別基尼為0.48×0.5+0.48×0.5=0.48。

d.計算使用多路劃分屬性車型的gini值。

家用車基尼為0.375，跑車為0，豪華車為0.2188。總基尼為0.1625。

e.計算使用多路劃分屬性襯衣尺碼的Gini指標(biāo)值。

?。?-0.4^2-0.6^2=0.48

中:1-(3/7)^2-(4/7)^2=0.4898

大：1-2*0.5^2=0.5

加大：1-2*0.5^2=0.5

總Gini：0.48*0.25+0.4898*7/20+0.5*0.2+0.5*0.2=0.4914

f.哪個屬性更好，性別、車型還是襯衣尺碼？

車型，因為它在三個屬性中基尼最低。

g.解釋為什么屬性顧客ID的Gini值最低，但卻不能作為屬性測試條件。

由于新客戶被分配給新客戶id，因此該屬性沒有預(yù)測能力。

3.已知二元分類問題的樣本集。

Data set for Exercise 3

a.整個訓(xùn)練樣本集關(guān)于類屬性的熵是多少？這個訓(xùn)練實例集合相對于正類的熵是多少？

有4個正號和5個負號。因此，P(+)=4/9，P(-)=5/9。訓(xùn)練實例的熵為?4/9log2(4/9)–5/9log2(5/9)=0.9911。

b.關(guān)于這些訓(xùn)練樣本，a1和a2的信息增益是多少？

對于屬性a1，相應(yīng)的計數(shù)和概率

a1的熵

因此，a1的信息增益為0.9911?0.7616=0.2294。

對于屬性a2，相應(yīng)的計數(shù)和概率

a2的熵

因此，a1的信息增益為0.9911? 0.9839 = 0.0072。

c.對于連續(xù)屬性a3，計算所有可能的劃分的信息熵增益。

a3的最佳分割發(fā)生在分割點等于2處。

d.根據(jù)信息增益，哪個是最佳劃分(a1,a2,a3)？

a1.

e.根據(jù)分類差錯率，哪個是最佳劃分（a1,a2)？

對于屬性a1：錯誤率=2/9。

對于屬性a2：錯誤率=4/9。

因此，根據(jù)錯誤率，a1產(chǎn)生最佳分割.

f.根據(jù)Gini指標(biāo)，那個是最佳劃分（a1,a2)？

對于屬性a1，基尼指標(biāo)是

對于屬性a2，基尼指標(biāo)是

由于a1的基尼指數(shù)較小，它產(chǎn)生了更好的分割。

4.證明：將結(jié)點劃分為更小的后繼結(jié)點后，結(jié)點熵不再會增加。

證明：設(shè)Y={y1，y2，···，Yc}表示c類，X={x1，x2，···，Xk}表示屬性X的k屬性值。在X上拆分結(jié)點之前，熵為：

其中，由全概率公式

在X上分割后，每個子節(jié)點X＝的熵是：

其中p(yj|xi)是X=xi的例子，屬于yj類。

在X上分割后的熵由子節(jié)點的加權(quán)熵給出：

其中我們使用了概率論中的一個已知事實，即。注意E（Y | X）也被稱為Y給定X的條件熵。

為了回答這個問題，我們需要證明E(Y | X)≤E(Y)。我們用方程4.1和4.3計算分裂后和分裂前的熵之差，即E(Y | X)-E(Y)：

為了證明方程4.4是非正的，我們使用對數(shù)函數(shù)的以下性質(zhì)：

以為條件。這個性質(zhì)是一個更一般的關(guān)于凸函數(shù)（包括對數(shù)函數(shù)）的定理的特例，稱為Jensen不等式。

通過應(yīng)用Jensen不等式，方程4.4可以有如下界：

因為E(Y|X)-E(Y)≤0，所以在一個屬性上分割后熵不會增加。