《數(shù)據(jù)聚類》PPT課件.ppt

1、聚類方法,聚類方法概述 劃分聚類方法 層次聚類方法 密度聚類方法 其它聚類方法,*,1,什么是聚類,聚類(clustering),指將樣本分到不同的組中使得同一組中的樣本差異盡可能的小，而不同組中的樣本差異盡可能的大。 聚類得到的不同的組稱為簇(cluster)。 一個(gè)好的聚類方法將產(chǎn)生以下的聚類 最大化類中的相似性 最小化類間的相似性,*,2,2020/9/11,數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘,3,什么是聚類分析？,聚類分析是根據(jù)“物以類聚”的道理，對(duì)樣本或指標(biāo)進(jìn)行分類的一種多元統(tǒng)計(jì)分析方法，它們討論的對(duì)象是大量的樣本，要求能合理地按各自的特性進(jìn)行合理的分類，沒有任何模式可供參考或依循，即在沒有先驗(yàn)知識(shí)

2、的情況下進(jìn)行的。,2020/9/11,數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘,4,聚類分析的基本思想,基本思想是認(rèn)為研究的樣本或變量之間存在著程度不同的相似性（親疏關(guān)系）。 根據(jù)一批樣本的多個(gè)觀測(cè)指標(biāo)，找出一些能夠度量樣本或變量之間相似程度的統(tǒng)計(jì)量，以這些統(tǒng)計(jì)量作為分類的依據(jù)，把一些相似程度較大的樣本（或指標(biāo)）聚合為一類，把另外一些相似程度較大的樣本（或指標(biāo)）聚合為一類，直到把所有的樣本（或指標(biāo)）都聚合完畢，形成一個(gè)由小到大的分類系統(tǒng)。,2020/9/11,數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘,5,聚類分析無(wú)處不在,誰(shuí)經(jīng)常光顧商店，誰(shuí)買什么東西，買多少？ 按會(huì)員卡記錄的光臨次數(shù)、光臨時(shí)間、性別、年齡、職業(yè)、購(gòu)物種類、金額等變量聚類

3、 這樣商店可以 識(shí)別顧客購(gòu)買模式（如喜歡一大早來(lái)買酸奶和鮮肉，習(xí)慣周末時(shí)一次性大采購(gòu)） 刻畫不同的客戶群的特征,2020/9/11,數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘,8,聚類的應(yīng)用領(lǐng)域,經(jīng)濟(jì)領(lǐng)域： 幫助市場(chǎng)分析人員從客戶數(shù)據(jù)庫(kù)中發(fā)現(xiàn)不同的客戶群，并且用購(gòu)買模式來(lái)刻畫不同的客戶群的特征。 誰(shuí)喜歡打國(guó)際長(zhǎng)途，在什么時(shí)間，打到那里？ 對(duì)住宅區(qū)進(jìn)行聚類，確定自動(dòng)提款機(jī)ATM的安放位置 股票市場(chǎng)板塊分析，找出最具活力的板塊龍頭股 企業(yè)信用等級(jí)分類 生物學(xué)領(lǐng)域： 推導(dǎo)植物和動(dòng)物的分類； 對(duì)基因分類，獲得對(duì)種群的認(rèn)識(shí) 數(shù)據(jù)挖掘領(lǐng)域 作為其他數(shù)學(xué)算法的預(yù)處理步驟，獲得數(shù)據(jù)分布狀況，集中對(duì)特定的類做進(jìn)一步的研究,聚類與分類的

4、差別,聚類與分類最主要的差別是聚類的樣本不具有類別標(biāo)號(hào)，而分類的樣本具有類別標(biāo)號(hào)。 聚類是無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning)，而分類是有監(jiān)督學(xué)習(xí)(supervised learning)。因此，分類里有訓(xùn)練和測(cè)試，而聚類沒有訓(xùn)練。 盡管分類是識(shí)別對(duì)象組類別的有效手段，但需要高昂的代價(jià)收集和標(biāo)記訓(xùn)練樣本集。因此，聚類提供了一種新的處理模式：先把數(shù)據(jù)集劃分為組，然后給有限的組指定類別標(biāo)號(hào)。,*,9,對(duì)聚類方法的一些要求,可伸縮性 處理不同類型屬性的能力 發(fā)現(xiàn)任意形狀的聚類 用于決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化 處理噪聲數(shù)據(jù)和孤立點(diǎn)的能力 對(duì)于輸入紀(jì)錄的順序不敏感 高維性 基于約束

5、的聚類 可解釋性和可用性,*,10,聚類分析中的數(shù)據(jù)類型,數(shù)據(jù)矩陣 相異度矩陣,*,11,標(biāo)準(zhǔn)度量的聚類描述,歐氏距離 衡量的是多維空間中各個(gè)點(diǎn)之間的絕對(duì)距離 曼哈頓距離 曼哈頓距離來(lái)源于城市區(qū)塊距離，是將多個(gè)維度上的距離進(jìn)行求和后的結(jié)果 明考斯基距離 是對(duì)多個(gè)距離度量公式的概括性的表述，這里的p值是一個(gè)變量，當(dāng)p=2的時(shí)候就得到了上面的歐氏距離。,*,12,聚類分析中的數(shù)據(jù)類型,向量對(duì)象的距離算法 余弦度量實(shí)際上計(jì)算的是向量x與y之間夾角的余弦值。 余弦度量對(duì)于平移與放大是不變的。,*,13,主要聚類方法的分類,聚類方法大致可以分為以下幾類： 劃分聚類方法 層次聚類方法 密度聚類方法 網(wǎng)格聚

6、類方法 基于模型的方法 其它聚類方法,*,14,主要聚類方法的分類,劃分聚類方法 劃分方法將給定的數(shù)據(jù)集劃分成k份，每份為一個(gè)簇。劃分方法通常采用迭代重定位技術(shù)，嘗試通過對(duì)象在簇之間的移動(dòng)在改進(jìn)劃分。,*,15,主要聚類方法的分類,層次聚類方法 層次聚類方法創(chuàng)建給定數(shù)據(jù)對(duì)象集的層次分解。一般可以分為凝聚法與分裂法。 凝聚法：也稱為自底向上的方法，開始將每個(gè)對(duì)象形成單獨(dú)的簇，然后逐次合并相近的對(duì)象或簇，直到滿足終止條件。 分裂法：也稱為自頂向下的方法，開始將所有對(duì)象放入一個(gè)簇中，每次迭代，簇分裂為更小的簇，直到滿足終止條件。,*,16,主要聚類方法的分類,密度聚類方法 大部分劃分方法基于對(duì)象間的

7、距離進(jìn)行聚類，這樣的方法只能發(fā)現(xiàn)球形簇，不能發(fā)現(xiàn)任意形狀的簇。 基于密度的聚類方法的思想是：只要鄰域中的密度超過某個(gè)閾值，就繼續(xù)聚類。 基于密度的聚類方法既可以發(fā)現(xiàn)任意形狀的簇，也可以過濾噪聲。,*,17,主要聚類方法的分類,網(wǎng)格聚類方法：把對(duì)象空間化為有限的數(shù)目單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)格結(jié)構(gòu)內(nèi)進(jìn)行。它的優(yōu)點(diǎn)是處理速度快。 基于模型的聚類方法：為每個(gè)簇假定一個(gè)模型，并尋找數(shù)據(jù)對(duì)給定模型的最佳組合。 其它聚類方法包括：針對(duì)高維數(shù)據(jù)的聚類方法，基于約束條件的聚類方法等等。,*,18,劃分聚類算法,給定一個(gè)有n個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇

8、。也就是說，它將數(shù)據(jù)劃分為k個(gè)簇，而且這k個(gè)劃分滿足下列條件： 每一個(gè)簇至少包含一個(gè)對(duì)象。 每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。 對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法，以后通過反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分方案都較前一次更好。 k-means算法 PAM算法,*,19,劃分聚類算法,一種直接方法就是觀察聚類的類內(nèi)差異(within cluster variation)和類間差異(Between cluster variation)。 類內(nèi)差異：衡量聚類的緊湊性，類內(nèi)差異可以用特定的距離函數(shù)來(lái)定義，例如， 類間差異：衡量不同聚類之間的距離，類間差異定義為聚類中心間的距離，例如

9、， 聚類的總體質(zhì)量可被定義為w(c)和b(c)的一個(gè)單調(diào)組合，比如w(c) / b(c) 。,*,20,k-means算法,k-means 算法基本步驟 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心； 根據(jù)每個(gè)聚類對(duì)象的均值(中心對(duì)象)，計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分； 重新計(jì)算每個(gè)(有變化)聚類的均值(中心對(duì)象)； 計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止；如果條件不滿足則回到步驟2。,*,21,k-means算法,*,22,算法5-1 k-means算法 輸入：簇的數(shù)目k和包含n個(gè)樣本的數(shù)據(jù)庫(kù)。 輸出：k個(gè)簇，使平方誤差準(zhǔn)則

10、最小。 （1)assign initial value for means; /*任意選擇k個(gè)對(duì)象作為初始的簇中心；*/ (2) REPEAT (3) FOR j=1 to n DO assign each xj to the closest centers; (4) FOR i=1 to k DO / *更新簇平均值*/ (5) Compute /*計(jì)算準(zhǔn)則函數(shù)E*/ (6) UNTIL E不再明顯地發(fā)生變化。,k-means算法,初始化聚類中心(k=3)； 根據(jù)每個(gè)樣本到各個(gè)中心的距離，計(jì)算k個(gè)簇。 使用每個(gè)簇的樣本，對(duì)每個(gè)簇生成新的中心。 重復(fù)STEP2和STEP3直到終止條件滿足。,*

11、,23,劃分聚類算法,請(qǐng)使用k-means算法對(duì)左邊的樣本進(jìn)行分類，其中k=2，初始中心為樣本1和樣本3。(第一次迭代),*,24,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,劃分聚類算法,紅色的樣本屬于一個(gè)簇，橙色的樣本屬于一個(gè)簇 計(jì)算每個(gè)簇新的中心 使用新的中心，重新對(duì)每個(gè)樣本所在的簇進(jìn)行分配(第二次迭代),*,25,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,劃分聚類算法,紅色的樣本屬于一個(gè)簇，橙色的樣本屬于一個(gè)簇

12、 計(jì)算每個(gè)簇新的中心 使用新的中心，重新對(duì)每個(gè)樣本所在的簇進(jìn)行分配(第三次迭代) 簇的分配情況沒有變化，聚類終止,*,26,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,k-means算法例題,*,27,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,根據(jù)所給的數(shù)據(jù)通過對(duì)其實(shí)施k-means (設(shè)n=8，k=2),，其主要執(zhí)行執(zhí)行步驟： 第一次迭代：假定隨機(jī)選擇的兩個(gè)對(duì)象，如序號(hào)1和序號(hào)3當(dāng)作初始點(diǎn)，分別找到離兩點(diǎn)最近的對(duì)象，

13、并產(chǎn)生兩個(gè)簇1，2和3，4，5，6，7，8。 對(duì)于產(chǎn)生的簇分別計(jì)算平均值，得到平均值點(diǎn)。 對(duì)于1，2，平均值點(diǎn)為（1.5，1）（這里的平均值是簡(jiǎn)單的相加出2）； 對(duì)于3，4，5，6，7，8，平均值點(diǎn)為（3.5，3）。 第二次迭代：通過平均值調(diào)整對(duì)象的所在的簇，重新聚類，即將所有點(diǎn)按離平均值點(diǎn)（1.5，1）、（3.5，1）最近的原則重新分配。得到兩個(gè)新的簇：1，2，3，4和5，6，7，8。重新計(jì)算簇平均值點(diǎn)，得到新的平均值點(diǎn)為（1.5，1.5）和（4.5，3.5）。 第三次迭代：將所有點(diǎn)按離平均值點(diǎn)（1.5，1.5）和（4.5，3.5）最近的原則重新分配，調(diào)整對(duì)象，簇仍然為1，2，3，4和5，6

14、，7，8，發(fā)現(xiàn)沒有出現(xiàn)重新分配，而且準(zhǔn)則函數(shù)收斂，程序結(jié)束。,迭代次數(shù)平均值平均值產(chǎn)生的新簇新平均值新平均值 （簇1） （簇2） （簇1） （簇2） 1（1，1）（1，2）1，2，3，4，5，6，7，8（1.5，1）（3.5，3） 2（1.5，1）（3.5，3）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5） 3（1.5，1.5）（4.5，3.5）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5）,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,練習(xí),請(qǐng)使用k-means算法對(duì)

15、左邊的樣本進(jìn)行分類，其中k=3，初始中心為樣本1、樣本3和樣本7。,*,28,樣本數(shù)據(jù) 序號(hào) 屬性 1 屬性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,k-means算法的性能分析,主要優(yōu)點(diǎn)： 是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速。 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。 當(dāng)結(jié)果簇是密集的，它的效果較好。 主要缺點(diǎn) 在簇的平均值被定義的情況下才能使用，可能不適用于某些應(yīng)用。 必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。 不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對(duì)于

16、“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的。,*,29,k-means算法的幾種變異,k -means算法對(duì)于孤立點(diǎn)是敏感的。為了解決這個(gè)問題，我們引入了k-中心點(diǎn)算法，該算法不采用簇中的平均值作為參照點(diǎn)，可以選用簇中位置最中心的對(duì)象，即中心點(diǎn)作為參照點(diǎn)。這樣劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來(lái)執(zhí)行的。,*,30,PAM算法,PAM是最早提出的k-中心點(diǎn)算法之一，它選用簇中最中心的對(duì)象作為代表對(duì)象，試圖對(duì)n個(gè)對(duì)象給出k個(gè)劃分。 代表對(duì)象也被稱為是中心點(diǎn)，其他對(duì)象則被稱為非代表對(duì)象。 最初隨機(jī)選擇k個(gè)對(duì)象作為中心點(diǎn)，該算法反復(fù)地用非代表對(duì)象來(lái)代替中心點(diǎn)，試圖找出更好的中心點(diǎn)，以改

17、進(jìn)聚類的質(zhì)量。,*,31,層次聚類算法,層次聚類方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為： 凝聚的層次聚類：一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到某個(gè)終結(jié)條件被滿足。 分裂的層次聚類：采用自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到達(dá)到了某個(gè)終結(jié)條件。 層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。,*,32,AGNES算法,AGNES (AGglomerative NESting)算法最初將每個(gè)對(duì)象作為一個(gè)簇，然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并。兩個(gè)簇間的相似度有多

18、種不同的計(jì)算方法。聚類的合并過程反復(fù)進(jìn)行直到所有的對(duì)象最終滿足簇?cái)?shù)目。,*,33,算法5-3 AGNES（自底向上凝聚算法） 輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。 輸出：滿足終止條件的若干個(gè)簇。 (1) 將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇； (2) REPEAT (3) 計(jì)算任意兩個(gè)簇的距離，并找到最近的兩個(gè)簇； (4) 合并兩個(gè)簇，生成新的簇的集合； (5) UNTIL 終止條件得到滿足；,AGNES算法,兩個(gè)簇的距離可以通過以下定義得到 若采用最小距離的定義，簇與簇的合并方式稱為單鏈接方法。,*,34,AGNES算法,假如空間中的五個(gè)點(diǎn)A、，各點(diǎn)之間的距離關(guān)系如表1所示，其中A,B是一個(gè)簇，C，D，E是一個(gè)

19、簇。計(jì)算這兩個(gè)簇的最小距離與最大距離。,*,35,AGNES算法,使用AGNES算法對(duì)下面的數(shù)據(jù)集進(jìn)行聚類。,*,36,AGNES算法,使用AGNES算法對(duì)下面 的數(shù)據(jù)集進(jìn)行聚類。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,37,AGNES算法,使用AGNES算法對(duì)下面 的數(shù)據(jù)集進(jìn)行聚類。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,38,AGNES算法,使用AGNES算法對(duì)下面 的數(shù)據(jù)集進(jìn)行聚類。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,39,AGNES算法,使用AGNES算法對(duì)下面 的數(shù)據(jù)集進(jìn)行聚類。 l=4 l=3 l=2

20、 l=1 l=0 A B C D E,*,40,AGNES算法,層次聚類方法的終止條件： 設(shè)定一個(gè)最小距離閾值D，如果最相近的兩個(gè)簇的距離已經(jīng)超過D，則它們不需再合并，聚類終止。 限定簇的個(gè)數(shù)k，當(dāng)?shù)玫降拇氐膫€(gè)數(shù)已經(jīng)達(dá)到k，則聚類終止。,*,41,AGNES算法性能分析,AGNES算法比較簡(jiǎn)單，但一旦一組對(duì)象被合并，下一步的處理將在新生成的簇上進(jìn)行。已做處理不能撤消，聚類之間也不能交換對(duì)象。增加新的樣本對(duì)結(jié)果的影響較大。 假定在開始的時(shí)候有n個(gè)簇，在結(jié)束的時(shí)候有1個(gè)簇，因此在主循環(huán)中有n次迭代，在第i次迭代中，我們必須在n-i+1個(gè)簇中找到最靠近的兩個(gè)聚類。另外算法必須計(jì)算所有對(duì)象兩兩之間的距

21、離，因此這個(gè)算法的復(fù)雜度為 O(n2)，該算法對(duì)于n很大的情況是不適用的。,*,42,第五章 聚類方法 內(nèi)容提要,聚類方法概述 劃分聚類方法 層次聚類方法 密度聚類方法 其它聚類方法,*,43,密度聚類算法,密度聚類方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)域值，就把它加到與之相近的聚類中去。這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類球形”的聚類的缺點(diǎn)，可發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感。 但計(jì)算密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來(lái)降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個(gè)數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)對(duì)象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時(shí)會(huì)造成頻繁的I/O操作。 代表算

22、法有：DBSCAN、OPTICS、DENCLUE算法等。,*,44,DBSCAN算法,DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一個(gè)比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。,*,45,DBSCAN算法,定義 5-3 對(duì)象的-臨域：給定對(duì)象在半徑內(nèi)的區(qū)域。 定義 5-4 核心對(duì)象：如果一個(gè)對(duì)象的-臨域至少包含最小數(shù)目MinPts個(gè)對(duì)象，則稱該對(duì)象為核心對(duì)象。 例如，

23、在下圖中，=1cm，MinPts=5，q是一個(gè)核心對(duì)象。,*,46,DBSCAN算法,定義 5-5 直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如果p是在q的-鄰域內(nèi)，而q是一個(gè)核心對(duì)象，我們說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。 例如，在下圖中，=1cm，MinPts=5，q是一個(gè)核心對(duì)象，對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。,*,47,DBSCAN算法,定義 5-6 密度可達(dá)的：如果存在一個(gè)對(duì)象鏈p1，p2，pn，p1=q，pn=p，對(duì)piD，（1=i=n），pi+1是從pi關(guān)于和MitPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于和MinPts密度可達(dá)的。 例如，在下圖中，=1cm，MinPts=5，q是一個(gè)核心對(duì)象，p1是從q關(guān)于和MitPts直接密度可達(dá)，p是從p1關(guān)于和MitPts直接密度可達(dá)，則對(duì)象p從對(duì)象q關(guān)于和MinPts密度可達(dá)的。,*,48,DBSCAN算法,定義 5-7密度相連的：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于和MinP