其他分类练习题

2020-03-20 本文已影响0人从此不迷茫

1.考虑一个二值分类问题，属性集和属性值如下：

空调={可用，不可用}

引擎={好，差}

行车里程={高，中，低}

生锈={是，否}

假设一个基于规则的分类器产生的规则集如下：

行车里程=高 $\rightarrow$ 价值=低

行车里程=低 $\rightarrow$ 价值=高

空调=可用，引擎=好 $\rightarrow$ 价值=高

可调=可用，引擎=差 $\rightarrow$ 价值=低

空调=不可用 $\rightarrow$ 价值=低

（a）这些规则是互斥的吗？

不是

（b)这些规则是完全的吗？

是。

（c)这些规则需要排序吗?

Yes because a test instance may trigger more than one rule.

(d)规则集需要默认类吗?

No because every instance is guaranteed to trigger at least

one rule.

2.RIPPER算法是早期算法IREP的扩展，两个算法都使用减少误差剪枝（reduced-error pruning）方法来确定一个规则是否需要剪枝，减少误差剪枝方法使用一个确认集来估计分类器的泛化误差。考虑下面两个规则：

R1:A $\rightarrow$ C

R2:A $\land$ B $\rightarrow$ C

R2是由R1左边添加合取项B得到的。现在的问题是，从规则增长和规则剪枝的角度来确定R2是否比R1好。为了确定规则是否应该剪枝，IREP计算下面的度量：

$v_{IREP} \frac{p+(N-n)}{P+N}$

其中，P是确认集中正例的总数，N是确认集中反例的总数，p是确认集中被规则覆盖的正例数，而n是确认集中被规则覆盖的反例数。实际上，virep类似于确认集的分类准确率.IREP偏向于virep值较高的规则。另一方面，RIPPER使用下面的度量来确定规则是否应该剪枝： $v_{RIPPER} \frac{p-n}{p+n}$

(1)假设R1覆盖350个正例和150个反例，而R2覆盖300个正例和50个反例。计算R2相对于R1的FOIL信息增益。

Gain=300*{log2(300/350)-log2(350/500)}=87.65

(2)考虑一个确认集，包含500个正例和500个反例。假设R1覆盖200个正例和50个反例，R2覆盖100个正例和5个反例。计算R1和R2的Virep,IREP 偏向于那个规则？

对R1： $v_{IREP} \frac{p+(N-n)}{P+N}$ ={200+（500-50）}/1000=0.65

对R2： $v_{IREP} \frac{p+(N-n)}{P+N}$ ={100+（500-5）}/1000=0.595

IREP偏向于R1

（3）计算（2）中的Vripper，RIPPER偏向于哪个规则？

对R1： $v_{RIPPER} \frac{p-n}{p+n}$ =（200-50）/（200+50）=0.6

对R2： $v_{RIPPER} \frac{p-n}{p+n}$ =（100-5）/（100+5）=0.9

RIPPER偏向于R2

3.C4.5规则是从决策树生成规则的间接方法的一个实现，而RIPPER是从数据中生成规则的直接方法的一个实现。

（a)讨论两者的优缺点。

C4.5规则算法从全局角度生成分类规则。这是因为规则是从决策树中派生出来的，决策树的目的是将特征空间划分为同质区域，而不关注任何类。相反，RIPPER一次生成一个类的规则。因此，它更偏向于首先生成的类。

（b)考虑一个数据集，其中类的大小差别很大（即有些累比其它类大得多）。在为较小的类寻找高准确率规则方面，哪一种方法（C4.5和RIPPER）更好？

C4.5规则使用的类排序方案比RIPPER使用的方案更容易解释。

4.考虑一个训练集，包含100个正例和400个反例。对于下面的候选规则：

R1：A->+(覆盖4个正例和1个反例)

R2:B->+ (覆盖30个正例和10个反例）

R3：C-> + (覆盖100个正例和90个反例）

根据下面的度量，确定最好规则和最差规则：

（1）规则准确率。

准确率依次为：R1:80%,R2:75%,R3:52.6%。因此最好规则是R1，最差规则是R3

（2）FOIL信息增益

假设初始规则： $\phi$ $\rightarrow$ +（覆盖100个正例和400个反例）

对R1：Gain1=4*{log2(4/5)-log2(100/500)}=8

对R2：Gain2=30*{log2(30/40)-log2(100/500)}=57.2

对R3：Gain3=100*{log2(100/190)-log2(100/500)}=139.6

因此，R3最好，R1最差。

（3）似然比统计量

对于R1，正类的期望频率为5×100/500=1

负类的期望频率为5×400/500=4。

因此，R1的似然比是2*{4*log2(4/1)+1*log2(1/4)}=12

对于R2，正类的期望频率为40×100/500=8

负类的期望频率为40×400/500=32。

因此，R2的似然比是2*{30*log2(30/8)+10*log2(10/32)}=80.85

对于R3，正类的期望频率为190×100/500=38

负类的期望频率为190×400/500=152。

因此，R3的似然比是2*{100*log2(100/38)+90*log2(90/152)}=143

R3是最好的规则，R1是最差的。

（4）拉普拉斯度量

（5）m度量（k=2且p+=0.2）

其中n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率。注意，当=1/k时，m估计等价于Laplace度量。

拉普拉斯度量依次为：R1：（4+1）/（5+2）=71.43%,R2:(30+1）/（40+2）=73.81%，R3：（100+1)/(190+2)=52.6%.因此R2是最好的，R3是最差的。

m度量：R1：（4+2*0.2）/（5+2）=62.86%，R2：（30+2*0.2）/（40+2）=73.38%，R3：（100+2*0.2）/（190+2）=52.3%

R2最好，R3最差。

5.下图给出了分类规则R1、R2、R3的覆盖率。根据以下度量确定最好规则和最差规则：

（1)似然比统计量

（2）拉普拉斯统计量

（3）m度量（k=2且p+=0.58）

（4）发现规则R1后的准确率，这里不删除R1覆盖的任何样例

（5）发现规则R1后的准确率，这里仅删除R1覆盖的正例

（6）发现R1后的准确率，这里删除R1覆盖的任何样例

Elimination of training records by the sequential covering algorithm. R1, R2, and R3represent regions covered by three different rules.

（1）数据集中有29个正例21个反例。R1覆盖了12个正例和3个反例，正例期望样例数为15*29/50=8.7，反例期望数为15*21/50=6.3.因此R1的似然比统计量为：

2*{12*log2(12/8.7)+3*log2(3/6.3)}=4.71

R2 covers 7 positive examples and 3 negative examples. The expected frequency for the negative class is 10 × 21/50 = 4.2 and the expected frequency for the positive class is 10 × 29/50 = 5.8. Therefore, the likelihood ratio for R2 is

2*{7*log2(7/5.8)+3*log2(3/4.2)}=0.89

R3 covers 8 positive examples and 4 negative examples. The expectedfrequency for the positive class is 12 × 29/50 = 6.96 and the expected frequency for the negative class is 12 × 21/50 = 5.04. Therefore, the likelihood ratio for R3 is

2*{8*log2(8/6.96)+4*log2(4/5.04)}=0.5472

因此根据似然比统计量，R1是最好的规则，R3最差。

（2）The Laplace measure for the rules are 76.47% ((12+1)/(15+2)for R1), 66.67% (for R2), and 64.29% (for R3), respectively. Therefore R1 is the best rule and R3 is the worst rule according to the Laplace measure.

(3)The m-estimate measure for the rules are 77.41% (for R1), 68.0% ((7+2*29/50)/(10+2)for R2), and 65.43% (for R3), respectively. Therefore R1 is the best rule and R3 is the worst rule according to the m-estimate measure.

(4)If the examples for R1 are not discarded, then R2 will be chosen because it has a higher accuracy (7/10=70%) than R3 (8/12=66.7%).

(5)If the positive examples covered by R1 are discarded, the new accuracies for R2 and R3 are 70% and 60%, respectively. Therefore R2 is preferred over R3.

(6)If the positive and negative examples covered by R1 are discarded, the new accuracies for R2 and R3 are 70% and 75%, respectively. In this case, R3 is preferred over R2.

6.(a)假设本科生抽烟的比例为15%，研究生抽烟的比例为23%。如果大学生中研究生占比1/5，其余是本科生，那么抽烟的学生是研究生的概率是多少？

设X={0，1}，表示抽烟与否。Y={本科生，研究生}

P{X=1|Y=本科生}=15%，P{X=1|Y=研究生}=23%,P{Y=研究生}=1/5

P{X=1}=P{X=1,Y=本科生}+P{X=1,Y=研究生}=P{X=1|Y=本科生}*P{Y=本科生}+P{X=1|Y=研究生}*P{Y=研究生}=15%*4/5+23%*1/5=16.6%

故P{Y=研究生|X=1}=P{X=1|Y=研究生}*P{Y=研究生}/P{X=1}=（23%*1/5）/16.6%=27.7%

（b)根据（a)中信息，随机选择一个大学生，该生是研究生和本科生的可能性哪个大？

本科生大。P(UG)>P(G)

（c)同（b)，假设学生是个抽烟者。

P{Y=本科生|X=1}=1-P{Y=研究生|X=1}=72.3%。本科生的可能性大。

（d)假设30%的研究生住学生宿舍，只有10%的本科生住学生宿舍。如果一个学生抽烟又住宿舍，那么他（她）是研究生或本科生的可能性哪个大？可以假设学生抽烟和住宿舍独立。

设Z={住宿舍，不住宿舍}={1，0}.P{Z=1|Y=研究生}=0.3 P{Z=1|Y=本科生}=0.1

P(D) = P(UG).P (D|UG)+P(G).P (D|G) = 0.8∗0.1+0.2∗0.3 = 0.14.

P(S) = P(S|UG)P(UG)+P(S|G)P(G) = 0.15∗0.8+0.23∗0.2 = 0.166.

P(DS|G) = P(D|G) × P(S|G) = 0.3 × 0.23 = 0.069 (using conditional independent assumption)

P(DS|UG) = P(D|UG) × P(S|UG) = 0.1 × 0.15 = 0.015.

P{Y=研究生|X=1,Z=1}=P(DS|G)*P（G)/P(DS)=0.069*0.2/P(DS)=0.0138/P(DS)

P{Y=本科|X=1,Z=1}=P(DS|UG)*P（UG)/P(DS)=0.015*0.8/P(DS)=0.012/P(DS)

P{Y=研究生|X=1,Z=1}>P{Y=本科|X=1,Z=1}.

7.考虑下表中数据集。

（1)估计条件概率P（A|+)，P(B|+),P(C|+),P(A|-),P(B|-),P(C|-)。

P(A=1|+)=P(A=1,+)/P(+)=0.3/0.5=0.6

P(A = 1|−) = 2/5 = 0.4, P(B = 1|−) = 2/5 = 0.4,

P(C = 1|−) = 1, P(A = 0|−) = 3/5 = 0.6,

P(B = 0|−) = 3/5 = 0.6, P(C = 0|−) = 0;

P(B = 1|+) = 1/5 = 0.2, P(C = 1|+) = 2/5 = 0.4,

P(A = 0|+) = 2/5 = 0.4, P(B = 0|+) = 4/5 = 0.8,

P(C = 0|+) = 3/5 = 0.6.

(2)根据（1）中条件概率，使用朴素贝叶斯方法预测测试样本（A=0,B=1,C=0)的类标号。

设P(A=0,B=1,C=0)=K

P（+|A=0,B=1,C=0)=P(A=0,B=1,C=0,+)/P(A=0,B=1,C=0)

=P(A=0,B=1,C=0|+)P(+)/K

=P(A=0|+)P(B=1|+)P(C=0|+)P(+)/K

=0.4*0.2*0.6*0.5/K=0.024/K

P(-|A=0,B=1,C=0|)=P(A=0,B=1,C=0|-)P(-)/K

由于P(-|A=0,B=1,C=0)<P(+|A=0,B=1,C=0),故类标号为+

（3）使用m估计方法（p=1/2且m=4）估计条件概率。

$P(x_{i} |y_{j})=\frac{n_{c} +mp}{n+m}$

P(A=1|+)=(3+4*1/2)/(5+4)=5/9

P(A = 0|+) = (2 + 2)/(5 + 4) = 4/9,

P(A = 0|−) = (3+2)/(5 + 4) = 5/9,

P(B = 1|+) = (1 + 2)/(5 + 4) = 3/9,

P(B = 1|−) = (2+2)/(5 + 4) = 4/9,

P(C = 0|+) = (3 + 2)/(5 + 4) = 5/9,

P(C = 0|−) = (0+2)/(5 + 4) = 2/9.

(4)同（b)，使用（c)中条件概率。

Let P(A = 0,B = 1, C = 0) = K

P(+|A = 0,B = 1, C = 0)

= P(A = 0,B = 1, C = 0|+) × P(+)/P(A = 0,B = 1, C = 0)

=P(A = 0|+)P(B = 1|+)P(C = 0|+) × P(+)/K

=(4/9) × (3/9) × (5/9) × 0.5/K

= 0.0412/K

P(−|A = 0,B = 1, C = 0)= 0.0274/K

类标号是+

（5）比较两种方法，哪种好?

当其中一个条件概率为零时，使用m-估计概率方法对条件概率的估计更好，因为我们不希望整个表达式变成零。

8.考虑下标数据集。

（1）估计条件概率P(A=1|+),P(B=1|+),P(C=1|+),P(A=1|-),P(B=1|-),P(C=1|-).

P(A=1|+)=3/5=0.6,P(A=1|-)=2/5=0.4

P(B=1|+)=2/5=0.4,P(B=1|-)=2/5=0.4

P(C=1|+)=4/5=0.8,P(C=1|-)=1/5=0.2

(2)根据（1）中条件概率，使用朴素贝叶斯方法预测测试样本（A=1,B=1,C=1)的类标号。

P(+|A=1,B=1,C=1)=P(A=1,B=1,C=1|+)P(+)/P(A=1,B=1,C=1)=P(A=1|+)P(B=1|+)P(C=1|+)P(+)/P(A=1,B=1,C=1)=0.6*0.4*0.8*0.5/0.1=0.96

P(-|A=1,B=1,C=1)=P(A=1,B=1,C=1|-)P(-)/P(A=1,B=1,C=1)=P(A=1|-)P(B=1|-)P(C=1|-)P(-)/P(A=1,B=1,C=1)=0.4*0.4*0.2*0.5/0.1=0.16

类标号为+

（3）比较P(A=1),P(B=1)和P(A=1,B=1).陈述A，B之间的关系。

P(A=1)=0.5,P(B=1)=0.4,P(A=1,B=1)=0.2.

P(A=1,B=1)=P(A=1)*P(B=1),因此A，B之间独立。

（4）对P(A=1),P(B=0)和P(A=1,B=0)重复（3）的分析。

P(A=1)=0.5,P(B=0)=0.6,P(A=1,B=0)=0.3,A,B独立。

（5）比较P（A=1,B=1|类=+）与P(A=1|类=+）和P(B=1|类=+）。给定+，变量A，B独立吗？

P（A=1,B=1|类=+）=0.2 P(A=1|类=+）=3/5=0.6 P(B=1|类=+）=0.4

P（A=1,B=1|类=+）=0.2≠P(A=1|类=+）*P(B=1|类=+）A,B不条件独立

9.（a)解释朴素贝叶斯分类器在下图数据集上的工作过程。

下图数据集

朴素贝叶斯分类器在这个数据集上做得不好，因为给定类的每个区别属性的条件概率对于类A和类B都是相同的。

（b)如果每个类进一步分割，得到四个类（A1,A2,B1,B2)，朴素贝叶斯分类器会工作得更好吗？

朴素贝叶斯分类器的性能在子类上会有所提高，因为每个子类的区分属性的条件概率乘积是不同的。

（c)决策树在该数据集上怎样工作（两类问题）？四个类呢？

对于两类问题，决策树的性能不好，因为在使用区分属性对数据进行分割后，熵不会得到改善。如果有四个类，那么决策树将会有很大的改进。

10.使用下面的信息，重复例子的分析，寻找决策边界位置：

（a)先验概率P(鳄鱼）=2*P（美洲鳄）

$P(X|鳄鱼)=\frac{P(鳄鱼|X)\times P(X)}{P(鳄鱼)}$

$P(X|美洲鳄)=\frac{P(美洲鳄|X)\times P(X)}{P(美洲鳄)}$

理想决策边界满足：ˆx = 13.0379.

（b)先验概率P(美洲鳄）=2*P(🐊）

ˆx = 13.9621.

（c)先验概率相同，但标准差不同，例如，σ（鳄鱼）=4，σ（美洲鳄）=2.

ˆx = 22.1668.

11.下图给出了下表数据集对应的贝叶斯信念网络（假设所有属性都是二元的）。

（a)画出网络中每个结点对应的概率表。

（b)使用贝叶斯信念网络计算P(引擎=差，空调=不可用）。

（a)P(行车里程=高）=0.5

P(引擎=好|行车里程=高）=0.5

P(引擎=好|行车里程=低）=0.5

P(空调=可用）=0.5

P(车的价值=高|引擎=好，空调=可用）=12/16

P（车的价值=高|引擎=好，空调=不可用）=6/9

P（车的价值=高|引擎=差，空调=可用）=2/9

P（车的价值=高|引擎=差，空调=不可用）=0

$（b)P(引擎=差，空调=不可用）=\sum\nolimits_{\alpha \beta }P(引擎=差，空调=不可用，行车里程=\alpha ，车的价值=\beta ）$

$=\sum\nolimits_{\alpha \beta }P(车的价值=\beta|引擎=差，空调=不可用）\times P(引擎 = 差|行车里程= α)P(行车里程 = α)P(空调=不可用)$

（上式中，用到全概率公式，空调和引擎独立条件）

=0.1453

12.给定下图所示贝叶斯信念网络，计算下面概率：

(a)P(B=好,F=空，G=空，S=是）

(b)P(B=差，F=空，G=非空，S=否）

(c)如果电池是差的，计算车发动起来的概率。

（a)P(B = good, F = empty,G = empty, S = yes)

= P(B = good) × P(F = empty) × P(G = empty|B = good, F = empty)×P(S = yes|B = good, F = empty)= 0.9 × 0.2 × 0.8 × 0.2 = 0.0288.

（b)P(B = bad, F = empty,G = not empty, S = no)= P(B = bad) × P(F = empty) × P(G = not empty|B = bad, F = empty)×P(S = no|B = bad, F = empty)= 0.1 × 0.2 × 0.1 × 1.0 = 0.002.

(c)P(S = yes|B = bad)

= $\sum_{\alpha }$ P(S = yes|B = bad, F = α)P(B = bad)P(F = α)

= 0.1 × 0.1 × 0.8

= 0.008