第7章數(shù)據(jù)挖掘

1、2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘1第六章第六章 聚聚 類類 分分 析析l什么是聚類分析？什么是聚類分析？l主要聚類方法的分類主要聚類方法的分類l劃分方法劃分方法l層次方法層次方法l基于密度的方法基于密度的方法l基于網(wǎng)格的方法基于網(wǎng)格的方法l聚類的評估聚類的評估l基于模型的聚類方法基于模型的聚類方法l小結小結2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘2聚類的普遍應用聚類的普遍應用2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘3聚類的應用舉例聚類的應用舉例2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘4什么是好的聚類？什么是好的聚類？2022-4-1420

2、22-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘5數(shù)據(jù)挖掘對聚類的要求數(shù)據(jù)挖掘對聚類的要求l可伸縮性可伸縮性l處理不同類型屬性的能力處理不同類型屬性的能力l發(fā)現(xiàn)任意形狀的聚類發(fā)現(xiàn)任意形狀的聚類l對于決定輸入?yún)?shù)的領域知識需求最小對于決定輸入?yún)?shù)的領域知識需求最小l處理帶噪聲數(shù)據(jù)的能力處理帶噪聲數(shù)據(jù)的能力l增量聚類和對輸入記錄的次序不敏感增量聚類和對輸入記錄的次序不敏感l(wèi)高維性高維性l基于約束的聚類基于約束的聚類l可解釋性和可用性可解釋性和可用性聚類方法的比較準則聚類方法的比較準則l劃分準則劃分準則l簇的分離性簇的分離性l相似性度量相似性度量l聚類空間聚類空間2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘6

3、2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘7主要聚類方法的分類主要聚類方法的分類2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘8劃分算法：基本概念劃分算法：基本概念2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘9K-平均聚類算法平均聚類算法21ikiip CEpm平方誤差準則函平方誤差準則函數(shù)數(shù)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘102022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘11K-平均方法的特點平均方法的特點局局2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘12K-平均方法的變種平均方法的變種lK-K-平均法在以下策略上的不同，有一些變種

4、平均法在以下策略上的不同，有一些變種lK K個平均值的選擇個平均值的選擇l相異度的計算相異度的計算l計算聚類平均值的策略計算聚類平均值的策略l處理分類數(shù)據(jù)：處理分類數(shù)據(jù)：K-K-模方法模方法l用模來代替聚類的平均值用模來代替聚類的平均值l使用新的相異性度量來處理分類對象使用新的相異性度量來處理分類對象l采用相關的定理來修改聚類的模采用相關的定理來修改聚類的模l分類數(shù)據(jù)和數(shù)值數(shù)據(jù)的混合分類數(shù)據(jù)和數(shù)值數(shù)據(jù)的混合: :K-K-原型方法原型方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘13K-中心點聚類方法中心點聚類方法1Ejkjjp Cpo絕對誤差標準絕對誤差標準2022-4-142022

5、-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘14K-中心點聚類方法中心點聚類方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘15PAM（圍繞中心點的劃分）（圍繞中心點的劃分）2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘16CLARA(Clustering large application)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘17層次方法層次方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘18AGNES (Agglomerative Nesting)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘19DIANA( Divisive Analysis)l與與AGNESA

6、GNES算法相反算法相反l最終每一個結點形成只包含它本身的簇最終每一個結點形成只包含它本身的簇2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘20更多關于層次聚類方法更多關于層次聚類方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘21BIRCH2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘22聚類特征向量聚類特征向量2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘232022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘24CHAMELEON2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘25CHAMELEON的總體框架的總體框架2022-4-142022-4-14數(shù)據(jù)

7、挖掘數(shù)據(jù)挖掘26基于密度的聚類方法基于密度的聚類方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘27基于密度的聚類：背景基于密度的聚類：背景2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘282022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘29DBSCAN:一個基于高度連接區(qū)域一個基于高度連接區(qū)域的密度聚類算法的密度聚類算法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘30DBSCAN:算法算法l任意選擇一個點任意選擇一個點P Pl找出從對象找出從對象P P關于關于EpsEps和和MinPtsMinPts密度可達的密度可達的所有點所有點l如果是一個中心點，則一個聚類就形成

8、了如果是一個中心點，則一個聚類就形成了l如果如果P P是一個邊界點，沒有從是一個邊界點，沒有從P P密度可達的密度可達的對象，則訪問數(shù)據(jù)庫中其他的點對象，則訪問數(shù)據(jù)庫中其他的點l繼續(xù)該過程，直到所有的點被處理繼續(xù)該過程，直到所有的點被處理2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘31基于網(wǎng)格的聚類方法基于網(wǎng)格的聚類方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘32STING:統(tǒng)計信息網(wǎng)格方法統(tǒng)計信息網(wǎng)格方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘332022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘34聚類的評估聚類的評估l估計聚類趨勢：僅當數(shù)據(jù)中存在非隨機結

9、構，聚估計聚類趨勢：僅當數(shù)據(jù)中存在非隨機結構，聚類分析是有意義類分析是有意義l確定數(shù)據(jù)集中的簇數(shù)：確定數(shù)據(jù)集中的簇數(shù)：l測定聚類的質量測定聚類的質量2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘35估計聚類趨勢估計聚類趨勢l霍普金斯統(tǒng)計量：霍普金斯統(tǒng)計量：l均勻地從均勻地從D D的空間中抽取的空間中抽取n n個點個點p p1 1,p,p2 2,p,pn n。對于。對于每個點找出在每個點找出在D D中的最近鄰集合中的最近鄰集合x xi il均勻地從均勻地從D D的空間中抽取的空間中抽取n n個點個點q q1 1,q,q2 2,q,qn n。對于。對于每個點找出在每個點找出在D D中的最近鄰

10、集合中的最近鄰集合y yi il計算霍普金斯統(tǒng)計量計算霍普金斯統(tǒng)計量H Hl如果如果D D為均勻分布，則為均勻分布，則H H大約為大約為0.50.52022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘36111niinniiiiyHxy確定簇數(shù)確定簇數(shù)l經(jīng)驗方法：對于經(jīng)驗方法：對于n n個數(shù)據(jù)點集合，設置簇數(shù)個數(shù)據(jù)點集合，設置簇數(shù)大約為大約為l肘方法：給定肘方法：給定k0k0，使用一種類似，使用一種類似k-k-均值的均值的算法對數(shù)據(jù)集聚類，并計算簇內方差和算法對數(shù)據(jù)集聚類，并計算簇內方差和var(k)var(k)，繪制，繪制varvar關于關于k k的曲線，曲線的第一的曲線，曲線的第一個拐點為

11、正確的簇數(shù)個拐點為正確的簇數(shù)l交叉驗證：交叉驗證：2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘372n測定聚類質量測定聚類質量l外在方法：有監(jiān)督的方法：外在方法：有監(jiān)督的方法：l簇的同質性：聚類中的簇越純，聚類越好簇的同質性：聚類中的簇越純，聚類越好l簇的完全性：屬于相同類別的對象分配到相同的簇簇的完全性：屬于相同類別的對象分配到相同的簇l碎布袋：把一個異種對象放入一個純的簇中應該比碎布袋：把一個異種對象放入一個純的簇中應該比放入碎布袋中受更大的懲罰放入碎布袋中受更大的懲罰l小簇保持性：把小類別劃分成小片比將大類別劃分小簇保持性：把小類別劃分成小片比將大類別劃分成小片更有害成小片更有害

12、2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘38l精度：同一簇中的有多少個其他對象與該精度：同一簇中的有多少個其他對象與該對象同屬一個類別對象同屬一個類別l召回率：反映有多少同一類別的對象被分召回率：反映有多少同一類別的對象被分配在相同的簇中配在相同的簇中2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘39內在方法內在方法l輪廓系數(shù)：輪廓系數(shù)：2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘40( )( )( )max ( ), ( )b oa os oa o b oO與與O所屬簇的其他對所屬簇的其他對象之間的平均距離象之間的平均距離O到不屬于到不屬于O的所有簇的所有簇的最小平

13、均距離的最小平均距離基于概率模型的聚類算法基于概率模型的聚類算法l期望最大化方法（期望最大化方法（EMEM）2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘41期望最大化方法期望最大化方法l期望步：根據(jù)當前的模糊聚類或概率期望步：根據(jù)當前的模糊聚類或概率簇的參數(shù)，把對象指派到簇中簇的參數(shù)，把對象指派到簇中l(wèi)最大化步：發(fā)現(xiàn)新的聚類或參數(shù)，最最大化步：發(fā)現(xiàn)新的聚類或參數(shù)，最小化模糊聚類的小化模糊聚類的SSESSE或基于概率模型的或基于概率模型的聚類的期望似然聚類的期望似然2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘422022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘43其他基于模型

14、的方法其他基于模型的方法l神經(jīng)網(wǎng)絡方法：神經(jīng)網(wǎng)絡方法：l將每個簇描述為一個標本，標本作為聚類的原將每個簇描述為一個標本，標本作為聚類的原型型l根據(jù)某些距離度量，新的對象可以被分配到標根據(jù)某些距離度量，新的對象可以被分配到標本于其最相似的簇本于其最相似的簇l競爭學習競爭學習l采用若干單元的層次結構（神經(jīng)元）采用若干單元的層次結構（神經(jīng)元）l以一種以一種“ “勝者全取勝者全取” ”的方式對系統(tǒng)當前處理的對的方式對系統(tǒng)當前處理的對象進行競爭象進行競爭2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘44什么是離群點發(fā)現(xiàn)什么是離群點發(fā)現(xiàn)l什么是離群點？什么是離群點？l和其他數(shù)據(jù)相當不同的對象集和其他

15、數(shù)據(jù)相當不同的對象集l問題問題l找出找出n n個離群點個離群點l應用應用l信用卡的欺詐檢測信用卡的欺詐檢測l電信的欺詐檢測電信的欺詐檢測l顧客分類顧客分類l醫(yī)療分析醫(yī)療分析l全局離群點：顯著偏離數(shù)據(jù)集中的其余對全局離群點：顯著偏離數(shù)據(jù)集中的其余對象，又稱點異常象，又稱點異常l情境離群點：關于對象的特定情境，它顯情境離群點：關于對象的特定情境，它顯著地偏離其他對象，又稱條件離群點著地偏離其他對象，又稱條件離群點l集體離群點：多個對象作為一個整體顯著集體離群點：多個對象作為一個整體顯著地偏離整個數(shù)據(jù)集地偏離整個數(shù)據(jù)集2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘45離群點檢測的方法離群點檢測的方法l統(tǒng)計學方法：假定正常的數(shù)據(jù)對象由一個統(tǒng)計學方法：假定正常的數(shù)據(jù)對象由一個統(tǒng)計模型產生，不遵守該模型的數(shù)據(jù)是離統(tǒng)計模型產生，不遵守該模型的數(shù)據(jù)是離群點群點l基于鄰近性方法：若某