参考书籍：《大数据：互联网大规模数据挖掘与分布式处理》（第二版）

原版英文书籍：Mining of Massive Datasets

注：答案为本人自己做的，并非标准答案，仅供参考。
如有错误，请私信我，我将及时修改。

《大数据：互联网大规模数据挖掘与分布式处理》（第二版）第四章习题答案

注：本书包含大量习题，较难的习题或习题中较难的部分都会用！标记，最难的习题用！！标记。

习题4.2.1

( a )

对每个元组产生一个随机整数，范围是0~19，并当且仅当随机数为0是才存储该元组。

对存储下来的元组，以university属性分类，对于同一university属性的元组，统计不同的courseID数量，将元组数/courseID数，得到的就是每所大学在一个课程中的平均学生数目。

SELECT university, COUNT(*)/COUNT(DISTINCT courseID) AS avg_student
FROM Grades_hash_0
GROUP BY university

( b )

对每个元组产生一个随机整数，范围是0~19，并当且仅当随机数为0是才存储该元组。

对存储下来的元组，统计grade>=3.5的数量，除以元组数就得到GPA不低于3.5分的学生所占的比例。

SELECT COUNT(*) AS num
FROM Grades_hash_0
WHERE grade>=3.5

SELECT COUNT(*) AS sum
FROM Grades_hash_0

ratio=num/sum

( c )

对每个元组产生一个随机整数，范围是0~19，并当且仅当随机数为0是才存储该元组。

设置一个计数器count，初始化为0。

对存储下来的元组，以courseID属性分类，统计课程数量sum。对于同一courseID属性的元组，统计greade为A的数量和元组数量，若两者相除结果≥0.5，计数器count加1。

最终结果=count/sum。

count=0

for courseid in courseID:
	
	SELECT COUNT(*) AS num_A
	FROM Grades_hash_0
	WHERE grade='A'
	GROUP BY courseID

	SELECT COUNT(*) AS num
	FROM Grades_hash_0
	GROUP BY courseID
	
	if(num_A/num>=0.5)
		count++

SELECT COUNT(DISTINCT courseID) AS sum
FROM Grades_hash_0

ratio=count/sum

习题4.3.1

如果使用3个哈希函数，相当于往80亿个靶位上投30亿支飞镖，某个位为0的概率为e^-3/8。一个非S中的元素若要成为伪正例的话，那么就必须在3个哈希函数的作用下都映射为1，而该概率为(1-e^-3/8)³≈0.0306。

如果使用4个哈希函数，相当于往80亿个靶位上投40亿支飞镖，某个位为0的概率为e^-1/2。一个非S中的元素若要成为伪正例的话，那么就必须在4个哈希函数的作用下都映射为1，而该概率为(1-e^-1/2)⁴≈0.0240。

!习题4.3.2

一次哈希未命中的概率为$\frac{n/k-1}{n/k}$。

$k$次哈希都未命中的概率为$(\frac{n/k-1}{n/k}{)}^k=(1-\frac{k}{n}{)}^k\approx e^{\frac{-k^2}{n}}$。

假阳率=$(1-e^{\frac{-m}{n/k}}{)}^k$

使用$k$个哈希函数的方法的假阳率=$(1-e^{\frac{-km}{n}}{)}^k$

这样做的假阳率与使用$k$个哈希函数的方法的假阳率相等。

!!习题4.3.3

设$f(k)=(1-e^{\frac{-km}{n}}{)}^k$。

令$f^{\prime }(k)=0$，即$(1-e^{\frac{-km}{n}}{)}^k\ast ln(1-e^{\frac{-km}{n}})\ast (-e^{\frac{-km}{n}})\ast (-\frac{m}{n})=0$，解得：$k=ln(2)\ast \frac{n}{m}$。

习题4.4.1

( a ) h(x)=2x+1 mod 32

流中整数a	h(a)	h(a)二进制表示	r(a)
3	7	00111	0
1	3	00011	0
4	9	01001	0
1	3	00011	0
5	11	01011	0
9	19	10011	0
2	5	00101	0
6	13	01101	0
5	11	01011	0

R=max_a r(a)=0，故估计的独立元素数目=2^R=1。

( b ) h(x)=3x+7 mod 32

流中整数a	h(a)	h(a)二进制表示	r(a)
3	16	10000	4
1	10	01010	1
4	19	10011	0
1	10	01010	1
5	22	10110	1
9	2	00010	1
2	13	01101	0
6	25	11001	0
5	22	10110	1

R=max_a r(a)=4，故估计的独立元素数目=2^R=16。

( c ) h(x)=4x mod 32

流中整数a	h(a)	h(a)二进制表示	r(a)
3	12	01100	2
1	4	00100	2
4	16	10000	4
1	4	00100	2
5	20	10100	2
9	4	00100	2
2	8	01000	3
6	24	11000	3
5	20	10100	2

R=max_a r(a)=4，故估计的独立元素数目=2^R=16。

!习题4.4.2

h(x)=2x+1 mod 32 不是一个好的哈希函数，因为对流中任意的整数$a$，$h(a)$一定是奇数，故$h(a)$的二进制表示的最后一位一定是$1$，因此，$r(a)$一定为0。

对一般的h(x)=ax+b mod 2^k，建议尽量生成更多不同的哈希值（完美情况是使h(a)满足平均分布），使对独立元素的估计更加精准。

习题4.5.1

在这个流中，有3个元素出现了2次，有个1元素出现了3次。

二阶矩=3×2²+1×3²=21

三阶矩=3×2³+1×3³=51

!习题4.5.2

有$n$个元素，其中有$m$个独立元素。

这些元素最均匀的分布：m-1个元素出现$\frac{n-1}{m}$次，1个元素出现$\frac{n+m-1}{m}$次。这种情况下，奇异数是最小的，为$(m-1)\times (\frac{n-1}{m}{)}^2+1\times (\frac{n+m-1}{m}{)}^2=\frac{n^2-1}{m}+1$。

这些元素最极端的分布：1个元素出现n-m+1次，其余m-1个元素各出现1次。这种情况下，奇异数是最大的，为$1\times (n-m+1{)}^2+(m-1)\times 1^2=n^2-(2n-m)\times (m-1)$。

习题4.5.3

每个X_i.value分别是：2，3，2，2，1，1，2，1，1。

习题4.5.4

每个变量的最终值是：2，3，2，2，1，1，2，1，1。

基于每个变量估计出的三阶矩分别是：63，171，63，63，9，9，63，9，9。

估计三阶矩的均值为：51。

三阶矩真实值=3×2³+1×3³=51。

误差为0。

习题4.5.5

当m=1时，1=1²，显然成立。

当m=i(i>=2)时，假设有1+…+(2i-1)=i²，
则，当m=i+1时，1+…+(2i-1)+(2i+1)=i²+2i+1=(i+1)²。

故，得证。

习题4.5.6

将v=X_i.value转变为n×(v⁴-(v-1)⁴)。

习题4.6.1

当k=5时，估计值为3，包括2个大小为1的桶的大小，1个大小为2的桶的大小的一半，真实值为3，此时，估计值与真实值的差值为0。

当k=15时，估计值为10，包括2个大小为1的桶的大小，1个大小为2的桶的大小，1个大小为4的桶的大小以及1个大小为4的桶的大小的一半，真实值为9，此时，估计值与真实值的差值为1。

!习题4.6.2

假设位流左边还要无穷个元素。

习题4.6.3

第一个1到达窗口时，桶序列为：

第二个1到达窗口时，桶序列为：

第三个1到达窗口时，桶序列为：