数据挖掘概念与技术_第三版_课后习题「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

写在前面

该文为数据挖掘概念与技术第三版课后习题的答案，部分参考了第二版的英文答案，由于个人水平有限，如若存在纰漏，请在评论区批评指正。另外，由于本次编辑格式较乱，可在资源下载区下载PDF版本以便参考。

第一章 引论

1. 什么是数据挖掘？在你的回答中，强调以下问题：
   1） 它是又一种噱头吗？
   2） 它是一种从数据库、统计学、机器学习和模式识别发展而来的技术的简单转换或应用吗？
   3） 我们提出了一种观点，说数据挖掘是数据库技术进化的结果。你认为数据挖掘也是机器学习研究进化的结果吗？你能基于该学科的发展历史提出这一观点吗？针对统计学和模式识别领域，做相同的事情。
   4） 当把数据挖掘当做知识发现过程时，描述数据挖掘所涉及的步骤。
   数据挖掘指从大量数据中挖掘出有趣模式和知识的过程或方法。
   数据挖掘不是另一种噱头，数据挖掘的兴起是由于海量数据及其转化为有效信息和知识的需求。因此，数据挖掘作为信息技术的自然革命的一个结果。
   数据挖掘比从数据库、统计学等简单转换或应用更复杂。数据挖掘是数据库、神经网络、机器学习、高性能计算、模式识别、数据可视化等的集成和综合。
   机器学习与数据挖掘高度相关，机器学习模型通常非常强调准确性，而数据挖掘则强调挖掘方法在大型数据集上的有效性和可收缩性，以及处理复杂数据类型的方法，开发新的非传统方法；统计学研究数据的收集、分析、解释和表示，与数据挖掘具有天然联系；统计学方法可以用来验证数据挖掘结果等。因此可以说数据挖掘是统计学技术进步的结果；模式识别重在认识事物，数据挖掘重在发现知识，因此可以说数据挖掘是一种方法，用于模式识别。
   数据挖掘作为知识发现过程时，步骤有：1）数据清理；2）数据集成；3）数据选择；4）数据转换；5）数据挖掘；6）模式评估；7）知识表示。

2. 数据仓库与数据库有何不同？它们有哪些相似之处？
   数据库是由一组内部相关的数据和一组管理和存取数据的软件程序组成；数据仓库是一个从多个数据源手机的信息存储库。不同点是数据库由表组成，数据仓库是由数据立方体的多维数据结构建模。相似点在于数据库和数据仓库都可以存储数据，都是数据分析和挖掘的信息源。

3. 定义以下数据挖掘功能：特征化、区分、关联和相关性分析、分类、回归、聚类、离群点分析。使用你熟悉的现实生活中的数据库，给出每种数据挖掘功能的例子。
   数据特征化是目标类数据的一般特性或者特征的汇总。例如可以通过收集销量在前10%的物品的信息，再进行特征汇总。
   数据区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。例如将销量增加10%和销量减少30%的物品放在一起进行比较。
   数据分类是找出描述和区分数据类或概念的模型，以便能够使用模型预测类标号位置的对象的类标号。例如找出描述销量增加30%和销量减少30%的物品，通过对其特征进行描述和建模，再对一个新的物品根据其特征将其分类。
   回归建立连续值函数模型，用于预测缺失的难以确定的数据值。例如补全未采样的数据。
   聚类根据最大化类内相似性、最小化类间相似性的原则分析数据对象，但不进行类标号。例如可以对客户数据进行分析，以簇形式表示每个购物目标群。
   离群点分析指研究那些与数据的一般行为或模型不一致的数据离散点，可以从中挖掘某种模式。例如使用离群点分析发现信用卡诈骗使用活动。

4. 给出一个例子，其中数据挖掘对于工商企业的成功是至关重要的。该工商企业需要什么数据挖掘功能？这种模式能够通过简单的查询处理或统计分析得到吗？
   以百货商店为例，可以使用数据挖掘去开展商业目标邮件活动，可以使用聚类方法去找出商品的特定消费人群的特征，进而给与该类人群相似的顾客发送该商品促销邮件。此时简单的查询处理不能找出特定人群特征，同样，统计分析不能处理该百货商店里大量的顾客数据记录。

5. 解释区分和分类、特征化和聚类、分类和回归之间的区别和相似之处。
   区分指的是将目标类数据的一般特性和一个或多个对比类对象的一般特性进行比较，即找出两者之间的特征区别；分类指的是找出一种模型来描述和区分数据类型或概念，并预测类标号未知的对象的类标号。两者的相似性在于他们都要对目标类数据对象进行处理和分析，输出结果都是类别特征，这些类别是预先指定的。
   特征化是对目标类数据的的一般特性或特征的汇总；聚类是指对数据对象在不考虑明确标签分类下的情况下进行分析。两者的相似处在于他们都刻画目标的总体特征。
   分类用于找出一种模型来描述和区分数据类型或概念，并预测类标号未知的对象的类标号；而回归则是建立一个连续值函数模型，而不是离散、无序的标号。相似点在于两者都是用函数进行预测。

6. 根据你的观察，描述一个可能的知识类型，它需要由数据挖掘方法发现，但未在本章中列出，他需要一种不同于本章列举的数据挖掘技术吗？
   建立一个周期性的知识类型，在不同时间段内数据会更新和修改，但是会发生重复性动作。此时要从时间出发，使用一种新的数据挖掘技术。

7. 以欺诈检测为例，提出两种可以用来检测离群点的方法，并讨论哪种方法更可靠。
   1） 使用聚类方法，在进行聚类分析之后，不同的簇代表着不同的数据类型，离散点不在簇的范围内。聚类分析是最有效的检测离群点的方法。
   2） 使用回归方法，基于全体数据建立一个可能的数据预测模型，如果一个值极大偏离回归值，可以认为该数据是一个离散点。

8. 描述三个关于数据挖掘方法和用户交互问题的数据挖掘挑战。
   1） 处理不同的知识类型：不同的用户对不同的知识类型感兴趣，可能以不同的方式使用同一个数据库，并且需要不同的数据挖掘技术。
   2） 挖掘多维空间中的知识：我们需要通过返回的结果给出和定义数据挖掘的要求，并在多维数据立方体中从不同角度和组合搜索有趣的知识模式。
   3） 跨学科的背景知识：背景知识能能够有助于帮助人们去分析、发现和表达发现的模式对于多学科的作用。

9. 与挖掘少量数据相比，挖掘海量数据的主要挑战是什么？
   一方面是数据挖掘算法的有效性和可伸缩性，即数据挖掘算法的运行时间必须是可预计的、短的和可以被应用接受的。
   另一方面是并行、分布式和增量挖掘算法，即海量数据引起的计算复杂性促进了并行和分布式数据密集型挖掘算法。

10. 概述在诸如流/传感器数据分析、时空数据分析或生物信息学某个特定引用领域中的数据挖掘的主要挑战？
    在生物信息学中，由于对某些生物对象、染色体序列、生物学网络和染色体的数据结构可能同时存在，对数据的清理和集成、一种数据的多个数据源之间的复杂相互作用给数据挖掘带来了巨大挑战。

第二章 认识数据

再给三个用于数据散布的常用特征度量（即未在本章讨论的），并讨论如何在大型数据库中有效的计算它们。
异众比率（variation ratio）：主要用于衡量众数对一组数据的代表程度。异众比率越大，说明非众数组的频数占频数的比重越大，众数的代表性就越差；反之说明众数的代表性越好。异众比率主要适合测度分类数据的离散程度。

其中∑▒f_i 表示变量值的总频数，∑▒f_m 表示众数组的频数。
标准分数：变量值与其平均数的差除以标准差后的值。给出了一组数据中各数值的相对位置。实际上，z分数只是将原始数据进行了线性变换，并没有改变一个数据在该组数据中的位置，也没有改变该组数据的分布形状。

离散系数：一组数据的标准差与其相应的平均数之比称为离散系数，也称变异系数。为了消除变量水平高低（即两个相同类型的属性其值分布差别特别大，比如一个为几百万，而另一个为几万或几十万）和计量单位不同对离散程度测量值的影响，需要计算离散系数。离散系数越小，说明数据离散程度越小；反之则说明数据离散程度越大。其计算公式为：


假设所分析的数据包括属性age，它在数据元组中的值（以递增序）为13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.
该数据的均值是多少？中位数是什么？

该组数据均值是29.963，中位数是25。
该数据的众数是什么？讨论数据的模态（即二模、三模等）。
该数据的众数是25和35，是一个双峰的分布，即二模。
该数据的中列数是多少？
该数据的中列数是（70+13）/2=41.5。
你能粗略地找出该数据的第一个四分位数（Q1）和第三个四分位数（Q3）吗？
第一个四分位数为[27/4]=7处，Q1=20,；第三个四分位数为21处，Q3=35。
给出该数据的五数概括。
五数概括即中位数25，四分位数Q120，第三个四分位数Q335，最大观测值70和最小观测值13。
绘制该数据的盒图。

分位数-分位数图与分位数图有何不同？
分位数图是一种观察单变量数据分布的简单有效分发。首先它显示给定属性的所有数据的分布情况；其次它给出了分位数信息。
分位数-分位数图则是反映了同一个属性的不同样本的数据分布情况，使得用户可以很方便地比较这两个样本之间的区别或联系。

设给定的数据集已经分组到区间。这些区间和对应频率如下所示，计算该数据的近似中位数。

使用书中P47的计算公式，可以计算出
median=21+29*□((0.5-0.297)/0.470)=33.526
即近似中位数为33.526。

假设医院对18个随机挑选的成年人检查年龄和身体肥胖，得到如下结果：

计算age和%fat的均值、中位数和标准差。

age的均值为46.44，中位数为（50+52）/2=51，标准差为12.85；
%fat的均值为28.78，中位数为（31.2+34.6）/2=32.9，标准差为8.99。
绘制age和%fat的盒图。

由于%fat中存在7.8和9.5两个数据被excel自动判定为离群点，故实际上%fat的图片中下须应该更长。
绘制基于这两个变量的散点图和q-q图。


简要概述如何计算被如下属性描述的对象的相异性：
标称属性。
两个对象i和j之间的相异性根据不匹配率来计算：

其中p为刻画对象的属性总数，m是匹配的数目。
非对称的二元属性。
使用二元属性的列联表进行计算，计算公式如下：

其中，r为在对象i中取1、在对象j中取0的属性数；s为在对象i中取0、对象j中取1的属性数；q为在对象i和j中都去1的属性数，即两个值都取1的正匹配更有意义的情况下。
数值属性。
使用闵可夫斯基 距离进行计算，即欧几里得距离和曼哈顿距离的推广。

其中，h是实数，h≥1。
词频向量。
使用余弦相似度进行计算，其计算公式如下：

给定两个元祖（22,1,42,10）和（20,0,36,8）表示的对象。
计算这两个对象之间的欧几里得距离。

d=√(2&〖(22-20)〗^{2+〖(1-0)〗}2+〖(42-36)〗^{2+〖(10-8)〗}2 )≈6.7
计算这两个对象之间的曼哈顿距离。
d=|22-20|+|1-0|+|42-36|+|10-8|=11
使用q=3，计算这两个对象之间的闵可夫斯基距离。
d=∛(〖(22-20)〗^{3+〖(1-0)〗}3+〖(42-36)〗^{3+〖(10-8)〗}3 )≈6.15
计算这两个对象之间的上确界距离。

中位数是数据分析中最重要的整体度量之一。提出几种中位数近似计算方法。在不同的参数设置下，分析它们各自的复杂度，并确定它们的实际相似程度。此外，提出一种启发式策略，平衡准确性与复杂性，然后把它用于你给出的所有方法。

通过查阅资料，很难查找到有效信息，对比原英文书的问题进行比较，发现应该是再找出几种方法描述数据分散程度。原书答案中使用的是平均偏差、偏态（skewness）和离散系数（the coefficient of variation）进行描述。

在数据分析中，最重要的是选择相似性度量。然而，不存在广泛接受的主观相似性度量，结果可能因所用的相似性度量而已。尽管如此，在进行某种变换后，看来似乎不同的相似性度量可能等价。假设我们有如下二维数据集：

把该数据看做二维数据点。给定一个新数据点x=（1.4， 1.6）作为查询点，使用欧几里得距离、曼哈顿距离、上确界距离和余弦相似性，基于与查询点的相似性对数据库的点排位。
规格化该数据集，使得每个数据点的范数等于1。在变换后的数据上使用欧几里得距离对诸数据点排位。

计算后得到的数据如图所示：

因此，按照欧几里得距离排位为1,4,3,5,2；按照曼哈顿距离为1,4,3,5,2,；根据上确界距离为1,4,3,5,2,；根据余弦相似性为1,3,4,5,2。
由于该题中的数据类型为向量，对向量进行范数等于1的规范化即计算一点x(a,b)的范式，即a^’=a/√(a2+b^2 )；因此，给出的规范化数据集之后的值为：

根据其值计算出来的欧几里得距离为：

第三章 数据预处理

数据质量可以从多方面进行评估，包括准确性、完整性和一致性问题。对于以上每个问题，讨论数据质量的评估如何依赖于数据的应用目的，给出例子。提出数据质量的两个其他尺度。

准确性：由于技术的限制或人为的失误，有些需要准确投入营销比如生日折扣等的商品可能会失去作用。
完整性：由于故意隐瞒和设置、转移数据时没有加入，有些需要完整信息的例如快递行业会在业务经营中遇到障碍。
一致性问题：由于某些不可抗因素导致的数据不一致，例如多个数据源命名不一致时会影响数据集成等。
其他两个尺度是可信性和时效性。

在现实世界是数据中，某些属性上缺失值得到元组是是比较常见的。讨论处理这一问题的方法。
忽略元组。
人工填写缺失值。
使用一个全局常量填充缺失值。
使用属性的中心度量（如均值或中位数）填充缺失值。
使用与给定元组属同一类的所有样本的属性均值或中位数。
使用最可能的值填充缺失值。

在习题2中，属性age包括如下值（以递增序）：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,35,35,36,40,45,46,52,70。
以深度为3的箱，用箱均值光滑以上数据。说明你的步骤，讨论这种技术对给定数据的效果。
将以上数据分为三个一组的箱为：

（13,15,16） （16,19,20） （20,21,22） （22,25,25） （25,25,30）
（33,33,35） （35,35,35,） （36,40,45） （46,52,70）
计算各个箱的平均值，给出以下结果。
（142/3，142/3, 142/3） （181/3，181/3，181/3） （21，21，21）
（24, 24, 24,） （262/3，262/3，262/3） （332/3, 332/3，332/3）
（35, 35, 35） （401/3, 401/3, 401/3） （56, 56, 56）
该方法在一定程度上光滑了噪声数据，但是在一定程度上还是会受到离群点的影响。
如何确定该数据中的离群点？
可以使用聚类检测，有相似特征的数据会聚集成一个簇，离簇较远的点可能是离群点。另外，还可以采用人机结合的方式，计算机将会给出疑似离群点，由人工进行复查确认是否需为离群点。
还有什么其他方法来光滑数据？
在分箱方法中，还可以通过箱中位数光滑、箱边界光滑等。或者使用回归技术和离群点分析技术。

讨论数据集成需要考虑的问题。
模式集成：涉及到实体识别问题，例如如何确认一个数据库中的customer_id和另一个数据库中的cust_number指的是同一个属性。
冗余数据：使用相关分析来解决数据库中的数据冗余问题。
数据值冲突的检测与处理：对于同一实体可能因为表示、尺度或编码不同导致属性值不同。

如下规范化方法的值域是什么？
最小-最大规范化。

[〖new_min〗_A,〖new_max〗_A]
Z分数规范化。
[(v_min-A ̅)/σ_A ,(v_max-A ̅)/σ_A ]
Z分数规范化，使用均值绝对偏差而不是标准差。
[(v_min-A ̅)/s_A ,(v_max-A ̅)/s_A ]
小数定标规范化。
(-1,1)
使用如下方法规范化如下数据组：
200, 300, 400, 600, 1000
令min=0，max=1，最小-最大规范化。

Z分数规范化。
A ̅=500，σ_A=282.8

Z分数规范化，使用均值绝对偏差而不是标准差。
A ̅=500，s_A=240

小数定标规范化。
令j=3，使用1000作为定标：

修正后，应该取j=4，使用10000作为定标，则各数字应该为0.02,0.03,0.04,0.06，,01。

使用习题3中给出的age数据，回答以下问题：
使用最大-最小值规范将age从35变换到[0.0，1.0]区间。

0.386
使用z分数规范化变换age35，其中age的标准差为12.70。
0.386
使用小数定标规范化变换age值35。
0.35
指出对于给定的数据，你愿意使用哪种方法。陈述你的理由。
在最大值和最小值确定的情况下，我更愿意使用最大-最小值规范，这样计算比较简单快速，且原来的数据不会改变太多。在数据的最大值和最小值不太明确的情况下使用均值绝对偏差的z分数规范，其鲁棒性更强。
使用习题4中给出的age和%fat数据，回答如下问题：
基于z分数规范化，规范化这两个属性。

计算相关系数（Pearson积矩系数）。这两个变量是正相关还是负相关？计算它们的协方差。
根据相关系数公式有：
r_(A,B)=(∑_(i=1)^18▒〖(a_i b_i )-1846.4428.78〗)/(1812.858.99)≈0.82
因此，这两个变量之间是正相关，协方差为0.82。

假设12个销售价格记录已经排序，如下所示：

5,10,11,13,15,35,50,55,72,92,204,215
使用如下各方法将它们划分为三个箱：
等频（等深）划分。
即划分为三个元素一样多的箱，即：

等宽划分。
分成三个区间即（215-5）/3=70，故区间距离为70，即：

聚类。
以数字间的最大间隔作为标准，即：

使用流程图概述如下属性子集选择过程：
逐步向前选择。

逐步向后删除。

结合逐步向前选择和逐步向后删除。
首先将属性集从中间开始分成两半，对于前半部分的采用逐步向前选择方法，符后半部分采用逐步向后删除方法。

使用习题3中给出的age数据：
画一个宽度为10的等宽的直方图。

简要描述如下每种抽样技术的例子：SRSWOR、SRSWR、簇抽样、分层抽样。使用大小为5的样本以及层“young”、“middle_aged”和“senior”。
SRSWOR：即无放回简单随机抽取，从D中抽取s个样本，每次收取一个样本且不放回到D中。
ARAWR：有放回简单随机抽取，与SRSWOR的区别在于抽取出的样本会再放回到D中。
簇抽样：如果D中的元组被分组放到M个互不相交的簇中， 则可以得到s（s<M）个簇的简单随机抽样。
分层抽样：如果D被划分成互不相交的部分，则对每一层进行简单随机抽样就可以得到D的分层抽样。在本题中即对所说的三个层分别进行抽样，分配可以根据各层样本比例定为2、2、1个。

ChiMerge[Ker92]是监督的、自底向上的（即基于合并的）数据化离散方法。它依赖于X^2分析：具有最小X^2值相邻区间合并在一起，直到满足确定的停止标准。
简略描述ChiMerge如何工作。

ChiMerge的基本算法为：
begin
将数据按序排好
将每个值放入到不同的区间内
while 停止条件没有满足
begin
计算每一对相邻区间的X^2
将X^2更小的区间合并
end
end
取鸢尾花数据集作为待离散化的数据集合，使用ChiMerge方法，对四个数值属性分别进行离散化。（令停止条件为max-interval=6）。你需要写一个小程序，以避免麻烦的数据计算。提交你的简要分析和检验结果：分裂点、最终的区间以及源程序文档。

对于如下问题，使用伪代码或者你喜欢用的程序设计语言，给出一个算法：
对于标称数据，基于给定模式中属性的不同值的个数，自动产生概念分层。

即建立三个数组，一个用于存储数据本身，一个用来存储给定模型中属性不同值的个数，一个二维数组用于存储最终概念分层的结果。对于每个概念分层，开启计数，如果计数给定的不同值之后，开始将数据存放在最终结果二维数组的下一维中。
对于数值数据，基于等宽划分规则，自动产生概念分层。

同样采取了两个数组作为存储结构，其中在concept_hierarchy中记录了用户自定义的每个概念分层的宽度及其最小值和最大值（可通过这个直接判断数据在哪个概念分层中），并计算出每个概念分层的总数和平均数。
对于数值数据，基于等频划分规则，自动产生概念分层。

与等宽划分基本一致，不同的是concept_hierarchy中记录了bin的深度，即每个bin最多容纳多少个元素，并在计数中采用j作为计数器，如果j超过了用户自定义的深度，则k++即下一个元素开始放入新的箱中，并将j复位为1。与此同时计算出每个概念分层的总数和平均数。

数据库系统中鲁棒的数据加载提出一个挑战，因为输入数据常常是脏的。在许多情况下，数据记录可能缺少多个值，某些记录可能被污染（即某些数据值不在期望的值域内或具有不同的类型）。设计一个自动数据清理和加载算法。使得有错误的数据被标记，被污染的数据在数据加载时不会错误地插入数据库中。

begin
for 数据集中的每个值r
begin
check r 是否为缺失值
if 是，根据掌握的信息填写缺失值（例如平均值、默认值等）
check r 是否为超出范围的值
if 是，根据掌握的信息修正该值（例如最大值或最小值）
check r 是否为错误的数据类型
if 是，根据掌握的信息修改其数据类型
if r是一个错误的数据，将其做上标记并写入到日志中
otherwise 将数据r载入到数据库中
end
end

第六章 挖掘频繁模式、关联和相关性：基本概念和方法

假设有数据集D上所有闭频繁项集的集合C，以及每个闭频繁项集的支持度计数。给出一个算法，确定给定的项集X是否频繁，如果频繁的话，给出X的支持度。

（此处参考了：
数据挖掘概念与技术（原书第三版）范明 孟小峰译—–第六章课后习题答案_数据库_Jack小站-CSDN博客 https://blog.csdn.net/u013272948/article/details/72885602 ）

项集X称为数据集D上的生成元，如果不存在真子集Y⊂X使得support(X)=support(Y)。生成元X是频繁的生成元，如果support(X)满足最小支持度阈值。设G是数据集D上所有频繁的生成元的集合。
仅使用G和它们的支持度计数，你能确定项集A是否频繁，并且如果A频繁，确定A的支持度吗？如果能，给出你的算法。否则，还需要什么信息？假定有所需要的信息，你能给出一个算法吗？

能够确定，根据题目描述X的集合即为频繁闭项集集合，则其算法可以参考习题1中解决。
闭项集和生成元有什么关系？
生成元集合是闭项集，其满足不存在真子集Y，使得Y与X具有相同的支持度计数；即生成元考察的是真子集，闭项集考察的是真超集。（Q：研究真子集和研究真超集会有什么不同？题1中我所认为的频繁生成元集可以看做频繁闭项集是成立的吗？）

Apriori算法使用子集支持度性质的先验知识。
证明频繁项集的所有非空子集一定也是频繁的。

设s是一个频繁项集，min_sup是最小支持度阈值，D是数据库事务的集合，|D|是D中的事务数量，则有support_counts(s)≥min_sup|D|；再设x’是s的子集，则易得任何包含项集s的事务中必然包含项集s’，故supports_counts(s’)≥support_counts(s)≥min_sup|D|，题目得证。
证明项集s的任意非空子集s’的支持度至少与s的支持度一样大。
由定义可知，support(s)=support_counts(s)/|D|。
由本题中题（1）中可知supports_counts(s’)≥support_counts(s);
故support(s’)=support_counts(s’)/|D|>=support(s),本题得证。
给定频繁项集l和l的子集s，证明规则s^‘⇒l(s’)的置信度不可能大于s⇒l(s)的置信度。其中s’是s的子集。
由置信度定义可知，s⇒l(s)的置信度为support(l)/support(s)；
由题2可知，support(s’)≥support(s)；
故s^‘⇒l(s’)的置信度support(l)/support(s’)≤support(l)/support(s)，得证。
Apriori算法的一种变形将事务数据库D中的事务划分成n个不重叠的分区。证明在D中频繁的项集至少在D中的一个分区中是频繁的。
使用反证法进行证明，假设频繁项集F在事务数据库D中的任何一个分区中都是非频繁的。令C表示D中的所有事务量；令A表示D中包含频繁模式F的事务量，令min_sup表示最小支持度阈值，令d1,d2,…,dn表示D的n个不重叠的分区，ci表示分区di中的事务总数，ai表示分区di中包含F的事务数。所以，C=c1+c2+…+cn,A=a1+a2+…+an。因为F是一个频繁项集，所以A>=C*min_sup，即（a1+a2+…+an）>=（c1+c2+…+cn）*min_sup。又因为F在每个分区中都是不频繁的，所以对于任意i, ai=（c1+c2+…+cn）*min_sup矛盾。所以得到：D中频繁的项集至少在D的一个分区中是频繁的。

设c是Apriori算法产生的C_k中的一个候选项集。在剪枝步，需要检查多少个长度为（k-1）个子集？根据你的答案，你能给出一个图6.4的has_infrequent_subset过程的改进版本吗？

需要检查的个数为C_k^(k-1)，暂时没有想到一个改进版本，猜测应该是做一个更加有效的剪枝或者检查手段。

6.2.2节介绍了由频繁项集产生关联规则的方法。提出一个更有效的方法。解释它为什么更有效。（考虑将习题3中的2和3的性质结合到你的设计中。）

.
这个算法比起6.2.2节的算法更加高效因为它只生成并测试必要的子集。如果一个长度为k的子集不满足最小置信度，那么生成其子集并进行测试是没有意义的（根据子集支持度的先验知识中的2、3点可知）。然而，如果x满足最低可信度，我们就生成并测试它的k-1项子集测试，由此我们从一个k项集逐渐测试到1项集。另一方面，生成频繁项集的所有非空子集然后测试他们是否存在潜在的关联规则是很不高效的，因为会产生很多不必要的自己。然而使用这个方法后，我们只生成x的k-1子集确定没有规则满足最小置信度后会避免生成和测试更多的子集，从而减少大量不必要的计算（剪枝）。

数据库由5个事务。设mini_sup=60%，min_conf=80%。

分别使用Apriori算法和FP-growth算法找出频繁项集。比较两种挖掘过程的有效性。
使用Apriori算法

首先找出频繁的1-项集，然后进行组合再找出频繁的2-项集，以此类推，有如下图（其中L表示频繁项集）：

使用FP-growth算法


首先找出频繁的1-项集，然后构建一个FP树，再对每个中间节点依次进行考察，建立条件FP树，最后得到单个路径的产生频繁模式的所有组合。

有效性比较：Apriori算法需要对数据库做多次扫描而FP-growth算法只需要一次扫描。Apriori的候选集产生代价较高（需要做多次自身连接），而FP-growth不需要生成任何候选集。
列举所有与下面的原规则匹配的强关联规则（给出支持度s和置信度c），其中X是代表顾客的变量，item是表示项的变量（如“A”，“B”等）；
∀x∈transaction,buys(X,〖item〗_1 )∧buys(X,〖item〗_2 )⇒buys(X,item_3 ) [s,c]

（实现项目）实现Apriori算法、FP-growth算法和ECLAT（使用垂直数据格式挖掘），比较其在不同数据集是哪个的性能，并分析在什么情况下，哪种算法更优。

数据库有4个事务。设min_sup=60%，min_conf=80%。

在item_category粒度（例如，〖item〗_i可以是“Milk”），对于下面的规则模板
∀x∈transaction,buys(X,〖item〗_1 )∧buys(X,〖item〗_2 )⇒buys(X,item_3 ) [s,c]
列出最大k的频繁k项集和包含最大k的频繁k项集的所有强关联规则（包括它们的支持度s和置信度c）
k=3且最大k的频繁k项集为{Bread, Milk, Cheese}，包含最大k的频繁k项集的所有强关联规则为：

在brand-item_category粒度（例如〖item〗_i可以是“Milk”），对于下面的规则模板

∀x∈transaction,buys(X,〖item〗_1 )∧buys(X,〖item〗_2 )⇒buys(X,item_3 ) [s,c]
列出最大k的频繁k项集（但不输出任何规则）。
k=3，且频繁3项集为{Wonder-Bread, Dairyland-Milk, Tasty-Pie},{Wonder-Bread, Sunset-Milk, Dairyland-Cheese}。

假定一个大型商店有一个事务数据库，分布在4个站点，每个成员数据库中的事务具有相同的格式T_j：{i_1,i_2,…,i_m}；其中T_j是事务标识符，而i_k (1≤k≤m)是事务中购买的商品标识符。提出一种有效的算法，挖掘全局关联规则。可以给出你算法的要点。你的算法不必将所有的数据都转移到一个站点，并且不造成过度的网络通信开销。

以下描述了一个简单算法：
在每个成员数据库中找到本地的频繁项集，用CF作为四个成员数据库中各自本地的频繁项集的集合。
在每个成员数据库中，计算出CF中本地频繁项集的支持度。
接下来在CF中计算全部的频繁项集的支持度，可以将四个成员数据库中项集支持度相加得到总的支持度，从而计算出支持度超过最小支持度阈值的频繁项集。
从频繁项集中推导出强关联规则。

假定大型事务数据库DB的频繁项集已经存储。讨论：如果新的事务集∆DB（增量地）加进，在相同的最小支持度阈值下，如何有效地挖掘（全局）关联规则？

我们可以将∆DB和DB作为两部分进行考虑：
对于DB中的频繁项集，在∆DB扫描一次并增加计数以判断它们在更新后的数据库是否仍然频繁；
对于在∆DB中但不在DB中的频繁项集，扫描一次DB并增加计数以判断他们是否在更新后的数据库仍然频繁。

大部分频繁模式挖掘算法只考虑事务中的不同项。然而，一种商品在一个购物篮中多次出现，例如4块蛋糕3桶牛奶的情况，在销售数据分析中可能是重要的。考虑项的多次出现，如何有效地挖掘频繁项集？对著名的算法如Apriori算法、FP-growth算法，提出修改方案，以适应这种情况。

考虑将一个项以及其出现的次数作为第一次处理中联合的一项，例如将{milk,3}作为一个项集。在第一次扫描单个频繁项集i时，如果i的最高次数超过了最小频繁阈值，例如(milk, 3)可能是一个频繁项集。对于(i, max_count)尝试找出k项集从1到max_count的计数（可以使用Apriori算法或者FP-growth算法）。例如在FP-growth算法中，一个(I, count)项可以使用一个节点表示，然而如果想要更高的效率，这样的一个节点可以再结合计数器存储更多的信息。

（实现项目）

给出一个小例子表明强关联规则中的项实际上可能是负相关的。

假设最小支持度为40%，最小置信度为60%。A⇒B时一个强关联规则，因为其满足最小支持度65/150=43.3%且满足最小置信度65/100=61.9%。然而，A和B之间的关联性为〖corr〗_(A,B)=0.433/(0.700×0.667)=0.928<1，故A和B之间的出现是负相关的。

下面的相依表汇总了超市的事务数据。其中，hot dogs表示包含热狗的事务，(hot dogs) ̅表示不包含热狗的事务。hamburgers表示包含汉堡包的事务，(hamburgers) ̅表示不包含汉堡包的事务。（题图中第二行第一列改成(hamburgers) ̅）

假设挖掘出了关联规则hot dogs⇒humburgers，给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强规则吗？
由于支持度为2000/5000=40%，置信度为2000/3000=66.7%。因此，该关联规则是强关联规则。
根据给定的数据，买hot dogs独立于买humburgers吗？如果不是，两者之间存在何种相关联系。
不是，〖corr〗(hotdog,hamburgers)=0.4/(0.5*0.6)=1.33>1，因此两者之间为正相关。
在给定的数据上，将全置信度、最大置信度、Kulczynski和余弦的使用与提升度和相关度进行比较。
全置信度：〖all_conf〗(hotdog,hamburgers)=0.4/0.6=2/3
最大置信度：max⁡_conf_(hotdog,hamburgers)=0.4/0.5=0.8
Kulczynski：〖Kul〗(hotdog,hamburgers)=1/2 （0.8+2/3）=11/15
余弦度量：cos(hotdog,hamburgers)=√(0.8*2/3)=(2√30)/15
提升度：lift_(hotdog,hamburgers)=(2/3)/0.5=4/3
相关度：由于没有得到期望值，因此没有办法计算出该项，其计算公式为：
x^{2=∑〖(观测值-期望值)〗}2/期望值
（实现项目）

第八章 分类：基本概念

简述决策树分类的主要步骤。

树从单个根节点开始，该节点包含所有的训练元组。
如果元组中都为同一类，则该节点变成一个叶子节点，并以该类标记它。
否则，调用算法确定分裂准则。分裂准则使用启发或统计标准（如信息增益或基尼系数）来确定将元组划分成各自的类的最好方法。即分裂准则指定分裂属性，并给出分裂点或分裂子集。
节点N使用分裂准则进行标记并进行测试。对分裂准则的每个输出，由节点N生长一个分支，该节点的元组因此分类，有以下三种分类方法：（1）属性值是离散的，则分支对应的是A的取值；（2）属性值是连续的，取两个分支，对应于条件A≤split_point和A＞split_point；（3）属性值是离散的且必须产生二叉分枝，测试形如“A∈S_A?”，其中S_A是A的分裂子集，是A中已知值的子集。
对于每个节点上的元组使用同样的算法进行递归形成决策树。
递归划分步骤终止条件是：（1）该节点所有元组都属于同一个类；（2）没有剩余的属性可以用来进一步划分元组，此时采用多数表决，将节点N转换成叶节点并使用元组中的大多数标记它；（3）给定的分支没有元组，此时用元组中的多数类创建一个叶节点。

在决策树归纳中，为什么树剪枝是有用的？使用独立的元组集评估剪枝有什么缺点？

决策树可能出现过拟合的情况，即分支的产生会受到训练数据中的噪声和离群点等异常的影响，剪枝技术可以通过使用统计度量删除最不可靠的分支来里面这种过拟合。这样能够产生可靠、简洁的决策树以更快、更精确对数据进行分类。
使用独立的元组集进行剪枝的缺点是剪枝后的决策树可能不如原决策树具有代表性。如果独立的数据元组集是倾斜的，则形成的决策树在分类上将不是准确的。此外，使用独立元组集剪枝意味着更少的元组用于产生和测试该树，对于机器学习而言这是一个巨大缺点，对于大数据集的数据挖掘下也是如此。

给定决策树，选项有：（a）将决策树转换成规则，然后对结果规则剪枝；（b）对决策树剪枝，然后将剪枝后的树转换成规则。相比于（b），（a）的优点是什么？

如果剪去一个子树，使用方法b可以完整删去一个子树；然而使用方法a如果剪去一个规则，我们可以删除它的所有前提条件，这更加严格。

计算决策树算法在最坏情况下的计算复杂度是重要的。给定数据集D，属性数n和训练元组数|D|，根据n和D来分析计算复杂度最多是n×|D|×log⁡〖|D|〗。

最差的情况就是我们需要使用尽可能多的元组来分出每个元组，对于一棵树来说最大深度是log⁡〖|D|〗；在每一层我们需要使用所有的属性计算attribute_selection算法（每个属性计算一次），每一层所有的元组数是|D|，因此树中的每一层计算复杂度是O(n×|D|)。因此，整个流程需要的复杂度是O(n×|D|×log⁡|D|)。

给定一个具有50个属性（每个属性包含100个不同值）的5GB的数据集，而你的台式机有512MB内存。简述对这种大型数据集构造决策树的一种有效算法。通过粗略地计算主存的使用说明你的答案是正确的。

使用雨林算法，此时内存中需要存储的是以avc_set为根的树，计算avc_set的根节点，扫描一次数据库，构建avc_list的50个属性，每个属性具有100个不同的值，则需要的总大小是10050|C|（|C|表示每个值占据的空间大小），则对于一个合理的|C|能够使适应512M的大小。使用这种每个节点存储一部分avc-集的方法，我们或许可以适应内存的水平。

为什么朴素贝叶斯分类称为“朴素”的？简述朴素贝叶斯分类的主要思想。

朴素贝叶斯被称为“朴素”是因为它假设条件独立分布，这个假设用于减少计算代价，因此称为“朴素”，其主要原理是通过后概率的贝叶斯定理使用P（X|C_i）P（C_i）得到最大值来对数据进行分类。
其主要步骤通过原书第三版P227描述。

下表由雇员数据库的训练数据组成。数据已泛化。例如，age“31…35”表示年龄在31~35之间。对于给定的行，count表示department、status、age和salary在该行上具有给定值的元组数。

设status是类标号属性。
1） 如何修改基本决策树算法，以便考虑每个广义数据元组（即每个行）的count？
① 将每个元组的count作为计算属性选择方法中的一部分（例如信息增益）。
② 在决定元组多数表决的时候考虑元组的count。
2） 使用修改过的算法，构造给定数据的决策树。

3） 给定一个数据元组，它的属性department、age和salary的值分别为“system”、“26…30”、“46…50K”。该元组status的朴素贝叶斯分类是什么？
P(X|senior)=0；P(X|junior)=0.018，因此应该属于junior。

8. RainForest是一种可伸缩的决策树归纳算法。开发一种可伸缩的朴素贝叶斯分类算法。对于大多数数据库，它只需要扫描整个数据集一次。讨论这种算法是否可以进一步求精，结合提升进一步调高分类的准确率。
   在一次对数据库的扫描中，对于每个属性的值我们可以采用下面的表进行计数：
   
   其中〖count〗_(i,j)表示〖class〗_j中对于属性A中〖value〗_i一值出现的次数，使用这个表格我们可以计算出任何P（〖class〗_i |〖tuple〗_j）的值。
   使用这个表格记录数据库会比原数据库占据空间更小，因为其大小取决于属性的数量、各属性值的个数以及类的数量。
   如果我们想要进一步求精，可以通过使用一部分训练样本先训练一些朴素贝叶斯分类器。对于每个被分类器误分类的元组我们给予更高的权重，在测试时间我们将收集所有的分类器决定并且使用它们分类的准确性作为权重的标准。在这种情况下，我们需要将每个分类器保持各自独立的计数表。

   设计一种方法，对无限的数据流进行有效的朴素贝叶斯分类（即只能扫描数据流一次）。如果想发现这种分类模式的演变（例如，将当前的分类模式与较早的模式进行比较，如与一周以前的模式相比），你有何修改建议？
   这种设计方法和上题类似，我们使用一个属性值计数表并在每个数据流输入的时候进行更新。
   为了发现分类模式的演变，我们可以保持一个基于所有历史数据的分类器，一个基于过去一星期数据的分类器，一个基于过去一天的分类器。对于以周计算的分类器，我们保持过去七天每项的独立技术；在每天结束后，我们抛弃掉最老天数的数据并且使用刚过去的一天的数据替换。对于以天计算的分类器，类似的使用过去的一个小时的数据替代最早的一个小时的数据。

   证明准确率是灵敏性和特效性度量的函数，即证明accuracy=sensitivity P/(（P+N）)+specificity N/(（P+N）)成立。

调和均值是多种平均值中的一种。第2章讨论了如何计算算术均值，这是大部分人计算平均值时所想到的。正实数x_1，x_2，…，x_n的调和均值H定义为：
?=????+???+……+???=??=?????
F度量是精度和召回率的调和均值。使用这一事实为F推导?=?×?????????×???????????????+??????。此外，把??写成真正例、假负例和假正例的函数。
根据定义，?=21?????????+1??????=2×?????????×??????1?????????×?????????×??????+1??????×????????×??????=21?????????+1??????
??=(1+?2)×?????????×???????2×?????????+??????=(1+?2)(2×??+??+??)1+?2??+?2×??+??

12. 如图中的数据元组已经按分类器返回概率值的递减序排序。对于每个元组，计算真正例（TP）、假正例（FP）、真负例（TN）和假负例（FN）的个数。计算真正例率（TPR）和假正例率（FPR）。为该数据绘制ROC曲线。

根据计算，可以得到如上图所示对应的TPR和FPR，绘制出来的表格如下：


当一个数据对象可以同时属于多个类时，很难评估分类的准确率。评述在这种情况下，你将使用何种标准比较在相同数据上建立的不同分类器。
一个数据对象可以同时属于多个类。然而，一个数据对象可能比起其他类会更多属于一个特定类。因此，应该建立一个分类器去判断数据对象通常属于哪个类。受此启发，一个类如果符合最可能或第二可能类即判断分类正确。另一个标准是使用同一个数据集判断不同分类器的分类速度、鲁棒性、可扩展性以及解释性。
通常我们会选择一个计算代价更小（训练时间、分类时间）、能在给出噪声甚至不完整数据下做出准确预测、在大型数据上有效工作并提供能够更易理解的准确结果的分类器。

假设在两个预测模型M1和M2之间进行选择。已经在每个模型上做了10轮10-折交叉验证，其中在第i轮，M1和M2都使用相同的数据划分。M1得到的错误率为30.5、32.2、20.7、20.6、31.0、41.0、27.7、28.0、21.5、28.0。M2得到的错误率为22.4、14.5、22.4、19.6、20.7、20.4、22.1、19.4、18.2、35.0。评述在1%显著水平上，一个模型是否显著地比另一个好。

我们可以使用假设检验去看平均错误率是否有明显不同。假设我们使用同样的测试数据做配对观察去比较平均误差：
H_0: (x_1 ) ̅-(x_2 ) ̅=0
H_1: (x_1 ) ̅-(x_2 ) ̅≠0
其中，(x_1 ) ̅是M1的平均误差，(x_2 ) ̅是M2的平均误差。
我们使用下面公式进行计算：
t=d ̅/(s_d/√n)
其中，d ̅是错误率差值的平均误差，s_d是标准误差，n是观察的样本数。在该题中可得d ̅=6.45，s_d=8.25，n=10，故得到t=2.47.使用t-分布表，我们查到probability为0.005且自由度为9的t_(α/2)为3.25，由于-3.25<2.47<3.25，因此我们可以接受假设，即在1%的显著水平下，这两个模型没有不同。

第九章 分类：高级方法

1. 比较急切分类（例如决策树、贝叶斯、神经网络）相比于惰性分类（例如k-最近邻、基于案例的推理）的优点和缺点
   急切分类（Eager Classification）比惰性分类速度更快，因为其在接收待分类的元组之前已经构建好了一个泛化模型。属性的权重可以进行分配能提升分类的准确性。但其缺点是急切分类需要的是一个能够覆盖所有实例空间的唯一假设，因此在增量分类中需要更多的时间对模型进行训练。
   惰性分类（Lazy Classification）使用更多的假设空间，从而提高分类的准确性，其训练时间比急切分类更短。但其缺点是所有的训练元组需要进行存储，因此付出更大的存储代价和有效的检索技术。另一个缺点在于其分类速度更慢，因为在新分组需要分类的时候才会进行模型的训练。此外，其属性的权重是相等的，因此可能会降低其模型的准确性（容易受到噪声等数据的影响）。
2. 什么是关联分类？为什么基于频繁模式的分类能够获得比经典的决策树的方法具有更高的准确率？
   关联分类指的是产生关联规则并且将其运用于分类分析中的方法。我们首先基于在频繁模式之间搜索强关联规则和类标号。使用这些强关联规则我们可以分类新的实例。基于频繁模式的分类能够具有更高的准确性的原因在于其克服了决策树的限制，即一次只考虑一个属性，基于频繁模式的分类方法通过置信度将多个属性结合。
3. 支持向量机是一种具有高准确率的分类方法。然而，在使用大型数据元组集进行训练时，SVM的处理速度很慢。讨论如何克服这一困难，并为大型数据集有效的SVM开发一种可伸缩的SVM算法。
   可以使用“微聚类技术”（Classifying large data sets using SVM with hierarchical clusters by Yu，Yang，and Han， in Proc 2003 ACM SIGKDD Int. Conf. Knowledge Discovery and Data Ming（KDD‘03’），page 306-315，Aug. 2003[YYH03]）。
   一种可伸缩的SVM算法如下：
   1） 使用微聚类方法建立一颗CT树。
   2） 在微聚类的圆心训练一个SVM。
   3） Decluster entries near the boundary.
   4） 使用其他项重复对SVM的训练。
   5） 重复以上所有步骤直至收敛。

第十章 聚类分析：基本概念和方法

1. 简略介绍如下聚类方法：划分方法、层次方法、基于密度的方法和基于网格的方法。每种给出一个例子。
   划分方法：给定n个数据对象或数据元组的数据集，以及要生成的簇数k（k≤n）；划分方法把数据对象集初步划分为k个部分，然后采用一种迭代的重定位技术将对象从一个组移动到另一个组来改进划分。好的划分的标准是同一个簇中的对象尽量相互接近或者相关，不同簇中的对象应该尽量远离。K-均值算法是最常用的划分方法之一。
   层次方法：层次方法创建给定数据对象集的层次分解，该算法可以通过凝聚或者分裂实现。凝聚（自底向上）方法从每个对象组成一个单独的组开始，然后逐次合并相近的对象或组，直到所有的组合并成一个组。分裂（自顶向下）方法从包含所有对象的簇开始，在每次迭代中将一个簇划分为更小的簇，直到每个对象组成他们各自的簇。AGNES和DIANA算法是层次方法的例子，BIRCH使用了基于距离的迭代重定位，是层次凝聚算法。
   基于密度的方法：该方法基于密度进行计算，主要思想是只要邻域中的密度朝富哦了给定的阈值就继续增长给定的簇。即对于每个给定的簇，其给定半径的邻域内必须有至少包含最少数目的点。该方法可以用来过滤噪声或离群点，发现任意形状的簇。
   基于网格的方法：该方法将对象空间化为有限个单位，形成一个网格结构。所有的对簇操作都在该网格空间中进行。该方法的优点在于处理速度很快，其处理时间通常独立于数据对象的个数，而仅依赖于量化空间中每一个维的单元数。STING是基于网格方法的一个例子。

   假设数据挖掘的任务是将如下的8个点（用（x，y）代表位置）聚类为3个簇。
   A_1(2,10) 〖,A〗_2 (2,5),A_3 (8,4),B_1 (5,8),B_2 (7,5),B_3 (6,4),C_1 (1,2),C_2 (9,4)
   距离是欧氏距离。假设初始我们选择A_1，B_1和C_1分别为每个簇的中心，用k-均值算法给出：
   在第一轮执行后的3个簇中心。
   在第一轮执行时，分别计算除中心点外的所有点和每个中心点的欧几里得距离，将其并入离自己最近的中心点的簇中。因此可得第一轮后，3个簇为：
   {A_1}，{B_1,A_3,B_2,B_3,C_2}，{C_1,A_2}，故他们的簇中心为（2, 10），（6, 6），（1.5, 3.5）。
   最后的3个簇。
   使用新的均值作为簇的中心点，再次按照以上流程进行计算；如此迭代后，直到分配稳定后，最后形成的三个簇为：{A_1,C_2 〖,B〗_1}，{A_3,B_2,B_3}，{C_1,A_2}。

   用一个例子表示k-均值不能找到全局最优解，即不能最优化簇内方差。
   对于k-均值算法，有趣的是通过小心地选择初始簇中心，我们或许不仅可以加快算法的收敛速度，并且能够保证结果聚类的质量。k-均值算法++是k-均值算法的变形，它按以下方法选择初始中心。首先，它从数据对象中随机地选择一个中心。迭代地，对于每个未被选为中心的每个对象p，选择一个作为新中心。该对象以正比于dist§²的概率随机选取，其中dist（p）是p到已选定的最近中心的距离。迭代过程继续，直到选出k个中心。
   解释为什么该方法不仅可以加快k-均值算法的收敛速度，并且能够保证最终聚类结果的质量。
   给出PAM的重新分配步骤的伪代码。
   k-均值和k-中心点算法都可以进行有效的聚类。
   概述k-均值和k-中心点相比较的优缺点。
   k-均值算法计算代价更小；k-中心点计算代价大，但是对于数据中的离群点和噪声鲁棒性更强，即更少受到离群点和噪声的影响。
   概述这两种方法与层次聚类方法（如AGNES）相比有何优缺点。
   k-均值和k-中心点都是划分方法的一种，这种方法的好处在于每次迭代重定位的时候可以撤销之前的聚群操作，但是层次聚类方法一旦一个步骤（分裂或合并）完成将不能被撤回，因此层次聚类方法可能会影响聚类的结果的质量。划分方法在球形聚类上表现良好，且其聚类的结果在小型到中中型的数据库上质量较好。划分方法的缺点在于需要指定簇的数量。
   层次聚类方法自动决定簇的数量。然而他们每一步做出合并或分裂步骤的时候需要进行大量计算来评估该步骤产生的簇的质量。然而，层次聚类方法能够和其他聚类方法集成一个扩展的聚类方法，提高层次聚类质量，如BIRCH、ROCK和Chameleon。

   证明：在DBSCAN中，紧密相连是等价关系。
   自反性：存在一个对象q∈D，对象p∈D是及其自身都是从q关于ε和MinPts密度可达的，即密度相连具有自反性。
   对称性：如果两个对象p1和p2是关于ε和MinPts密度可达的；则存在一个对象q∈D，使得对象p2和p1都是从q关于ε和MinPts密度可达的，即紧密相连具有对称性。
   传递性：在DBSCAN中，如果对象p1和p2是关于ε和MinPts密度可达的，对象p2和p3,是关于ε和MinPts密度可达的，则会存在核心对象使得对象p1和p3关于ε和MinPts密度可达，因此DBSCAN中密度相连具有传递性。
   综上所述，在DBSCAN中，紧密相连是等价关系。

   证明：在DBSCAN中，对于固定的MinPts值和两个相邻阈值ε_1<ε_2，关于ε_1和MinPts的簇C一定是关于ε_2和MinPts的簇C’的子集。
   给出OPTICS算法的伪代码。
   给参考第三版中文中的P310页算法写出。

   为什么BIRCH方法在发现任意形状的簇时会遇到困难，而OPTICS却不会？对BIRCH算法做一定改进，使得它可以发现任意形状的簇。
   作为一个基于距离的方法，BIRCH方法使用欧几里得距离和簇内邻近度，导致其倾向于发现球形簇。而OPTICS使用的是基于密度（连接度）的方法，其对簇的增长的基础是在规定半径内的连接点，因此可以发现任意形状的簇。
   我们可以通过使用基于密度和基于连接度的距离测量来构造low-level B++树和CF-树，从而对BIRCH算法进行改进。这将倾向于一个基于连接度（任意形状的）簇。

   给出CLIQUE算法在所有子控件发现稠密单元步骤的伪代码。
   指出在何种情况下，基于密度的聚类方法比基于划分的聚类方法和层次聚类方法更合适。并给出一些应用实例来支持你的观点。
   基于划分的聚类方法和层次聚类方法都是基于对象之间的距离。这样的方法更倾向于发现球形簇并在发现任意形状的簇上遇到困难。划分方法还在簇的密度和直径方面存在问题；而层次划分方法计算代价昂贵且不能撤回已经完成的分裂或合并步骤。
   基于密度的聚类方法是建立在每个簇通常其簇内的点的密度比簇外的大的前提之上的，即簇时数据空间中被稀疏区域分开的稠密区域。基于密度的方法能够发现任意形状的簇，不同意传统的聚类方法，其可以处理数据中的噪声。下图中展示了不同形状的簇，使用DBSCAN方法将能轻松处理这些簇。
   

2. 给出一个例子来说明如何集成特定的聚类方法，例如，一种聚类方法被用作另一种算法的预处理步骤。此外，请解释为什么两种聚类方法的集成有时候会改进聚类的质量和有效性。
   一个例子是BIRCH，一种集成了层次性聚类方法（预处理步骤）和其他聚类方法的聚类算法。一开始使用树形结构作为层次划分的对象，然后使用其他聚类算法（例如迭代划分）来重新定义簇，BIRCH增量地构建一个聚类特征树（CF树），是一棵高度平衡树，用于为层次聚类存储聚类特征（总和特征）。BIRCH包括两个阶段，第一个阶段（微聚类）扫描一遍数据库，在内存中建立一棵CF树，可以看做数据的多层压缩，视图保留数据的内在结构；第二个阶段（宏聚类）采用其他的聚类算法（例如迭代重定位）来对CF树的叶节点进行聚类，把稀疏的点当做离群点移出并且将稠密的簇合并为更大的簇。
   集成不同的聚类方法能够克服单个方法的局限性。例如，集成层次聚类方法和一种其他聚类方法，例如BIRCH克服了层次聚类分两大局限性——可扩展性和不能撤销已经完成的步骤。

3. 聚类已经被认为是一种具有广泛应用、重要的数据挖掘任务。对如下每种情况给出一个应用实例：
   1） 把聚类作为主要的数据挖掘功能的应用；
   一个例子是将城市中的房子根据房屋类型、价值和地理位置进行分组。具体地说，即可以使用CLARANS这样的聚类算法去发现温哥华中最贵的房屋单元可以组成一些簇。
   2） 把聚类作为预处理的工具，为其他数据挖掘任务做数据准备的应用。
   一个应用实例是空间数据挖掘。空间数据挖掘是指在空间数据中挖掘暗藏的有趣的关系或者特性。当自然的相似性存在，我们可以对空间属性应用聚类分析。从聚类中获取的簇可能会触发下一个步骤中非空间部分的产生，这可能是有趣的一组对象的结果。

4. 数据立方体和多维数据库以层次的或聚集的形式包含标称的、序数的和数值的数据。根据你已经学习的关于聚类的知识，设计一个可以有效地在大型数据立方体中发现簇的聚类方法。
   我们可以使用基于网格的聚类方法，例如CLIQUE，来找一个大型数据立方体中的簇，这是因为一个数据立方体可以解释为一个多分辨率网格结构。首先我们需要预处理并且离散化数据（例如序数和数值的数据）来获取一个单维度的离散。然后将会在两步内完成多维度聚类。第一步是将n维数据空间划分为不重叠的矩形单元，计算其中各个单元的密度，这一步在每个维度的1-D中实现。然后我们可以在k维空间中通过查找k-1维空间中的密度生成候选密度单元。在第二步中，对于每个簇的最小描述已经产生；对于每个簇，这决定了覆盖连通的密度单元的最大区域。然后决定每个簇的最小覆盖。使用这样的方法，我们能够在数据中找到有效代表数据立方体的簇。

5. 按如下标准对下列每种聚类方法进行描述：可以确定的簇的形状、必须指定的输入参数、局限性。

1. k-均值。
   球形；需指定簇的数量；对噪声敏感，只在小数据集上表现良好。
2. k-中心点。
   球形；需指定簇的数量；适用于小数据集（没有可扩展性）。
3. CLARA。
   球形；需指定簇的数量；对初始样本选取敏感。
4. BIRCH。
   球形；需给出n个d维的数据对象；由于CF树因为容量限制仅能容纳有限的实体，且不能满足用户对于一个自然类的聚类需求。
5. CHAMELEON。
   任意形状；需给出n个d维的数据对象；在最差情况下为O（n²）的复杂度。
6. DBSCAN。
   任意形状；最大可能距离即密度可达和簇中点的最少数量；在最差情况下为O（n²）的复杂度。

17. 人眼在判断聚类方法对二维数据的聚类质量上是快速而高效的。你能设计一个数据可视化方法来使数据聚类可视化并帮助人判断三维数据的聚类质量吗？对更高维数据又如何？
    方法如下：我们首先使用一个聚类算法获取三维数据中的簇，然后画出找到的簇。这些可以被投影到二维平面，以便可视化。为了更好判断三维数据的质量，可以以不同的角度翻转数据空间。然后，我们可以将其投影到其他的二维空间，类似地翻转数据空间。通过比较不同的二维空间簇，我们可以对三维数据有更全面的了解。
    对于更高维的空间，首先我们将其转化为低维数据，然后使用任何一个聚类算法去获取在低维水平下的簇，然后画出这些簇，再重复以上操作。理论上来说，我们可以从比较簇的不同颜色来对高维数据簇的质量有更好的理解。

18. 假设你打算在一个给定的区域分配一些自动取款机（ATM），使得满足大量约束条件。住宅或工作场所可以被聚类以便每个簇分配一个ATM。然而，该聚类可能被两个因素所约束：1）障碍物对象，即由一些困难影响ATM可达性的桥梁、河流和公路。2）用户指定的其他约束，如每个ATM机应该能为10 000户家庭服务。在这两个约束限制下，怎样修改聚类算法（如k-均值）来实现高质量的聚类？
    微聚类：对象在本地被微聚类处理，在一个微聚类中，任何两个物体之间没有障碍物。
    距离测量：如果有障碍物在两个物体中间则需要适当地调整他们的距离。在本例中，可达距离应该代替直接距离。可达距离给出在考虑障碍物的情况下两物体之间距离的最小值（可预测的最小值）。
    基于中心的：对于许多区域而言，初始化k个簇，其中k的值位于一个区域内允许的ATM数量最大值和最小值之间。假设中心将被移到一个区域的边缘，如果在移动后该区域资源包含的ATM数比需要的少或者超过了期望的阈值，那么该中心只能在边界内移动最靠近其他区域响应点的区域。

19. 对基于约束的聚类，除了每个簇具有最小数目的客户（如对ATM机的分配）的约束外，还可以有许多其他种类的约束。例如，约束可以是每个簇中客户的最大数目，每个簇中客户的平均收入，每两个簇之间的最大距离等。请对可以影响生成簇的约束条件进行分类，并讨论在这些约束条件之下怎样有效地实现聚类。

20. 设计一种保护隐私的聚类方法，使得数据所有者可以放心地让第三方来挖掘其数据以获得高质量聚类，而不必担心数据中某些私有或敏感的信息被泄露出去。
    一种保护私有信息的方法是对于敏感属性提供一个修改后的值，下面介绍两种方法。
    The value-class membership method：在这个方法中，属性的值被划分为一个互不相交的、互相排斥的类。考虑到一个特殊的离散即属性中的值被离散成一个个区间，所有的区间不需要等长。例如salary可以将10k划分进lower、将50k划分进higher。相比于给出一个属性的真值，给用户提供这样的值更好。
    The value distortion method：对于值x返回值x+r，其中r是一个由某种分布得出的随机值，包括以下两种：服从均匀分布，在[-a,+a]之间，数据的均值为0；高斯分布，服从正态分布，其均值为0且有标准偏差。