(完整word版)離群點(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)的異常成因：數(shù)

2、據(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-mea ns算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià) 指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠 近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。1、算法思路K-mea ns 算法先隨機(jī)選取K個(gè)對(duì)象作為初始的聚類中心。然后計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對(duì)象就代表一

4、個(gè)聚類。一旦全部對(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)Nvdc*K* pu ； J tr-方5去0 Nod0 KMean先!i曰車留i 氣 dusier_numi: int 豈s dustr : ctor ode 憶 eoLint : mt 氣 cutData vs ctor clN ode R 叫 data : wectpr meari.ncdes : vector 氣，rsdio r double*!回方法0 -KM E and% ClusiLerProcessO : void artO : void也童 get D

6、 ita hcb N od e a rtive. Kode other) : douJblefj1a getlndcxOfClu5te r(vector rncons. Node octiv i int% getMeansfnt duster ndex): Nod叫rrean_n0de5! : doublejheQ s void KMfranfintvectorNede*:0 Ed irvCul Re 山 tQ : void” JNode類，定義了二維空間中的一個(gè)點(diǎn)，pos_x,pos_y三成員變量分別為x ,y， 軸的值，且為double型。Node類作為基本數(shù)據(jù)結(jié)構(gòu)，使用在KMean類里。

7、KMean類封裝了一系列成員變量和函數(shù)，實(shí)現(xiàn)了 KMean算法。具體成員變 量和函數(shù)詳細(xì)說(shuō)明如下：class KMeanprivate :int cluster.num; /生成的簇的數(shù)量。vector mean_nodes; / 均值點(diǎn)vector data; / 所有的數(shù)據(jù)點(diǎn)vector * clusters; /簇,key為簇的下標(biāo)，value為該簇中所有點(diǎn)int count; /記錄迭代次數(shù)vector * cutData;double * radio;/初始化函數(shù)(首先隨即生成代表點(diǎn))void Init_Means();/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中void ClusterP

8、rocess();/獲取當(dāng)前結(jié)點(diǎn)的簇下標(biāo)int getIndexOfCluster(vector means. Nodeactive);/獲取每個(gè)點(diǎn)到各自簇中心的距離和double getSumOfDist( vector * clusters, vector mean_nodes);/生成均值Node getMeans( int cluster_index);/獲取兩個(gè)點(diǎn)之間的距離double getDista nce( Node active, Node other);public :/構(gòu)造函數(shù)，c_nun為簇個(gè)數(shù)，node_vector為原始數(shù)據(jù)KMean(nt c_num, vecto

9、r node_vector);KMea n();/找出離群點(diǎn)只要距離大于平均距離+標(biāo)準(zhǔn)差，則視為離群點(diǎn)void cut();/顯示剪枝結(jié)果void showCutResult(); |;程序代碼圖& Quite rPrpcen$ input getMeans如 getlndexOKIusterH getSumOfDistt sboiMCutResLult口 getDi stance注：代碼圖中相關(guān)函數(shù)的說(shuō)明見(jiàn) KMean類的方法說(shuō)明七、程序截圖tfa 4!4.0 an. 2m.r 側(cè)n. 懾址的亠th CiHV.aC21112如 m隨機(jī)二生亦個(gè)罷巾心如Fs此 iw9.a2165 .M5 3 (

10、DISV4_MC274N IIa 4斗樺、 1353.11 Ifilfl 飾4曉ILC + MJ.tt. muC14H&J 刃BLI2$tf JC24G4J 47111 HPdl列霊(4490.8 a&.R. 3沖7胡 4H3BP7 Cl .H, 373-Hi.44i.Hft. cm.n.応翻鮮 UffTT.B. 27b6x0 343B.a 41S.Si9!a.H425 J. B4241.H4924.B55a9aZ77,? 1744.1, K7e亙|l亙*3 ill I|fe|-T XJ tT U BJT JT MJ 1-FBJ1 M BJ m RJ -M- BJ U BJT m IU M M

11、-fUJ離群點(diǎn)基干距離進(jìn)行底卸檢涮.當(dāng)距為大于平找值寫1亦倍桁準(zhǔn)差的和則算離群點(diǎn)跌1 朕心* (3562,0, 點(diǎn)0也.氐 點(diǎn)“73.點(diǎn) 4203.0,點(diǎn)(3345.0, 點(diǎn)3730-0.工點(diǎn) 3511.0, 龜點(diǎn) 4667.0.詳點(diǎn) 800,0) 773.0 1721.0)；481.8:898.5:4?2 .1675.7311.1508.3659 .0105氛3超血正常半徑,離群!埶=4022 邕點(diǎn)W柏.也 戸點(diǎn) 3962.0, gj4549.0, 宦點(diǎn) 4579.0, p F4059 .9, |jC3743.0, 也點(diǎn) 3548.8, 一庁眈5”乩 F點(diǎn)3426,0. g(g4694.0,

12、 也點(diǎn)(45?.0, rA 3529.8 3652.8 3797.0 4440.Q 2521.B) 4803.0 3509.0 2706.0) 2343.0) 4531. 3157.0 21. 4038. 2285.8正常半徑：1573.1 半彳仝：882.b2維：lfiS.S丄遙* 595-12 三徑；698.72峯；898.2三程 I 1505,1872.9二衝 896.0注理：1230.92維 | 1291.32勺 717.3隹：1335.62徑 1271 3丄一二 訕4.4超噫正常半檢離群!rrr經(jīng)過(guò)聚類，簇1、簇2的中心已改變，算出的閥值、檢測(cè)到的離群點(diǎn)如上圖所示。51589.981

13、585.87 *4.1734 .3H 4e 4 0 0 0 M I-9JT-P4 - 200Q *0 0-00 2 *(11017 7 0 5644 S 80 - 7 - Z7 3 8 4 2 352404678966 9 4 Dc c-ctcccc-ccccccctc 宀響告告X苦小點(diǎn)占占點(diǎn)占E點(diǎn)占心點(diǎn)占小點(diǎn)占笞心;891G9H621293209-23 XN _318114B91 半靜t=書廖書港一 ETT-三半_TTHH_0,:L0即-1319.0 E730 2402.31?4.0?3旣価 ?7?,05 739.05 唧Q 2184-01332. lt33_0J 270-0 924.0 H

14、7_H220.0 2171.3常半徑；K； 5B5. fe： 272. 隹：1319倉(cāng) 1464 桎；921-793. 11705.415.1233 W 12641006587.llbM1B7B158.B冷超過(guò)止常生點(diǎn) 點(diǎn)G藥.(J, 4235.點(diǎn)(176.0, 4&97.0 點(diǎn)(16.0, 42S5.0)簇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. 程序源碼

15、ma in .cpp主程序入口#in elude #in elude #i nclude k-mea n.h#i nclude using n amespace std;輸入數(shù)據(jù)void in put(vector& vecData,i nt nu m);int mai n()srand(int) time(0);vector data;int nu m,k;cout num k;in put(data, nu m);KMea n kmea n( k,data);kmea n.cut();kmea n. showCutResult();system(pause);return 0;void i

16、n put(vector& vecData,i nt num)for(i nt i =0;i nu m;i+)Node no de;n ode.pos_x = (ran d() % 5000);n ode.pos_y = (ran d() % 5000 ); vecData.push_back (no de); _k-mean.hkmean類和 Node 類聲明/k-mea n.h#pragma once#in clude using n amespace std;空間點(diǎn)的定義class Nodepublic:double pos_x;double pos_y;Node()pos_x = 0.

17、0;pos_y = 0.0; _frie nd bool operator (const Node& first,c onst Node& sec ond)/對(duì)x軸的比較if(first.pos_x sec on d.pos_x)return false;/對(duì)y軸的比較elseif(first.pos_y sec on d.pos_y) 一 一return true;elsereturn false;frie nd bool operator = (const Node& first,c onst Node& sec ond)if(first.pos_x = sec on d.pos_x &

18、first.pos_y = sec on d.pos_y) return true;elsereturn false;class KMea nprivate:int cluster_num;生成的簇的數(shù)量。 vector mean_no des;均 值點(diǎn) vector data;/所有的數(shù)據(jù)點(diǎn) vector* clusters;/簇 ,key為簇的下標(biāo)，value為該簇中所有點(diǎn) int cou nt;記錄迭代次數(shù) vector* cutData;double* radio;初始化函數(shù)(首先隨即生成代表點(diǎn))void Ini t_Mea ns();/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中void C

19、lusterProcess();/獲取當(dāng)前結(jié)點(diǎn)的簇下標(biāo)int get In dexOfCluster(vector means. Node active);/獲取每個(gè)點(diǎn)到各自簇中心的距離和double getSumOfDist(vector* clusters, vector mea n_no des);/生成均值Node getMea ns(i nt cluster_i ndex);獲取兩個(gè)點(diǎn)之間的距離一double getDistance(Node active,Node other);public:/構(gòu)造函數(shù)，c_num為簇個(gè)數(shù)，node_vector為原始數(shù)據(jù)KMea n(i nt c

20、_num ,vector no de_vector);KMea n();/找出離群點(diǎn)只要距離大于平均距離+標(biāo)準(zhǔn)差，則視為離群點(diǎn)void cut();顯示剪枝結(jié)果void showCutResult();k-mean.cpp kmean類的成員函數(shù)具體定義#i nclude k-mea n.h#in clude #in clude #in clude #i nclude #in clude #in clude #i nclude using n amespace std;KMea n:KMea n(i nt c_num ,vector no de_vector)cluster, num = c_

21、num;data = no de_vector;clusters = new vectorcluster_ nu m;cutData = new vectorcluster_ nu m;radio = new doublecluster_ nu m;In it_Mea ns();ClusterProcess();/進(jìn)行聚類過(guò)程KMea n:KMea n()delete clusters;delete cutData;delete radio;void KMea n: :l nit_Mea ns()初始化函數(shù)(首先隨即生成代表點(diǎn)) int num = data.size();sran d(i n

22、t)time(O);for(i nt i =0 ;icluster_ nu m;) _int pos = ran d()% num;bool in sert_flag = true;/首先判斷選中的點(diǎn)是否是中心點(diǎn)for(un sig ned int j = 0;j mean_no des.size();j+) _if(mea n_no desj = datapos) _in sert_flag = false;break;if(i nsert_flag ) _mean_no des.push_back(datapos);i+;cout.setf(ios:fixed);cout setpreci

23、sion(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)生的 cluster_num 個(gè)簇中心如下：n;for (int i = 0; i cluster, num; i+) _cout ( mean_no desi.pos_x , mean_no desi.pos_y )t;cout endl en dl;void KMea n:ClusterProcess()/聚類過(guò)程，將空間中的點(diǎn)分到不同的簇中/下面是聚類過(guò)程int i;double newV

24、ar = 3,oldVar =-1;/ 新舊距離和dofor(i = 0;i data.size();i+)/ 找到每個(gè)點(diǎn)當(dāng)前最近的中心點(diǎn)，并放進(jìn)對(duì)應(yīng)的簇int in dex = getl ndexOfCluster(mea n_no des,datai); clustersi ndex.push_back(datai); _for (i = 0; i = 1)for (int i = 0; i = 1);/當(dāng)前后兩次距離和相差不大時(shí)，則認(rèn) 為達(dá)到分類要求double KMea n:getDista nce(Node active,Node other)return sqrt(pow(acti

25、ve.pos_*other.pos_x),2) + pow(active.pos_y - other.pos_y),2);Node KMea n:getMea ns(i nt clusterndex) _/求出簇中所有點(diǎn)的均值Node tmpNode;int num = clusterscluster_i ndex.size();for( int j = 0;j nu m;j+)tmpNode.pos_x += clusterscluster_i ndexj.pos_x;tmpNode.pos_y += clusterscluster_i ndexj.pos_y; tmpNode.pos_x

26、= tmpNode.pos_x/ num;tmpNode.pos_y = tmpNode.pos_y/num;return tmpNode;int KMean:getlndexOfCluster(vector means. Node active)/獲取當(dāng)前 結(jié)點(diǎn)的簇下標(biāo)int num = mean s.size();int in dex = 0;double tmpDist,mi nDist = getDista nce(mea nsO,active);for (int i = 0; i num; i+)tmpDist = getDista nce(mea nsi,active);if (t

27、mpDist mi nDist)mi nDist = tmpDist;in dex = i;retur n in dex;double KMea n:getSumOfDist(vector* clusters, vector mea n_no des)double sum = 0;int m_size = mean_no des.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 += getDista nce(mea n_no desi,clustersij); _return sum;void KMea n:cut()double avgDist;for (int i = 0; i cluster_ num; i+)double sum = 0;int c_size = clustersi.size();for (i nt j = 0; j c_size; j+)/計(jì)算每個(gè)簇的平均值 _sum += getDista nce(mea n_no de