国科大学习资料数据挖掘（刘莹）第六章习题及参考答案

国科大学习资料–数据挖掘（刘莹）–第六章习题及参考答案

国科大学习资料–数据挖掘（刘莹）–第六章习题及参考答案

国科大学习资料–数据挖掘（刘莹）–第六章习题及参考答案

第 6 章离群点挖掘
6.1 为什么离群点挖掘是重要的？
答: 离群点是指与大部分其它对象不同的对象，在数据的散布图中，它们远离其它数据点， 其属性值显著地偏离期望的或常见的属性值。(1) 因为离群点可能是度量或执行错误所导致的，例如相对少的离群点可能扭曲一组值的均值和标准差，或者改变聚类算法产生的簇的集合。( 2) 因为离群点本身可能是非常重要的，隐藏着重要的信息，在欺诈检测， 入侵检测等方面有着广泛的应用。所以离群点挖掘是非常重要的。

6.2 讨论基于如下方法的离群点检测方法潜在的时间复杂度：使用基于聚类的、基于距离的和基于密度的方法。不需要专门技术知识，而是关注每种方法的基本计算需求，如计算每个对象的密度的时间需求。
答：如果使用 K-means 算法，它的时间复杂度就是O(n) ，一般基于邻近度和基于密度的算
法的时间复杂度都是O(n2 ) ，但是对于低维数据，使用专门的数据结构，如树或者 k- d

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

6.3 许多用于离群点检测的统计检验方法是