习题及参考答案

S({hamburgers})=2500/5000=50%

提升度lift({hot dogs}→{hamburgers})= C({hot dogs}→{hamburgers})/ S({hamburgers}) =1.334 提升度大于1，表明hot dogs和hamburgers不是互相独立的，二者之间存在正相关关系。

5.11对于表5-17所示序列数据集，设最小支持度计数为2，请找出所有的频繁模式。

表5-17 习题5.11数据集

Sequence ID 1 2 3 4 Sequence ID <(ad)c(bc)(ae)> <(e f )(ab)(d f )cb> 答：频繁1-序列：

、、、、、、<(ab)>、<(bc)>

频繁2-序列：

、、、、、

、、、 、、 、

、、、 、

<(bc)a> 频繁3-序列：

、、、、、、

、 、 频繁4-序列：

第6章离群点挖掘

6.1 为什么离群点挖掘是重要的？

答:离群点是指与大部分其它对象不同的对象，在数据的散布图中，它们远离其它数据点，

其属性值显著地偏离期望的或常见的属性值。(1) 因为离群点可能是度量或执行错误所导致的，例如相对少的离群点可能扭曲一组值的均值和标准差，或者改变聚类算法产生的簇的集合。(2) 因为离群点本身可能是非常重要的，隐藏着重要的信息，在欺诈检测，入侵检测等方面有着广泛的应用。所以离群点挖掘是非常重要的。

6.2 讨论基于如下方法的离群点检测方法潜在的时间复杂度：使用基于聚类的、基于距离的和基于密度的方法。不需要专门技术知识，而是关注每种方法的基本计算需求，如计算每个对象的密度的时间需求。

答：如果使用 K-means算法，它的时间复杂度就是O(n)，一般基于邻近度和基于密度的算

法的时间复杂度都是O(n2)，但是对于低维数据，使用专门的数据结构，如树或者k-d

第 25 页 共 27 页

树，可以把基于邻近度的算法的时间复杂度降低到O(nlog而对基于密度的算法来说，n)，

如果使用基于网格的算法，则可以把时间复杂度降低到O(n)，但这种方法不太精确而且也是用于低维数据。

6.3 许多用于离群点检测的统计检验方法是在这样一种环境下开发的：数百个观测就是一个大数据集。我们考虑这种方法的局限性：

(a) 如果一个值与平均值的距离超过标准差的三倍，则检测称它为离群点。对于1000000个值的集合，根据该检验，有离群点的可能性有多大？(假定正态分布)； (b) 一种方法称离群点是具有不寻常低概率的对象。处理大型数据集时，该方法需要调整吗？如果需要，如何调整？

答：(a)如果指的是单面的点的距离超过标准差的3倍，那么概率就是0.00135，则有1350

个离群点；如果指的是两面的点的距离超过标准差的3倍，那么概率就是0.0027，则有2700个离群点。

(b)具有百万个对象的数据集中，有成千上万个离群点，我们可以接受它们作为离群点或者降低临界值用以减少离群点。

6.4 假定正常对象被分类为离群点的概率是0.01，而离群点被分类为离群点概率为0.99，

如果99%的对象都是正常的，那么假警告率或误报率和检测率各为多少？(使用下面的

定义)

检测率?检测出的离群点个数离群点的总数假离群点的个数被分类为离群点的个数

假警告率?答： 假警告率=(99%*1%)/(99%*1%+1%*99%)=50%

检测率=(1%*99%)/(1%)=99%

6.5 从包含大量不同文档的集合中选择一组文档，使得它们尽可能彼此相异。如果我们认为相互之间不高度相关(相连接、相似)的文档是离群点，那么我们选择的所有文档可能都被分类为离群点。一个数据集仅由离群对象组成可能吗？或者，这是误用术语吗？ 答：离群点暗含的意思是稀有的、不常见的，有很多离群点的定义在一定的程度上融合了这

个概念。然而,在一些情况下, 离群点通常不会普遍发生，举一个相关例子：网络故障，

但有一个具体的定义。这就使得它能够区分这两种情况：纯粹检测一个异常和所要处理的对象大多数都是异常。同时，如果异常的概念是由数学或由算法定义的，这些定义可能会导致这样的一种情况：所研究的数据集中大部分或所有的对象都被归类为异常。另一种观点则可能认为如果不能够定义一种有意义的正常的情形，那么所有的对象都是异常。(“独特“这一术语通常也是用于这种情况。)总的来说，这可以被看作是哲学问题或语义问题。一个好的定义(尽管不可能是没有争议的)是能够分辨出当所收集的对象大多数或全部都是异常这一种情况。

6.6 考虑一个点集，其中大部分点在低密度区域，少量点在高密度区域。如果我们定义离群点为低密度区域的点，则大部分点被划分为离群点。这是对基于密度的离群点定义的适当使用吗？是否需要用某种方式修改该定义？

答：如果密度有一个绝对意义，比如被指定到某一定义域内，那么它可能会非常合理的考虑

第 26 页 共 27 页

把大部分的点作为异常。然而，在很多情况下，为了能够准确使用异常检测技术，通常会考虑使用相对密度这一概念。

6.7 一个数据分析者使用一种离群点检测算法发现了一个离群子集。出于好奇，该分析者对

这个离群子集使用离群点检测算法。

(a) 讨论本章介绍的每种离群点检测技术的行为。(如果可能，使用实际数据和算法来做)； (b) 当用于离群点对象的集合时，你认为离群点检测算法将做何反应？

答：(a)在某些情况下，以统计学为基础的异常检测技术，在离群子集上使用这将是无效的

使用技术，因为这种检测方法的假设将不再成立。对于那些依赖于模型的方法也是如此。以邻近点为基础或者以密度为基础的方法主要取决于特定的技术。如果保留原来的参数，使用距离或密度的绝对阈值的方法会将异常归类为一个异常对象的集合。其他相关方法会将大部分异常归类为普通点或者将一部分归类为异常。

(b)一个对象是否异常取决于整个对象的集合。因此，期望一种异常检测技术能够辨别一个异常集合，就像原始集合中并不存在这样一个异常集合，这是不合理的。

第 27 页 共 27 页