离群点检测(基于距离)实验报告.doc

题 目离群点检测(基于距离)学生姓名学生学号专业班级指导教师2015-1-17实验四 离群点检测(基于距离)此实验是在实验三的基础上，修改完成。实验算法与上次相同，但增加了离群点检测。离群点检测方法为：在聚类完成之后，计算簇中的点到各自簇心的距离。当簇中的一点到簇心的距离大于该簇的平均距离与1.5倍标准差的和时，则认为该点为离群点，即阀值平均距离与1.5倍标准差的和。一、 实验目的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，直到簇心不再移动（或其他条件，如前后两次距离和不超过特定值），继续下一步；e. 计算每个簇的正常半径，即阀值（此程序阀值为每个簇的平均距离与1.5倍标准差之和）；f. 从每个簇中，找出大于阀值的点，即离群点。六、 数据结构Node类，定义了二维空间中的一个点，pos_x,pos_y三成员变量分别为x，y，轴的值，且为double型。Node类作为基本数据结构，使用在KMean类里。KMean类封装了一系列成员变量和函数，实现了KMean算法。具体成员变量和函数详细说明如下：class KMeanprivate:int cluster_num;/生成的簇的数量。vector mean_nodes;/均值点vector data;/所有的数据点vector* clusters;/簇,key为簇的下标，value为该簇中所有点int count;/记录迭代次数vector* cutData;double* radio;/初始化函数（首先随即生成代表点）void Init_Means();/聚类过程，将空间中的点分到不同的簇中void ClusterProcess();/获取当前结点的簇下标int getIndexOfCluster(vector means, Node active);/获取每个点到各自簇中心的距离和double getSumOfDist(vector* clusters, vector mean_nodes);/生成均值Node getMeans(int cluster_index);/获取两个点之间的距离double getDistance(Node active,Node other);public:/构造函数，c_num为簇个数，node_vector为原始数据KMean(int c_num,vector node_vector);KMean();/找出离群点 只要距离大于平均距离+标准差，则视为离群点void cut();/显示剪枝结果void showCutResult();程序代码图注：代码图中相关函数的说明见KMean类的方法说明。七、 程序截图随机生成50个数据，随机选取4个簇心，如上图所示。经过聚类，簇1、簇2的中心已改变，算出的阀值、检测到的离群点如上图所示。簇3、簇4聚类后，正常点和离群点如图所示。八、 实验总结实验程序，是在聚类完成之后，基于距离筛选出了离群点。在数据挖掘过程中，将离群点数据丢弃，更有利于分析获取有用的数据。从实验结果看，部分离群点的距离远大于正常距离，丢弃这些数据，避免无效数据干扰，显得非常有意义。九、 附件1. 程序源码main.cpp主程序入口#include #include #include k-mean.h#include using namespace std;/输入数据void input(vector& vecData,int num);int main()srand(int) time(0);vector data;int num,k;cout num k;input(data,num);KMean kmean(k,data);kmean.cut();kmean.showCutResult();system(pause);return 0;void input(vector& vecData,int num)for(int i =0;inum;i+)Node node;node.pos_x = (rand() % 5000 );node.pos_y = (rand() % 5000 );vecData.push_back(node);k-mean.hkmean类和Node类声明/k-mean.h#pragma once#include using namespace std;/空间点的定义class Nodepublic:double pos_x;double pos_y;Node()pos_x = 0.0;pos_y = 0.0;friend bool operator (const Node& first,const Node& second)/对x轴的比较if(first.pos_x second.pos_x)return false;/对y轴的比较else if(first.pos_y second.pos_y)return true;elsereturn false; friend bool operator = (const Node& first,const Node& second)if(first.pos_x = second.pos_x & first.pos_y = second.pos_y)return true;elsereturn false;class KMeanprivate:int cluster_num;/生成的簇的数量。vector mean_nodes;/均值点vector data;/所有的数据点vector* clusters;/簇,key为簇的下标，value为该簇中所有点int count;/记录迭代次数vector* cutData;double* radio;/初始化函数（首先随即生成代表点）void Init_Means();/聚类过程，将空间中的点分到不同的簇中void ClusterProcess();/获取当前结点的簇下标int getIndexOfCluster(vector means, Node active);/获取每个点到各自簇中心的距离和double getSumOfDist(vector* clusters, vector mean_nodes);/生成均值Node getMeans(int cluster_index);/获取两个点之间的距离double getDistance(Node active,Node other);public:/构造函数，c_num为簇个数，node_vector为原始数据KMean(int c_num,vector node_vector);KMean();/找出离群点 只要距离大于平均距离+标准差，则视为离群点void cut();/显示剪枝结果void showCutResult();k-mean.cppkmean类的成员函数具体定义#include k-mean.h#include #include #include #include #include #include #include using namespace std;KMean:KMean(int c_num,vector node_vector)cluster_num = c_num;data = node_vector;clusters = new vectorcluster_num;cutData = new vectorcluster_num;radio = new doublecluster_num;Init_Means();ClusterProcess();/进行聚类过程KMean:KMean()delete clusters;delete cutData;delete radio;void KMean:Init_Means()/初始化函数（首先随即生成代表点）int num = data.size();srand(int)time(0);for(int i =0 ;icluster_num;)int pos = rand()%num;bool insert_flag = true;/首先判断选中的点是否是中心点for(unsigned int j = 0;j mean_nodes.size();j+)if(mean_nodesj = datapos)insert_flag = false;break;if(insert_flag )mean_nodes.push_back(datapos);i+;cout.setf(ios:fixed);cout setprecision(1);cout 随机产生的数据如下：n;for (int i = 0; i num; i+)cout ( datai.pos_x , datai.pos_y )tt;cout n随机产生的 cluster_num 个簇中心如下：n;for (int i = 0; i cluster_num; i+)cout ( mean_nodesi.pos_x , mean_nodesi.pos_y )t;cout endl endl;void KMean:ClusterProcess()/聚类过程，将空间中的点分到不同的簇中/下面是聚类过程int i;double newVar = 3,oldVar = -1; /新旧距离和dofor(i = 0;i data.size();i+) /找到每个点当前最近的中心点，并放进对应的簇int index = getIndexOfCluster(mean_nodes,datai);clustersindex.push_back(datai);for (i = 0; i = 1)for (int i = 0; i = 1);/当前后两次距离和相差不大时，则认为达到分类要求double KMean:getDistance(Node active,Node other)return sqrt(pow(active.pos_x-other.pos_x),2) + pow(active.pos_y - other.pos_y),2);Node KMean:getMeans(int cluster_index)/求出簇中所有点的均值Node tmpNode;int num = clusterscluster_index.size();for( int j = 0;j num;j+)tmpNode.pos_x += clusterscluster_indexj.pos_x;tmpNode.pos_y += clusterscluster_indexj.pos_y;tmpNode.pos_x = tmpNode.pos_x/num;tmpNode.pos_y = tmpNode.pos_y/num;return tmpNode;int KMean:getIndexOfCluster(vector means, Node active)/获取当前结点的簇下标int num = means.size();int index = 0;double tmpDist,minDist = getDistance(means0,active);for (int i = 0; i num; i+)tmpDist = getDistance(meansi,active);if (tmpDist minDist)minDist = tmpDist;index = i;return index;double KMean:getSumOfDist(vector* clusters, vector mean_nodes)double sum = 0;int m_size = mean_nodes.size();int c_size;for (int i = 0; i m_size; i+)c_size = clustersi.size();for (int j = 0; j c_size; j+)sum += getDistance(mean_nodesi,clustersij);return sum;void KMean:cut()double avgDist;for (int i = 0; i cluster_num; i+)double sum = 0;int c_size = clustersi.size();for (int j = 0; j c_size; j+) /计算每个簇的平均值sum += getDistance(mean_nodesi,clustersij);avgDist = sum/c_size;/计算每个簇的正常半径：平均值+标准差sum = 0;for (int j = 0; j c_size; j+)double d = getDistance(mean_nodesi,clustersij) - avgDist;sum += pow(d,2);radioi = 1.5*sqrt(sum/c_size) + avgDist;for (int j = 0; j radioi)vector:iterator it = clustersi.begin();for (int k = 0; k j; k+, it+)cutDatai.push_back(*it);clustersi.erase(it);void KMean:showCutResult()cout nn*离群检测结果*;cout n*离群点基于距离进行局部检测，当距离大于平均值与1.5倍标准差的和，则算离群点*;cout n*n;for (int i = 0; i cluster_num; i+)int sizeOfCluster = clustersi.size();cout nn簇 i+1 簇心：( mean_nodesi.pos_x , mean_nodesi.pos_y )t 正常半径： radioi;for (int j = 0; j sizeOfCluster; j+)cout n正常点( clustersij.pos_x , clustersij.pos_y )tt半径： getDistance(mean_nodesi,clustersij);int cu_size = cutDatai.size();for (int j = 0; j cu_size; j+)cout n离群点( cutDataij.pos_x , cutDataij.pos_y )tt半径： getDistance(mean_nodesi,cutDataij) 超过正常半径，离群！;cout endl ;2. 数据集随机产生