四川大学计算机学院2013-2014学年数据挖掘试题

（面向硕士研究生）

1、（10分）分类和聚类有什么相同点和不同点？不带类标的数据可以为分类器的学习提供什么信息？

2、（10分）什么叫线性可分？支持向量机如何解决线性不可分的问题？

3、（10分）文档集的信息检索（Information Retrieval）与数据库的查询之间有什么相同点和不同点？

4、（总分20分）

（1）证明一个频繁项集的任意子集也必定是频繁的。（5分）

（2）给定如下的数据库表：

Transaction ID Items - Bought

1 {Milk, Beer, Diapers}

2 {Bread, Butter, Milk}

3 {Milk, Diapers, Cookies}

4 {Bread, Butter, Cookies}

5 {Beer, Cookies,Diapers}

6 {Milk, Diapers, Bread, Butter}

7 {Bread, Butter, Diapers}

8 {Beer, Diapers}

9 {Milk, Diapers, Bread, Butter}

10 {Beer, Cookies}

请用Apriori算法找出最小支持度30%情况下的所有频繁项集。（15分）5、（15分）用类C语言伪代码描述简单（朴素）贝叶斯分类算法（包括训练部分和测试部分）。

6、（15分）假设有如下的网页及其链接关系，

1注意：堂上开卷，只能查看自己携带的纸质资料。

假设d=0.1。请计算PageRank 算法迭代前五轮每一轮每个网页的PageRank 值。

7、（20分）下面给出了4篇文档构成的文档集以及词表中每个词在文档中出现的次数情况，

D1 Tropical Freshwater Aquarium Fish.

D2 Tropical Fish, Aquarium Care, Tank Setup.

D3 Keeping Tropical Fish and Goldfish in Aquariums and Fish Bowls. D4 The Tropical Tank Homepage – Tropical Fish and Aquariums.

Terms

Documents

D 1 D 2 D 3 D 4

aquarium 1 1 1 1 bowl 0 0 1 0 care 0 1 0 0 fish 1 1 2 1 freshwater 1 0 0 0 goldfish 0 0 1 0 homepage 0 0 0 1 keep 0 0 1 0 setup 0 1 0 0 tank 0 1 0 1 tropical

1

1

1

2

请用统计语言模型计算每篇文档与查询“Tropical Fish ”的相似度，得到该查询结果的列表，要求采用Laplace 方法对概率估计进行评平滑。

Page A

Page B Page C