離群點挖掘分析課件

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

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

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

4、偏離并非由隨機因素產生，而是產生于完全不同的機制。Weisberg的定義：離群點是與數據集中其余部分不服從相同統(tǒng)計模型的數據。Samuels的定義：離群點是足夠地不同于數據集中其余部分的數據。Porkess的定義：離群點是遠離數據集中其余部分的數據離群點的特殊意義和實用價值 現有數據挖掘研究大多集中于發(fā)現適用于大部分數據的常規(guī)模式,在許多應用領域中，離群點通常作為噪音而忽略，許多數據挖掘算法試圖降低或消除離群點的影響。而在有些應用領域識別離群點是許多工作的基礎和前提，離群點會帶給我們新的視角。 如在欺詐檢測中，離群點可能意味欺詐行為的發(fā)生，在入侵檢測中離群點可能意味入侵行為的發(fā)生。 6.1 概

5、述 (2)離群點檢測的應用領域電信、保險、銀行中的欺詐檢測與風險分析 發(fā)現電子商務中的犯罪行為災害氣象預報稅務局分析不同團體交所得稅的記錄，發(fā)現異常模型和趨勢 海關、民航等安檢部門推斷哪些人可能有嫌疑 海關報關中的價格隱瞞營銷定制：分析花費較小和較高顧客的消費行為醫(yī)學研究中發(fā)現醫(yī)療方案或藥品所產生的異常反應計算機中的入侵檢測應用異常檢測到文本編輯器，可有效減少文字輸入的錯誤 6.1 概述 (3)離群點挖掘問題由兩個子問題構成： (1)定義在一個數據集中什么數據是不一致或離群的數據；(2)找出所定義的離群點的有效挖掘方法。離群點挖掘問題可以概括為如何度量數據偏離的程度和有效發(fā)現離群點的問題。為什

6、么會出現離群點？測量、輸入錯誤或系統(tǒng)運行錯誤所致數據內在特性所決定客體的異常行為所致由于離群點產生的機制是不確定的，離群點挖掘算法檢測出的“離群點”是否真正對應實際的異常行為，不是由離群點挖掘算法來說明、解釋的，只能由領域專家來解釋，離群點挖掘算法只能為用戶提供可疑的數據，以便用戶引起特別的注意并最后確定是否真正的異常。對于異常數據的處理方式也取決于應用，并由領域專家決策。6.1 概述 (4)離群點挖掘中需要處理的幾個問題(1) 全局觀點和局部觀點離群點與眾不同，但具有相對性。(2) 點的離群程度可以通過定義對象的偏離程度來給對象打分離群因子(Outlier Factor)或離群值得分(Out

7、lier Score)，即都為離群點的情況下，也還有分高和分低的區(qū)別。(3) 離群點的數量及時效性正常點的數量遠遠超過離群點的數量，離群點的數量在大規(guī)模數據集中所占的比例較低，小于5%甚至1%.6.1 概述 (5)離群點實例一個人的年齡為-999就可能是由于程序處理缺省數據設置默認值所造成的 ；一個公司的高層管理人員的工資明顯高于普通員工的工資可能成為離群點但卻是合理的數據(如平安保險公司2007年 5位高管稅后收入超過了1000萬元)； 一部住宅電話的話費由每月200元以內增加到數千元可能就因為被盜打或其它特殊原因所致； 一張信用卡出現明顯的高額消費也許是因為是盜用的卡。6.1 概述 (6)

8、離群點與眾不同但具有相對性： 高與矮，瘋子與常人。類似術語： Outlier mining，Exception mining:異常挖掘、離群挖掘、例外挖掘和稀有事件挖掘 。6.1 概述 (7)(1)用于定義離群點的屬性個數一個對象只有單個屬性一個對象具有多個屬性：可能某個屬性異常，某個屬性正常如：對于男生而言， 身高1.6m，體重55kg，這個很正常； 身高1.6m，體重75kg，這個有點離群； 身高1.8m，體重75kg，基本正常。若對于女生，則三組值可能都不太正常。 所以，定義離群點需要指明如何使用多個屬性的值確定一個對象是否離群？6.2 基于相對密度的離群點檢測 (1)(2)全局觀點和局

9、部觀點一個對象可能相對于所有對象看上去離群，但它相對于它的局部近鄰不是離群的例如：身高1.85m對于一般人群是不常見的，但對于職業(yè)籃球運動員不算什么6.2 基于相對密度的離群點檢測 (2)到k-最近鄰的距離的計算定義6-1 對于正整數k，對象p的k最近鄰距離k_distance(p)定義為: (1)除p外，至少有k個對象o滿足 (2)除p外，至多k-1個對象o滿足利用k最近鄰距離的大小來判定離群使用k-最近鄰的距離度量一個對象是否遠離大部分點，一個對象的離群程度由到它的k-最近鄰的距離給定 。這種方法對k的取值比較敏感。k太小(例如1)，則少量的鄰近離群點可能導致較低的離群程度。k太大，則點數

10、少于k的簇中所有的對象可能都成了離群點。6.2 基于相對密度的離群點檢測 (1)定義6-2 (1) 對象的局部鄰域密度 (2) 相對密度其中， 是不包含x的k-最近鄰的集合， 是該集合的大小，y是一個最近鄰?；谙鄬γ芏鹊碾x群點檢測方法通過比較對象的密度與它的鄰域中的對象平均密度來檢測離群點。 簇內靠近核心點的對象的相對密度接近于1，而處于簇的邊緣或是簇的外面的對象的相對較大。定義相對密度為離群因子：6.2 基于相對密度的離群點檢測 (2)基于相對密度離群點檢測算法,該算法由三步組成：第一步：對于每一對象x，確定x的k-最近鄰集合N(x,k)和密度density(x,k)第二步：對于每一對象x

11、，確定x的相對密度relative density(x,k)，并賦值給OF1(x,k)第三步：對OF1(x,k)降序排列，確定離群因子大的若干對象6.2 基于相對密度的離群點檢測 (3)選擇合適的離群因子閾值一種形式上簡單的方法是指定離群點個數；這里介紹另一種確定OF1(x,k)分割閾值的方法：對OF1(x,k)降序排列，選擇OF1(x,k)急劇下降的點作為離群值、正常值的分隔點，如圖6-3所示，在該圖中，有兩個點判定為離群點。6.2 基于相對密度的離群點檢測 (4) 例6-1 給定二維數據集，表6-1給出了點的坐標，可視化的圖形如圖6-2所示(對象間的距離采用曼哈頓(Manhattan)距離

12、計算)。K取2，3，5時，以表格方式給出所有點的局部鄰域密度及相對密度的離群因子。表6-1 例6-1二維數據集P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18P19P20P21P22X1222345.55.566666.56.57772.53345Y7876776.5787.57676.587621.5254K取2，3，5時，所有點的局部鄰域密度、相對密度如表6-3所示表6-3 不同k值的計算結果.點的坐標k=2k=3k=5標號xy局部鄰域密度相對密度局部鄰域密度相對密度局部鄰域密度相對密度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 基于聚類的離群點檢測方法 （1）6.3.1 基于對象的離群因子的方法6.3.2 基于簇的離群因子的方法6.3.3 基于聚類的動態(tài)數據的離群點檢測方法6.3 基于聚類的離群點檢測方法 (2)基于聚類的方法有兩個共同特點：(1)先采用特殊的聚類算法處理輸入數據而得到聚類，再在聚類的基礎上來檢測離群點。(2)只需要掃描數據集若干次，效率較高，適用于大規(guī)模數據集。6.3 基于聚類的離群點檢測方法 (3)靜態(tài)數據的離群點檢測第一階段對數據進行聚類第二階段計算對象或簇的離群因子，將離群因子大的對象或簇中對象判定為離群點。動態(tài)數據的離群點檢測第一步，利用靜態(tài)數據的離

16、群檢測方法建立離群檢測模型第二步，利用對象與已有模型間的相似程度來檢測離群點關鍵問題：距離的定義、離群程度的度量6.3.1 基于對象離群因子的方法 (1)首先聚類所有對象 ，然后評估對象屬于簇的程度如果一個對象不強屬于任何簇，則稱該對象為基于聚類的離群點?？梢杂脤ο蟮剿拇刂行牡木嚯x來度量對象屬于簇的程度。 6.3.1 基于對象離群因子的方法 (2)定義6-3 給定簇C，C 的摘要信息CSI(Cluster Summary Information)定義為： 其中n為簇C 的大小，Summary由分類屬性中不同取值的頻度信息和數值屬性的質心兩部分構成，即：定義6-4 假設據集D被聚類算法劃分為k

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

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

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

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

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