數(shù)據(jù)挖掘-第8章-聚類分析：基本概念和算法

1、聚類分析：基本概念和算法第8章 聚類分析：基本概念和算法目錄概述K均值聚類（重點(diǎn)）層次聚類（重點(diǎn)）DBSCAN（重點(diǎn)）什么是聚類分析?聚類分析將數(shù)據(jù)劃分成有意義或有用的組（簇）。聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對(duì)象及其關(guān)系的信息，將數(shù)據(jù)對(duì)象分組。其目標(biāo)是，組內(nèi)的對(duì)象相互之間是相似的，而不同組中的對(duì)象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized聚類的復(fù)雜性How many clusters?Four Clusters Two Clusters Six Clusters 不同的聚類類型

2、劃分聚類（Partitional Clustering）層次聚類（Hierarchical Clustering）互斥聚類（exclusive clustering）非互斥（重疊）聚類（non-exclusive）模糊聚類（fuzzy clustering）完全聚類（complete clustering）部分聚類（partial clustering）劃分聚類（Partitional Clustering）Original PointsA Partitional Clustering劃分成不重疊的子集，使得每個(gè)數(shù)據(jù)對(duì)象恰在一個(gè)子集。層次聚類（Hierarchical Clustering）T

3、raditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram嵌套簇的集族，組織成一棵樹(shù)。聚類的類型：層次的與劃分的How many clusters?Four Clusters Two Clusters Six Clusters 聚類的類型：互斥的、重疊的、模糊的互斥的（Exclusive）每個(gè)對(duì)象都指派到單個(gè)簇.重疊的（overlapping）或非互斥的（non-exclusive）聚類用來(lái)反映一個(gè)對(duì)象.同時(shí)屬于

4、多個(gè)組（類）這一事實(shí)。例如：在大學(xué)里，一個(gè)人可能既是學(xué)生，又是雇員模糊聚類（Fuzzy clustering ）每個(gè)對(duì)象以一個(gè)0（絕對(duì)不屬于）和1（絕對(duì)屬于）之間的隸屬權(quán)值屬于每個(gè)簇。換言之，簇被視為模糊集。聚類的類型：部分、完全部分的（Partial） 部分聚類中數(shù)據(jù)集某些對(duì)象可能不屬于明確定義的組。如：一些對(duì)象可能是離群點(diǎn)、噪聲。完全的（complete）完全聚類將每個(gè)對(duì)象指派到一個(gè)簇。不同的簇類型明顯分離的基于原型的基于圖的基于密度的概念簇簇類型: 明顯分離的（Well-Separated）每個(gè)點(diǎn)到同簇中任一點(diǎn)的距離比到不同簇中所有點(diǎn)的距離更近。3 well-separated clus

5、ters遠(yuǎn)簇類型:基于原型的每個(gè)對(duì)象到定義該簇的原型（質(zhì)心、中心）的距離比到其他簇的原型的距離更近。4 center-based clusters簇類型:基于圖的如果數(shù)據(jù)用圖表示，其中節(jié)點(diǎn)是對(duì)象，而邊代表對(duì)象之間的聯(lián)系。簇可以定義為連通分支（connected component）：互相連通但不與組外對(duì)象連通的對(duì)象組。簇類型: 基于密度的（Density-Based）簇是對(duì)象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。6 density-based clusters簇類型: 概念簇（Conceptual Clusters）可以把簇定義為有某種共同性質(zhì)的對(duì)象的集合。例如：基于中心的聚類。還有一些簇的共同性質(zhì)

6、需要更復(fù)雜的算法才能識(shí)別出來(lái)。. 2 Overlapping Circles目錄概述K均值聚類（重點(diǎn)）層次聚類（重點(diǎn)）DBSCAN（重點(diǎn)）基本K均值算法（重點(diǎn)）1.選擇k個(gè)點(diǎn)作為初始的質(zhì)心2.repeat3.將每個(gè)點(diǎn)指派到最近的質(zhì)心，形成k個(gè)簇4. 重新計(jì)算每個(gè)簇的質(zhì)心5.until 質(zhì)心不發(fā)生變化算法演示算法分解演示選擇初始的質(zhì)心隨機(jī)選擇從層次聚類中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心隨機(jī)選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)二分K均值選擇了較差的初始質(zhì)心的結(jié)果演示選擇了較差的初始質(zhì)心的結(jié)果分解演示二分k均值二分k均值算

7、法是基本k均值算法的直接擴(kuò)充。它將所有點(diǎn)的集合分裂成兩個(gè)簇，從這些簇中選取一個(gè)繼續(xù)分裂，如此下去，直到產(chǎn)生k個(gè)簇。算法演示二分k均值算法初始化簇表，使之包含由所有的點(diǎn)組成的簇。Repeat 從簇表中取出一個(gè)簇。 for i=1 to 實(shí)驗(yàn)次數(shù) do 使用基本k均值，二分選定的簇。 end for 從二分實(shí)驗(yàn)中選擇具有最小總sse的兩個(gè)簇。 將這兩個(gè)簇添加到簇表中。Until 簇表中包含k個(gè)簇。優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：算法簡(jiǎn)單適用于球形簇二分k均值等變種算法運(yùn)行良好，不受初始化問(wèn)題的影響。缺點(diǎn)：不能處理非球形簇、不同尺寸和不同密度的簇對(duì)離群點(diǎn)、噪聲敏感K均值應(yīng)用gene帶有病人生存期的樣本目錄概述K均值

8、聚類（重點(diǎn)）層次聚類（重點(diǎn)）DBSCAN（重點(diǎn)）層次聚類算法（重點(diǎn)）計(jì)算鄰近度矩陣Repeat 合并最近的兩個(gè)簇 更新鄰近性矩陣，以反映新的簇與 原來(lái)的簇之間的鄰近行Until 僅剩下一個(gè)簇層次聚類各種相似度和相異度測(cè)量方法（重點(diǎn)）簡(jiǎn)單屬性之間的相似度和相異度數(shù)據(jù)對(duì)象之間的相異度歐氏距離.明可夫斯基距離.馬氏距離數(shù)據(jù)對(duì)象之間的相似度簡(jiǎn)單匹配系數(shù)、雅卡爾系數(shù).余弦相似度.相關(guān)性定義簇之間的近鄰性（重點(diǎn)）單鏈（single link）全鏈（complete link）組平均（group average）城市塊距離應(yīng)用-衡量疾病之間的”距離”優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：某些應(yīng)用領(lǐng)域需要層次結(jié)構(gòu)。如：系統(tǒng)發(fā)生樹(shù)，

9、基因芯片有些研究表明，這種算法能夠產(chǎn)生較高質(zhì)量的聚類缺點(diǎn)：計(jì)算量、存儲(chǔ)量大對(duì)噪聲、高維數(shù)據(jù)敏感目錄概述K均值聚類（重點(diǎn)）層次聚類（重點(diǎn)）DBSCAN（重點(diǎn)）DBSCAN算法DBSCAN 是一種簡(jiǎn)單、有效的基于密度的聚類算法.基于中心的DBSCAN在基于中心的方法中，數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)對(duì)該點(diǎn)Eps半徑之內(nèi)的點(diǎn)計(jì)數(shù)（包括點(diǎn)本身）來(lái)估計(jì)該方法實(shí)現(xiàn)簡(jiǎn)單，但是點(diǎn)的密度依賴于指定的半徑。例如，如果半徑足夠大，則所有點(diǎn)的密度都等于數(shù)據(jù)集中的點(diǎn)數(shù)m。類似地，如果半徑太小，則所有點(diǎn)的密度都是1。DBSCAN: 核心點(diǎn), 邊界點(diǎn), 噪聲點(diǎn)DBSCAN 算法將所有點(diǎn)標(biāo)記為核心點(diǎn)、邊界點(diǎn)或噪聲點(diǎn)刪除噪聲點(diǎn)為距離

10、在Eps之內(nèi)的所有核心點(diǎn)之間賦予一條邊。每組連通的核心點(diǎn)形成一個(gè)簇。將每個(gè)邊界點(diǎn)指派到一個(gè)與之關(guān)聯(lián)的核心點(diǎn)的簇中。DBSCAN: 選擇 EPS and MinPts基本方法是觀察點(diǎn)到它的k個(gè)最近鄰的距離（稱為k-距離）的特性。計(jì)算所有點(diǎn)的k-距離，以遞增次序?qū)⑺鼈兣判?，然后繪制排序后的值，則我們預(yù)期會(huì)看到k-距離的急劇變化，對(duì)應(yīng)于合適的Eps值。如果我們選取該距離為Eps參數(shù)，而取k的值為MinPts參數(shù)。Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4變密度的簇如果簇的密度變化很大，DBSCAN可能會(huì)有問(wèn)題?？紤]圖8-24，它包含4個(gè)埋藏在噪聲中的簇。簇和噪聲區(qū)域的密度由它們的明暗度指出。較密的兩個(gè)簇A和B周圍的噪聲的密度與簇C和D的密度相同。如果Eps域值足夠低，使得DBSCAN可以發(fā)現(xiàn)簇C和D，則A、B和包圍它們的點(diǎn)將變成單個(gè)簇。如果Eps域值足夠高，使得DBSCAN可以發(fā)現(xiàn)A和B，并且將包圍它們的點(diǎn)標(biāo)記為噪聲，則C、D和包圍它們的點(diǎn)也將標(biāo)記為噪聲。Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimensional dataDBSCAN的優(yōu)點(diǎn)與缺點(diǎn)因?yàn)镈B