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

1、离群点检测（基于距离）题 目 学生姓名 学生学号 专业班级 指导教师2015117实验四离群点检测（基于距离）此实验是在实验三的基础上，修改完成。实验算法与上次相同，但增加了离 群点检测。离群点检测方法为：在聚类完成之后，计算簇中的点到各自簇心的距 离。当簇中的一点到簇心的距离大于该簇的平均距离与1.5倍标准差的和时，则 认为该点为离群点，即阀值平均距离与1.5倍标准差的和。一、实验目的1. 深刻理解离群点，了解离群点检测的一般方法；2. 掌握基于距离的离群点检测算法；3. 锻炼分析问题、解决问题的思维，提高动手实践的能力。二、背景知识异常对象被称作离群点。异常检测也称偏差检测和例外挖掘。常见

2、的异常成因：数据来源于不同的类（异常对象来自于一个与大多数数据对象源（类）不同的源（类）的思想），自然变异，以及数据测量或收集误差。 异常检测的方法：（1）基于模型的技术：首先建立一个数据模型，异常是那些同模型不能完 美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使 用冋归模型吋，异常是相对远离预测值的对象；（2）基于邻近度的技术：通常可以在对象之间定义邻近性度量，异常对象 是那些远离其他对象的对象；（3）基于密度的技术：仅当一个点的局部密度显著低于它的大部分近邻时 才将其分类为离群点。三、实验要求改写一种简单的半监督方法，用于离群点检测。使用一种你熟悉的程序设计 语言，

3、如c+或java,实现该方法，并在两种不同的数据集上进行讨论（1）只 有一些被标记的正常对象；（2）只有一些被标记的离群点实例。四、实验环境win7 旗舰版 + visual studio 2012 语言：c+五、算法描述k-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价 指标，即认为两个对象的距离越近，其相似度就越人。该算法认为簇是由距离靠 近的对象组成的，因此把得到紧凑且独立的簇作为最终0标。1、算法思路k-means 算法先随机选取k个对象作为初始的聚类中心。然后计算每个对象与各个种子 聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及 分配给它

4、们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类 中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终 止条件。终止条件可以是以下任何一个：1）没有（或最小数0）对象被重新分配给不同的聚类。2）没有（或最小数目）聚类中心再发生变化。3）误差平方和局部最小。2、算法步骤a. 从数据集中随机挑k个数据当簇心；b. 对数据中的所有点求到这k个簇心的距离，假如点pi离簇心si最近， 那么pi属于si对应的簇；c.根据每个簇的数据，更新簇心，使得簇心位于簇的中心；d. 重复步骤e和步骤f,直到簇心不再移动（或其他条件，如前后两次距 离和不超过特定值），继续下一步；e. 计

5、算每个簇的正常半径，即阀值（此程序阀值为每个簇的平均距离与1.5 倍标准差之和）；f. 从每个簇中，找出大于阀值的点，即离群点。:据结构node25ae摊 po5.x :double pos:doublee方5去0 nodeovkmean*sss摊 duster.num : int : vector<node>*count: int cutdata : vector<node>w data : vector<node> mean-nodes : vectors node > radio : doublei u猫o *kmeano 公 clusterpr

6、ocesso : void ® cuto : voidgetdistance(node active. node other): double getindexofcluster(vector<node> means. node active): int getmeans(int clusterjndex): nodegetsumofdi$t(vector<node>* clusters，vector<node> mean.nodes): double init.meanso : void0 kmean(int c.num. vector<n

7、ode» node.vector)0 showcutresultq : voidnode类，定义了二维空间中的一个点，pos_x，pos_y三成员变量分别为x，y， 轴的值，且为double型。node类作为基木数据结构，使用在kmean类里。kmean类封装了一系列成员变量和函数，实现了 kmean算法。具体成员变 量和函数详细说明如下：class kmeanprivate:int clustcr_num;/生成的簇的数量。 vector<ode> mean_nocles;/均值点 vector<ode> data;/所科的数扼点vector<ode&

8、gt;* clusters;/簇,key为簇的下标，value为该簇中所有点 int count;/记聚迭代次数vector<ode>* cutdata; double* radio;/初始化函数(首先随即生成代表点) void init_moans ();/聚类过程，将空间中的点分到不同的簇中 void clusterprocesso ;/获取当前结点的簇下标int getindexofcluster(vector<node> means, node active);/获取每个点到各向簇屮心的距离和double getsumofdist(vector<ode&g

9、t;* clusters, vector<ode> mean nodes); /生成均值node getmeans(int cluster index);/获取两个点之间的距离double getdistancc(odo active, node other); public:/构造函数，c_num为簇个数，node_vcctor为原姑数裾 kmean(int c nuni, vector<node> node_vector);'kmean ();/找出离群点只要距离大于平均距离+标准差，则视为离群点 void cut ();/显示剪枝结果 void showc

10、utresult ():；程序代码o maino inputo kmeano init means$ clusterprocesso showcutresultc getmeanso getindexofcluster® getsumofdisto cut0 getdistance注：代码图中相关函数的说明见kmean类的方法说明。七、程序截i*依次犏assm、麟僧 < 教据期机托!>0 4随机产生的利捤如下<1227.0. 1784.0><1408.0, 1122.0<4743.0. 19s2.0<3321.0, 4427.8><

11、;4257.0. 1246.0><2740.0, 0s.0><24k.b>m88.0><47b1.0>-12-11.h)<595.3849.m<1353.0. 461霸.0><4988.343s.0>24b8.0.4924.h><1097.0. 2338.0o40s.0.621.0><2589.0.41s2.0<11b8.0>4618.0<816.0, 521.b><2891.0， 1237.0><2464.h,3s1.0<13明.0, 4614

12、.0<2452.0. 3282.0<230(.0. 1744.0><2737.0.2688.0<4490.0.2550.0><4600.0, 4754.8<1693.0,477.0><4704.0.4253.b><4555.0.27s7.0><632.0, 2158.0><265.0. 1s16.0><1s32.0. 90.0<46?.0. 572.0>216s.6><2042.0.1s21.0<176.0,1“s.，><3496.b.3907.

13、0<3s78.m,3993.><2269.0.3533.0><3877.b.29“.0<6si.h.相30.04s94.b<1247.0, 2340.h><3231.0.3699.0<8u0* 2783.0<2039.0*1s46.h><2333.0, 2969.0<71.8. 2421.0<4349.h.245.0<1298.0, 1434.0<1730.b. 3782.0随机产生的4个译中心如下*<2486.0* 1488.0<1188.0,4618.0<2333.0.2

14、969.0><2042.0,1521.e>随机生成50个数据，随机选取4个簇心，如上图所示。e d;deslctop检3 kmeandebugc-kmean.exe o hs r s3离群点基于距离进行局b检硇，当距离大于平均值与1.s倍标准差的和，则算离群点*iii)hibj： <4011.1、709.3 <3562.0. 535.0> <4041.0. 713.0> <4726.0. 165.0 <4203.0, 278.0> <3345.0, 823.0 <3730.0. 576.0> <3511.

15、0. 800.0 <4667.0. 773.0> <4315.0. 1721.0>常震雲樓正呈：tppxll :i| :im5私径：996.9 481.830.1 898.5472.1 675.7311.1 508.3 g59.010s6.3超过正常半径离群!<4022正 $点<4?83.0， 正$点<3962.0， 正盡点 <低49.0. 正！点 <4579.0.正赛点<40m.0,费点 <3743.0. 宽点 <3548.0.正生点<488s.0，龙点 <3426.0， 覆点 <4694.0. >

16、;<4597.0. $<4706.0. 龙点 <3130.0, 正有点<2938.0. 离群点<2738.0.ijnafias。 3374.62927.03529.03652.0>3797.0>4440.0>2521.04803.03509.0>2706.02343.04531.03157.0>2381.04038.02285.0正窜半径：1573.1 半择：882.5 上华：165.8 上嗔595.1698.71066.0上 m至：898.2 1505.12唯：872.9上唯：896.02 韦：1230.9h轻：1291.3士嗜：7

17、17.3 1335.6 1271.3-mx： 1&84.4超过正常半径,离群!in经过聚类，簇1、簇2的中心已改变，算出的阀值、检测到的离群点如上图所示。e d:desktop该检3 kmeandebugc-kmean.exe拍yl、： 1329.0. 1087.4 1867.0. 1319.0点149?.0, 873.0'点1220.0, 2402.0绝点 130.0, 1929.0 底举点1sss.0. 194.0点1216.0, 302.0 4/2494.0. 979.0布点1084.0, 739.0 点946.0. 927.0点764.0, 2184.0'点1?

18、0.0, 1332.0点 188.0, 1633.0广点1917.0, 270.0点765.0, 924.0 省%0.0, 87.0 1957.0. 220.0群点2463.0, 2171.0正常半径：1s09j585.8272.31319.21464.9 921.5793.4 1170.0425.9415.2 1233.6504.31264.81006.9 587.21150.91070.81568.s超过正常半径离群1297.7. 3909.8 (1610.0, 3939.0点769.0, 2737.0点1518.0, 3038.0 2175.0. 4892.0点46.0, 3733.0点

19、1624.0. 3662.0点2135.0, 4235.0点1786.0. 4697.0 )fe16.0. 4255.0育按任意键继续.簇3、簇4聚类后，正常点和离群点如阁所示八、实验总结实验程序，是在聚类完成之后，基于距离筛选出了离群点。在数据挖掘过程 中，将离群点数据丢弃，更有利于分析获取有用的数据。从实验结果看，部分离 群点的距离远大于正常距离，丢弃这些数据，避免无效数据干扰，显得非常有意 义。九、附件1. 程序源码main.cpp 主程序入口 #includeiostream#includevector#include nk-mean.h”#include <ctime>u

20、sing namespace std;/输入数据void input(vector<node>& vecdata，int num);int main()srand(int) time(o); vector<node> data; int num，k;cout « ”请依次输入数据量、聚类个数(数据随机产生)n”;cin » num » k;input(data，num);kmean kmean(k，data); kmean.cut(); kmean.showcutresult(); system(pausen); return 0;

21、void input(vector<node>& vecdatajnt num)for(int i =0;i<num;i+)node node;node.pos_x = (rand() % 5000 ); node.pos_y = (rand() % 5000 ); vecdata.push_back(node);k-mean.h kmean 类和 node 类声明"k-mean.h#pragma once#includevector using namespace std;/空间点的定义 class nodepublic:double pos_x; dou

22、ble 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 true;else if (first.pos_x > second.pos_x)return false;/对y轴的比较 else if(first.pos_y < second.pos_y)return true;elsereturn false;friend

23、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<node> mean_nodes;/均值点 vector<node> data;/所有的数据点vector<node* clusters;/簇，k

24、ey为簇的下标，value为该簇中所存点 int count;/记录迭代次数 vector<node>* cutdata; double* radio;/初始化函数(首先随即生成代表点) void init_means();/聚类过i呈，将空间中的点分到不同的簇中 void clusterprocess();/获取当前结点的簇下标int getindexofcluster(vector<node> means，node active);/获取每个点到各自簇屮心的距离和double getsumofdist(vector<node>* clusters, ve

25、ctor<node> mean_nodes); /生成均值node getmeans(int clusterindex);/获取两个点之间的距离double getdistance(node active,node other);public:/构造函数，c_num为簇个数，node_vector为原始数据 kmean(int c_num，vector<nodenode_vector);kmean();/找出离群点只要距离大于平均距离+标准差，则视为离群点 void cut();/显示剪枝结果void showcutresult();k-mean.cpp kmean类的成员函

26、数具体定义#include "k-mean.h"#includevector#include <ctime>#include <cstdlib>#includealgorithm#include <cmath>#includeiostream#include <iomanip>using namespace std;kmean: kmean(int c_num，vector<nodenode_vector) cluster_num = c_num; data = node_vector;clusters = new ve

27、ctor<node>cluster_num; cutdata = new vector<node>cluster_num; radio = new doublecluster_num;init_means();clusterprocess();/进行聚类过程kmean:kmean()delete clusters; delete cutdata; delete radio;void kmeanzinit_means()/初始化函数(首先随即生成代表点) int num = data.size();srand(int)time(o);for(int i =0 ;i<

28、cluster_num;)int pos = rand()%num; bool insert_flag = true;/首先判断选中的点是否是中心点 for(unsigned int j = 0;j< mean_nodes.size();j+)if(mean一nodes j = datapos)insert_flag = false; break;if(insert_flag)mean_nodes.push_back(datafpos);i+;cout.setf(ios:fixed); cout« setprecision(l); cout« "随机产生的数

29、据如下：nn; for (int i = 0; i < num; i+)cout <<(" << datai.pos_x « "， << datai.pos_y « ")tt"cout « nn随机产生的 cluster_num « 1个簇屮心如下：n" for (int i = 0; i < cluster_num; i+)cout «« mean_nodesfil.pos_x « h, *' « mean_

30、nodesfil.pos_y «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 &

31、lt; cluster_num;i+) /更新每个簇的中心点 meanjodesfi = getmeans(i); /获取簇中心oldvar = newvar; count +;newvar = getsumofdist(clusters,mean_nodes); if(abs(newvar - oldvar) >= 1)for (int i = 0; i < cluster_num; i+)clustersi.clear(); _while(abs(newvar - oldvar) >= 1);/当前后两次距离和相差不大时，则认 为达到分类要求double kmean:ge

32、tdistance(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; tmpno

33、de.pos_y += c 1 usters cl uster_index j . pos_y;tmpnode.pos_x = tmpnode.pos_x/num; tmpnode.pos_y = tmpnode.pos_y/num;return tmpnode;int kmean:getindexofcluster(vector<node> means，node active)/获取当前 结点的簇下标 int num = means.size(); int index = 0;double tmpdist，mindist = getdistance(meanso，active);

34、 for (int i = 0; i < num; i+)tmpdist = getdistance(means f i 1 .active); if (tmpdist < mindist)mindist = tmpdist; index = i;return index;double kmean:getsumofdist(vector<node>* clusters， vector<node> mean_nodes)double sum = 0;int m_size = mean_nodes-size(); int c_size;for (int i =

35、0; i < m_size; i+)c一size = clustersi.size(); for (int j = 0; j < c一size; j+)sum += getdistance(mean_nodes i .clusters i j );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+)/计算每个簇的平均值su

36、m += getdistance(mean_nodes i .clusters i j );avgdist = sum/c_size;/计算每个簇的正常半径：平均值+标准差 sum = 0;for (int j = 0; j < c_size; j+)double d = getdistance(mean_nodesfi,clustersfifjl) - avgdist; sum += pow(d，2);radioi = 1.5*sqrt(sum/c_size) + avgdist;for (int j = 0; j < clustersfil.size(); j+)double

37、d = getdistance(meannodesi，clustersij); if(d > radioi)vector<node>:iterator it = clustersi.begin(); for (int k = 0; k < j; k+，it+)cutdatai .push_back(*it); clustersi.erase(it);void kmean:showcutresult()cout «"nn* 离 群 检 测 结 果 i7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* 7* <t% <t% <t% &