分类练习题1

1.为四个布尔属性A,B,C,D的奇偶函数画一棵完全决策树。可以简化该决策树吗？

Figure 4.1.四个布尔属性奇偶函数的决策树。

不能简化该决策树。

2.考虑下表中二元分类问题的训练样本。

Data set for Exercise 2.

a.计算整个训练样本集的Gini指标值。

1-2*0.5^2=0.5

b.计算属性顾客ID的Gini指标值。

每个客户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指标值。

小：1-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，因此该属性没有预测能力。

3.已知二元分类问题的样本集。

Data set for Exercise 3

a.整个训练样本集关于类属性的熵是多少？这个训练实例集合相对于正类的熵是多少？

有4个正号和5个负号。因此，P(+)=4/9，P(-)=5/9。训练实例的熵为−4/9log2(4/9)–5/9log2(5/9)=0.9911。

b.关于这些训练样本，a1和a2的信息增益是多少？

对于属性a1，相应的计数和概率

a1的熵

因此，a1的信息增益为0.9911−0.7616=0.2294。

对于属性a2，相应的计数和概率

a2的熵

因此，a1的信息增益为0.9911− 0.9839 = 0.0072。

c.对于连续属性a3，计算所有可能的划分的信息熵增益。

a3的最佳分割发生在分割点等于2处。

d.根据信息增益，哪个是最佳划分(a1,a2,a3)？

a1.

e.根据分类差错率，哪个是最佳划分（a1,a2)？

对于属性a1：错误率=2/9。

对于属性a2：错误率=4/9。

因此，根据错误率，a1产生最佳分割.

f.根据Gini指标，那个是最佳划分（a1,a2)？

对于属性a1，基尼指标是

对于属性a2，基尼指标是

由于a1的基尼指数较小，它产生了更好的分割。

4.证明：将结点划分为更小的后继结点后，结点熵不再会增加。

证明：设Y={y1，y2，···，Yc}表示c类，X={x1，x2，···，Xk}表示属性X的k属性值。在X上拆分结点之前，熵为：

其中，由全概率公式

在X上分割后，每个子节点X＝的熵是：

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

在X上分割后的熵由子节点的加权熵给出：

其中我们使用了概率论中的一个已知事实，即。注意E（Y | X）也被称为Y给定X的条件熵。

为了回答这个问题，我们需要证明E(Y | X)≤E(Y)。我们用方程4.1和4.3计算分裂后和分裂前的熵之差，即E(Y | X)-E(Y)：

为了证明方程4.4是非正的，我们使用对数函数的以下性质：

以为条件。这个性质是一个更一般的关于凸函数（包括对数函数）的定理的特例，称为Jensen不等式。

通过应用Jensen不等式，方程4.4可以有如下界：

因为E(Y|X)-E(Y)≤0，所以在一个属性上分割后熵不会增加。