all：1
A: 1,000,000; B: 100; C: 1, 000; 小计: 1,001,100
AB: 1,000,000*100=100,000,000; BC: 100*1,000=100,000; AC: 1,000,000*1,000=1,000,000,000;
小计: 1,100,100,000
ABC: 1,000,000*100*1,000=100,000,000,000
总和: 1+1,001,100+1,100,100,000+100,000,000,000=101,101,101,101 * 4 = 404,404,404,404 字节
（C）指出空间需求量最小的立方体中的块计算次序，并计算2-D平面计算所需要的内存空间总量。 答：顺序计算，需要最少数量的空间B-C-A.如图所示：
计算二维平面需要的总主内存空间是：
总空间 = (100×1,000) + (1,000,000 × 10) + (100 × 10,000) = 20,100,000 单元* 4字节/单元= 80,400,000 字节
6.3 Apriori算法使用子集支持性质的先验知识。 (a) 证明频繁项集的所有非空的子集也必须是频繁的。
答：设s是一个频繁项集，min_sup 是最小支持度阀值，任务相关的数据D是数据库事务的集合，|D|是D 有事务量，则有Support_count(s) = min_sup×|D|；
再设s’是s的非空子集，则任何包含项集s的事务将同样包含项集s’ , 即：
support_ count(s') support count(s) = min_sup ×|D|.
所以，s’也是一个频繁项集。
(b) 证明项集s的任意非空子集s’的支持至少和s的支持度一样大。
答：设任务相关的数据D是数据库事务的集合，|D|是D 的事务量，由定义得：
设s’是s的非空子集，由定义得： 由（a）可知：support(s’) support(s)
由此证明，项集s的任意非空子集s’的支持至少和s的支持度一样大。
（c）给定频繁项集 l 和 l 的子集 s ,证明规则
的置信度不可能大于
答：设 s 是 l 的子集, 则
设s’是s的非空子集，则
由（b）可知：support_count(s') support count(s)，
此外，confidence(s’) 所以，规则
(l-s’)) confidence(s) (l- s)) 。
的置信度不可能大于
6.6设数据库有5个事务。设min_sup =60%, min_conf=80%
(a)分别使用Apriori和FP增长算法找出所有频繁项集。比较两种挖掘过程的效率。
效率比较：Apriori需多次扫描数据库而FP增长建立FP树只需一次的扫描。在Apriori算法中产生候选是昂贵的（由于联接），而FP增长不产生任何候选。
(b)列举所有与下面的元规则匹配的强关联规则（给出支持度S和置信度C）,其中，X是代表顾客的变量，itemi是表示项的变量（如：“A”、“B”等）：
答： k,o e [0.6,1]
e,o k [0.6,1]
6.8.数据库有4个事务，设min_sup =60%, min_conf=80%
（a）在item_category粒度（例如，itemi 可以是“Milk”），对于下面的规则模板
对最大的k,列出频繁k项集包含最大的k的频繁k项集的所有强关联规则（包括它们的支持度S和置信度c）. (b)在 粒度（例如：itemi 可以是“Sunset-Milk”）对于下面的规则模板
对最大的k，列出频繁k项集（但不输出任何规则）。
6.14 下面的相依表汇总了超级市场的事务数据。其中，hot dogs表示包含热狗的事务，hot dogs表示不包含热狗的事务，hamburgers表示包含汉堡包的事务，hamburgers表示不包含汉堡包的事务，
（a）假定挖掘出了关联规则该关联规则是强规则吗？
答：根据规则， support = 2000/5000 = 40%， confidence = 2000/3000 = 66.7%. 该关联规则是强规则.
。给定最小支持度阀值25%，最小置信度阀值50%，
（b）根据给定的数据，买 hot dogs独立于买humburgers吗？如果不是，二者之间存在何种相关联系。 答：corr{hotdog;hamburger} = P({hot dog, hamburger})/(P({hot dog}) P({hamburger})=0.4/(0.5 × 0.6)
=1.33 > 1. 所以，买 hot dogs不是独立于买humburgers。两者存在正相关关系 8.1 简述决策树分类的主要步骤。
8.5 给定一个具有50个属性（每个属性包含100个不同值）的5GB的数据集，而你的台式机有512M内存。简述对这种大型数据集构造决策树的一种有效算法。通过粗略地计算机主存的使用说明你的答案是正确的。
这个问题我们将使用雨林算法。假设有C类标签。最需要的内存将是avc-set为根的树。计算avc-set的根节点，我们扫描一次数据库，构建avc-list每50个属性。每一个avc-list的尺寸是100×C，avc-set的总大小是100×C×50，对于合理的C将很容易适应512 MB内存，计算其他avc-sets也是使用类似的方法，但他们将较小，因为很少属性可用。在并行计算时，我们可以通过计算avc-set节点来减少同一水平上的扫描次数，使用这种每节点小avc-sets的方法，我们或许可以适应内存的水平。
8.7下表由雇员数据库的训练数据组成。数据已泛化。例如：age “31...35”表示年龄在31-35之间。对于给定的行，count表示department,status,age和salary在该行具有给定值的元组数。设status 是类标号属性。
（a）如何修改基本决策树算法，以便考虑每个广义数据元组（即每一行）的count? (b)使用修改的算法，构造给定数据的决策树。
(c)给定一个数据元组，它在属性department,age和salary的值分别为“systems”,“26..30”,和“46K.. 50K”。该元组status的朴素贝叶斯分类是什么？
9.2支持向量机（SVM）是一种具有高准确率的分类方法。然而，在使用大型数据元组集进行训练时，SVM的处理速度很慢。讨论如何克服这一困难，并为大型数据集有效的SVM算法。
数据挖掘概念与技术(第三版)部分习题答案.doc
