數(shù)據(jù)挖掘-第九章離群點(diǎn)挖掘

2023/2/4離群點(diǎn)挖掘主要內(nèi)容離群點(diǎn)挖掘的概述離群點(diǎn)數(shù)據(jù)挖掘方法簡(jiǎn)介基于統(tǒng)計(jì)的方法基于距離的方法基于密度的方法基于聚類(lèi)的方法什么是離群點(diǎn)(Outlier)？Hawkins的定義：離群點(diǎn)是在數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)的偏離并非由隨機(jī)因素產(chǎn)生，而是產(chǎn)生于完全不同的機(jī)制。Weisberg的定義：離群點(diǎn)是與數(shù)據(jù)集中其余部分不服從相同統(tǒng)計(jì)模型的數(shù)據(jù)。Samuels的定義：離群點(diǎn)是足夠地不同于數(shù)據(jù)集中其余部分的數(shù)據(jù)。Porkess的定義：離群點(diǎn)是遠(yuǎn)離數(shù)據(jù)集中其余部分的數(shù)據(jù)離群點(diǎn)的特殊意義和實(shí)用價(jià)值

現(xiàn)有數(shù)據(jù)挖掘研究大多集中于發(fā)現(xiàn)適用于大部分?jǐn)?shù)據(jù)的常規(guī)模式,在許多應(yīng)用領(lǐng)域中，離群點(diǎn)通常作為噪音而忽略，許多數(shù)據(jù)挖掘算法試圖降低或消除離群點(diǎn)的影響。而在有些應(yīng)用領(lǐng)域識(shí)別離群點(diǎn)是許多工作的基礎(chǔ)和前提，離群點(diǎn)會(huì)帶給我們新的視角。如在欺詐檢測(cè)中，離群點(diǎn)可能意味欺詐行為的發(fā)生，在入侵檢測(cè)中離群點(diǎn)可能意味入侵行為的發(fā)生。實(shí)例：例如我們?cè)O(shè)兒童上學(xué)的具體年齡總體服從正態(tài)分布，所給的數(shù)據(jù)集是某地區(qū)隨機(jī)選取的開(kāi)始上學(xué)的20名兒童的年齡具體的年齡特征如下:

年齡={6,7,6,8,9,10,8,11,7,9,12,7,11,8,13,7,8,14,9,12}

那么.相應(yīng)的統(tǒng)計(jì)參數(shù)是:均值=9.1;標(biāo)準(zhǔn)差=2.3。

如果選擇數(shù)據(jù)分布的閾值為：閾值=均值±2×標(biāo)準(zhǔn)差

故在[4.5,13.7]區(qū)間以外的數(shù)據(jù)都是潛在的離群點(diǎn)，將最大值取整為13。所以年齡為14的孩子可能是個(gè)例外。而且由均值可知，此地的孩子普遍上學(xué)較晚.教育部門(mén)以后可據(jù)此作一些政策上的改進(jìn)。案例：孤立點(diǎn)挖掘在高等學(xué)校科技統(tǒng)計(jì)數(shù)據(jù)分析中的應(yīng)用

孤立點(diǎn)實(shí)驗(yàn)數(shù)據(jù)源：（選自全國(guó)普通高等學(xué)?？萍冀y(tǒng)計(jì)數(shù)據(jù)上報(bào)基表中的數(shù)據(jù)）

甘肅省2010年科技統(tǒng)計(jì)上報(bào)數(shù)據(jù)中的一所高校數(shù)據(jù)

對(duì)基表中的數(shù)據(jù)，如選取科技人員職稱(chēng)和學(xué)歷作為最終測(cè)試對(duì)象，因職稱(chēng)只有院士、正高、副高、講師、助教和其它職稱(chēng)共六種職稱(chēng)，而學(xué)歷只有高中以下、中專(zhuān)、大專(zhuān)、本科、碩士和博士共六種職稱(chēng)，職稱(chēng)和學(xué)歷跨度小，檢測(cè)出來(lái)的孤立點(diǎn)孤立程度相對(duì)較低，故選取跨度較大的出生年月作為測(cè)試對(duì)象。選取三個(gè)指標(biāo):出生年月、學(xué)位和職稱(chēng)作為檢測(cè)屬性。 實(shí)驗(yàn)及結(jié)果分析用DS算法時(shí)，取M=20，算法返回距離的值最大的20個(gè)教師信息如表1所示。通過(guò)分析，可以發(fā)現(xiàn)孤立點(diǎn)數(shù)據(jù)中存在兩種典型的孤立點(diǎn)類(lèi)別：

(1)孤立點(diǎn)數(shù)據(jù)遠(yuǎn)遠(yuǎn)偏離于正常值的范圍

序號(hào)1-4（噪聲）(2)孤立點(diǎn)數(shù)據(jù)偏離于正常值的范圍

可能是錄入錯(cuò)誤，可能是真實(shí)數(shù)據(jù)序號(hào)出生年月學(xué)歷職稱(chēng)1198907大學(xué)本科正高級(jí)2198510碩士研究生副高級(jí)3196008博士研究生初級(jí)4197909專(zhuān)科副高級(jí)5196002博士研究生中級(jí)6195511博士研究生副高級(jí)7198109碩士研究生副高級(jí)8197408博士研究生初級(jí)9198109碩士研究生副高級(jí)10198206博士研究生副高級(jí)11198301博士研究生副高級(jí)12195706博士研究生副高級(jí)13195712博士研究生副高級(jí)14197302碩士研究生正高級(jí)15197211大學(xué)本科正高級(jí)16195001碩士研究生正高級(jí)17197304碩士研究生副高級(jí)18195011碩士研究生副高級(jí)19196911碩士研究生初級(jí)20197002碩士研究生初級(jí)離群點(diǎn)檢測(cè)的應(yīng)用領(lǐng)域電信、保險(xiǎn)、銀行中的欺詐檢測(cè)與風(fēng)險(xiǎn)分析發(fā)現(xiàn)電子商務(wù)中的犯罪行為災(zāi)害氣象預(yù)報(bào)稅務(wù)局分析不同團(tuán)體交所得稅的記錄，發(fā)現(xiàn)異常模型和趨勢(shì)海關(guān)、民航等安檢部門(mén)推斷哪些人可能有嫌疑

海關(guān)報(bào)關(guān)中的價(jià)格隱瞞營(yíng)銷(xiāo)定制：分析花費(fèi)較小和較高顧客的消費(fèi)行為醫(yī)學(xué)研究中發(fā)現(xiàn)醫(yī)療方案或藥品所產(chǎn)生的異常反應(yīng)計(jì)算機(jī)中的入侵檢測(cè)應(yīng)用異常檢測(cè)到文本編輯器，可有效減少文字輸入的錯(cuò)誤

……離群點(diǎn)挖掘(Outliermining)離群點(diǎn)挖掘問(wèn)題由兩個(gè)子問(wèn)題構(gòu)成：。(1)定義在一個(gè)數(shù)據(jù)集中什么數(shù)據(jù)是不一致或離群的數(shù)據(jù)；(2)找出所定義的離群點(diǎn)的有效挖掘方法。離群點(diǎn)挖掘問(wèn)題可以概括為如何度量數(shù)據(jù)偏離的程度和有效發(fā)現(xiàn)離群點(diǎn)的問(wèn)題。為什么會(huì)出現(xiàn)離群點(diǎn)？測(cè)量、輸入錯(cuò)誤或系統(tǒng)運(yùn)行錯(cuò)誤所致數(shù)據(jù)內(nèi)在特性所決定客體的異常行為所致

由于離群點(diǎn)產(chǎn)生的機(jī)制是不確定的，離群點(diǎn)挖掘算法檢測(cè)出的“離群點(diǎn)”是否真正對(duì)應(yīng)實(shí)際的異常行為，不是由離群點(diǎn)挖掘算法來(lái)說(shuō)明、解釋的，只能由領(lǐng)域?qū)＜襾?lái)解釋?zhuān)x群點(diǎn)挖掘算法只能為用戶(hù)提供可疑的數(shù)據(jù)，以便用戶(hù)引起特別的注意并最后確定是否真正的異常。對(duì)于異常數(shù)據(jù)的處理方式也取決于應(yīng)用，并由領(lǐng)域?qū)＜覜Q策。離群點(diǎn)挖掘中需要處理的幾個(gè)問(wèn)題

(1)全局觀點(diǎn)和局部觀點(diǎn)

離群點(diǎn)與眾不同，但具有相對(duì)性。(2)點(diǎn)的離群程度

可以通過(guò)定義對(duì)象的偏離程度來(lái)給對(duì)象打分——離群因子(OutlierFactor)或離群值得分(OutlierScore)，即都為離群點(diǎn)的情況下，也還有分高和分低的區(qū)別。(3)離群點(diǎn)的數(shù)量及時(shí)效性

正常點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)超過(guò)離群點(diǎn)的數(shù)量，離群點(diǎn)的數(shù)量在大規(guī)模數(shù)據(jù)集中所占的比例較低，小于5%甚至1%離群點(diǎn)實(shí)例一個(gè)人的年齡為-999就可能是由于程序處理缺省數(shù)據(jù)設(shè)置默認(rèn)值所造成的；一個(gè)公司的高層管理人員的工資明顯高于普通員工的工資可能成為離群點(diǎn)但卻是合理的數(shù)據(jù)(如平安保險(xiǎn)公司2007年5位高管稅后收入超過(guò)了1000萬(wàn)元)；一部住宅電話(huà)的話(huà)費(fèi)由每月200元以?xún)?nèi)增加到數(shù)千元可能就因?yàn)楸槐I打或其它特殊原因所致；一張信用卡出現(xiàn)明顯的高額消費(fèi)也許是因?yàn)槭潜I用的卡。離群點(diǎn)與眾不同但具有相對(duì)性：

高與矮，瘋子與常人。類(lèi)似術(shù)語(yǔ)：

Outliermining，Exceptionmining:異常挖掘、離群挖掘、例外挖掘和稀有事件挖掘。離群點(diǎn)檢測(cè)方法分類(lèi)從使用的主要技術(shù)路線(xiàn)角度分類(lèi)基于統(tǒng)計(jì)的方法基于距離的方法基于密度的方法基于聚類(lèi)的方法基于偏差的方法基于深度的方法基于小波變換的方法基于神經(jīng)網(wǎng)絡(luò)的方法…從類(lèi)標(biāo)號(hào)(正常或異常)利用的程度分類(lèi)無(wú)監(jiān)督的離群點(diǎn)檢測(cè)方法在實(shí)際情況下，沒(méi)有提供類(lèi)標(biāo)號(hào)有監(jiān)督的離群點(diǎn)檢測(cè)方法要求存在離群點(diǎn)類(lèi)和正常類(lèi)的訓(xùn)練集半監(jiān)督的離群點(diǎn)檢測(cè)方法訓(xùn)練數(shù)據(jù)包含被標(biāo)記的正常數(shù)據(jù)，但是沒(méi)有關(guān)于離群點(diǎn)對(duì)象的信息離群點(diǎn)檢測(cè)中需要處理的問(wèn)題(1)用于定義離群點(diǎn)的屬性個(gè)數(shù)一個(gè)對(duì)象只有單個(gè)屬性一個(gè)對(duì)象具有多個(gè)屬性：可能某個(gè)屬性異常，某個(gè)屬性正常如：對(duì)于男生而言，身高1.6m，體重55kg，這個(gè)很正常；身高1.6m，體重75kg，這個(gè)有點(diǎn)離群；身高1.8m，體重75kg，基本正常。若對(duì)于女生，則三組值可能都不太正常。所以，定義離群點(diǎn)需要指明如何使用多個(gè)屬性的值確定一個(gè)對(duì)象是否離群？(2)全局觀點(diǎn)和局部觀點(diǎn)一個(gè)對(duì)象可能相對(duì)于所有對(duì)象看上去離群，但它相對(duì)于它的局部近鄰不是離群的例如：身高1.85m對(duì)于一般人群是不常見(jiàn)的，但對(duì)于職業(yè)籃球運(yùn)動(dòng)員不算什么(3)點(diǎn)的離群程度某些技術(shù)方法是以二元方式來(lái)報(bào)告對(duì)象是否離群點(diǎn)，即：離群點(diǎn)或正常點(diǎn)但，這不能反映某些對(duì)象比其他對(duì)象更加極端偏離的基本事實(shí)通過(guò)定義對(duì)象的離群程度來(lái)給對(duì)象打分，如都為離群點(diǎn)的情況下，也還有分高和分低的區(qū)別?！x群點(diǎn)得分(outlierscore)或離群因子(OutlierFactor)離群點(diǎn)檢測(cè)的挑戰(zhàn)和前提挑戰(zhàn)：數(shù)據(jù)中有多少離群點(diǎn)?方法應(yīng)該是無(wú)監(jiān)督的，就像在干草堆中尋找一根針前提假設(shè)假定數(shù)據(jù)集中被認(rèn)為正常的點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)超過(guò)被認(rèn)為離群的點(diǎn)數(shù)基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)這類(lèi)方法大部分是從針對(duì)不同分布的離群點(diǎn)檢驗(yàn)方法發(fā)展起來(lái)的，通常用戶(hù)使用分布來(lái)擬合數(shù)據(jù)集。假定所給定的數(shù)據(jù)集存在一個(gè)分布或概率模型(例如，正態(tài)分布或泊松分布)，然后將與模型不一致(即分布不符合)的數(shù)據(jù)標(biāo)識(shí)為離群數(shù)據(jù)。基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)假定用一個(gè)參數(shù)模型來(lái)描述數(shù)據(jù)的分布(如正態(tài)分布)應(yīng)用基于統(tǒng)計(jì)分布的離群點(diǎn)檢測(cè)方法依賴(lài)于數(shù)據(jù)分布參數(shù)分布(如均值或方差)期望離群點(diǎn)的數(shù)目

(置信度區(qū)間)離群點(diǎn)的概率定義離群點(diǎn)的概率定義：離群點(diǎn)是一個(gè)對(duì)象，關(guān)于數(shù)據(jù)的概率分布模型，它具有低概率概率分布模型通過(guò)估計(jì)用戶(hù)指定的分布的參數(shù)，由數(shù)據(jù)創(chuàng)建。例：如果假定數(shù)據(jù)具有高斯分布，則基本分布的均值和標(biāo)準(zhǔn)差可以通過(guò)計(jì)算數(shù)據(jù)的均值和標(biāo)準(zhǔn)差來(lái)估計(jì)，然后可以估計(jì)每個(gè)對(duì)象在該分布下的概率。實(shí)例：檢測(cè)一元正態(tài)分布中的離群點(diǎn)下面利用統(tǒng)計(jì)學(xué)中最常用的分布--高斯(正態(tài))分布，來(lái)介紹一種簡(jiǎn)單的統(tǒng)計(jì)學(xué)離群點(diǎn)檢測(cè)方法。正態(tài)分布用記號(hào)：N(μ，σ)表示，μ表示均值，σ表示方差。cN(0,1)的α10.31731.50.133620.04552.50.012430.00273.50.000540.0001來(lái)自N(0,1)分布的對(duì)象(值)出現(xiàn)在分布尾部的機(jī)會(huì)很小。例如，對(duì)象落在3標(biāo)準(zhǔn)差的中心區(qū)域以外的概率僅有0.0027。更一般地，如果x是屬性值，則|x|>=c的概率隨c增加而迅速減小。設(shè)α=p(|x|≥c)。表6-1顯示當(dāng)分布為N(0,1)時(shí)c的某些樣本值和對(duì)應(yīng)的α值。注意：離群值超過(guò)4個(gè)標(biāo)準(zhǔn)差的值出現(xiàn)的可能性是萬(wàn)分之一。實(shí)例：檢測(cè)一元正態(tài)分布中的離群點(diǎn)定義定義設(shè)屬性x取自具有均值0和標(biāo)準(zhǔn)差1的高斯分布。如果屬性值x滿(mǎn)足：P(|x|≥c)=α，其中c是一個(gè)選定的常量，則x以概率1-α為離群點(diǎn)。為了使用該定義，需要指定α值。從不尋常的值(對(duì)象)預(yù)示來(lái)自不同的值的觀點(diǎn)來(lái)說(shuō)，α表示我們錯(cuò)誤地將來(lái)自給定分布的值分類(lèi)為離群點(diǎn)的概率。從離群點(diǎn)是N(0,1)分布的稀有值的觀點(diǎn)來(lái)說(shuō)，α表示稀有程度。如果(正常對(duì)象的)一個(gè)感興趣的屬性的分布是具有均值μ和標(biāo)準(zhǔn)差σ的正態(tài)分布，即

分布，則可以通過(guò)變換z=(x-μ)/σ轉(zhuǎn)換為標(biāo)準(zhǔn)正態(tài)分布N(0,1)，通常μ和σ是未知的，可以通過(guò)樣本均值和樣本標(biāo)準(zhǔn)差來(lái)估計(jì)。實(shí)踐中，當(dāng)觀測(cè)值很多時(shí)，這種估計(jì)的效果很好；另一方面，由概率統(tǒng)計(jì)中的大數(shù)定律可知，在大樣本的情況下可以用正態(tài)分布近似其它分布。在該圖中，中心線(xiàn)μ是觀測(cè)值的預(yù)測(cè)值，μ3σ

對(duì)應(yīng)上下控制線(xiàn)，μ2σ對(duì)應(yīng)上、下警告線(xiàn)。根據(jù)3σ原則，99.73%的觀測(cè)值將落在上下控制線(xiàn)的區(qū)間內(nèi)，僅有0.27%的觀測(cè)值落在此區(qū)間之外。質(zhì)量控制示意圖μ+3σxtμ-3σμ-2σμ+2σμ對(duì)于觀測(cè)樣本X：(1)如此點(diǎn)在上、下警告線(xiàn)之間區(qū)域內(nèi),則測(cè)定過(guò)程處于控制狀態(tài)，生產(chǎn)過(guò)程或樣本分析結(jié)果有效；(2)如果此點(diǎn)超出上、下警告線(xiàn)，但仍在上、下控制線(xiàn)之間的區(qū)域內(nèi)，提示質(zhì)量開(kāi)始變劣，可能存在“失控”傾向,應(yīng)進(jìn)行初步檢查，并采取相應(yīng)的校正措施；(3)若此點(diǎn)落在上、下控制線(xiàn)之外，表示生產(chǎn)或測(cè)定過(guò)程“失控"，生產(chǎn)的是廢品或觀測(cè)樣本無(wú)效。應(yīng)立即檢查原因，予以糾正。質(zhì)量控制示意圖

tμ+3σxμ-3σμ-2σμ+2σμ基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)方法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：離群點(diǎn)檢測(cè)的統(tǒng)計(jì)學(xué)方法具有堅(jiān)實(shí)的基礎(chǔ)，建立在標(biāo)準(zhǔn)的統(tǒng)計(jì)學(xué)技術(shù)(如分布參數(shù)的估計(jì))之上。當(dāng)存在充分的數(shù)據(jù)和所用的檢驗(yàn)類(lèi)型的知識(shí)時(shí)，這些檢驗(yàn)可能非常有效。缺點(diǎn)：大部分統(tǒng)計(jì)方法是針對(duì)單個(gè)屬性的，對(duì)于多元數(shù)據(jù)技術(shù)方法較少。在許多情況下,數(shù)據(jù)分布是未知的。對(duì)于高維數(shù)據(jù),很難估計(jì)真實(shí)的分布。這類(lèi)方法不適合混合類(lèi)型數(shù)據(jù)基于距離的離群點(diǎn)檢測(cè)基于距離的離群點(diǎn)檢測(cè)基于距離的離群點(diǎn)檢測(cè)方法，其基本思想如下：一個(gè)對(duì)象是離群的，如果它遠(yuǎn)離大部分其它對(duì)象。優(yōu)點(diǎn)：確定數(shù)據(jù)集的有意義的鄰近性度量比確定它的統(tǒng)計(jì)分布更容易，綜合了基于分布的思想，克服了基于分布方法的主要缺陷?；诰嚯x方法的兩種不同策略第一種策略是采用給定鄰域半徑，依據(jù)點(diǎn)的鄰域中包含的對(duì)象多少來(lái)判定離群點(diǎn)如果一個(gè)點(diǎn)的鄰域內(nèi)包含的對(duì)象少于整個(gè)數(shù)據(jù)集的一定比例則標(biāo)識(shí)它為離群點(diǎn)，也就是將沒(méi)有足夠鄰居的對(duì)象看成是基于距離的離群點(diǎn)。利用k最近鄰距離的大小來(lái)判定離群使用k-最近鄰的距離度量一個(gè)對(duì)象是否遠(yuǎn)離大部分點(diǎn)，一個(gè)對(duì)象的離群程度由到它的k-最近鄰的距離給定。這種方法對(duì)k的取值比較敏感。k太小(例如1)，則少量的鄰近離群點(diǎn)可能導(dǎo)致較低的離群程度。k太大，則點(diǎn)數(shù)少于k的簇中所有的對(duì)象可能都成了離群點(diǎn)。到k-最近鄰的距離的計(jì)算k-最近鄰的距離：一個(gè)對(duì)象的離群點(diǎn)得分由到它的k-最近鄰的距離給定。離群點(diǎn)得分的最低值為0，最高值是距離函數(shù)的可能最大值----如無(wú)窮大定義6-2對(duì)于正整數(shù)k，對(duì)象p的k最近鄰距離k-distance(p)定義為:(1)除p外，至少有k個(gè)對(duì)象o滿(mǎn)足(2)除p外，至多k-1個(gè)對(duì)象o滿(mǎn)足2023/2/4定義6-3點(diǎn)x的離群因子定義為：這里是不包含x的k-最近鄰的集合，

是該集合的大小?；诰嚯x的離群點(diǎn)檢測(cè)算法輸入：數(shù)據(jù)集D；最近鄰個(gè)數(shù)k輸出：離群點(diǎn)對(duì)象列表1：forall對(duì)象xdo2：

確定x的k-最近鄰集合N(x,k)3：

確定x的離群因子OF1(x,k)4：endfor5：對(duì)OF1(x,k)降序排列，確定離群因子大的若干對(duì)象6：return應(yīng)注意：x的k-最近鄰的集

包含的對(duì)象數(shù)可能超過(guò)k。選擇合適的離群因子閾值一種形式上簡(jiǎn)單的方法是指定離群點(diǎn)個(gè)數(shù)；這里介紹另一種確定OF1(x,k)分割閾值的方法：對(duì)OF1(x,k)降序排列，選擇OF1(x,k)急劇下降的點(diǎn)作為離群值、正常值的分隔點(diǎn)，如圖6-3所示，在該圖中，有兩個(gè)點(diǎn)判定為離群點(diǎn)。例6-1例6-1在圖6-4所示的二維數(shù)據(jù)集中，當(dāng)k=2時(shí)，P1、P2哪個(gè)點(diǎn)具有更高的離群點(diǎn)得分？(使用歐式距離)xy1213112122236824325752例6-1解答：對(duì)P1點(diǎn)進(jìn)行分析：k=2；最近鄰的點(diǎn)為P3(5,7)，P2(5,2)，distance(P1，P2)與distance(P1，P3)分別為6.08,1.41，平均距離為：對(duì)P2點(diǎn)進(jìn)行分析：k=2；最近鄰的點(diǎn)為P3，P4,同理有：因?yàn)镺F1(P1,K)>OF1(P2,K),因此，P1點(diǎn)更有可能是離群點(diǎn)。基于距離的離群點(diǎn)檢測(cè)例6-2在圖6-5所示的二維數(shù)據(jù)集中，當(dāng)k=5時(shí)，哪個(gè)點(diǎn)具有最大的離群因子,B的離群因子和D的離群因子哪個(gè)小？CDAB解答：圖所示的二維數(shù)據(jù)集主體由一個(gè)緊密的簇和一個(gè)松散的簇組成，下圖以灰度圖顯示了各點(diǎn)的離群因子情況，D的離群因子低于松散簇中部分點(diǎn)的離群因子。點(diǎn)C的離群因子最大，B點(diǎn)的離群因子大于D點(diǎn)的離群因子。這個(gè)例子說(shuō)明，當(dāng)數(shù)據(jù)集包含不同密度的區(qū)域時(shí)，基于距離的離群點(diǎn)檢測(cè)方法不能很好地識(shí)別離群點(diǎn)。CDAB離群點(diǎn)得分遞增基于距離的離群檢測(cè)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：基于距離的離群點(diǎn)檢測(cè)方案簡(jiǎn)單缺點(diǎn)：(1)檢測(cè)結(jié)果對(duì)參數(shù)k的選擇較敏感(2)時(shí)間復(fù)雜度為

，難以用于大規(guī)模數(shù)據(jù)集，這里n為數(shù)據(jù)集的規(guī)模；(3)需要有關(guān)離群因子閾值或數(shù)據(jù)集中離群點(diǎn)個(gè)數(shù)的先驗(yàn)知識(shí)，在實(shí)際使用中有時(shí)由于先驗(yàn)知識(shí)的不足會(huì)造成一定的困難。(4)因?yàn)樗褂萌珠撝?，不能處理不同密度區(qū)域的數(shù)據(jù)集?；谙鄬?duì)密度的離群點(diǎn)檢測(cè)2023/2/4基于密度的離群點(diǎn)檢測(cè)

當(dāng)數(shù)據(jù)集含有多種分布或數(shù)據(jù)集由不同密度子集混合而成時(shí)，數(shù)據(jù)是否離群不僅僅取決于它與周?chē)鷶?shù)據(jù)的距離大小，而且與鄰域內(nèi)的密度狀況有關(guān)。這里使用每個(gè)對(duì)象到第k個(gè)最近鄰的距離大小來(lái)度量密度。定義6-4(1)對(duì)象的局部鄰域密度(2)相對(duì)密度其中，是不包含x的k-最近鄰的集合，是該集合的大小，y是一個(gè)最近鄰。基于相對(duì)密度的離群點(diǎn)檢測(cè)方法通過(guò)比較對(duì)象的密度與它的鄰域中的對(duì)象平均密度來(lái)檢測(cè)離群點(diǎn)。簇內(nèi)靠近核心點(diǎn)的對(duì)象的相對(duì)密度接近于1，而處于簇的邊緣或是簇的外面的對(duì)象的相對(duì)較大。定義相對(duì)密度為離群因子：相對(duì)密度離群點(diǎn)檢測(cè)算法1：{k是最近鄰個(gè)數(shù)}2：forall對(duì)象xdo3：確定x的k-最近鄰N(x,k)。4：使用x的最近鄰(即N(x,k)中的對(duì)象)，確定x的密度density(x,k)。5：endfor6：forall對(duì)象xdo7：確定x的相對(duì)密度relativedensity(x,k)，并賦值給OF2(x,k)。8：endfor9:對(duì)OF2(x,k)降序排列，確定離群點(diǎn)得分高的若干對(duì)象例6-3：給定二維數(shù)據(jù)集，表6-2給出了點(diǎn)的坐標(biāo)，可視化的圖形如圖6-7所示(對(duì)象間的距離采用曼哈頓(Manhattan)距離計(jì)算)。(1)取k=2，計(jì)算點(diǎn)P4，P15的局部鄰域密度

及相對(duì)密度

，哪個(gè)點(diǎn)更可能是離群點(diǎn)？(2)取k=2，按照基于距離的離群點(diǎn)檢測(cè)，P4，P15哪個(gè)點(diǎn)更可能是離群點(diǎn)？P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16X1112222333344455Y2341234123412301(1)對(duì)于P4，k最近鄰鄰域包含兩個(gè)對(duì)象：

對(duì)于P15，k最近鄰鄰域包含2個(gè)對(duì)象：P12，P16的密度均為1，相對(duì)點(diǎn)P4，點(diǎn)P15更可能是離群點(diǎn)。(2)對(duì)于k=2P4的k最近鄰鄰域?yàn)?/p>

，k最近鄰距離均值為1。P15的k最近鄰鄰域?yàn)?/p>

，k最近鄰距離均值為1.5。經(jīng)過(guò)比較可以看出，點(diǎn)P15的離群程度要高。例6-4模擬圖6-8中類(lèi)似數(shù)據(jù)，K取2，3，5時(shí)，以表格方式給出所有點(diǎn)的局部鄰域密度及相對(duì)密度、基于距離的離群因子。(采用歐式距離)解答：K取2，3，5時(shí)，所有點(diǎn)的局部鄰域密度、相對(duì)密度、基于距離的離群因子表所示。點(diǎn)的坐標(biāo)

k=2

k=3

k=5

x

y局部鄰域密度相對(duì)密度距離離群因子局部鄰域密度相對(duì)密度距離離群因子局部鄰域密度相對(duì)密度距離離群因子45950.070.8814.000.060.8716.330.040.9022.6060960.051.3420.500.041.1522.330.041.1127.0051800.060.9617.000.050.9618.330.050.8020.6038900.080.9113.000.060.9416.330.040.9623.8039770.070.9814.500.061.0417.670.041.0225.0069790.041.2122.500.041.3325.670.031.3531.801511690.131.398.000.131.168.000.101.079.801451630.131.568.000.111.409.330.091.2711.401511560.141.367.000.121.208.670.101.0910.401531630.171.046.000.150.876.670.140.767.401611540.121.118.500.091.4911.330.071.4913.601511610.220.704.500.180.705.670.140.767.401571670.131.178.000.111.409.330.091.2411.201611590.121.448.500.101.209.670.091.1410.801121860.027.0056.000.027.9958.670.026.6860.80502380.015.85131.000.015.66138.000.015.52146.60基于聚類(lèi)的離群點(diǎn)檢測(cè)2023/2/4基于聚類(lèi)的離群點(diǎn)檢測(cè)方法

物以類(lèi)聚—相似的對(duì)象聚合在一起?；诰垲?lèi)的方法有兩個(gè)共同特點(diǎn)：

(1)先采用特殊的聚類(lèi)算法處理輸入數(shù)據(jù)而得到聚類(lèi)，再在聚類(lèi)的基礎(chǔ)上來(lái)檢測(cè)離群點(diǎn)。

(2)只需要掃描數(shù)據(jù)集若干次，效率較高，適用于大規(guī)模數(shù)據(jù)集。2023/2/4基于聚類(lèi)的離群點(diǎn)檢測(cè)方法靜態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)第一階段對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)第二階段計(jì)算對(duì)象或簇的離群因子，將離群因子大的對(duì)象或簇中對(duì)象判定為離群點(diǎn)。動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)第一步，利用靜態(tài)數(shù)據(jù)的離群檢測(cè)方法建立離群檢測(cè)模型第二步，利用對(duì)象與已有模型間的相似程度來(lái)檢測(cè)離群點(diǎn)關(guān)鍵問(wèn)題：距離的定義、離群程度的度量基于對(duì)象離群因子的方法首先聚類(lèi)所有對(duì)象，然后評(píng)估對(duì)象屬于簇的程度如果一個(gè)對(duì)象不強(qiáng)屬于任何簇，則稱(chēng)該對(duì)象為基于聚類(lèi)的離群點(diǎn)。對(duì)于基于原型的聚類(lèi)，可以用對(duì)象到它的簇中心的距離來(lái)度量對(duì)象屬于簇的程度。基于對(duì)象離群因子的方法定義6-5

給定簇C，C的摘要信息CSI(ClusterSummaryInformation)定義為：其中n為簇C的大小，Summary由分類(lèi)屬性中不同取值的頻度信息和數(shù)值屬性的質(zhì)心兩部分構(gòu)成，即：定義6-6

假設(shè)據(jù)集D被聚類(lèi)算法劃分為k個(gè)簇對(duì)象p的離群因子(OutlierFactor)OP3(p)定義為p與所有簇間距離的加權(quán)平均值：引理如果隨機(jī)變量服從正態(tài)分布，則有：兩階段離群點(diǎn)挖掘方法TOD描述如下：第一步，對(duì)數(shù)據(jù)集D進(jìn)行采用一趟聚類(lèi)算法進(jìn)行聚類(lèi)，得到聚類(lèi)結(jié)果第二步，計(jì)算數(shù)據(jù)集D中所有對(duì)象p的離群因子OF3(p)，及其平均值A(chǔ)ve_OF和標(biāo)準(zhǔn)差Dev_OF，滿(mǎn)足條件：

的對(duì)象判定為離群點(diǎn)。

通常取

例6-5基于聚類(lèi)的離群點(diǎn)檢測(cè)示例1對(duì)于圖所示的二維數(shù)據(jù)集，比較點(diǎn)P1(6,8)，P2(5,2)，哪個(gè)更有可能成為離群點(diǎn)。假設(shè)數(shù)據(jù)集經(jīng)過(guò)聚類(lèi)后得到聚類(lèi)結(jié)果為C={C1、C2、C3}，圖中紅色圓圈標(biāo)注，三個(gè)簇的質(zhì)心分別為：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)，試計(jì)算所有對(duì)象的離群因子。例6-5基于聚類(lèi)的離群點(diǎn)檢測(cè)示例1解答：根據(jù)定義6-6，公式對(duì)于P1點(diǎn)有：

對(duì)于P2有：可見(jiàn)，點(diǎn)P1較P2更可能成為離群點(diǎn)。例6-5基于聚類(lèi)的離群點(diǎn)檢測(cè)示例1同理可求得所有對(duì)象的離群因子，結(jié)果如表所示。xyOF3122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.4進(jìn)一步求得所有點(diǎn)的離群因子平均值A(chǔ)ve_OF=2.95，標(biāo)準(zhǔn)差Dev_OF=1.3，假設(shè)

；則閾值E=Ave_OF+*Dev_OF=2.95+1.3=4.25離群因子大于4.25的對(duì)象可視為離群點(diǎn)，P1與P2都是離群點(diǎn)，但相對(duì)而言，P1更有可能成為離群點(diǎn)。基于簇的離群因子的方法(1)在某種度量下，相似對(duì)象或相同類(lèi)型的對(duì)象會(huì)聚集在一起，或者說(shuō)正常數(shù)據(jù)與離群數(shù)據(jù)會(huì)聚集在不同的簇中；(2)正常數(shù)據(jù)占絕大部分，且離群數(shù)據(jù)與正常數(shù)據(jù)表現(xiàn)出明顯不同，或者說(shuō)離群數(shù)據(jù)會(huì)偏離正常數(shù)據(jù)(也就是大部分?jǐn)?shù)據(jù))。介紹簇的離群因子概念，利用簇的離群因子將簇區(qū)分為正常簇和離群簇。定義6-7給定簇C，C的摘要信息CSI(ClusterSummaryInformation)定義為：其中kind為簇的類(lèi)別(取值‘normal’或‘outlier’)，為簇C的大小,Cluster為簇C中對(duì)象標(biāo)識(shí)的集合，Summary由分類(lèi)屬性中不同取值的頻度信息和數(shù)值型屬性的質(zhì)心兩部分構(gòu)成，即：定義6-8假設(shè)據(jù)集D被聚類(lèi)算法劃分為k個(gè)簇，簇離群因子(OutlierFactor)定義為簇其它所有簇間距離的加權(quán)平均值：如果一個(gè)簇離幾個(gè)大簇的距離都比較遠(yuǎn)，則表明該簇偏離整體較遠(yuǎn)，其離群因子也較大。度量了簇偏離整個(gè)數(shù)據(jù)集的程度，其值越大，說(shuō)明偏離整體越遠(yuǎn)?；诰垲?lèi)的離群挖掘方法(CBOD)CBOD方法由兩個(gè)階段構(gòu)成：第一階段是利用一趟聚類(lèi)算法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)；第二階段是計(jì)算每個(gè)簇的離群因子，并按離群因子對(duì)簇進(jìn)行排序，最終確定離群簇，也即確定離群對(duì)象。CBOD算法描述如下：第一階段，聚類(lèi)：對(duì)數(shù)據(jù)集D進(jìn)行聚類(lèi)，得到聚類(lèi)結(jié)果；第二階段，確定離群簇：計(jì)算每個(gè)簇的離群因子，按遞減的順序重新排列，求滿(mǎn)足：

的最小，將簇標(biāo)識(shí)為‘outlier’類(lèi)(即其中每個(gè)對(duì)象均看成離群)，而將標(biāo)識(shí)為‘normal’類(lèi)(即其中每個(gè)對(duì)象均看成正常)。例6-6基于聚類(lèi)的離群點(diǎn)檢測(cè)示例2對(duì)例6-5中的數(shù)據(jù)集，聚類(lèi)后得到三個(gè)簇C={C1、C2、C3}，簇心分別為：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。簇之間的距離分別為進(jìn)一步計(jì)算三個(gè)簇的離群因子，具體如下：例6-6基于聚類(lèi)的離群點(diǎn)檢測(cè)示例2可見(jiàn)簇C1的離群因子最大，其中包含的對(duì)象判定為離群點(diǎn)，與例6-5得到的結(jié)論相同?；诰垲?lèi)的動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)

基本思想如下：

在對(duì)訓(xùn)練集聚類(lèi)的基礎(chǔ)上，按照簇的離群因子排序簇，并按一定比例將簇標(biāo)識(shí)為”normal”或”outlier”，以標(biāo)識(shí)的簇作為分類(lèi)模型，按照對(duì)象與分類(lèi)模型中最接近簇的距離判斷它是否離群點(diǎn)。

基于聚類(lèi)的動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)第一步，聚類(lèi)：對(duì)訓(xùn)練集進(jìn)行聚類(lèi)，得到聚類(lèi)結(jié)果；第二步，給簇作標(biāo)記：計(jì)算每個(gè)簇的離群因子，按遞減的順序重新排列，求滿(mǎn)足：

的最小b，將簇標(biāo)識(shí)為離群簇，而將標(biāo)識(shí)為正常簇。第三步，確定模型：以每個(gè)簇的摘要信息，聚類(lèi)半徑閾值r作為模型。(1)模型建立(2)模型評(píng)估利用改進(jìn)的最近鄰分類(lèi)方法INN(ImprovedNearestNeighbor)

評(píng)估測(cè)試集中的每個(gè)對(duì)象。INN方法具體描述如下：對(duì)于測(cè)試集中對(duì)象p，計(jì)算p與每個(gè)簇的距離若，則說(shuō)明p是已知類(lèi)型的行為，將簇的標(biāo)識(shí)作為p的標(biāo)識(shí)，否則說(shuō)明p是一種新的行為，將p標(biāo)識(shí)為可疑對(duì)象——候選離群點(diǎn)。(3)模型更新對(duì)于測(cè)試集中對(duì)象p，按照前面聚類(lèi)的方式，對(duì)新增對(duì)象進(jìn)行增量式聚類(lèi)更新用建立模型同樣的方法對(duì)所有簇重新標(biāo)記其類(lèi)別。6.6離群點(diǎn)挖掘方法的評(píng)估

可以通過(guò)下表所示混淆矩陣來(lái)描述離群點(diǎn)挖掘方法的檢測(cè)性能。在離群點(diǎn)檢測(cè)問(wèn)題中，并不關(guān)注預(yù)測(cè)正確的normal類(lèi)對(duì)象，重點(diǎn)關(guān)注的是正確預(yù)測(cè)的outlier類(lèi)對(duì)象。預(yù)測(cè)類(lèi)別outliernormal實(shí)際類(lèi)別outlier預(yù)測(cè)正確的outlier預(yù)測(cè)錯(cuò)誤的outliernormal預(yù)測(cè)錯(cuò)誤的normal預(yù)測(cè)正確的normal離群點(diǎn)檢測(cè)方法準(zhǔn)確性的兩個(gè)指標(biāo)檢測(cè)率(Detectionrate)表示被正確檢測(cè)的離群點(diǎn)記錄數(shù)占整個(gè)離群點(diǎn)記錄數(shù)的比例；誤報(bào)率(Falsepositiverate)表示正常記錄被檢測(cè)為離群點(diǎn)記錄數(shù)占整個(gè)正常記錄數(shù)的比例。期望離群點(diǎn)挖掘方法對(duì)離群數(shù)據(jù)有高的檢測(cè)率，對(duì)正常數(shù)據(jù)有低的誤報(bào)率，但兩個(gè)指標(biāo)之間會(huì)有一些沖突，高的檢測(cè)率常常會(huì)導(dǎo)致高的誤報(bào)率。也可以采用ROC曲線(xiàn)來(lái)顯示檢測(cè)率和誤報(bào)率之間關(guān)系例6-7采用基于聚類(lèi)的離群點(diǎn)挖掘方法處理UCI中