聚類分析(孤立點(diǎn)分析).ppt

《聚類分析(孤立點(diǎn)分析).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《聚類分析(孤立點(diǎn)分析).ppt（29頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 第7章 聚類分析 什么是聚類 Clustering 分析 聚類分析中的數(shù)據(jù)類型主要聚類方法分類劃分方法 PartitioningMethods 層次方法 HierarchicalMethods 基于密度的方法 Density BasedMethods 基于網(wǎng)格的方法 Grid BasedMethods 基于模型的聚類方法 Model BasedClusteringMethods 孤立點(diǎn)分析 OutlierAnalysis 小結(jié) 2 孤立點(diǎn)分析 什么是孤立點(diǎn) 對(duì)象的集合 它們與數(shù)據(jù)的其它部分不一致孤立點(diǎn)可能是度量或執(zhí)行錯(cuò)誤所導(dǎo)致的孤立點(diǎn)也可能是固有的數(shù)據(jù)變異性的結(jié)果問題給定一個(gè)n個(gè)數(shù)據(jù)點(diǎn)或?qū)ο蟮募?及預(yù)期的孤立點(diǎn)的數(shù)目k 發(fā)現(xiàn)與剩余的數(shù)據(jù)相比是相異的 例外的 或不一致的前k個(gè)對(duì)象兩個(gè)子問題 定義在給定的數(shù)據(jù)集合中什么樣的數(shù)據(jù)可以被認(rèn)為是不一致的找到一個(gè)有效的方法來挖掘這樣的孤立點(diǎn) 3 孤立點(diǎn)分析 應(yīng)用 信用卡欺詐檢測(cè)電信欺詐檢測(cè)顧客分割 確定極低或極高收入的客戶的消費(fèi)行為醫(yī)療分析 發(fā)現(xiàn)對(duì)多種治療方式的不尋常的反應(yīng)孤立點(diǎn)的定義是非平凡的如果采用一個(gè)回歸模型 余量的分析可以給出對(duì)數(shù)據(jù) 極端 的很好的估計(jì)當(dāng)在時(shí)間序列數(shù)據(jù)中尋找孤立點(diǎn)時(shí) 它們可能隱藏在趨勢(shì)的 周期性的 或者其他循環(huán)變化中 這項(xiàng)任務(wù)非常棘手當(dāng)分析多維數(shù)據(jù)時(shí) 不是任何特別的一個(gè) 而是維值的組合可能是極端的 對(duì)于非數(shù)值型的數(shù)據(jù) 如分類數(shù)據(jù) 孤立點(diǎn)的定義要求特殊的考慮 4 孤立點(diǎn)分析 采用數(shù)據(jù)可視化方法來進(jìn)行孤立點(diǎn)探測(cè)如何 不適用于包含周期性曲線的數(shù)據(jù)對(duì)于探測(cè)有很多分類屬性的數(shù)據(jù) 或高維數(shù)據(jù)中的孤立點(diǎn)效率很低方法統(tǒng)計(jì)學(xué)方法基于距離的方法基于密度的方法 5 基于統(tǒng)計(jì)學(xué)的孤立點(diǎn)檢測(cè) 對(duì)給定的數(shù)據(jù)集合假設(shè)了一個(gè)分布或概率模型 例如 正態(tài)分布 然后根據(jù)模型采用不一致性檢驗(yàn) discordancytest 來確定孤立點(diǎn)檢驗(yàn)要求的參數(shù)數(shù)據(jù)集參數(shù) 例如 假設(shè)的數(shù)據(jù)分布分布參數(shù) 例如平均值和方差和預(yù)期的孤立點(diǎn)的數(shù)目統(tǒng)計(jì)學(xué)的不一致性檢驗(yàn)需要檢查的兩個(gè)假設(shè)工作假設(shè) workinghypothesis 替代假設(shè) alternativehypothesis 6 基于統(tǒng)計(jì)學(xué)的孤立點(diǎn)檢測(cè) 工作假設(shè)H是一個(gè)命題 n個(gè)對(duì)象的整個(gè)數(shù)據(jù)集合來自一個(gè)初始的分布模型F 即H Oi F i 1 2 n不一致性檢驗(yàn)驗(yàn)證一個(gè)對(duì)象Oi關(guān)于分布F是否顯著地大 或者小 依據(jù)關(guān)于數(shù)據(jù)的可用知識(shí) 已提出不同的統(tǒng)計(jì)量用于不一致性檢驗(yàn)假設(shè)某個(gè)統(tǒng)計(jì)量被選擇用于不一致性檢驗(yàn) 對(duì)象Oi的該統(tǒng)計(jì)量的值為Vi 則構(gòu)建分布T估算顯著性概率SP Vi Prob T Vi 如果某個(gè)SP Vi 是足夠的小 那么Oi是不一致的 工作假設(shè)被拒絕 替代假設(shè)被采用 它聲明Oi來自于另一個(gè)分布模型G 7 檢測(cè)一元正態(tài)分布中的離群點(diǎn) 8 檢測(cè)一元正態(tài)分布中的離群點(diǎn) 若考察的屬性服從正態(tài)分布 可以用屬性的出現(xiàn)概率確定是否離群點(diǎn) 出現(xiàn)概率低于一個(gè)閾值 就可以認(rèn)為該屬性是一個(gè)離群點(diǎn) 確定的方法由下面定義 9 檢測(cè)一元正態(tài)分布中的離群點(diǎn) 出現(xiàn)概率在2 5 左邊或者右邊的屬性都可以作為離群點(diǎn) 因?yàn)楦怕市∮诮o定的閾 10 檢測(cè)二元正態(tài)分布中的離群點(diǎn) 11 用mahalanobis距離來衡量是否離群點(diǎn) 距離超過一個(gè)閾值就是離群點(diǎn) 12 檢測(cè)二元正態(tài)分布中的離群點(diǎn) 13 檢測(cè)二元正態(tài)分布中的離群點(diǎn) 若A B的距離超過一個(gè)閾值 它們就是離群點(diǎn) A的Mahalanobis距離比B大 證明A離中心點(diǎn)更遠(yuǎn) 14 基于統(tǒng)計(jì)學(xué)的孤立點(diǎn)檢測(cè) 結(jié)果非常依賴于模型F的選擇Oi可能在一個(gè)模型下是孤立點(diǎn) 在另一個(gè)模型下是非常有效的值替代分布在決定檢驗(yàn)的能力上是非常重要的不同的替代分布固有的替代分布 inherentalternativedistribution 所有對(duì)象來自分布F的工作假設(shè)被拒絕 而所有對(duì)象來自另一個(gè)分布G的替代假設(shè)被接受混合替代分布 mixturealternativedistribution 不一致的值不是F分布中的孤立點(diǎn) 而是來自其他分布的污染物滑動(dòng)替代分布 slippagealternativedistribution 所有的對(duì)象 除了少量外 根據(jù)給定的參數(shù) 獨(dú)立地來自初始的模型F 而剩余的對(duì)象是來自修改過的F的獨(dú)立的觀察 15 基于統(tǒng)計(jì)學(xué)的孤立點(diǎn)檢測(cè) 檢測(cè)孤立點(diǎn)有兩類基本的過程批 block 過程 或者所有被懷疑的對(duì)象都被作為孤立點(diǎn)對(duì)待 或者都被作為一致數(shù)據(jù)而接受連續(xù)的過程 該過程的一個(gè)例子是內(nèi)部出局 inside out 過程主要思想首先檢驗(yàn)最不可能是孤立點(diǎn)的對(duì)象 如果它是孤立點(diǎn) 那么所有更極端的值都被認(rèn)為是孤立點(diǎn) 否則 檢驗(yàn)下一個(gè)極端的對(duì)象 依次類推該過程往往比批過程更為有效 16 基于統(tǒng)計(jì)學(xué)的孤立點(diǎn)檢測(cè) 缺點(diǎn)絕大多數(shù)檢驗(yàn)是針對(duì)單個(gè)屬性的 而許多數(shù)據(jù)挖掘問題要求在多維空間中發(fā)現(xiàn)孤立點(diǎn)統(tǒng)計(jì)學(xué)方法要求關(guān)于數(shù)據(jù)集合參數(shù)的知識(shí) 如 數(shù)據(jù)分布 但是在許多情況下 數(shù)據(jù)分布可能是未知的當(dāng)沒有特定的檢驗(yàn)時(shí) 統(tǒng)計(jì)學(xué)方法不能確保所有的孤立點(diǎn)被發(fā)現(xiàn) 或者觀察到的分布不能恰當(dāng)?shù)乇蝗魏螛?biāo)準(zhǔn)的分布來模擬 17 基于距離的孤立點(diǎn)檢測(cè) 為了解決統(tǒng)計(jì)學(xué)方法帶來的一些限制 引入了基于距離的孤立點(diǎn)的概念基于距離的孤立點(diǎn) DB p d 孤立點(diǎn)是數(shù)據(jù)集T中的一個(gè)對(duì)象o 使得T中的對(duì)象至少有p部分與o的距離大于d將基于距離的孤立點(diǎn)看作是那些沒有 足夠多 鄰居的對(duì)象 這里的鄰居是基于距給定對(duì)象的距離來定義的對(duì)許多不一致性檢驗(yàn)來說 如果一個(gè)對(duì)象o根據(jù)給定的檢驗(yàn)是一個(gè)孤立點(diǎn) 那么對(duì)恰當(dāng)定義的p和d o也是一個(gè)DB p d 孤立點(diǎn)例如 如果離平均值偏差3或更大的對(duì)象被認(rèn)為是孤立點(diǎn) 假設(shè)一個(gè)正態(tài)分布 那么這個(gè)定義能夠被一個(gè)DB 0 9988 0 13 孤立點(diǎn)所概括 18 基于距離的異常檢測(cè) 指定參數(shù)pct和dmin 如果數(shù)據(jù)集合D中的對(duì)象至少有pct部分與對(duì)象o的距離大于dmin 則稱對(duì)象o是以pct和dmin為參數(shù)的基于距離的異常 記為DB pct dmin 19 算法 尋找基于距離的異常檢測(cè) D dmin M 輸入 數(shù)據(jù)對(duì)象集合D 鄰域半徑dmin 一個(gè)異常的dmin鄰域內(nèi)最多對(duì)象數(shù)目M輸出 D中的異常對(duì)象步驟 1 forD中每個(gè)數(shù)據(jù)對(duì)象ti do 1 1 counti 0 1 2 forD中除ti的每個(gè)對(duì)象tj 1 2 1 ifdist ti tj dmin thencounti 1 dist 是距離函數(shù) 1 2 2 ifcounti M then標(biāo)記ti不是一個(gè)異常 處理下一個(gè)ti 1 3 ifcounti M then標(biāo)記ti是一個(gè)異常 處理下一個(gè)ti 基于距離的異常檢測(cè) 20 基于偏離的孤立點(diǎn)檢測(cè) 通過檢查一組對(duì)象的主要特征來確定孤立點(diǎn)與給出的描述偏離的對(duì)象被認(rèn)為是孤立點(diǎn)序列異常技術(shù) sequentialexceptiontechnique 模仿人類從一系列推測(cè)類似的對(duì)象中識(shí)別異常對(duì)象的方式術(shù)語異常集 exceptionset 它是偏離或孤立點(diǎn)的集合 被定義為某類對(duì)象的最小子集 這些對(duì)象的去除會(huì)導(dǎo)致剩余集合的相異度的最大減少相異度函數(shù) dissimilarityfunction 是滿足如下條件的任意函數(shù) 當(dāng)給定一組對(duì)象時(shí) 如果對(duì)象間相似 返值就較小 對(duì)象間的相異度越大 函數(shù)返回的值就越大 21 基于密度的異常檢測(cè) 相關(guān)概念基于密度的異常檢測(cè)算法 22 相關(guān)概念 1 1 k距離對(duì)象p的k距離k distance p 是p到它的k最近鄰的最大距離 它定義為p與對(duì)象o D之間的距離d p o 滿足 1 D中至少存在k個(gè)對(duì)象到p的距離小于或等于p到o的距離 2 D中最多有k 1個(gè)對(duì)象到p的距離比p到o的距離小 k與聚類算法DBSCAN中的MinPts相同 用于定義對(duì)象p的局部鄰域 2 k距離鄰域?qū)ο髉的k距離鄰域Nk distance p p 包含所有與p的距離不超過k distance p 的對(duì)象 即 Nk distance p p q D p d p q k distance p 23 3 可達(dá)距離給定自然數(shù)k 對(duì)象p關(guān)于對(duì)象o的可達(dá)距離reach distk p o 為 reach distk p o max k distance o d p o reach distk p o 的含義是 如果對(duì)象p遠(yuǎn)離o 則兩者間的可達(dá)距離就是它們間的實(shí)際距離 但是 如果p在o的k距離鄰域內(nèi) 則實(shí)際距離用o的k距離取代 k距離越大 在相同鄰域中對(duì)象的可達(dá)距離越相似 圖9 5所示的是 4時(shí)對(duì)象p1和p2關(guān)于對(duì)象o的可達(dá)距離 圖9 7k 4時(shí)對(duì)象p1和p2的可達(dá)距離 相關(guān)概念 2 24 4 局部可達(dá)密度用MinPts表示p的鄰域中最小的對(duì)象個(gè)數(shù) 那么對(duì)象p的局部可達(dá)密度為對(duì)象p與它的MinPts 鄰域的平均可達(dá)距離的倒數(shù) 5 局部異常因子LOF對(duì)象p的局部異常因子定義為 LOF是對(duì)象p和它的最近鄰的局部可達(dá)密度的比率的平均值 p的局部可達(dá)密度越小 p的MinPts最近鄰的局部可達(dá)密度越大 LOFMinPts p 越高 LOF表征了p的異常程度 如果p不是局部異常 則LOFMinPts p 接近于1 p是局部異常的程度越大 LOFMinPts p 越高 相關(guān)概念 3 25 基于密度的異常檢測(cè)算法 1 LOF表征了對(duì)象p的異常程度 因此 可以通過計(jì)算LOF p 來判斷對(duì)象p是否是局部異常 基于密度的異常檢測(cè)算法的核心是對(duì)于指定的近鄰個(gè)數(shù)k 基于對(duì)象的最近鄰計(jì)算對(duì)象的LOF 算法 基于密度的異常檢測(cè)算法 D MinPts k 輸入 數(shù)據(jù)對(duì)象集合D 近鄰個(gè)數(shù)MinPts 異常對(duì)象數(shù)目k輸出 k個(gè)異常步驟 1 forD中每個(gè)數(shù)據(jù)對(duì)象p 1 1 確定p的MinPts距離鄰域NMinpts distance p p 26 基于密度的異常檢測(cè)算法 2 1 2 使用p的最近鄰 即NMinPts distance p p 中的對(duì)象 計(jì)算p的局部可達(dá)密度lrdMinPts p 1 3 計(jì)算NMinPts distance p p 中每個(gè)對(duì)象o的局部可達(dá)密度lrdMinPts o 1 4 計(jì)算p的局部異常因子LOFMinPts p 2 輸出D中LOF值最大的k個(gè)對(duì)象基于密度的異常檢測(cè)算法的時(shí)間復(fù)雜度為O n2 其中n是D中對(duì)象個(gè)數(shù) 算法給出了對(duì)象異常程度的定量度量 并且在數(shù)據(jù)具有不同密度的區(qū)域也能夠很好地識(shí)別局部異常 27 基于偏離的孤立點(diǎn)檢測(cè) 例 給定n個(gè)對(duì)象的子集合 x1 xn 一個(gè)可能的相異度函數(shù)是集合中對(duì)象的方差基數(shù)函數(shù) cardinalityfunction 一般是給定的集合中對(duì)象的數(shù)目平滑因子 smoothingfactor 一個(gè)為序列中的每個(gè)子集計(jì)算的函數(shù) 它估算從原始的數(shù)據(jù)集合中移走子集合可以帶來的相異度的降低程度 平滑因子值最大的子集是異常集一般的尋找異常集的任務(wù)可以是NP完全的 即 難處理的 28 基于偏離的孤立點(diǎn)檢測(cè) 一個(gè)順序的方法在計(jì)算上是可行的 能夠用一個(gè)線性的算法實(shí)現(xiàn)不考慮估算當(dāng)前子集關(guān)于其補(bǔ)集的相異度 該算法從集合中選擇了一個(gè)子集合的序列來分析對(duì)每個(gè)子集合 它確定其與序列中前一個(gè)子集合的相異度差異為了減輕輸入順序?qū)Y(jié)果的任何可能的影響 以上的處理過程可以被重復(fù)若干次 每一次采用子集合的一個(gè)不同的隨機(jī)順序在所有的迭代中有最大平滑因子值的子集合成為異常集 29 基于偏離的孤立點(diǎn)檢測(cè) OLAP數(shù)據(jù)方技術(shù)使用數(shù)據(jù)方識(shí)別大型多維數(shù)據(jù)中的異常區(qū)域