離群點(diǎn)挖掘分析課件

1、商務(wù)數(shù)據(jù)挖掘與應(yīng)用案例分析第6章 離群點(diǎn)挖掘 6.1 概述 6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè)方法 6.3 基于聚類的離群點(diǎn)檢測(cè)方法 6.4 離群點(diǎn)檢測(cè)方法的評(píng)估 開(kāi)篇案例保險(xiǎn)欺詐檢驗(yàn)隨著保險(xiǎn)業(yè)的蓬勃發(fā)展，保險(xiǎn)欺詐現(xiàn)象也越來(lái)越嚴(yán)重。有關(guān)統(tǒng)計(jì)數(shù)據(jù)顯示，國(guó)際上某些險(xiǎn)種因被欺詐而導(dǎo)致的賠款支出最高可達(dá)保險(xiǎn)費(fèi)收入的50。從所發(fā)生的保險(xiǎn)欺詐案例看，手段無(wú)所不用且花樣翻新，有的虛構(gòu)或者偽造索賠，人壽保險(xiǎn)中常見(jiàn)的是移花接木、冒名頂替，或者自演自導(dǎo)一幕幕自殘的苦肉計(jì)，更惡劣的還有殺親騙保者，財(cái)產(chǎn)保險(xiǎn)中，諸如故意沉船、故意縱火等騙賠伎倆，五花八門。愈演愈烈的保險(xiǎn)欺詐違法犯罪活動(dòng)，不僅極大地?fù)p害了保險(xiǎn)合同當(dāng)事人的合

2、法權(quán)益，而且還嚴(yán)重?cái)_亂了保險(xiǎn)市場(chǎng)的正常秩序。一方面他對(duì)保險(xiǎn)公司的財(cái)產(chǎn)構(gòu)成了直接的侵犯；另一方面，保險(xiǎn)公司面對(duì)保險(xiǎn)欺詐不得不提高保費(fèi)，這樣，誠(chéng)實(shí)的投保人成為最大的損失者，這將會(huì)嚴(yán)重阻礙保險(xiǎn)業(yè)的發(fā)展。在人壽保險(xiǎn)業(yè)務(wù)中，一份保單就是一個(gè)事務(wù)。保險(xiǎn)公司在接受保險(xiǎn)前，往往需要記錄投保人詳盡的信息，有時(shí)還要到醫(yī)院做身體檢查。保單上記錄有投保人的年齡、性別、健康狀況、工作單位、工作地址、工資水平、索賠次數(shù)等等。我們主要想通過(guò)數(shù)據(jù)挖掘找出行為異常的客戶記錄。我們主要關(guān)注購(gòu)買人的年齡、工作單位、健康狀況、工資水平的信息和購(gòu)買后的索賠情況，可以認(rèn)為保單號(hào)、單位代號(hào)、單位名稱是一些無(wú)關(guān)信息。這種人壽保險(xiǎn)公司通過(guò)分析

3、客戶信息識(shí)別保險(xiǎn)中的欺詐特征就是離群點(diǎn)檢測(cè)方法研究的問(wèn)題。數(shù)據(jù)挖掘中的多數(shù)方法都會(huì)將異常數(shù)據(jù)視為噪音或異常而丟棄。而離群點(diǎn)檢驗(yàn)在激增的客戶信息和業(yè)務(wù)數(shù)據(jù)中尋找異常數(shù)據(jù)，并進(jìn)行更深層次的分析。這些異常數(shù)據(jù)與數(shù)據(jù)的一般行為或模型不一致，發(fā)生的概率非常小。但在保險(xiǎn)欺詐檢驗(yàn)中，小概率事件可能比正常發(fā)生的事件更有意義。因此，通過(guò)離群點(diǎn)檢驗(yàn)將客戶信息進(jìn)行細(xì)致的分類挖掘，尋找欺詐的一般特征，并建立客戶分析預(yù)測(cè)模型，對(duì)具有欺詐特征的客戶群體實(shí)施相應(yīng)的措施，以提高公司的反欺詐能力。6.1 概述 (1)什么是離群點(diǎn)(Outlier)？Hawkins的定義：離群點(diǎn)是在數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)的

4、偏離并非由隨機(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ā)生。 6.1 概

5、述 (2)離群點(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)、民航等安檢部門推斷哪些人可能有嫌疑 海關(guān)報(bào)關(guān)中的價(jià)格隱瞞營(yíng)銷定制：分析花費(fèi)較小和較高顧客的消費(fèi)行為醫(yī)學(xué)研究中發(fā)現(xiàn)醫(yī)療方案或藥品所產(chǎn)生的異常反應(yīng)計(jì)算機(jī)中的入侵檢測(cè)應(yīng)用異常檢測(cè)到文本編輯器，可有效減少文字輸入的錯(cuò)誤 6.1 概述 (3)離群點(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)題。為什

6、么會(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)解釋，離群點(diǎn)挖掘算法只能為用戶提供可疑的數(shù)據(jù)，以便用戶引起特別的注意并最后確定是否真正的異常。對(duì)于異常數(shù)據(jù)的處理方式也取決于應(yīng)用，并由領(lǐng)域?qū)＜覜Q策。6.1 概述 (4)離群點(diǎn)挖掘中需要處理的幾個(gè)問(wèn)題(1) 全局觀點(diǎn)和局部觀點(diǎn)離群點(diǎn)與眾不同，但具有相對(duì)性。(2) 點(diǎn)的離群程度可以通過(guò)定義對(duì)象的偏離程度來(lái)給對(duì)象打分離群因子(Outlier Factor)或離群值得分(Out

7、lier Score)，即都為離群點(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%.6.1 概述 (5)離群點(diǎn)實(shí)例一個(gè)人的年齡為-999就可能是由于程序處理缺省數(shù)據(jù)設(shè)置默認(rèn)值所造成的 ；一個(gè)公司的高層管理人員的工資明顯高于普通員工的工資可能成為離群點(diǎn)但卻是合理的數(shù)據(jù)(如平安保險(xiǎn)公司2007年 5位高管稅后收入超過(guò)了1000萬(wàn)元)； 一部住宅電話的話費(fèi)由每月200元以內(nèi)增加到數(shù)千元可能就因?yàn)楸槐I打或其它特殊原因所致； 一張信用卡出現(xiàn)明顯的高額消費(fèi)也許是因?yàn)槭潜I用的卡。6.1 概述 (6)

8、離群點(diǎn)與眾不同但具有相對(duì)性： 高與矮，瘋子與常人。類似術(shù)語(yǔ)： Outlier mining，Exception mining:異常挖掘、離群挖掘、例外挖掘和稀有事件挖掘 。6.1 概述 (7)(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ì)象是否離群？6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (1)(2)全局觀點(diǎn)和局

9、部觀點(diǎn)一個(gè)對(duì)象可能相對(duì)于所有對(duì)象看上去離群，但它相對(duì)于它的局部近鄰不是離群的例如：身高1.85m對(duì)于一般人群是不常見(jiàn)的，但對(duì)于職業(yè)籃球運(yùn)動(dòng)員不算什么6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (2)到k-最近鄰的距離的計(jì)算定義6-1 對(duì)于正整數(shù)k，對(duì)象p的k最近鄰距離k_distance(p)定義為: (1)除p外，至少有k個(gè)對(duì)象o滿足 (2)除p外，至多k-1個(gè)對(duì)象o滿足利用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ù)

10、少于k的簇中所有的對(duì)象可能都成了離群點(diǎn)。6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (1)定義6-2 (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ì)密度為離群因子：6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (2)基于相對(duì)密度離群點(diǎn)檢測(cè)算法,該算法由三步組成：第一步：對(duì)于每一對(duì)象x，確定x的k-最近鄰集合N(x,k)和密度density(x,k)第二步：對(duì)于每一對(duì)象x

11、，確定x的相對(duì)密度relative density(x,k)，并賦值給OF1(x,k)第三步：對(duì)OF1(x,k)降序排列，確定離群因子大的若干對(duì)象6.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (3)選擇合適的離群因子閾值一種形式上簡(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.2 基于相對(duì)密度的離群點(diǎn)檢測(cè) (4) 例6-1 給定二維數(shù)據(jù)集，表6-1給出了點(diǎn)的坐標(biāo)，可視化的圖形如圖6-2所示(對(duì)象間的距離采用曼哈頓(Manhattan)距離

12、計(jì)算)。K取2，3，5時(shí)，以表格方式給出所有點(diǎn)的局部鄰域密度及相對(duì)密度的離群因子。表6-1 例6-1二維數(shù)據(jù)集P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18P19P20P21P22X1222345.55.566666.56.57772.53345Y7876776.5787.57676.587621.5254K取2，3，5時(shí)，所有點(diǎn)的局部鄰域密度、相對(duì)密度如表6-3所示表6-3 不同k值的計(jì)算結(jié)果.點(diǎn)的坐標(biāo)k=2k=3k=5標(biāo)號(hào)xy局部鄰域密度相對(duì)密度局部鄰域密度相對(duì)密度局部鄰域密度相對(duì)密度P1170.571.380.571.210.501.20P22

13、80.571.380.571.210.501.20P3271.000.681.000.580.830.64P4260.571.380.571.210.461.23P5371.000.900.631.050.630.92P6470.801.880.571.890.571.41P75.56.51.141.331.141.190.921.14P85.572.000.791.331.210.861.16P9681.201.391.201.150.91 1.10P1067.52.000.801.331.220.861.17P11672.001.002.000.781.230.81P12661.001.3

14、11.001.310.821.22P136.572.000.702.000.701.430.72P146.56.51.091.261.091.261.090.94P15781.001.160.81.760.641.64P16771.111.281.111.241.110.91P17761.001.071.001.070.671.55P182.521.331.250.331.290.331.03P1931.51.331.250.38 1.000.281.43P20322.000.670.440.820.321.25P21450.501.180.381.900.381.64P22540.382.3

15、50.382.240.292.676.3 基于聚類的離群點(diǎn)檢測(cè)方法 （1）6.3.1 基于對(duì)象的離群因子的方法6.3.2 基于簇的離群因子的方法6.3.3 基于聚類的動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)方法6.3 基于聚類的離群點(diǎn)檢測(cè)方法 (2)基于聚類的方法有兩個(gè)共同特點(diǎn)：(1)先采用特殊的聚類算法處理輸入數(shù)據(jù)而得到聚類，再在聚類的基礎(chǔ)上來(lái)檢測(cè)離群點(diǎn)。(2)只需要掃描數(shù)據(jù)集若干次，效率較高，適用于大規(guī)模數(shù)據(jù)集。6.3 基于聚類的離群點(diǎn)檢測(cè)方法 (3)靜態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)第一階段對(duì)數(shù)據(jù)進(jìn)行聚類第二階段計(jì)算對(duì)象或簇的離群因子，將離群因子大的對(duì)象或簇中對(duì)象判定為離群點(diǎn)。動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)第一步，利用靜態(tài)數(shù)據(jù)的離

16、群檢測(cè)方法建立離群檢測(cè)模型第二步，利用對(duì)象與已有模型間的相似程度來(lái)檢測(cè)離群點(diǎn)關(guān)鍵問(wèn)題：距離的定義、離群程度的度量6.3.1 基于對(duì)象離群因子的方法 (1)首先聚類所有對(duì)象 ，然后評(píng)估對(duì)象屬于簇的程度如果一個(gè)對(duì)象不強(qiáng)屬于任何簇，則稱該對(duì)象為基于聚類的離群點(diǎn)。可以用對(duì)象到它的簇中心的距離來(lái)度量對(duì)象屬于簇的程度。 6.3.1 基于對(duì)象離群因子的方法 (2)定義6-3 給定簇C，C 的摘要信息CSI(Cluster Summary Information)定義為： 其中n為簇C 的大小，Summary由分類屬性中不同取值的頻度信息和數(shù)值屬性的質(zhì)心兩部分構(gòu)成，即：定義6-4 假設(shè)據(jù)集D被聚類算法劃分為k

17、個(gè)簇 對(duì)象p的離群因子(Outlier Factor)OF2(p)定義為p與所有簇間距離的加權(quán)平均值： OF2(p)度量了對(duì)象p偏離整個(gè)數(shù)據(jù)集的程度，其值越大，說(shuō)明p偏離整體越遠(yuǎn)。 基于對(duì)象的離群因子檢測(cè)方法描述如下：第一步，對(duì)數(shù)據(jù)集D進(jìn)行采用一趟聚類算法進(jìn)行聚類，得到聚類結(jié)果第二步，計(jì)算數(shù)據(jù)集D中所有對(duì)象p的離群因子OF2(p)，對(duì)OF2(p)降序排列，確定離群因子大的若干對(duì)象。 6.3.1 基于對(duì)象離群因子的方法 (3)例6-2 基于聚類的離群點(diǎn)檢測(cè)示例1對(duì)于圖所示的二維數(shù)據(jù)集，比較點(diǎn)P1(6,8)，P2(5,2)，哪個(gè)更有可能成為離群點(diǎn)。假設(shè)數(shù)據(jù)集經(jīng)過(guò)聚類后得到聚類結(jié)果為C=C1、C2、

18、C3，圖中紅色圓圈標(biāo)注，三個(gè)簇的質(zhì)心分別為：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)，試計(jì)算所有對(duì)象的離群因子。解答：根據(jù)定義6-4，公式對(duì)于P1點(diǎn)有： 對(duì)于P2有：可見(jiàn)，點(diǎn)P1較P2更可能成為離群點(diǎn)。同理可求得所有對(duì)象的離群因子，結(jié)果如表所示。xyOF2122.2132.3112.9212.6221.7231.9685.9242.5322.2574.8523.46.3.2 基于簇的離群因子的方法 （1）(1)在某種度量下，相似對(duì)象或相同類型的對(duì)象會(huì)聚集在一起，或者說(shuō)正常數(shù)據(jù)與離群數(shù)據(jù)會(huì)聚集在不同的簇中；(2)正常數(shù)據(jù)占絕大部分，且離群數(shù)據(jù)與正常數(shù)據(jù)表現(xiàn)出明顯不同，或

19、者說(shuō)離群數(shù)據(jù)會(huì)偏離正常數(shù)據(jù)(也就是大部分?jǐn)?shù)據(jù))。 定義6-5 給定簇C，C的摘要信息CSI (Cluster Summary Information)定義為： 其中kind為簇的類別(取值normal或outlier)， 為簇C的大小, Cluster為簇C中對(duì)象標(biāo)識(shí)的集合，Summary 由分類屬性中不同取值的頻度信息和數(shù)值型屬性的質(zhì)心兩部分構(gòu)成， 即：6.3.2 基于簇的離群因子的方法 （2）定義6-6 假設(shè)據(jù)集D被聚類算法劃分為k個(gè)簇 ， 簇 離群因子(Outlier Factor) 定義為簇 與其它所有簇間距離的加權(quán)平均值：如果一個(gè)簇離幾個(gè)大簇的距離都比較遠(yuǎn)，則表明該簇偏離整體較遠(yuǎn)，其

20、離群因子也較大。 度量了簇 偏離整個(gè)數(shù)據(jù)集的程度，其值越大，說(shuō)明 偏離整體越遠(yuǎn)。 6.3.2 基于簇的離群因子的方法 （3）該方法由兩個(gè)階段構(gòu)成：第一階段是利用一趟聚類算法對(duì)數(shù)據(jù)集進(jìn)行聚類；第二階段是計(jì)算每個(gè)簇的離群因子，并按離群因子對(duì)簇進(jìn)行排序，最終確定離群簇，也即確定離群對(duì)象。 6.3.2 基于簇的離群因子的方法 （4）具體算法描述如下：第一階段，聚類：對(duì)數(shù)據(jù)集D進(jìn)行聚類，得到聚類結(jié)果 ；第二階段，確定離群簇：計(jì)算每個(gè)簇 的離群因子 ，按 遞減的順序重新排列 ， 求滿足： 的最小 ，將簇 標(biāo)識(shí)為outlier類(即其中每個(gè)對(duì)象均看成離群)，而將 標(biāo)識(shí)為normal類(即其中每個(gè)對(duì)象均看成正

21、常)。6.3.2 基于簇的離群因子的方法 （5）例6-3 基于聚類的離群點(diǎn)檢測(cè)示例2對(duì)例6-3中的數(shù)據(jù)集，聚類后得到三個(gè)簇C=C1、C2、C3，簇心分別為：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。簇之間的距離分別為：進(jìn)一步計(jì)算三個(gè)簇的離群因子，具體如下：基本思想如下：在對(duì)訓(xùn)練集聚類的基礎(chǔ)上，按照簇的離群因子排序簇，并按一定比例將簇標(biāo)識(shí)為”normal”或”outlier”，以標(biāo)識(shí)的簇作為分類模型，按照對(duì)象與分類模型中最接近簇的距離判斷它是否離群點(diǎn)。 6.3.3 基于聚類的動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)方法 （1）6.3.3 基于聚類的動(dòng)態(tài)數(shù)據(jù)的離群點(diǎn)檢測(cè)方法 （2）(1) 模型建立第一步，聚類：對(duì)訓(xùn)練集 進(jìn)行聚類，得到聚類結(jié)果 ；第二步，給簇作標(biāo)記：計(jì)算每個(gè)簇 的離群因子 ，按 遞減的順序重新排列 ，求滿足： 的最小b，將簇 識(shí)為離群簇，而將 標(biāo)識(shí)為正常簇。第三步，確定模型：以每個(gè)簇的摘要信息，聚類半徑閾值r作為模型(2) 模型評(píng)估利用改進(jìn)的最近鄰分類方法INN(Improved Nearest Neighbor) 評(píng)估測(cè)試集中的每個(gè)