聚類分析(孤立點分析).ppt

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

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