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

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

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

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

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

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

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

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

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

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

10、最小。 （1)assign initial value for means; /*任意選擇k個對象作為初始的簇中心；*/ (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 /*計算準則函數(shù)E*/ (6) UNTIL E不再明顯地發(fā)生變化。,k-means算法,初始化聚類中心(k=3)； 根據(jù)每個樣本到各個中心的距離，計算k個簇。 使用每個簇的樣本，對每個簇生成新的中心。 重復STEP2和STEP3直到終止條件滿足。,*

11、,23,劃分聚類算法,請使用k-means算法對左邊的樣本進行分類，其中k=2，初始中心為樣本1和樣本3。(第一次迭代),*,24,樣本數(shù)據(jù) 序號 屬性 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,劃分聚類算法,紅色的樣本屬于一個簇，橙色的樣本屬于一個簇 計算每個簇新的中心 使用新的中心，重新對每個樣本所在的簇進行分配(第二次迭代),*,25,樣本數(shù)據(jù) 序號 屬性 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,劃分聚類算法,紅色的樣本屬于一個簇，橙色的樣本屬于一個簇

12、 計算每個簇新的中心 使用新的中心，重新對每個樣本所在的簇進行分配(第三次迭代) 簇的分配情況沒有變化，聚類終止,*,26,樣本數(shù)據(jù) 序號 屬性 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ù) 序號 屬性 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ù)通過對其實施k-means (設n=8，k=2),，其主要執(zhí)行執(zhí)行步驟： 第一次迭代：假定隨機選擇的兩個對象，如序號1和序號3當作初始點，分別找到離兩點最近的對象，

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

14、，7，8，發(fā)現(xiàn)沒有出現(xiàn)重新分配，而且準則函數(shù)收斂，程序結束。,迭代次數(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ù) 序號 屬性 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算法對

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

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

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

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

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

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

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

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

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