离群点检测(基于距离)实验报告.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 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,Node other);
public:
//构造函数，c_num为簇个数，node_vector为原始数据
KMean(int c_num,vector<Node> node_vector);
~KMean();
//找出离群点 只要距离大于平均距离+标准差，则视为离群点
void cut();
//显示剪枝结果
void showCutResult();
};
程序代码图

注：代码图中相关函数的说明见KMean类的方法说明。
七、 程序截图

随机生成50个数据，随机选取4个簇心，如上图所示。

经过聚类，簇1、簇2的中心已改变，算出的阀值、检测到的离群点如上图所示。

簇3、簇4聚类后，正常点和离群点如图所示。
八、 实验总结
实验程序，是在聚类完成之后，基于距离筛选出了离群点。在数据挖掘过程中，将离群点数据丢弃，更有利于分析获取有用的数据。从实验结果看，部分离群点的距离远大于正常距离，丢弃这些数据，避免无效数据干扰，显得非常有意义。
九、 附件
1. 程序源码
main.cpp 主程序入口
#include <iostream>
#include <vector>
#include "k-mean.h"
#include <ctime>
using namespace std;

//输入数据
void input(vector<Node>& vecData,int num);

int main()
{
srand((int) time(0));
vector<Node> data;
int num,k;
cout << "请依次输入数据量、聚类个数(数据随机产生)\n";
cin >> num >> k;
input(data,num);
KMean kmean(k,data);
kmean.cut();
kmean.showCutResult();
system("pause");
return 0;
}

void input(vector<Node>& vecData,int 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

#include <vector>
using namespace std;

//空间点的定义
class Node
{
public:
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 true;
}
else if (first.pos_x > second.pos_x)
{
return false;
}
//对y轴的比较
else
{
if(first.pos_y < second.pos_y)
{
return true;
}
else
{
return 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;
}
else
{
return false;
}
}
};

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,Node other);
public:
//构造函数，c_num为簇个数，node_vector为原始数据
KMean(int c_num,vector<Node> node_vector);
~KMean();
//找出离群点 只要距离大于平均距离+标准差，则视为离群点
void cut();
//显示剪枝结果
void showCutResult();
};

k-mean.cpp kmean类的成员函数具体定义
#include "k-mean.h"
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>

using namespace std;

KMean::KMean(int c_num,vector<Node> node_vector)
{
cluster_num = c_num;
data = node_vector;
clusters = new vector<Node>[cluster_num];
cutData = new vector<Node>[cluster_num];
radio = new double[cluster_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 ;i<cluster_num;)
{
int pos = rand()%num;
bool insert_flag = true;
//首先判断选中的点是否是中心点
for(unsigned int j = 0;j< mean_nodes.size();j++)
{
if(mean_nodes[j] == data[pos])
{
insert_flag = false;
break;
}
}

if(insert_flag )
{
mean_nodes.push_back(data[pos]);
i++;
}
}
cout.setf(ios::fixed);
cout << setprecision(1);
cout << "随机产生的数据如下：\n";
for (int i = 0; i < num; i++)
{
cout << "(" << data[i].pos_x << ", " << data[i].pos_y << ")\t\t";
}
cout << "\n随机产生的" << cluster_num << "个簇中心如下：\n";
for (int i = 0; i < cluster_num; i++)
{
cout << "(" << mean_nodes[i].pos_x << ", " << mean_nodes[i].pos_y << ")\t";
}
cout << endl << endl;
}

void KMean::ClusterProcess()//聚类过程，将空间中的点分到不同的簇中
{
//下面是聚类过程
int i;
double newVar = 3,oldVar = -1; //新旧距离和
do{
for(i = 0;i < data.size();i++) //找到每个点当前最近的中心点，并放进对应的簇
{
int index = getIndexOfCluster(mean_nodes,data[i]);
clusters[index].push_back(data[i]);
}
for (i = 0; i < cluster_num;i++) //更新每个簇的中心点
{
mean_nodes[i] = getMeans(i); //获取簇中心
}
oldVar = newVar;
count ++;
newVar = getSumOfDist(clusters,mean_nodes);
if(abs(newVar - oldVar) >= 1)
for (int i = 0; i < cluster_num; i++)
{
clusters[i].clear();
}
}while(abs(newVar - oldVar) >= 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 = clusters[cluster_index].size();
for( int j = 0;j < num;j++)
{
tmpNode.pos_x += clusters[cluster_index][j].pos_x;
tmpNode.pos_y += clusters[cluster_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(means[0],active);
for (int i = 0; i < num; i++)
{
tmpDist = getDistance(means[i],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 = 0; i < m_size; i++)
{
c_size = clusters[i].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 = clusters[i].size();
for (int j = 0; j < c_size; j++) //计算每个簇的平均值
{
sum += 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_nodes[i],clusters[i][j]) - avgDist;
sum += pow(d,2);
}
radio[i] = 1.5*sqrt(sum/c_size) + avgDist;

for (int j = 0; j < clusters[i].size(); j++)
{
double d = getDistance(mean_nodes[i],clusters[i][j]);
if(d > radio[i])
{
vector<Node>::iterator it = clusters[i].begin();
for (int k = 0; k < j; k++, it++)
{
}
cutData[i].push_back(*it);
clusters[i].erase(it);
}
}
}
}

void KMean::showCutResult()
{
cout << "\n\n******************离群检测结果********************************************";
cout << "\n*离群点基于距离进行局部检测，当距离大于平均值与1.5倍标准差的和，则算离群点*";
cout << "\n***************************************************************************\n";
for (int i = 0; i < cluster_num; i++)
{
int sizeOfCluster = clusters[i].size();
cout << "\n\n簇" << i+1 << "簇心：(" << mean_nodes[i].pos_x << ", " << mean_nodes[i].pos_y << ")\t"
<< "正常半径：" << radio[i];
for (int j = 0; j < sizeOfCluster; j++)
{
cout << "\n正常点(" << clusters[i][j].pos_x << ", " << clusters[i][j].pos_y << ")\t\t半径："
<< getDistance(mean_nodes[i],clusters[i][j]);
}
int cu_size = cutData[i].size();
for (int j = 0; j < cu_size; j++)
{
cout << "\n离群点(" << cutData[i][j].pos_x << ", " << cutData[i][j].pos_y << ")\t\t半径："
<< getDistance(mean_nodes[i],cutData[i][j]) << "超过正常半径，离群！";
}
}
cout << endl ;
}

2. 数据集 随机产生