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