第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聚類的評(píng)估聚類的評(píng)估l基于模型的聚類方法基于模型的聚類方法l小結(jié)小結(jié)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘2聚類的普遍應(yīng)用聚類的普遍應(yīng)用2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘3聚類的應(yīng)用舉例聚類的應(yīng)用舉例2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘4什么是好的聚類？什么是好的聚類？2022-4-1420

2、22-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘5數(shù)據(jù)挖掘?qū)垲惖囊髷?shù)據(jù)挖掘?qū)垲惖囊髄可伸縮性可伸縮性l處理不同類型屬性的能力處理不同類型屬性的能力l發(fā)現(xiàn)任意形狀的聚類發(fā)現(xiàn)任意形狀的聚類l對(duì)于決定輸入?yún)?shù)的領(lǐng)域知識(shí)需求最小對(duì)于決定輸入?yún)?shù)的領(lǐng)域知識(shí)需求最小l處理帶噪聲數(shù)據(jù)的能力處理帶噪聲數(shù)據(jù)的能力l增量聚類和對(duì)輸入記錄的次序不敏感增量聚類和對(duì)輸入記錄的次序不敏感l(wèi)高維性高維性l基于約束的聚類基于約束的聚類l可解釋性和可用性可解釋性和可用性聚類方法的比較準(zhǔn)則聚類方法的比較準(zhǔn)則l劃分準(zhǔn)則劃分準(zhǔn)則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平方誤差準(zhǔn)則函平方誤差準(zhǔn)則函數(shù)數(shù)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘102022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘11K-平均方法的特點(diǎn)平均方法的特點(diǎn)局局2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘12K-平均方法的變種平均方法的變種lK-K-平均法在以下策略上的不同，有一些變種

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

5、-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘14K-中心點(diǎn)聚類方法中心點(diǎn)聚類方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘15PAM（圍繞中心點(diǎn)的劃分）（圍繞中心點(diǎn)的劃分）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最終每一個(gè)結(jié)點(diǎn)形成只包含它本身的簇最終每一個(gè)結(jié)點(diǎn)形成只包含它本身的簇2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘20更多關(guān)于層次聚類方法更多關(guān)于層次聚類方法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:一個(gè)基于高度連接區(qū)域一個(gè)基于高度連接區(qū)域的密度聚類算法的密度聚類算法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘30DBSCAN:算法算法l任意選擇一個(gè)點(diǎn)任意選擇一個(gè)點(diǎn)P Pl找出從對(duì)象找出從對(duì)象P P關(guān)于關(guān)于EpsEps和和MinPtsMinPts密度可達(dá)的密度可達(dá)的所有點(diǎn)所有點(diǎn)l如果是一個(gè)中心點(diǎn)，則一個(gè)聚類就形成

8、了如果是一個(gè)中心點(diǎn)，則一個(gè)聚類就形成了l如果如果P P是一個(gè)邊界點(diǎn)，沒(méi)有從是一個(gè)邊界點(diǎn)，沒(méi)有從P P密度可達(dá)的密度可達(dá)的對(duì)象，則訪問(wèn)數(shù)據(jù)庫(kù)中其他的點(diǎn)對(duì)象，則訪問(wèn)數(shù)據(jù)庫(kù)中其他的點(diǎn)l繼續(xù)該過(guò)程，直到所有的點(diǎn)被處理繼續(xù)該過(guò)程，直到所有的點(diǎn)被處理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)計(jì)信息網(wǎng)格方法統(tǒng)計(jì)信息網(wǎng)格方法2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘332022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘34聚類的評(píng)估聚類的評(píng)估l估計(jì)聚類趨勢(shì)：僅當(dāng)數(shù)據(jù)中存在非隨機(jī)結(jié)

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

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

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

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

13、均距離的最小平均距離基于概率模型的聚類算法基于概率模型的聚類算法l期望最大化方法（期望最大化方法（EMEM）2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘41期望最大化方法期望最大化方法l期望步：根據(jù)當(dāng)前的模糊聚類或概率期望步：根據(jù)當(dāng)前的模糊聚類或概率簇的參數(shù)，把對(duì)象指派到簇中簇的參數(shù)，把對(duì)象指派到簇中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)絡(luò)方法：神經(jīng)網(wǎng)絡(luò)方法：l將每個(gè)簇描述為一個(gè)標(biāo)本，標(biāo)本作為聚類的原將每個(gè)簇描述為一個(gè)標(biāo)本，標(biāo)本作為聚類的原型型l根據(jù)某些距離度量，新的對(duì)象可以被分配到標(biāo)根據(jù)某些距離度量，新的對(duì)象可以被分配到標(biāo)本于其最相似的簇本于其最相似的簇l競(jìng)爭(zhēng)學(xué)習(xí)競(jìng)爭(zhēng)學(xué)習(xí)l采用若干單元的層次結(jié)構(gòu)（神經(jīng)元）采用若干單元的層次結(jié)構(gòu)（神經(jīng)元）l以一種以一種“ “勝者全取勝者全取” ”的方式對(duì)系統(tǒng)當(dāng)前處理的對(duì)的方式對(duì)系統(tǒng)當(dāng)前處理的對(duì)象進(jìn)行競(jìng)爭(zhēng)象進(jìn)行競(jìng)爭(zhēng)2022-4-142022-4-14數(shù)據(jù)挖掘數(shù)據(jù)挖掘44什么是離群點(diǎn)發(fā)現(xiàn)什么是離群點(diǎn)發(fā)現(xiàn)l什么是離群點(diǎn)？什么是離群點(diǎn)？l和其他數(shù)據(jù)相當(dāng)不同的對(duì)象集和其他

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