数据仓库与数据挖掘教程（第2版）课后习题答案 第八章

第七章作业

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

等价关系：对于?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.

粗糙集定义：

? ，即BND ( X ) ? ? ， 即边界为空，称X为A的可定义集； A若(X)?A?(X)否则X为A不可定义的， 即 X ) ? ? ( X A ?(A) ，称X为A的Rough集（粗糙集） 确定度定义：

?A(X)?UU?A?X?A?XUA?X?A?X 分别表示集合U、（?AXAX??其中和）中的元素个数 5.

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

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

core(A)??red(A)

Core(A)是A中为保证信息表中对象可精确定义的必要属性组成的集合，为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

若r=0，则称D完全不依赖于C，即利用条件C不能分类到D的类别中去。

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

属性重要度的定义：C、D包含A C为条件属性集，D为决策属性集，a属于a关于D的重要度定义为 SGF（a，C, D）=r（C,D）-r（C-{a},D）

其中r(C-{a},D)表示在C中缺少属性a后，条件属性与决策属性的依赖程度SGF（a、C、D）表示C中缺少属性a后，导致不能被准确分类的对象在系统中所占的比例。 （2）SGF（a、C、D）性质。 1，SGF（a、C、D）∈[0,1]。

2，若SGF（a、C、D）=0，表示属性a关于D是可省的，因为从属性集中去除属性a后，C-{a}中的消息，原来可以被准确分类为所有的对象仍可以能准确的划分到决策类中去。

3. SGF（a、C、D）≠0，表示属性a关于D是不可省的。因为属性集C中去除属性a后，某些原来可以被准确分类的对象再不能准确划分。

11.最小属性集的概念是什么？

答：设C, D分别是信息系统S的条件集和决策属性集，属性集P（P是C的子集）是C的一个最小属性集，当且仅当r(P,D)=r(C,D)并且P包含’,P，r(P’,D）≠r（P,D）,说明若P是C的最小属性集，则P具有与C同样的区分决策的能力。

需要注意的是，C的属性集一般不是唯一的，而要找到所有的最小属性集是以个NP问题。在大多数应用中，没有必要找到所有的最小属性集。用户可以根据不同的原则来选择一个他认为最好的最小属性集。

12、在数据库中获得最小属性集的步骤是什么？

答：在数据库中根据决策属性将一组对象划分为各不相交的等价集，通过条件属性来决定每一个决策类，并产生每一个类的判定规则，对每个判断规则进行精简，得到具有全部条件属性区分决策属性所划分的决策类能力的集合。

13、如何利用集合之间的上下近似关系获得规则？

答：设U中有两个划分C={Ei}和D={Yj}，把C视为分类条件，把D视为分类结论，(1)当Ei∩Yj≠时，有ij：Des(Ei)?Des(Yj), Des(Ei)和Des(Yj)分别为Ei和Yj中的特征描述。

当Ei∩Yj=Ei即下近似时，建立的规则ij是确定的，规则的可信度cf=1; 当Ei∩Yj≠Ei即上近似，建立的规则ij是不确定的，规则的可信度cf= (2)当Ei∩Yj=时，Ei和Yj不能建立规则；

14、按照聚类的原理和方法划分有哪三种聚类算法？各种聚类算法的思想是什么？ 答：按聚类的原理和方法划分，可分为层次聚类、划分聚类和基于密度的聚类；

层次聚类：递归地对对象进行合并或分裂直至满足某终止条件；

划分聚类：给定聚类数目k和目标函数F，将D划分为k个类，是目标函数在此划分下达最优，即把聚类问题过转换为一个组合最优问题，从一个初始划分开始，利用迭代控制策略优化目标函数；

基于密度的聚类：单位体积内点的个数为该点的密度，根据空间密度的差别，把具有相似密度的点作为聚类。 15

K-均值聚类算法的计算步骤：

首先随机地选取k个初始聚类中心，并把每个对象分配给离他最近的中心，从而得到一个初始聚类；然后，计算出当前每个聚类的重心作为新的聚类中心，并把每个对象重新

分配到最近的中心；如果新的聚类的质量优于原先的聚类，则用新聚类代替原聚类。循环执行这一过程直至聚类质量不再提高为止。

16．规则的支持度和可信度是什么？

规则的支持度：规则A→B在数据库D中具有支持度S，表示S是D中事物同时包含AB的百分比，它是概率P（AB）。

规则的可信度：规则A→B具有可信度C，表示C是包含A项集的同时也包含B项集，相对于包含A项集的百分比，这是条件概率P（B|A）。

17.关联规则的兴趣度定义是什么？说明兴趣度的作用。 兴趣度为 I（A→B）=P（AB）/P（A）P（B） 公式反应了项集A与项集B的相关程度。

在兴趣度的使用中，一条规则的兴趣度越大于1说明我们对规则越感兴趣（即其实际利用价值越大）；一条规则的兴趣度越小于1说明我们对这条规则的反面规则感兴趣（即其反面规则的实际利用价值越大）；显然，兴趣度I不小于0。

18.使用apriori算法找出所有的频繁项目集。 假定最小事务支持计数为2 Min-sup=2/4=0.5

C1候选集：A支持度2 ，B支持度3，C支持度3，D支持度1，E支持度3 D不是频繁项集

L1 1-项集 A支持度2 ，B支持度3，C支持度3， E支持度3

C2候选集：A,B支持度1， A,C支持度2， A,E支持度1， B,C支持度2，B,E支持度3， C,E支持度2

A,B、A,E不是频繁项集

L2频繁2-项集：A,C支持度2， B,C支持度2，B,E支持度3， C,E支持度2 C3候选集： B,C,E=2

L3频繁3-项集：B，C，E=2 算法终止，L3是最大频繁项集

19.实现apriori算法，说明apriori算法的主要系统开销在哪里？

（1）可能产生大量的候选集。当长度为1的频繁集有10000个的时候，长度为2候选集个数将会超过10M。还有就是如果要产生一个很长的规则的时候，要产生的中间元素也是巨大的。

（2）必须多次重复扫描数据库，对候选集进行模式匹配，因此效率低下。

20 L1频繁1-项集： 项集 支持度计数 L2频繁2-项集 项集 A,C A,D C,D B,C B,E C,E A,B A,E A 2 B 3 C 3 D 1 E 3 支持度计数 项集 2 1 1 2 3 2 1 1 L3频繁3-项集 A,C,D 1 A,B,C 1 A,B,C,E 1 A,C,E 1 B,C,E 2 支持度计数 L4频繁4-项集 项集 支持度计数 差异：随着最小支持度的逐渐减小，Apriori算法的性能急剧降低，而FP-树算法的性能相对稳定，所需时间没有发生突变的增加，FP-树算法比Apriori算法快一个数量级，且FP-树算法对不同长度的规则都有很好的适应性。 21，计算过程： 第一个事物：“T0：e”只有一个事物，从L表中节点链中，项e的指针指向树中节点e，且e的计数为1，即e：1。

第二个事物“T1：a，c，g，i”包含四个事物，具有四个分支，其中a为根节点，c链接到a，i链接到c，g链接到i，且计数均为1，从L表中节点链中，项，a，c，g，i的指针分别指向树中的a，c，i，g节点，因为不包含e事物，所以从R节点产生一个新分支指向a。

第三个事物“T2：d，h”因为最小支持度为20%，所以只有一个事物d，计数为1，因为不包含事物e，所以从R产生一个新分支指向d，从L表中节点链中，项d的指针指向树中的d节点。

第四个事物“T3：b，d”因为最小支持度为20%，所以只有一个事物d，从L表中节点链中，项d的指针指向树中的d节点，d计数加1.即d：2.

第五个事物“T4：d，e”包含两个事物，节点e计数加1，即e：2,，节点d链接到e，即d：1，因为已存在d：2，则有d：2指向d：1.

第六个事物“T5：a，c，e，i”包含四个事物，节点e计数加1，即e：4，a链接到e，因为已存在节点a：1，所以节点a：1指向a，a计数为1，即a：1，c连接到a，i链接到c，c：1，i：1分别指向c，i。c，i计数加1，即c：1，i：1.

第七个事物“T6：a，c，e，f，i”因为最小支持度，所以只有四个事物，则a链接到e，c链接到a，i链接到c，e，a，c，i计数分别加1，即e：4，a:2，c:2，i:2.

第八个事物“T7：a，e，g”包含三个事物，则a链接到e，g链接到a，e，a，g计数分别加1，即e：5，a:3，g:1,因为已存在g：1，所以有g：1指向新节点g:1.

第九个事物“T8：a，c，e，i”包含四个事物，则a链接到e，c链接到a，i链接到c，e，a，c，i计数分别加1，即e：6，a：4，c：3，i:3.

第十个事物“T9：c，e，g”包含三个事物，则产生一条新分支，a链接到e，g链接到a，e，c，g计数分别加1，即e：7，c：1，g：1.因为已存在节点c：3，g：1，所以节点c：3指向新节点c：1，节点g：1指向新节点g：1.

22.对上题得出的频繁项集，求出关联规则。 答：不懂。

23.集合论原理用于分类问题的思想是什么？

答：集合论原理用于分类问题时，主要是利用集合之间的覆盖关系，构成规则知识。

24.集合论原理集合论或集论是研究集合由一堆抽象物件构成的整体）的数学理论，包含了集合、元素和成员关系等最基本的数学概念。在大多数现代数学的公式化中，集合论提供了要如何描述数学物件的语言。集合论和逻辑与一阶逻辑共同构成了数学的公理化基础，以未定义的“集合”与“集合成员”等术语来形式化地建构数学物件。用于解决聚类问题时，主要是按数据集中元素间的距离远近或者是相似度的大小聚集成多个类别集合。

25. 关联规则是形如X→Y的蕴涵式，其中且， X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。集合论原理用于关联规则挖掘是计算数据项集在整个集合中和相关集合中所占的比例，大于阈值时构成数据项之间关联规则。

23.集合论原理用于分类问题的思想是什么？

答：集合论原理用于分类问题时，主要是利用集合之间的覆盖关系，构成规则知识。

24.集合论原理集合论或集论是研究集合由一堆抽象物件构成的整体）的数学理论，包含了集合、元素和成员关系等最基本的数学概念。在大多数现代数学的公式化中，集合论提供了要如何描述数学物件的语言。集合论和逻辑与一阶逻辑共同构成了数学的公理化基础，以未定义的“集合”与“集合成员”等术语来形式化地建构数学物件。用于解决聚类问题时，主要是按数据集中元素间的距离远近或者是相似度的大小聚集成多个类别集合。

25. 关联规则是形如X→Y的蕴涵式，其中且， X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。集合论原理用于关联规则挖掘是计算数据项集在整个集合中和相关集合中所占的比例，大于阈值时构成数据项之间关联规则。

本文来源：https://www.bwwdw.com/article/yg9r.html