文档介绍：题目离群点检测 ( 基于距离 )
学生姓名
学生学号
专业班级
指导教师
2015-1-17
实验四离群点检测 ( 基于距离 )
此实验是在实验三的基础上，修改完成。实验算法与上次相同，但增加了离
群点检测。离群点检测方法为：在聚类完成之后，计算簇中的点到各自簇心的距
离。当簇中的一点到簇心的距离大于该簇的平均距离与倍标准差的和时，则
认为该点为离群点，即阀值平均距离与倍标准差的和。
一、实验目的
1. 深刻理解离群点，了解离群点检测的一般方法；
2. 掌握基于距离的离群点检测算法；
3. 锻炼分析问题、解决问题的思维，提高动手实践的能力。
二、背景知识
异常对象被称作离群点。异常检测也称偏差检测和例外挖掘。
常见的异常成因：数据来源于不同的类（异常对象来自于一个与大多数数据
对象源（类）不同的源（类）的思想），自然变异，以及数据测量或收集误差。
异常检测的方法：
（1）基于模型的技术：首先建立一个数据模型，异常是那些同模型不能完
美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使
用回归模型时，异常是相对远离预测值的对象；
（2）基于邻近度的技术：通常可以在对象之间定义邻近性度量，异常对象
是那些远离其他对象的对象；
（3）基于密度的技术：仅当一个点的局部密度显著低于它的大部分近邻时
才将其分类为离群点。
三、实验要求
改写一种简单的半监督方法，用于离群点检测。使用一种你熟悉的程序设计
语言，如 C++或 Java，实现该方法，并在两种不同的数据集上进行讨论（ 1）只
有一些被标记的正常对象；（2）只有一些被标记的离群点实例。
四、实验环境
Win7 旗舰版 + Visual Studio 2012
语言： C++
五、算法描述
K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价
指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠
近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
1、算法思路
K -means 算法
先随机选取 K 个对象作为初始的聚类中心。然后计算每个对象与各个种子
聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及
分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类
中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终
止条件。终止条件可以是以下任何一个：
1)没有（或最小数目）对象被重新分配给不同的聚类。
2)没有（或最小数目）聚类中心再发生变化。
3)误差平方和局部最小。
2、算法步骤
a. 从数据集中随机挑 K 个数据当簇心；
b. 对数据中的所有点求到这 K 个簇心的距离，假如点 Pi 离簇心 Si 最近，
那么 Pi 属于 Si 对应的簇；
c. 根据每个簇的数据，更新簇心，使得簇心位于簇的中心；
d. 重复步骤 e 和步骤 f，直到簇心不再移动（或其他条件，如前后两次距
离和不超过特定值），继续下一步；