数据仓库与数据挖掘教程（第2版） 陈文伟版课后习题答案（非常全） - 图文

3.为什么机器学习和数据挖掘的分类问题可以利用信息论原理？

信息论原理是数据挖掘的理论基础之一。一般用于分类问题，即从大量数据中获取分类知识。具体来说，就是在已知各实例的类别的数据中，找出确定类别的关键的条件属性。求关键属性的方法，即先计算各条件属性的信息量，再从中选出信息量最大的属性，信息量的计算是利用信息论原理中的公式。 4

自信息：单个消息ui发出前的不确定性（随机性）称为自信息。 计算公式为:

I(ui)?log

1??logP(ui)P(ui)

互信息：H（U）代表接受到输出符号集V以前关于输入符号集U的平均不确定性，而H（U|V）代表接受到输出符号集V后关于输入符号U的平均不确定性。则定义： I（U，V）=H（U）- H（U|V）

I（U，V）称为U和V之间的互信息，它代表接受到符号集V后获得的关于U的信息量。 计算公式为:

H(U)??P(ui)logi21P(ui) （1）

1P(ui|vj)H(U|V)??P(vj)?P(ui|vj)logji （2）

I(U,V)?H(U)?H(U|V) （3）

5

信道容量：给定信道的互信息

I(U,V)是P（U）的?型函数。由?型函数的性质知道，一定存在一概率分布P（U）I(U,V)达

，使得

到最大。这个最大的互信息就称为信道容量。 6

译码准则的基本思想是使后验概率最大或者平均错误概率最小。

7 决策树是用样本的属性作为结点，用属性的取指作为分支的树结构。通过决策树对新样本属性值的测试，从树的根节点开始，按照样本属性的取指，逐渐沿着决策树向下，直到树的叶节点，该叶节点表示的类别就是新样本的类型。

8.决策树方法的基本思想是什么？

答：J.R.Quinlan的ID方法，它的前身是CLS方法，Hunt提出的CLS工作过程为：首先找出有判断能力的属性，把数据分成多个子集，每个子集又选择有判别力的属性进行划分，一直进行到所有子集仅包括同一类的数据为止。最后得到一颗决策树，可以用它来对新的样例进行分类。CLS的不足是没有说明如可选择有判断力的属性。

9、设计用ID3决策树进行实例判别的判别算法。 答：

信息熵的计算：

信息熵：H(U)=-

类别ui出现概率：P(ui)=|ui|/|S| |S|为子集S的总数，|ui|为类别的例子数 条件熵计算：

条件熵: H(U/V)=

属性A1取值vj时，类别ui 的条件概率：P(ui/vj)=| ui |/| vj | 互信息计算： I(U/V)=H(U)-H(U|V) 4. 建决策树的树根和分支：

ID3算法将选择互信息最大的特征为树根，在所有的例子中对树根属性的取值进行分支，所有的分支对于相应的子集，若某个例子的子集全属于P类，就将其对应的分支标记为P，其余的子集将递归调用建树算法； 5. 递归建树：

对既包含正例又含有反例的例子用ID3算法，在每个子集中对各特征求互信息，并执行之前的所用算法。 10 11 12

13、C4.5方法对ID3方法的改进主要体现在什么地方？

答：C4.5克服了ID3在应用中存在的不足，比如：用信息增益率来选择属性；在树构成过程中或者构造完 成之后，进行修剪；能够完成对连续性属性的里离散化处理；能够对于不完整数据进行处理；C4.5采用 的只是表示形式为决策树，并最终可以形成产生式规则。

14、信息增益率与信息增益有什么不同？在C4.5中为什么使用信息增益率作为分支标准? 答：信息增益：I(C,V)=H(C)-H(C|V)=info(T)-infov(T)=gain（T） 信息增益率：gain_ratio=-∑p（vi）log（p（vi））

C4.5利用信息增益率是因为客服了ID3方法选择偏向取值多的属性。

15、在C4.5中如何对连续的属性进行处理？

答：在C4.5中，这在集合T中，连续属性A的取值为{v1，v2,....,vm},则任何vi和vi+1之间的任意取值都 可以把实例都可以把实例集合分为两部分T1={t|A<=vi}和T2={t|A>vi}。对属性A的m-1各种分割的任意一 种情况，最属性的两个离散取值，重新构造该属性的里三种，再按照上述公式计算每种分割所对应的信 息增益率，从而将连续的值离散化处理。

16．IBLE用信道容量作为特征选择量。

I(气温)=0.029bit I(湿度)=0.151bit I(风)=0.048bit

ID3优点：算法基础理论清晰，算法简单。

缺点：①互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。

②用互信息作为特征选择量存在一个假设，即训练例子集中的正，反例debilitating应与实际问题领域里正、反例比例相同。③ID3在建树时，每个节点仅含一个特征，是一种单变量的算法，特征间的相关性强调不够。 ④ID3对噪声较为敏感。

⑤当训练集增加时，ID3的决策树会随之变化。 略??

一般情况不能保证相同，这样计算训练集的互信息就有偏差。

17．IBLE决策树的表现形式包括：@1类的决策规则树，@2类的决策规则树和@3类的决策规则树。相比之下，IBLE的预测正确率比ID3高出近10%。IBLE用信道容量作为选择特征量，而ID3用互信量，信道容量不依赖于正反例的比例，互信息依赖训练集中正反例的比例。IBLE的规则与专家知识在内容上有较高的一致性，用IBLE获取的知识建立的专家系统对实例的判别进行解释时提供了良好的条件。这一点正是ID3的一个重要缺陷。显然，IBLE比ID3优越。

18．决策规则树中非叶节点均为规则，规则表示为特征，权值，标准值，阀值。 19、

答：第一个例子，a、c、d分别满足标准值，则权和为0.021+0.282+0.282=0.585大于等于Sp，所以第一个例子属于P类。 第二个例子，a、b、d分别满足标准值，则权和为0.021+0.048+0.282=0.345小于等于Sn，所以第二个例子属于N类。

20、说明IBLE决策规则树中结点中阀值Sn和Sp求解的思想。

答：先对各正、反例子求权和并填入数组中，再按权和大小从小到大排序，对权和相同的不同的正反例，将它们合并成一列相同的权和，累计正反例个数。此时正反例权和的规律就出现了：权和小的部分，正例个数为零，反例个数偏大；权和大的部分，正例个数偏大，反例个数为零。将整个例子集合划分成三个区：反例区，正反例混合区，正例区。在三个区的分界线处的权和值作为Sp、Sn值。

21、说明隐形眼镜简例中@3类决策规则树的含义。 答：不懂。

22. f（p（a））=log（1/p（a））

23. 在特定约束下，给定信道从规定的源发送消息的能力的度量。通常是在采用适当的代码，且差错率在可接受范围的条件下，以所能达到的最大比特率来表示。平均互信息是信道容量。

24. 译码准则的基本思想：是的平均错误概率最小的译码准则是最大后验概率准则或者是最小错误概率准则。

第8章作业

周劼人1-3 郭朋4-6 王国梁7-9 旦增群培10-11刘洋12-14 许赟昊15-17 杜海洋18-19 徐文松20-21 何金海22-23 陶汉24-25

说明等价关系、等价类以及划分的定义。

等价关系：对于?a∈A（A中包含一个或多个属性），A?R，x∈U，y∈U，他们的属性值相同，即fa（x）=fb（y）成立，称对象x和y是对属性A的等价关系。

等价类：在U中，对属性集A中具有相同等价关系的元素集合成为等价关系IND（A）的等价类。 划分：在U中对属性A的所有等价类形成的划分表示为A={Ei | Ei=[xi]a，i=1,2，? }

说明集合X的上、下近似关系定义。 下近似定义：

任一一个子集X?U，属性A的等价类Ei=[x]A ，有：A-（X）=U{Ei|Ei∈A∧Ei?X} 或A-（X）={x|[x]A?X} 表示等价类Ei=[x]A中的元素x都属于X，即?x∈A-（X），则x一定属于X。 上近似定义：

任一一个子集X?U，属性A的等价类Ei=[x]A ，有：A-（X）=U{Ei|Ei∈A∧Ei∩X≠?} 或A-（X）={x|[x]A∩X≠?} 表示等价类Ei=[x]A中的元素x可能属于X，即?x∈A-（X），则x可能属于X，也可能不属于X。

说明正域、负域和边界的定义。

全集U可以划分为三个不相交的区域，即正域（pos），负域（neg）和边界（bnd）： POSA(X)= A-（X） NEGA(X)=U- A-（X） BNDA(X) = A-（X）-A-（X）

4.

粗糙集定义：

若 ，即X为A的可定义集； BND(，X )即边界为空，称??A?(X)?A(X)

?否则X为A不可定义的，

即 A?(X)?A(X，称)X为A的Rough集（粗糙集）

?确定度定义：

?A(X)?UU?A?X?A?XUA?X?A?X ?AX?AX?分别表示集合U、（

其中5.

和 ）中的元素个数

在信息表中根据等价关系，我们可以用等价类中的一个对象（元组）来代表整个等价类，这实际上是按纵方向约简了信息表中数据。对信息表中的数据按横方向进行约简就是看信息表中有无冗余的属性，即去除这些属性后能保持等价性，使对象分类能力不会下降。约减后的属性集称为属性约减集。 6.

属性集A的所有约简的交集称为A的核。记作 core(A) 7

表6.3中，定义类别第一类人和第二类人为决策属性，身高、头发、眼睛为条件属性，身高为a，头发为b，眼睛为c，类别d。 C={a,b,c}，D={d}

IND(C)={{1},{2},{3},{4},{5},{6},{7},{8},{9}} IND(D)={{1,2,3,4},{5,6,7,8,9}} Pos C(D)=U

IND(C\\{a})={{1,3},{2},{4},{5,9},{6,7},{8}} IND(C\\{b})={{1,6},{2,3,7},{4},{5},{8},{9}} IND(C\\{c})={{1,4,9},{2},{3,5},{6},{7,8}} Pos (C\\{a}) (D)=U Pos (C\\{b}) (D)={4,5,8,9} Pos (C\\{c}) (D)={2,6,7,8}

IND(C\\{b,c})(D)={{1,4,6,9},{2,3,5,7,8}} Pos ()(C\\{b,c})(D)=空集 所以red D(C)={{a,b},{a,c}} 8

条件属性C和决策属性D之间的依赖度r(C,D)=|Pos C(D)| / |U|

其中|Pos C(D)|表示正域Pos C(D)的元素个数，|U|表示整个对象集合的个数。 9

依赖度r(C,D)的性质：

若r=1，意味着IND(C) IND(D),即在已知条件C下，可将U上全部个体准确分类到决策属性D的类别中去，即D完全依赖于C。 若0

10.属性a的重要度SGF（a、C、D）的含义是什么？ 答：

?red(A)Core(A)是A中为保证信息表中对象可精确定义的必要属性组成的集合，为A中不能约简的重要属性，它是进行属性约简的基础。