第6章 數(shù)據(jù)聚類

第六章聚類分析劉輝數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘1/31/2023主要內(nèi)容6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/20232數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘物以類聚人以群分1/31/20233數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘聚類分析示例1/31/20234數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.1聚類的概念聚類的定義聚類分析是將物理的或者抽象的數(shù)據(jù)集合劃分為多個(gè)類別的過程，聚類之后的每個(gè)類別中任意兩個(gè)數(shù)據(jù)樣本之間具有較高的相似度(距離較小)，而不同類別的數(shù)據(jù)樣本之間具有較低的相似度(距離較大)。分類與聚類的區(qū)別與聯(lián)系監(jiān)督學(xué)習(xí)非監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)1/31/20235數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.1聚類的概念樣本序號(hào)描述屬性1描述屬性2…x113…x216.5…x31.54…x44.57.5…x548.5…x65.59…x74.58…聚類分析的數(shù)據(jù)集沒有類別屬性AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1………描述屬性類標(biāo)識(shí)聚類分類1/31/20236數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/20237數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.2相似度計(jì)算連續(xù)型屬性的相似度計(jì)算方法二元離散型屬性的相似度計(jì)算方法多值離散型屬性的相似度計(jì)算方法混合類型屬性的相似度計(jì)算方法1/31/20238數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘數(shù)據(jù)矩陣數(shù)據(jù)樣本通常用矩陣來表示單個(gè)數(shù)據(jù)樣本可用d-維向量表示相似度矩陣對(duì)稱的距離度量會(huì)得到對(duì)稱的相似度矩陣數(shù)據(jù)樣本的表示n個(gè)樣本，d個(gè)屬性1/31/20239數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.2.1連續(xù)型屬性的相似度(距離)計(jì)算歐氏距離（Euclideandistance）曼哈頓距離（Manhattandistance）明考斯基距離（Minkowskidistance）馬哈拉諾比斯距離（Mahalanobisdistance）1/31/202310數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘相關(guān)系數(shù)衡量?jī)蓚€(gè)變量之間的相關(guān)程度，反映了兩個(gè)變量之間的變化方向ρ落在[-1，1]之間ρ>0表示正相關(guān)，兩個(gè)變量具有相同的變化方向（類似的表現(xiàn)模式）ρ=0表示不相關(guān)ρ<0表示負(fù)相關(guān)，兩個(gè)變量具有相反的變化方向（相反的表現(xiàn)模式）1/31/202311數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘cosine距離xyθ優(yōu)點(diǎn)：計(jì)算方便，值在0與1之間1/31/202312數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘KL距離（KL散度）衡量?jī)蓚€(gè)概率分布之間的差異度假設(shè)p,q是兩個(gè)概率分布，則KL距離為：如何將兩個(gè)樣本數(shù)據(jù)轉(zhuǎn)換為兩個(gè)分布呢？p,q兩種將兩個(gè)向量進(jìn)行規(guī)范化，使得每個(gè)分量的值落在(0,1)之間，且分量之和等于1注意：KL距離是非對(duì)稱的！1/31/202313數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.2.2二元屬性的相似度計(jì)算數(shù)據(jù)樣本的二值離散型屬性的取值情況數(shù)據(jù)樣本xi10合計(jì)數(shù)據(jù)樣本xj1a11a10a11+a100a01a00a01+a00合計(jì)a11+a01a10+a00a11+a10+a01+a001/31/202314數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘二元屬性的相似度計(jì)算對(duì)稱的二值離散型屬性不對(duì)稱的二值離散型屬性1/31/202315數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘二元屬性的相異度示例設(shè)Y與P置為1,N的值置為01/31/202316數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.2.3多值離散型屬性的相似度計(jì)算假設(shè)d為數(shù)據(jù)集中的屬性個(gè)數(shù)，u為樣本xi和xj取值相同的屬性個(gè)數(shù)樣本序號(hào)年齡段學(xué)歷收入X1青年研究生高X2青年本科低X3老年本科以下中X4中年研究生高1/31/202317數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.2.4混合型屬性的相似度計(jì)算對(duì)于包含混合類型屬性的數(shù)據(jù)集的相似度通常有兩種計(jì)算方法：將屬性按照類型分組，每個(gè)新的數(shù)據(jù)集中只包含一種類型的屬性；之后對(duì)每個(gè)數(shù)據(jù)集進(jìn)行單獨(dú)的聚類分析把混合類型的屬性放在一起處理，進(jìn)行一次聚類分析，需要將連續(xù)型屬性離散化。1/31/202318數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘主要內(nèi)容6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/202319數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘聚類算法的性能評(píng)價(jià)指標(biāo)數(shù)據(jù)挖掘技術(shù)對(duì)聚類算法的要求：可伸縮性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀聚類的能力減小對(duì)先驗(yàn)知識(shí)和用戶自定義參數(shù)的依賴性處理噪聲數(shù)據(jù)的能力可解釋性和實(shí)用性與分類評(píng)價(jià)指標(biāo)對(duì)比1/31/202320數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.3劃分聚類的基本概念劃分方法:把具有n個(gè)數(shù)據(jù)樣本劃分成具有k個(gè)簇的集合給定k，找出有k個(gè)簇的一個(gè)劃分使得所選擇的劃分準(zhǔn)則最優(yōu)全局最優(yōu):窮舉所有可能的劃分啟發(fā)式方法:k-平均算法和k-中心點(diǎn)算法k-means算法(MacQueen’67):每個(gè)簇用簇的中心表示k-medoids算法或圍繞中心點(diǎn)的劃分PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每一個(gè)簇用接近聚類中心的一個(gè)數(shù)據(jù)樣本表示1/31/202321數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.3.1k-means聚類算法1/31/202322數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.3.1k-means算法步驟1/31/202323數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘k-means算法例題假設(shè)數(shù)據(jù)集D含有9個(gè)數(shù)據(jù)對(duì)象（用2維空間的點(diǎn)表示）：A1(3,1),A2(3,9),A3(8,6),B1(2,5),B2(2,4),B3(3,6),C1(2,6),C2(2,6),C3(2,2)采用k-均值方法進(jìn)行聚類，距離函數(shù)采用歐幾里德距離，取k=3，假設(shè)三個(gè)簇的初始分別為A1,B1,和C1，求第一次循環(huán)結(jié)束時(shí)的三個(gè)簇的質(zhì)心，要求寫出計(jì)算過程。1/31/202324數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘K-means算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)

復(fù)雜度:O(tkn),其中n是對(duì)象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù).通常k,t<<n.通常以局部最優(yōu)結(jié)束.使用遺傳算法或模擬退火可以達(dá)到全球最優(yōu)缺點(diǎn)只有在簇的平均值被定義的情況下才能使用，那當(dāng)涉及有分類屬性的數(shù)據(jù)時(shí)該怎么辦?需要事先給出k，即簇的數(shù)目，這往往是最難的不能處理噪聲數(shù)據(jù)和孤立點(diǎn)不適合發(fā)現(xiàn)非凸面形狀的簇1/31/202325數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.3.2PAM算法PAM(PartitioningAroundMedoids，圍繞中心點(diǎn)的劃分，1987)，其特點(diǎn)是：選擇代表性樣本表示類，稱之為中心點(diǎn)(Medoids)首先隨機(jī)選擇一個(gè)中心點(diǎn)集，如果一個(gè)非中心點(diǎn)改善了結(jié)果聚類的整體距離，則用一個(gè)非中心點(diǎn)代替中心點(diǎn)，不斷重復(fù)此過程至判別函數(shù)不再變化為止。對(duì)小數(shù)據(jù)集很有效，但對(duì)大數(shù)據(jù)集計(jì)算代價(jià)相當(dāng)高1/31/202326數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘PAM算法示例jihttihjhitjtihj總的交換花費(fèi)：1/31/202327數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘PAM算法步驟使用實(shí)際樣本點(diǎn)表示簇任意選擇k個(gè)代表樣本對(duì)每一對(duì)沒有選擇的樣本h和選擇的樣本j計(jì)算完全交換花費(fèi)TCih對(duì)每一對(duì)i和h如果TCih<0,則i被h所替代接著把每個(gè)沒選擇的樣本賦給最相似的代表對(duì)象重復(fù)步驟2和3直到不發(fā)生變化1/31/202328數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘主要內(nèi)容6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/202329數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.4層次聚類使用距離矩陣作為聚類的標(biāo)準(zhǔn).這種方法不需要簇的數(shù)目k作為輸入,但需要一個(gè)中止條件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)1/31/202330數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.4.1AGNES算法AGNES(AgglomerativeNesting)使用單鏈接方法和相異矩陣合并最小相異的結(jié)點(diǎn)以一個(gè)非下降的模式進(jìn)行最終所有的結(jié)點(diǎn)屬于同一個(gè)簇1/31/202331數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘?qū)哟尉垲悾睾喜⑹纠?/31/202332數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘?qū)哟尉垲愊嗨菩远攘繉哟尉垲惙椒ㄗ畛Ｓ玫南嗨菩远攘坑校鹤钚【嚯x最大距離均值距離平均距離1/31/202333數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘?qū)哟尉垲愃惴ú襟E凝聚型層次聚類的操作步驟1/31/202334數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.4.2DIANA算法DIANA(DivisiveAnalysis)與AGNES算法的順序正好相反最終每一個(gè)結(jié)點(diǎn)形成只包含它本身的簇DIANA用到如下兩個(gè)定義：簇的直徑：在一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)歐氏距離，這些距離中的最大值是簇的直徑平均相異度（平均距離）1/31/202335數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘DIANA算法步驟輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目k輸出：k個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目將所有對(duì)象整個(gè)當(dāng)成一個(gè)初始簇For(i=1;i!=k;i++)DoBegin在所有簇中挑選出具有最大直徑的簇；找出所挑出簇里與其他點(diǎn)平均相異度最大的一個(gè)點(diǎn)放入splintergroup，剩余的放入oldparty中。Repeat在oldparty里找出到splintergroup中點(diǎn)的最近距離不大于oldparty中點(diǎn)的最近距離的點(diǎn)，并將該點(diǎn)加入splintergroupUntil沒有新的oldparty的點(diǎn)被分配給splintergroup；Splintergroup和oldparty為被選中的簇分裂成的兩個(gè)簇，與其他簇一起組成新的簇集合END1/31/202336數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘其他層次聚類算法CUREClusteringUsingRepresentatives

ROCK1/31/202337數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘主要內(nèi)容6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/202338數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.5基于密度聚類算法的基礎(chǔ)（1）兩個(gè)參數(shù):Eps:鄰域的最大半徑MinPts:一個(gè)對(duì)象的Eps-鄰域至少包含的對(duì)象數(shù)NEps(p): {qbelongstoD|dist(p,q)<=Eps}直接密度可達(dá):一個(gè)樣本點(diǎn)p是從對(duì)象q關(guān)于Eps,MinPts直接密度可達(dá)的，如果滿足以下兩個(gè)條件：

1)p屬于NEps(q)2)核心對(duì)象條件：

|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm1/31/202339數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘基于密度聚類算法的基礎(chǔ)（2）密度可達(dá)（Density-reachable）:一個(gè)樣本p從對(duì)象q關(guān)于Eps和MinPts是密度可達(dá)的，如果存在一個(gè)樣本鏈p1,…,pn,p1=q,pn=p，pi+1是從pi關(guān)于Eps,MinPts直接密度可達(dá) 密度連通（Density-connected）如果存在一個(gè)對(duì)象o,使得對(duì)象p和q是從o關(guān)于Eps和MinPts密度可達(dá)的，那么稱對(duì)象p與q關(guān)于Eps與MinPts是密度連通的.pqp1pqo1/31/202340數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.5.1DBSCAN算法DBSCAN算法的思想：它定義簇為密度相連的點(diǎn)的最大集合在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類核心邊界異常點(diǎn)Eps=1cmMinPts=51/31/202341數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘DBSCAN算法步驟任意選擇一個(gè)點(diǎn)p找出從對(duì)象p關(guān)于Eps和MinPts.密度可達(dá)的所有點(diǎn)如果是一個(gè)中心點(diǎn)，則一個(gè)聚類就形成了如果p是一個(gè)邊界點(diǎn)，沒有從p密度可達(dá)的對(duì)象，DBSCAN則訪問數(shù)據(jù)庫(kù)中的其他點(diǎn)繼續(xù)這個(gè)過程，直到所有的點(diǎn)被處理1/31/202342數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.5.2OPTICS算法OPTICS:通過對(duì)象排序來識(shí)別聚類結(jié)構(gòu)產(chǎn)生數(shù)據(jù)庫(kù)的一個(gè)關(guān)于基于密度聚類結(jié)構(gòu)的的一個(gè)次序簇次序包含的信息，等同于從一個(gè)寬廣的參數(shù)設(shè)置范圍內(nèi)獲得基于密度的聚類對(duì)包括找出內(nèi)在的聚類結(jié)構(gòu)的自動(dòng)和交互式聚類分析方法很有用可以用圖形或使用可視化技術(shù)表示1/31/202343數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘OPTICS:DBSCAN的擴(kuò)充核心距離(core－distance)C(o)=2.8cm可達(dá)距離(reachability-distant)Dp2MinPts=5e=3cmMax(core-distance(o),d(o,p))r(p1,o)=2.8cm.r(p2,o)=4cmoop1e1/31/202344數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘Reachability-distanceCluster-orderoftheobjectsundefined‘1/31/202345數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘主要內(nèi)容6.1聚類的基本概念6.2相似度的計(jì)算6.3劃分聚類方法6.3.1k-means算法6.3.2PAM算法6.4層次聚類方法6.4.1AGNES算法6.4.2DIANA算法6.5基于密度的聚類方法6.5.1DBSCAN算法6.5.2OPTICS算法6.6基于網(wǎng)格的聚類方法6.6.1STING算法6.6.2CLIQUE算法上機(jī)實(shí)驗(yàn)：使用KNIME進(jìn)行聚類分析1/31/202346數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.6基于網(wǎng)格的聚類使用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)幾種代表性的方法STING(aSTatisticalINformationGridapproach)由Wang,Yang和Muntz在1997年提出WaveCluster由Sheikholeslami,Chatterjee,和Zhang提出(VLDB’98)一個(gè)采用小波變換方法的多分辨率聚類算法CLIQUE:Agrawal,etal.(SIGMOD’98)1/31/202347數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘6.6.1STING:統(tǒng)計(jì)信息網(wǎng)格方法由Wang,Yang和Muntz提出(VLDB’97)將空間區(qū)域劃分成矩形單元針對(duì)不同級(jí)別的分辨率，通常存在不同級(jí)別的矩形單元1/31/202348數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘STING:統(tǒng)計(jì)信息網(wǎng)格方法(2)高層的每個(gè)單元被劃分成多個(gè)低一層的單元每個(gè)單元屬性的統(tǒng)計(jì)信息被預(yù)先計(jì)算和存儲(chǔ)，這對(duì)查詢處理是有用的高層單元的統(tǒng)計(jì)參數(shù)很容易從低層單元的計(jì)算得到，這些參數(shù)包括：Count（計(jì)數(shù)）,mean（平均值）,s（標(biāo)準(zhǔn)差）,min（最小值）,max（最大值）分布類型－正態(tài)分布，一致分布等等使用自頂向下的方法回答空間數(shù)據(jù)的查詢從一個(gè)預(yù)先選擇的層次開始－通常包含少量的單元為當(dāng)前層的每個(gè)單元計(jì)算置信區(qū)間1/31/202349數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘STING:統(tǒng)計(jì)信息網(wǎng)格方法(3)不相關(guān)的單元不再考慮當(dāng)