離群點(diǎn)檢測(cè)(基于距離)實(shí)驗(yàn)報(bào)告

1、題 目離群點(diǎn)檢測(cè)(基于距離)學(xué)生姓名學(xué)生學(xué)號(hào)專業(yè)班級(jí)指導(dǎo)教師2015-1-17實(shí)驗(yàn)四 離群點(diǎn)檢測(cè)(基于距離)此實(shí)驗(yàn)是在實(shí)驗(yàn)三的基礎(chǔ)上，修改完成。實(shí)驗(yàn)算法與上次相同，但增加了離群點(diǎn)檢測(cè)。離群點(diǎn)檢測(cè)方法為：在聚類完成之后，計(jì)算簇中的點(diǎn)到各自簇心的距離。當(dāng)簇中的一點(diǎn)到簇心的距離大于該簇的平均距離與1.5倍標(biāo)準(zhǔn)差的和時(shí)，則認(rèn)為該點(diǎn)為離群點(diǎn)，即閥值平均距離與1.5倍標(biāo)準(zhǔn)差的和。一、 實(shí)驗(yàn)?zāi)康?. 深刻理解離群點(diǎn)，了解離群點(diǎn)檢測(cè)的一般方法；2. 掌握基于距離的離群點(diǎn)檢測(cè)算法；3. 鍛煉分析問(wèn)題、解決問(wèn)題的思維，提高動(dòng)手實(shí)踐的能力。二、 背景知識(shí)異常對(duì)象被稱作離群點(diǎn)。異常檢測(cè)也稱偏差檢測(cè)和例外挖掘。常見(jiàn)的異

2、常成因：數(shù)據(jù)來(lái)源于不同的類（異常對(duì)象來(lái)自于一個(gè)與大多數(shù)數(shù)據(jù)對(duì)象源（類）不同的源（類）的思想），自然變異，以及數(shù)據(jù)測(cè)量或收集誤差。異常檢測(cè)的方法：（1）基于模型的技術(shù)：首先建立一個(gè)數(shù)據(jù)模型，異常是那些同模型不能完美擬合的對(duì)象；如果模型是簇的集合，則異常是不顯著屬于任何簇的對(duì)象；在使用回歸模型時(shí)，異常是相對(duì)遠(yuǎn)離預(yù)測(cè)值的對(duì)象；（2）基于鄰近度的技術(shù)：通?？梢栽趯?duì)象之間定義鄰近性度量，異常對(duì)象是那些遠(yuǎn)離其他對(duì)象的對(duì)象；（3）基于密度的技術(shù)：僅當(dāng)一個(gè)點(diǎn)的局部密度顯著低于它的大部分近鄰時(shí)才將其分類為離群點(diǎn)。三、 實(shí)驗(yàn)要求改寫一種簡(jiǎn)單的半監(jiān)督方法，用于離群點(diǎn)檢測(cè)。使用一種你熟悉的程序設(shè)計(jì)語(yǔ)言，如C+或Jav

3、a，實(shí)現(xiàn)該方法，并在兩種不同的數(shù)據(jù)集上進(jìn)行討論（1）只有一些被標(biāo)記的正常對(duì)象；（2）只有一些被標(biāo)記的離群點(diǎn)實(shí)例。四、 實(shí)驗(yàn)環(huán)境Win7 旗艦版 + Visual Studio 2012語(yǔ)言：C+五、 算法描述K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。1、 算法思路K-means算法先隨機(jī)選取K個(gè)對(duì)象作為初始的聚類中心。然后計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對(duì)象就代表一個(gè)聚類

4、。一旦全部對(duì)象都被分配了，每個(gè)聚類的聚類中心會(huì)根據(jù)聚類中現(xiàn)有的對(duì)象被重新計(jì)算。這個(gè)過(guò)程將不斷重復(fù)直到滿足某個(gè)終止條件。終止條件可以是以下任何一個(gè)：1)沒(méi)有（或最小數(shù)目）對(duì)象被重新分配給不同的聚類。2)沒(méi)有（或最小數(shù)目）聚類中心再發(fā)生變化。3)誤差平方和局部最小。2、 算法步驟a. 從數(shù)據(jù)集中隨機(jī)挑K個(gè)數(shù)據(jù)當(dāng)簇心； b. 對(duì)數(shù)據(jù)中的所有點(diǎn)求到這K個(gè)簇心的距離，假如點(diǎn)Pi離簇心Si最近，那么Pi屬于Si對(duì)應(yīng)的簇；c. 根據(jù)每個(gè)簇的數(shù)據(jù)，更新簇心，使得簇心位于簇的中心；d. 重復(fù)步驟e和步驟f，直到簇心不再移動(dòng)（或其他條件，如前后兩次距離和不超過(guò)特定值），繼續(xù)下一步；e. 計(jì)算每個(gè)簇的正常半徑，即閥

5、值（此程序閥值為每個(gè)簇的平均距離與1.5倍標(biāo)準(zhǔn)差之和）；f. 從每個(gè)簇中，找出大于閥值的點(diǎn)，即離群點(diǎn)。六、 數(shù)據(jù)結(jié)構(gòu)Node類，定義了二維空間中的一個(gè)點(diǎn)，pos_x,pos_y三成員變量分別為x，y，軸的值，且為double型。Node類作為基本數(shù)據(jù)結(jié)構(gòu)，使用在KMean類里。KMean類封裝了一系列成員變量和函數(shù)，實(shí)現(xiàn)了KMean算法。具體成員變量和函數(shù)詳細(xì)說(shuō)明如下：class KMeanprivate:int cluster_num;/生成的簇的數(shù)量。vector<Node> mean_nodes;/均值點(diǎn)vector<Node> data;/所有的數(shù)據(jù)點(diǎn)vecto

6、r<Node>* clusters;/簇,key為簇的下標(biāo)，value為該簇中所有點(diǎn)int count;/記錄迭代次數(shù)vector<Node>* cutData;double* radio;/初始化函數(shù)（首先隨即生成代表點(diǎn)）void Init_Means();/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中void ClusterProcess();/獲取當(dāng)前結(jié)點(diǎn)的簇下標(biāo)int getIndexOfCluster(vector<Node> means, Node active);/獲取每個(gè)點(diǎn)到各自簇中心的距離和double getSumOfDist(vector<

7、;Node>* clusters, vector<Node> mean_nodes);/生成均值Node getMeans(int cluster_index);/獲取兩個(gè)點(diǎn)之間的距離double getDistance(Node active,Node other);public:/構(gòu)造函數(shù)，c_num為簇個(gè)數(shù)，node_vector為原始數(shù)據(jù)KMean(int c_num,vector<Node> node_vector);KMean();/找出離群點(diǎn) 只要距離大于平均距離+標(biāo)準(zhǔn)差，則視為離群點(diǎn)void cut();/顯示剪枝結(jié)果void showCutRes

8、ult();程序代碼圖注：代碼圖中相關(guān)函數(shù)的說(shuō)明見(jiàn)KMean類的方法說(shuō)明。七、 程序截圖隨機(jī)生成50個(gè)數(shù)據(jù)，隨機(jī)選取4個(gè)簇心，如上圖所示。經(jīng)過(guò)聚類，簇1、簇2的中心已改變，算出的閥值、檢測(cè)到的離群點(diǎn)如上圖所示。簇3、簇4聚類后，正常點(diǎn)和離群點(diǎn)如圖所示。八、 實(shí)驗(yàn)總結(jié)實(shí)驗(yàn)程序，是在聚類完成之后，基于距離篩選出了離群點(diǎn)。在數(shù)據(jù)挖掘過(guò)程中，將離群點(diǎn)數(shù)據(jù)丟棄，更有利于分析獲取有用的數(shù)據(jù)。從實(shí)驗(yàn)結(jié)果看，部分離群點(diǎn)的距離遠(yuǎn)大于正常距離，丟棄這些數(shù)據(jù)，避免無(wú)效數(shù)據(jù)干擾，顯得非常有意義。九、 附件1. 程序源碼main.cpp主程序入口#include <iostream>#include <

9、;vector>#include "k-mean.h"#include <ctime>using namespace std;/輸入數(shù)據(jù)void input(vector<Node>& vecData,int num);int main()srand(int) time(0);vector<Node> data;int num,k;cout << "請(qǐng)依次輸入數(shù)據(jù)量、聚類個(gè)數(shù)(數(shù)據(jù)隨機(jī)產(chǎn)生)n"cin >> num >> k;input(data,num);KMean

10、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.hkmean類和Node類聲明/k-mean.h#pragma once#inc

11、lude <vector>using namespace std;/空間點(diǎn)的定義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)/對(duì)x軸的比較if(first.pos_x < second.pos_x)return true;else if (first.pos_x > second.pos_x)return false;/對(duì)y軸的

12、比較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;/生成的簇的數(shù)量。vector<Node> m

13、ean_nodes;/均值點(diǎn)vector<Node> data;/所有的數(shù)據(jù)點(diǎn)vector<Node>* clusters;/簇,key為簇的下標(biāo)，value為該簇中所有點(diǎn)int count;/記錄迭代次數(shù)vector<Node>* cutData;double* radio;/初始化函數(shù)（首先隨即生成代表點(diǎn)）void Init_Means();/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中void ClusterProcess();/獲取當(dāng)前結(jié)點(diǎn)的簇下標(biāo)int getIndexOfCluster(vector<Node> means, Node act

14、ive);/獲取每個(gè)點(diǎn)到各自簇中心的距離和double getSumOfDist(vector<Node>* clusters, vector<Node> mean_nodes);/生成均值Node getMeans(int cluster_index);/獲取兩個(gè)點(diǎn)之間的距離double getDistance(Node active,Node other);public:/構(gòu)造函數(shù)，c_num為簇個(gè)數(shù)，node_vector為原始數(shù)據(jù)KMean(int c_num,vector<Node> node_vector);KMean();/找出離群點(diǎn) 只要距離

15、大于平均距離+標(biāo)準(zhǔn)差，則視為離群點(diǎn)void cut();/顯示剪枝結(jié)果void showCutResult();k-mean.cppkmean類的成員函數(shù)具體定義#include "k-mean.h"#include <vector>#include <ctime>#include <cstdlib>#include <algorithm>#include <cmath>#include <iostream>#include <iomanip>using namespace std;KMea

16、n: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 doublecluster_num;Init_Means();ClusterProcess();/進(jìn)行聚類過(guò)程KMean:KMean()delete clusters;delete cutData;delete radio

17、;void KMean:Init_Means()/初始化函數(shù)（首先隨即生成代表點(diǎn)）int num = data.size();srand(int)time(0);for(int i =0 ;i<cluster_num;)int pos = rand()%num;bool insert_flag = true;/首先判斷選中的點(diǎn)是否是中心點(diǎn)for(unsigned int j = 0;j< mean_nodes.size();j+)if(mean_nodesj = datapos)insert_flag = false;break;if(insert_flag )mean_nodes

18、.push_back(datapos);i+;cout.setf(ios:fixed);cout << setprecision(1);cout << "隨機(jī)產(chǎn)生的數(shù)據(jù)如下：n"for (int i = 0; i < num; i+)cout << "(" << datai.pos_x << ", " << datai.pos_y << ")tt"cout << "n隨機(jī)產(chǎn)生的" <<

19、; cluster_num << "個(gè)簇中心如下：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()/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中/下面是聚類過(guò)程in

20、t i;double newVar = 3,oldVar = -1; /新舊距離和dofor(i = 0;i < data.size();i+) /找到每個(gè)點(diǎn)當(dāng)前最近的中心點(diǎn)，并放進(jìn)對(duì)應(yīng)的簇int index = getIndexOfCluster(mean_nodes,datai);clustersindex.push_back(datai);for (i = 0; i < cluster_num;i+) /更新每個(gè)簇的中心點(diǎn)mean_nodesi = getMeans(i); /獲取簇中心oldVar = newVar;count +;newVar = getSumOfDist

21、(clusters,mean_nodes);if(abs(newVar - oldVar) >= 1)for (int i = 0; i < cluster_num; i+)clustersi.clear();while(abs(newVar - oldVar) >= 1);/當(dāng)前后兩次距離和相差不大時(shí)，則認(rèn)為達(dá)到分類要求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)

22、;Node KMean:getMeans(int cluster_index)/求出簇中所有點(diǎn)的均值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 tm

23、pNode;int KMean:getIndexOfCluster(vector<Node> means, Node active)/獲取當(dāng)前結(jié)點(diǎn)的簇下標(biāo)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

24、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 = clustersi.size();for (int j = 0; j < c_size; j+)sum += getDistance(mean_nodesi,clustersij);return sum;voi

25、d 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+) /計(jì)算每個(gè)簇的平均值sum += getDistance(mean_nodesi,clustersij);avgDist = sum/c_size;/計(jì)算每個(gè)簇的正常半徑：平均值+標(biāo)準(zhǔn)差sum = 0;for (int j = 0; j < c_size; j+)double d = getDist

26、ance(mean_nodesi,clustersij) - avgDist;sum += pow(d,2);radioi = 1.5*sqrt(sum/c_size) + avgDist;for (int j = 0; j < clustersi.size(); j+)double d = getDistance(mean_nodesi,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*離群檢測(cè)結(jié)果*"cout << "n*離群點(diǎn)基于距離進(jìn)