第6章聚類分析ppt課件

《第6章聚類分析ppt課件》由會員分享，可在線閱讀，更多相關《第6章聚類分析ppt課件（168頁珍藏版）》請在裝配圖網上搜索。

1、第1頁第第5章章 聚類分析聚類分析 本章概述 本章的學習目標主要內容第2頁什么是聚類什么是聚類l聚類（聚類（Clustering）就是將數據分組成為多個類）就是將數據分組成為多個類（Cluster或譯為簇）?；蜃g為簇）。l在同一個類內對象之間具有較高的相似度，不同類在同一個類內對象之間具有較高的相似度，不同類之間的對象差別較大。之間的對象差別較大。簇之間的距離最大化在一個簇內的距離最小化第3頁l從機器學習的角度講，簇相當于隱藏模式。聚類是從機器學習的角度講，簇相當于隱藏模式。聚類是搜索簇的無監督學習過程。搜索簇的無監督學習過程。l與分類不同，無監督學習不依賴預先定義的類或帶與分類不同，無監督學

2、習不依賴預先定義的類或帶類標記的訓練實例，需要由聚類學習算法自動確定類標記的訓練實例，需要由聚類學習算法自動確定標記，而分類學習的實例或數據對象有類別標記。標記，而分類學習的實例或數據對象有類別標記。第4頁什么是聚類什么是聚類l早在孩提時代，人就通過不斷改進下意識中的聚類早在孩提時代，人就通過不斷改進下意識中的聚類模式來學會如何區分貓和狗，動物和植物模式來學會如何區分貓和狗，動物和植物l將周圍的人分為家人和非家人將周圍的人分為家人和非家人第5頁聚類分析無處不在聚類分析無處不在l誰經常光顧商店，誰買什么東西，買多少？誰經常光顧商店，誰買什么東西，買多少？按忠誠卡記錄的光臨次數、光臨時間、性別、按

3、忠誠卡記錄的光臨次數、光臨時間、性別、年齡、職業、購物種類、金額等變量分類年齡、職業、購物種類、金額等變量分類這樣商店可以這樣商店可以.識別顧客購買模式（如喜歡一大早來買酸奶和識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉，習慣周末時一次性大采購）鮮肉，習慣周末時一次性大采購）刻畫不同的客戶群的特征（用變量來刻畫，就刻畫不同的客戶群的特征（用變量來刻畫，就象刻畫貓和狗的特征一樣）象刻畫貓和狗的特征一樣）第6頁什么情況下需要聚類什么情況下需要聚類l為什么這樣分類？為什么這樣分類？l因為每一個類別里面的人消費方式都不一樣，需要因為每一個類別里面的人消費方式都不一樣，需要針對不同的人群，制定不同的關系

4、管理方式，以提針對不同的人群，制定不同的關系管理方式，以提高客戶對公司商業活動的響應率。高客戶對公司商業活動的響應率。第7頁聚類分析無處不在聚類分析無處不在l挖掘有價值的客戶，并制定相應的促銷策略：挖掘有價值的客戶，并制定相應的促銷策略：如，對經常購買酸奶的客戶如，對經常購買酸奶的客戶對累計消費達到對累計消費達到12個月的老客戶個月的老客戶l針對潛在客戶派發廣告，比在大街上亂發傳單命中針對潛在客戶派發廣告，比在大街上亂發傳單命中率更高，成本更低！率更高，成本更低！第8頁聚類分析無處不在聚類分析無處不在l誰是銀行信用卡的黃金客戶？誰是銀行信用卡的黃金客戶？利用儲蓄額、刷卡消費金額、誠信度等變量對

5、客利用儲蓄額、刷卡消費金額、誠信度等變量對客戶分類，找出戶分類，找出“黃金客戶黃金客戶”！這樣銀行可以這樣銀行可以制定更吸引的服務，留住客戶！比如：制定更吸引的服務，留住客戶！比如：一定額度和期限的免息透資服務！一定額度和期限的免息透資服務！百盛的貴賓打折卡！百盛的貴賓打折卡！在他或她生日的時候送上一個小蛋糕！在他或她生日的時候送上一個小蛋糕！l手機套餐的制定手機套餐的制定第9頁聚類的應用領域聚類的應用領域l經濟領域：經濟領域：幫助分析人員從客戶數據庫中發現不同的客戶群，幫助分析人員從客戶數據庫中發現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。并且用購買模式來刻畫不同的客戶群的特征。

6、誰喜歡打國際長途，在什么時間，打到那里？誰喜歡打國際長途，在什么時間，打到那里？對住宅區進行聚類，確定自動提款機對住宅區進行聚類，確定自動提款機ATM的安放的安放位置位置股票市場板塊分析，找出最具活力的板塊龍頭股股票市場板塊分析，找出最具活力的板塊龍頭股企業信用等級分類企業信用等級分類第10頁l生物學領域生物學領域推導植物和動物的分類推導植物和動物的分類(門、綱、目、科、屬、門、綱、目、科、屬、種種)；對基因分類，獲得對種群的認識對基因分類，獲得對種群的認識l數據挖掘領域數據挖掘領域作為其他數學算法的預處理步驟，獲得數據分布作為其他數學算法的預處理步驟，獲得數據分布狀況，集中對特定的類做進一步

7、的研究狀況，集中對特定的類做進一步的研究第11頁聚類分析原理介紹聚類分析原理介紹l聚類分析中聚類分析中“類類”的特征：的特征：聚類所說的類不是事先給定的，而是根據數據的聚類所說的類不是事先給定的，而是根據數據的相似性和距離來劃分相似性和距離來劃分聚類的數目和結構都沒有事先假定聚類的數目和結構都沒有事先假定第12頁有多少個簇？四個簇2個簇6個簇簇簇(類類)的概念可能是模糊的的概念可能是模糊的如何對漢語方言進行分類？如何對漢語方言進行分類？第13頁聚類分析原理介紹聚類分析原理介紹l我們看以下的例子：我們看以下的例子：l有有16張牌張牌l如何將他們分為如何將他們分為 一組一組的牌呢？一組一組的牌呢？

8、AKQJ第14頁聚類分析原理介紹聚類分析原理介紹l分成四組分成四組l每組里每組里花色相同花色相同l組與組之間花色相異組與組之間花色相異AKQJ花色相同的牌為一副花色相同的牌為一副Individual suits第15頁聚類分析原理介紹聚類分析原理介紹l分成四組分成四組l符號相同符號相同的牌為一組的牌為一組AKQJ符號相同的的牌符號相同的的牌Like face cards第16頁聚類分析原理介紹聚類分析原理介紹l分成兩組分成兩組l顏色相同顏色相同的牌為一組的牌為一組AKQJ顏色相同的配對顏色相同的配對Black and red suits第17頁聚類分析原理介紹聚類分析原理介紹l分成兩組分成兩組

9、l大小程度相近大小程度相近的牌分到的牌分到一組一組AKQJ大配對和小配對大配對和小配對Major and minor suits第18頁聚類分析原理介紹聚類分析原理介紹l這個例子告訴我們，分這個例子告訴我們，分組的意義在于我們怎么組的意義在于我們怎么定義并度量定義并度量“相似性相似性”(Similar)l因此衍生出一系列度量因此衍生出一系列度量相似性的方法相似性的方法AKQJ大配對和小配對大配對和小配對Major and minor suits第19頁聚類分析原理介紹聚類分析原理介紹變量按測量尺度（變量按測量尺度（Measurement Level）分類）分類l區間（區間（Interval）值

10、變量）值變量連續變量，如長度、重量、速度、溫度等連續變量，如長度、重量、速度、溫度等l有序（有序（Ordinal）值變量）值變量等級變量，不可加，但可比，如一等、二等、三等級變量，不可加，但可比，如一等、二等、三等獎學金等獎學金l名詞性（名詞性（Nominal）變量）變量類別變量，不可加也不可比，如性別、職業等類別變量，不可加也不可比，如性別、職業等l下面介紹對各種不同類型的變量如何進行度量下面介紹對各種不同類型的變量如何進行度量第20頁度量對象間的相似與差異度量對象間的相似與差異l對象間的對象間的相似度相似度或或相異度相異度通?；诿繉ο箝g的距通?；诿繉ο箝g的距離的計算離的計算l歐幾里

11、得距離歐幾里得距離lMinkowski距離距離qppjxixjxixjxixjid)|.|(|),(2222211qqppqqjxixjxixjxixjid)|.|(|),(2211第21頁度量對象間的相似與差異度量對象間的相似與差異l曼哈頓距離曼哈頓距離(Block距離距離)l歐幾里得距離是當歐幾里得距離是當q=2時的時的Minkowski距離的特例距離的特例l曼哈頓距離是當曼哈頓距離是當q=1時的時的Minkowski距離的特例距離的特例l當當q=時得到無窮距離時得到無窮距離(無窮范數無窮范數)，由向量間各分量，由向量間各分量的最大差決定的最大差決定|.|),(2211ppjxixjxix

12、jxixjid第22頁度量對象間的相似與差異度量對象間的相似與差異l距離所應滿足的數學性質距離所應滿足的數學性質d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)l除此之外，還可以使用除此之外，還可以使用加權加權的距離的距離第23頁二元屬性變量二元屬性變量l二元變量只有兩種狀態：二元變量只有兩種狀態：0或或1例如給定描述患者的變量例如給定描述患者的變量smoker，1表示患者抽表示患者抽煙，煙，0表示不抽煙表示不抽煙l像處理一般數值量一樣來處理二元變量會產生誤導像處理一般數值量一樣來處理二元變量會產生誤導的聚類結果的聚類結果第24頁二元屬性變量的相依

13、表二元屬性變量的相依表l如果所有的二元變量具有相同的權重，則可以得到如果所有的二元變量具有相同的權重，則可以得到上表所示的兩行兩列的相依表上表所示的兩行兩列的相依表q是對象是對象i和和j值都為值都為1的變量的數目的變量的數目r是在對象是在對象i值為值為1，但對象，但對象j值為值為0的變量數目的變量數目變量的總數是變量的總數是p=q+r+s+tptrsqsumtstsrqrqsum0101Object iObject j第25頁對稱二元變量和非對稱二元變量對稱二元變量和非對稱二元變量l對二元變量的相異度計算還要考慮變量的對二元變量的相異度計算還要考慮變量的對稱性對稱性l對稱二元變量對稱二元變量如

14、果他的兩個狀態具有同等價值和相等的權重如果他的兩個狀態具有同等價值和相等的權重輸出用輸出用0或或1編碼沒有優先權，如性別編碼沒有優先權，如性別l對稱二元相異度對稱二元相異度tsrqsr jid),(第26頁對稱二元變量和非對稱二元變量對稱二元變量和非對稱二元變量l非對稱二元變量非對稱二元變量如果狀態的輸出不是同等重要的如果狀態的輸出不是同等重要的例如基本檢查的陽性和陰性結果。根據慣例，將例如基本檢查的陽性和陰性結果。根據慣例，將比較重要的輸出結果比較重要的輸出結果(通常也是出現機率較小的結通常也是出現機率較小的結果果)編碼為編碼為1，而將另一種結果編碼為，而將另一種結果編碼為0(如如HIV陰性

15、陰性)給定兩個非對稱二元變量，兩個都取值給定兩個非對稱二元變量，兩個都取值1的情況認的情況認為比兩個都取值為比兩個都取值0的情況更有意義的情況更有意義l非對稱二元相異度非對稱二元相異度srqsr jid),(第27頁對稱二元變量和非對稱二元變量對稱二元變量和非對稱二元變量l有時采用兩個二元變量的有時采用兩個二元變量的相似度相似度而不是而不是相異度相異度來測來測量他們之間的距離。量他們之間的距離。l非對稱二元相似度非對稱二元相似度sim(i,j)如下定義如下定義l系數系數sim(i,j)常稱作常稱作Jaccard系數系數),(1),(jidsrqq jisimJaccard第28頁例例 二元變量

16、之間的相異度二元變量之間的相異度l假設一個患者記錄表包含上述屬性，其中假設一個患者記錄表包含上述屬性，其中name是標是標識符，性別是對稱二元屬性，其余的屬性都是非對識符，性別是對稱二元屬性，其余的屬性都是非對稱二元屬性稱二元屬性l對于非對稱屬性，值對于非對稱屬性，值Y和和P(positive)置為置為1，值，值N(no或或negative)置為置為0第29頁例例 二元變量之間的相異度二元變量之間的相異度l假設對象之間的距離只基于非對稱變量來計算。根假設對象之間的距離只基于非對稱變量來計算。根據公式，三個患者據公式，三個患者Jack、Mary和和Jim兩兩之間的兩兩之間的相相異度異度如下：如下

17、：l度量顯示度量顯示Jim和和Mary不大可能患相似的疾病，而不大可能患相似的疾病，而Jack和和Mary最可能患相似的疾病最可能患相似的疾病75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd第30頁名詞性屬性變量名詞性屬性變量l可取多個相異值，之間沒有序關系可取多個相異值，之間沒有序關系l如產品顏色可以?。杭t、黃、綠、藍等如產品顏色可以?。杭t、黃、綠、藍等也可以用也可以用0，1，2，3等代碼來表示，但注意這里等代碼來表示，但注意這里的數字僅是標識，不能做運算的數字僅是標識，不能做運算l兩個對象兩個對象i和和j之間的相異度

18、簡單的處理方法是計算不之間的相異度簡單的處理方法是計算不匹配率：匹配率：其中其中p是全部變量的數目，是全部變量的數目，m是匹配的數目是匹配的數目l也可以構造一個大的二元變量數組，再按二元變量也可以構造一個大的二元變量數組，再按二元變量處理處理pmpjid),(第31頁余弦相似度余弦相似度l文檔數據文檔數據第32頁l 在信息檢索、文本文檔聚類和生物學分類中，需要在信息檢索、文本文檔聚類和生物學分類中，需要對包含了大量符號實體的復雜對象進行比較和聚類對包含了大量符號實體的復雜對象進行比較和聚類l為了測量復雜對象間的距離，通常期望放棄傳統的度為了測量復雜對象間的距離，通常期望放棄傳統的度量距離計算，

19、而引入量距離計算，而引入非度量非度量的相似度函數的相似度函數l 如果如果d1 和和 d2 是兩個文檔向量，則是兩個文檔向量，則 cos(d1,d2)=(d1 d2)/|d1|d2|,l 其中其中 表示向量的點積表示向量的點積(內積內積)，|d|表示向量的范表示向量的范數數.l問題：余弦相似度的范圍？取最大值時是否兩個向量問題：余弦相似度的范圍？取最大值時是否兩個向量相等？相等？余弦相似度余弦相似度第33頁余弦相似度計算的例子余弦相似度計算的例子ld1=3 2 0 5 0 0 0 2 0 0 ld2=1 0 0 0 0 0 0 1 0 2 ld1 d2 =3*1+2*0+0*0+5*0+0*0+

20、0*0+0*0+2*1+0*0+0*2=5l|d1|=(3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5=6.481l|d2|=(1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2)0.5=(6)0.5=2.245lcos(d1,d2)=5/(6.481*2.245).3150第34頁如何選擇恰當的度量如何選擇恰當的度量l有很多方法用來選擇一個具體的相似度或距離函數，有很多方法用來選擇一個具體的相似度或距離函數，但是還沒有一個通用的標準用來指導這樣的選擇但是還沒有一個通用的標準用來指導這樣的選擇l這種度量的選擇高

21、度依賴于具體的應用。這種度量的選擇高度依賴于具體的應用。第35頁主要聚類方法的分類主要聚類方法的分類l劃分方法劃分方法：給定：給定n個對象，劃分方法構建數據的個對象，劃分方法構建數據的k個個劃分，每個劃分表示一簇，劃分，每個劃分表示一簇，k=n，滿足如下要求，滿足如下要求每組至少包含一個對象每組至少包含一個對象每個對象必須只屬于一個組每個對象必須只屬于一個組(在軟聚類技術中可放在軟聚類技術中可放寬寬)l對于給定的劃分數目對于給定的劃分數目k，通常創建一個初始劃分，然，通常創建一個初始劃分，然后采用迭代方法嘗試通過對象在組間移動來改進劃后采用迭代方法嘗試通過對象在組間移動來改進劃分分第36頁主要

22、聚類方法的分類主要聚類方法的分類l好的劃分的標準：同一個簇中的對象之間盡可能相好的劃分的標準：同一個簇中的對象之間盡可能相似，不同簇的對象盡可能有大的差異似，不同簇的對象盡可能有大的差異l常用方法：常用方法：k均值方法：每個簇都用該簇中對象的均值來表示均值方法：每個簇都用該簇中對象的均值來表示k中心點法：每個簇用接近簇中心的一個對象來表中心點法：每個簇用接近簇中心的一個對象來表示示第37頁l層次方法創建給定數據對象的層次分解層次方法創建給定數據對象的層次分解l根據使用的方法，層次的方法可以分類為凝聚的或根據使用的方法，層次的方法可以分類為凝聚的或分裂的方法分裂的方法凝聚法：也稱自底向上的方法，

23、開始將每個對象凝聚法：也稱自底向上的方法，開始將每個對象形成單獨的組，然后逐次合并相近的對象或組，形成單獨的組，然后逐次合并相近的對象或組，直到所有的組合并為一個或滿足某個終止條件直到所有的組合并為一個或滿足某個終止條件分裂法：自頂向下的方法，一開始將所有對象置分裂法：自頂向下的方法，一開始將所有對象置于一個簇中，每次迭代，簇分裂為更小的簇，直于一個簇中，每次迭代，簇分裂為更小的簇，直到每個對象在一個簇中或滿足終止條件到每個對象在一個簇中或滿足終止條件層次方法層次方法第38頁基于模型的方法基于模型的方法l為每簇假定一個模型，并尋找數據對給定模型的最為每簇假定一個模型，并尋找數據對給定模型的最

24、佳擬合佳擬合l常見算法常見算法EM算法：基于統計模型并進行期望最大化分析算法：基于統計模型并進行期望最大化分析COBWEB：概念學習算法，進行概率分析并把概：概念學習算法，進行概率分析并把概念作為簇模型念作為簇模型SOM(自組織映射自組織映射)：一種基于神經網絡的算法，：一種基于神經網絡的算法，通過把高維數據映射到通過把高維數據映射到2維或維或3維特征空間進行聚維特征空間進行聚類類第39頁劃分聚類劃分聚類原始點原始點劃分聚類劃分聚類第40頁層次聚類層次聚類p4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3Traditional Hierarchical Cluster

25、ingNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram第41頁l互斥的與非互斥的互斥的與非互斥的在非互斥聚類中，點可以屬于多個簇在非互斥聚類中，點可以屬于多個簇.可以表示多重類或邊界類可以表示多重類或邊界類l模糊聚類與非模糊聚類模糊聚類與非模糊聚類模糊聚類中，一個點到隸屬于每個簇的情況可模糊聚類中，一個點到隸屬于每個簇的情況可以用一個在以用一個在0到到1之間的隸屬度描述之間的隸屬度描述其他的聚類類型的差別其他的聚類類型的差別第42頁不同的簇類型不同的簇類型l明顯分離的簇

26、明顯分離的簇l基于中心的簇基于中心的簇l基于近鄰的簇基于近鄰的簇l基于密度的簇基于密度的簇l概念簇概念簇第43頁不同的簇類型不同的簇類型l明顯分離的簇明顯分離的簇:每個點到同簇中任意點的距離比到不同簇中所每個點到同簇中任意點的距離比到不同簇中所有點的距離更近有點的距離更近3 個明顯分離的簇個明顯分離的簇第44頁不同的簇類型不同的簇類型l基于中心的簇基于中心的簇 每個點到其簇中心的距離比到任何其他簇中心每個點到其簇中心的距離比到任何其他簇中心的距離更近的距離更近 簇的中心通常是重心，簇中所有點的平均值，簇的中心通常是重心，簇中所有點的平均值，或者是簇的原型，即一個簇中最具代表性的點或者是簇的原型

27、，即一個簇中最具代表性的點4 center-based clusters第45頁不同的簇類型不同的簇類型l基于近鄰的簇基于近鄰的簇(基于圖的基于圖的連通分支連通分支)每個點到該簇中至少一個點的距離比到不同簇每個點到該簇中至少一個點的距離比到不同簇中任意點的距離更近中任意點的距離更近8 contiguous clusters第46頁不同的簇類型不同的簇類型l基于密度的簇基于密度的簇簇是被低密度區域分開的高密度區域簇是被低密度區域分開的高密度區域.當簇不規則或互相盤繞，并且有噪聲和離群點當簇不規則或互相盤繞，并且有噪聲和離群點時，通常使用基于密度的簇定義時，通常使用基于密度的簇定義6 densit

28、y-based clusters第47頁劃分方法劃分方法l對于一個給定的對于一個給定的n個對象或元組的數據庫，采用目標個對象或元組的數據庫，采用目標函數最小化的策略，通過迭代把數據分成函數最小化的策略，通過迭代把數據分成k個劃分塊，個劃分塊，每個劃分塊為一個簇，這就是劃分方法。每個劃分塊為一個簇，這就是劃分方法。l劃分方法滿足兩個條件：劃分方法滿足兩個條件：（1）每個分組至少包含一個對象；）每個分組至少包含一個對象；（2）每個對象必屬于且僅屬于某一個分組。）每個對象必屬于且僅屬于某一個分組。l常見的劃分方法有常見的劃分方法有k-均值方法和均值方法和k-中心點方法。其他中心點方法。其他方法大都是

29、這兩種方法的變形。方法大都是這兩種方法的變形。第48頁k-均值算法均值算法 lk-均值聚類算法的核心思想是通過迭代把數據對象劃均值聚類算法的核心思想是通過迭代把數據對象劃分到不同的簇中，以求分到不同的簇中，以求目標函數目標函數最小化，從而使生最小化，從而使生成的簇盡可能地緊湊和獨立。成的簇盡可能地緊湊和獨立。隨機選取隨機選取k個對象作為初始的個對象作為初始的k個簇的質心；個簇的質心；將其余對象根據其與各個簇質心的距離分配到最將其余對象根據其與各個簇質心的距離分配到最近的簇；再求新形成的簇的質心。近的簇；再求新形成的簇的質心。這個迭代重定位過程不斷重復，直到目標函數最這個迭代重定位過程不斷重復，

30、直到目標函數最小化為止。小化為止。第49頁k-均值算法均值算法 算法算法K均值均值輸入輸入K：簇的數目：簇的數目D：包含：包含n個對象的點集個對象的點集輸出輸出K個簇的集合個簇的集合方法方法1從從D中任意選擇中任意選擇K個點作為初始簇中心個點作為初始簇中心2Repeat3根據簇中對象的均值，將每個對象再指派到最相似的簇根據簇中對象的均值，將每個對象再指派到最相似的簇4更新簇均值，即計算每個簇中對象的均值更新簇均值，即計算每個簇中對象的均值5Until 不再發生變化不再發生變化第50頁-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-

31、0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6初始質心的選擇非常重要初始質心的選擇非常重要第51頁-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-

32、2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6使用使用K均值算法的迭代過程均值算法的迭代過程第52頁K-K-均值算法均值算法 01234567891001234567891001

33、2345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign第53頁歐幾里得空間中的數據歐幾里得空間中的數據l通常使用誤差的平方和通常使用誤差的平方

34、和(sum of the squared error,SSE)作為度量聚類質量的目標函數作為度量聚類質量的目標函數lSSE也稱散布也稱散布(scatter)：計算每個數據點的誤差：計算每個數據點的誤差即它到最近質心的歐幾里得距離，然后計算誤差的即它到最近質心的歐幾里得距離，然后計算誤差的 平方和平方和l給定由兩次運行給定由兩次運行K均值產生的兩個不同的簇集，我們均值產生的兩個不同的簇集，我們更喜歡誤差的平方和最小的那個，這意味著聚類的更喜歡誤差的平方和最小的那個，這意味著聚類的 原型原型(質心質心)是簇中點的更好代表是簇中點的更好代表KiCxiixmdistSSE12),(第54頁歐幾里得空間

35、中的數據歐幾里得空間中的數據l可以證明在歐幾里得空間中是簇的可以證明在歐幾里得空間中是簇的SSE最小的質心最小的質心 就是均值就是均值lK均值算法的第均值算法的第3步和第步和第4步試圖直接最小化步試圖直接最小化SSE步驟步驟3通過將點指派到最近的質心形成簇，最小化通過將點指派到最近的質心形成簇，最小化關于給定質心集的關于給定質心集的SSE步驟步驟4重新計算質心，進一步最小化重新計算質心，進一步最小化SSEl問題：問題：K均值的步驟均值的步驟3和和4只能找到關于只能找到關于SSE的的局部最局部最小值小值，因為它們是對選定的質心和簇，而不是對，因為它們是對選定的質心和簇，而不是對 所所有可能的選擇

36、來優化有可能的選擇來優化SSE第55頁-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5初始質心的選擇非常重要初始質心的選擇非常重要第56頁-2-1.5-1-0.500.511.5

37、200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5初始質心的選擇非常重要初始質心的選擇非常重要第57頁隨機初始化隨機初始化l由于由于K均值算法會陷入局部最小值而得到次優聚類，均值算法會陷入局部最小值而得到次優聚類，一種常

38、用的選取初始質心的方法是多次運行，每次一種常用的選取初始質心的方法是多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小使用一組不同的隨機初始質心，然后選取具有最小SSE的簇集的簇集l下面我們看一看這種方法的問題下面我們看一看這種方法的問題l下頁的圖中有下頁的圖中有5個簇對，每個簇對有上下兩個簇。個簇對，每個簇對有上下兩個簇。如果每個簇對有兩個初始質心，則效果較好如果每個簇對有兩個初始質心，則效果較好如果有一個簇對中只有一個初始中心，而另一個如果有一個簇對中只有一個初始中心，而另一個簇對中有三個初始中心，則會出現錯誤。簇對中有三個初始中心，則會出現錯誤。第58頁05101520-6-4-

39、202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4Starting with two initial centroids in one cluster of each pair of clusters5個簇對，個簇對，10個簇的例子個簇的例子第59頁05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xy

40、Iteration 305101520-6-4-202468xyIteration 4Starting with two initial centroids in one cluster of each pair of clusters5個簇對，個簇對，10個簇的例子個簇的例子第60頁Starting with some pairs of clusters having three initial centroids,while other have only one.05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration

41、205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 45個簇對，個簇對，10個簇的例子個簇的例子第61頁Starting with some pairs of clusters having three initial centroids,while other have only one.05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468x

42、yIteration 45個簇對，個簇對，10個簇的例子個簇的例子第62頁解決初始質心設置問題的方法解決初始質心設置問題的方法l多次運行多次運行不一定總有效不一定總有效l對數據作采樣并使用層次聚類，從中提取對數據作采樣并使用層次聚類，從中提取K個簇并使個簇并使用這些簇的質心作為初始質心用這些簇的質心作為初始質心l選取多于選取多于k個的初始質心，然后從其中選擇個的初始質心，然后從其中選擇k個個最分離的最分離的k個點個點l后處理后處理l二分二分K-均值均值第63頁二分二分K均值均值l基本思想：基本思想：l為了得到為了得到K個簇，將所有點的集合分裂成兩個簇，從個簇，將所有點的集合分裂成兩個簇，從這些

43、簇中選取一個繼續分裂，如此下去直到產生這些簇中選取一個繼續分裂，如此下去直到產生K個個簇簇l可以使用多種方法選擇待分裂的簇可以使用多種方法選擇待分裂的簇最大的簇最大的簇具有最大具有最大SSE的簇的簇基于大小和基于大小和SSEl二分二分K均值得到的最終的簇集并不代表使均值得到的最終的簇集并不代表使SSE局部最局部最小的聚類小的聚類第64頁二分二分K均值算法均值算法算法算法二分二分K均值均值1初始化簇表，使之包含有所有的點組成的簇初始化簇表，使之包含有所有的點組成的簇2Repeat3從簇表中取出一個簇從簇表中取出一個簇4對選定的簇進行多次二分試驗對選定的簇進行多次二分試驗5for i=1 to 試

44、驗次數試驗次數 do6 使用基本使用基本K均值，二分選定的簇均值，二分選定的簇7end for8從二分試驗中選擇具有最小總從二分試驗中選擇具有最小總SSE的兩個簇的兩個簇9將這兩個簇添加到簇表中將這兩個簇添加到簇表中10until 簇表中包含簇表中包含K個簇個簇第65頁二分二分K-均值的例子均值的例子第66頁K-均值方法的缺陷均值方法的缺陷lK-均值方法當簇在下述方面有較大不同時會出現問均值方法當簇在下述方面有較大不同時會出現問題題 不同大小不同大小不同密度不同密度非球形的形狀非球形的形狀第67頁Original PointsK-means(3 Clusters)K-均值的缺陷：不同的簇大小均

45、值的缺陷：不同的簇大小WHY？第68頁Original PointsK-means(3 Clusters)K-均值的缺陷均值的缺陷不同的密度分布不同的密度分布WHY？第69頁Original PointsK-means(2 Clusters)K均值的缺陷：非球形形狀均值的缺陷：非球形形狀K均值目標函數是最小化等尺度和等密度的球形簇，或明顯分均值目標函數是最小化等尺度和等密度的球形簇，或明顯分離的簇離的簇第70頁Original PointsK-means Clusters一種方法是使用更多的簇，再反過來使其部分合并一種方法是使用更多的簇，再反過來使其部分合并克服克服K均值方法的缺陷均值方法的缺

46、陷第71頁Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷第72頁Original PointsK-means Clusters克服克服K均值方法的缺陷均值方法的缺陷第73頁層次聚類方法層次聚類方法l定義：對給定的數據進行層次的分解：定義：對給定的數據進行層次的分解：l凝聚的（凝聚的（agglomerative）方法（自底向上）方法（自底向上）思想：一開始將每個對象作為單獨的一組，然后思想：一開始將每個對象作為單獨的一組，然后根據同類相近，異類相異的原則，合并對象，直根據同類相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終

47、止條件為到所有的組合并成一個，或達到一個終止條件為止。止。l分裂的方法（分裂的方法（divisive）（自頂向下）（自頂向下）思想：一開始將所有的對象置于一類，在迭代的思想：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。個對象在單獨的一個類中，或達到一個終止條件。第74頁凝聚的和分裂的層次聚類凝聚的和分裂的層次聚類 a,b,c,d,e c,d,e d,e a,b e d c b a 第 4 步 第 3 步 第 2 步 第 1 步 第 0 步 凝聚的（AGENS）第 0 步 第

48、1 步 第 2 步 第 3 步 第 4 步 分裂的（DIANA）第75頁層次聚類方法層次聚類方法l產生一個相鄰簇的集合，通常用一棵樹來表示產生一個相鄰簇的集合，通常用一棵樹來表示lCan be visualized as a dendrogram樹狀圖記錄了分裂或合并的序列樹狀圖記錄了分裂或合并的序列13254600.050.10.150.212345612345以樹狀圖和嵌套簇圖顯示的以樹狀圖和嵌套簇圖顯示的4個點的層次聚類個點的層次聚類第76頁層次聚類法的特點層次聚類法的特點l不用預知不用預知(預設預設)簇的數目簇的數目任何需要簇數的聚類可以通過在樹狀圖的適當層任何需要簇數的聚類可以通過在

49、樹狀圖的適當層次切割而得到次切割而得到l得到更有意義的結構得到更有意義的結構如生物學中的分類如生物學中的分類l傳統的層次聚類算法使用相似度矩陣或距離矩陣傳統的層次聚類算法使用相似度矩陣或距離矩陣每次合并或分裂一個簇每次合并或分裂一個簇第77頁1 計算距離矩陣計算距離矩陣2 令每個點為一個簇令每個點為一個簇3 Repeat4 合并最接近的兩個簇合并最接近的兩個簇5 更新距離矩陣更新距離矩陣6 until 僅剩下一個簇僅剩下一個簇基本凝聚層次聚類算法基本凝聚層次聚類算法第78頁l關鍵步驟在于計算兩個簇之間的鄰近度關鍵步驟在于計算兩個簇之間的鄰近度 不同的定義簇之間的距離的方法區分了不同的不同的定義

50、簇之間的距離的方法區分了不同的算法算法基本凝聚層次聚類算法基本凝聚層次聚類算法第79頁開始開始.l每個點為一個簇，計算各個簇兩兩之間的距離矩陣每個點為一個簇，計算各個簇兩兩之間的距離矩陣p1p3p5p4p2p1p2p3p4p5.距離矩陣距離矩陣第80頁接下來接下來.l經過若干凝聚步驟，得到如下的簇經過若干凝聚步驟，得到如下的簇 C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距離矩陣距離矩陣第81頁接下來接下來.l合并兩個最靠近的簇合并兩個最靠近的簇(C2 和和 C5)并更新距離矩陣并更新距離矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距離矩陣距離矩陣第82頁合

51、并后合并后l問題變為如何更新距離矩陣問題變為如何更新距離矩陣C1C4C2 U C5C3?C2 U C5C1C1C3C4C2 U C5C3C4距離矩陣距離矩陣第83頁 p1p3p5p4p2p1p2p3p4p5.距離距離lMIN(單鏈單鏈)lMAX(全鏈全鏈)lGroup Average(組平均組平均)l質心的距離質心的距離l其他的源自目標函數的方法其他的源自目標函數的方法Ward方法使用平方差方法使用平方差距離矩陣距離矩陣如何定義簇之間的鄰近度如何定義簇之間的鄰近度第84頁 p1p3p5p4p2p1p2p3p4p5.距離矩陣距離矩陣lMIN(單鏈單鏈)lMAX(全鏈全鏈)lGroup Avera

52、ge(組平均組平均)l質心的距離質心的距離l其他的源自目標函數的方法其他的源自目標函數的方法Ward方法使用平方差方法使用平方差如何定義簇之間的鄰近度如何定義簇之間的鄰近度第85頁 p1p3p5p4p2p1p2p3p4p5.距離矩陣距離矩陣lMIN(單鏈單鏈)lMAX(全鏈全鏈)lGroup Average(組平均組平均)l質心的距離質心的距離l其他的源自目標函數的方法其他的源自目標函數的方法Ward方法使用平方差方法使用平方差如何定義簇之間的鄰近度如何定義簇之間的鄰近度第86頁 p1p3p5p4p2p1p2p3p4p5.距離矩陣距離矩陣lMIN(單鏈單鏈)lMAX(全鏈全鏈)lGroup A

53、verage(組平均組平均)l質心的距離質心的距離l其他的源自目標函數的方法其他的源自目標函數的方法Ward方法使用平方差方法使用平方差如何定義簇之間的鄰近度如何定義簇之間的鄰近度第87頁 p1p3p5p4p2p1p2p3p4p5.距離矩陣距離矩陣 lMIN(單鏈單鏈)lMAX(全鏈全鏈)lGroup Average(組平均組平均)l質心的距離質心的距離l其他的源自目標函數的方法其他的源自目標函數的方法Ward方法使用平方差方法使用平方差如何定義簇之間的鄰近度如何定義簇之間的鄰近度第88頁MIN或單鏈或單鏈l兩個簇之間的鄰近度基于兩個簇中最近的兩個點的兩個簇之間的鄰近度基于兩個簇中最近的兩個點

54、的距離距離由一個點對決定，或者說由圖中的一條鏈決定由一個點對決定，或者說由圖中的一條鏈決定I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345第89頁Nested ClustersDendrogram1234561234536254100.050.10.150.2層次聚類層次聚類:MIN第90頁Original PointsTwo Clusters可

55、以處理非橢圓的形狀可以處理非橢圓的形狀MIN的優點的優點第91頁Original PointsTwo Clusters 對噪聲點和離群點很敏感對噪聲點和離群點很敏感MIN的不足的不足第92頁MAX或全鏈或全鏈l兩個簇之間的鄰近度由兩個簇間最不相似的兩個簇之間的鄰近度由兩個簇間最不相似的(最大距最大距離的離的)點對決定點對決定由兩個簇中所有的點對決定由兩個簇中所有的點對決定I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00

56、 0.80I5 0.20 0.50 0.30 0.80 1.0012345第93頁Nested ClustersDendrogram36412500.050.10.150.20.250.30.350.412345612534MAX或全鏈或全鏈第94頁Original PointsTwo Clusters對噪聲點和離群點不太敏感對噪聲點和離群點不太敏感MAX的優點的優點第95頁Original PointsTwo Clusters傾向于分裂大的簇傾向于分裂大的簇傾向于球狀的簇傾向于球狀的簇MAX的不足的不足第96頁組平均組平均l兩個簇的鄰近度定義為不同簇的所有點對的平均逐對鄰近度兩個簇的鄰近度定

57、義為不同簇的所有點對的平均逐對鄰近度lNeed to use average connectivity for scalability since total proximity favors large clusters|Cluster|Cluster)p,pproximity()Cluster,Clusterproximity(jiClusterpClusterpjijijjiiI1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.4

58、0 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345第97頁Nested ClustersDendrogram36412500.050.10.150.20.2512345612534組平均組平均第98頁組平均組平均l是單鏈和全鏈之間的一個折中，該法利用了所有樣是單鏈和全鏈之間的一個折中，該法利用了所有樣本的信息，被認為是較好的層次聚類法本的信息，被認為是較好的層次聚類法l優點優點 對噪聲和離群點不太敏感對噪聲和離群點不太敏感l不足不足 傾向于球狀的簇傾向于球狀的簇第99頁 Ward方法和質心方法方法和質心方法l兩個簇的鄰近度定義為兩個簇合并時導致的平方誤兩個簇

59、的鄰近度定義為兩個簇合并時導致的平方誤差的增量，該方法使用的目標函數與差的增量，該方法使用的目標函數與K均值相同均值相同可以證明，當取距離的平方作為兩個點間的鄰近可以證明，當取距離的平方作為兩個點間的鄰近度時，度時，Ward方法與組平均方法相似方法與組平均方法相似l對噪聲和離群點不太敏感對噪聲和離群點不太敏感l傾向于球狀的簇傾向于球狀的簇l可以用來初始化可以用來初始化K均值方法均值方法第100頁層次聚類法：比較層次聚類法：比較Group AverageWards Method12345612534MINMAX123456125341234561253412345612345第101頁lO(N2

60、)空間復雜度，因為要存儲鄰近度矩陣，空間復雜度，因為要存儲鄰近度矩陣，N為點為點的數目的數目l最壞情況下最壞情況下O(N3)的時間復雜度的時間復雜度共有共有N步，在每一步中要更新和搜索步，在每一步中要更新和搜索N2規模的鄰規模的鄰近度矩陣近度矩陣在某些算法中可以接近在某些算法中可以接近O(N2 log(N)的時間復雜的時間復雜度度層次聚類：時間和空間復雜度層次聚類：時間和空間復雜度第102頁層次聚類方法的優缺點層次聚類方法的優缺點l層次聚類方法的優點在于可以在不同粒度水平上對層次聚類方法的優點在于可以在不同粒度水平上對數據進行探測，而且容易實現相似度量或距離度量。數據進行探測，而且容易實現相似

61、度量或距離度量。l單純的層次聚類算法終止條件含糊，而且執行合并單純的層次聚類算法終止條件含糊，而且執行合并或分裂簇的操作后不可修正，這很可能導致聚類結或分裂簇的操作后不可修正，這很可能導致聚類結果質量很低。果質量很低。l通?？紤]把層次聚類方法與其他方法（如迭代重定通?？紤]把層次聚類方法與其他方法（如迭代重定位方法）相結合來解決實際聚類問題。位方法）相結合來解決實際聚類問題。第103頁lDBSCAN是一種基于密度的聚類算法是一種基于密度的聚類算法 密度密度=給定半徑給定半徑(Eps)內點的數目內點的數目 核心點核心點(core point)在半徑在半徑Eps的鄰域內擁有的鄰域內擁有多于特定數目多

62、于特定數目(MinPts)的鄰點的點，在基于密的鄰點的點，在基于密度的簇內部的點度的簇內部的點 邊界點邊界點(border point)在半徑在半徑Eps的鄰域內擁的鄰域內擁有多于特定數目有多于特定數目(MinPts)的鄰點的點，但是落的鄰點的點，但是落在某個核心點的鄰域內在某個核心點的鄰域內 噪聲點噪聲點(noise point)既非核心點也非邊界點既非核心點也非邊界點的任何點的任何點基于密度的聚類：基于密度的聚類：DBSCAN第104頁DBSCAN:核心點，邊界點和噪聲點核心點，邊界點和噪聲點第105頁DBSCAN 算法算法l算法算法1：將所有點標記為核心點、邊界點或噪聲點：將所有點標記為

63、核心點、邊界點或噪聲點2：刪除噪聲點：刪除噪聲點3：為距離在：為距離在Eps之內的所有核心點之間賦予一條之內的所有核心點之間賦予一條邊邊4：每組連通的核心點形成一個簇：每組連通的核心點形成一個簇將每個邊界點指派到一個與之關聯的核心點的簇將每個邊界點指派到一個與之關聯的核心點的簇中中第106頁原始點原始點點的類型點的類型:核心核心,邊界邊界 和和噪聲噪聲Eps=10,MinPts=4DBSCAN 算法算法第107頁原始點原始點得到的簇得到的簇 對噪聲不敏感對噪聲不敏感 可以處理不同形狀和大小的簇可以處理不同形狀和大小的簇當當DBSCAN工作良好時工作良好時第108頁原始點集原始點集(MinPts

64、=4,Eps=9.75).(MinPts=4,Eps=9.92)變密度的簇變密度的簇 對高維數據計算量巨大對高維數據計算量巨大當當DBSCAN工作不佳時工作不佳時第109頁l基本方法：觀察點到它的基本方法：觀察點到它的k個最近鄰的距離個最近鄰的距離(稱作稱作k-距離距離)。對于屬于某個簇的點，如果。對于屬于某個簇的點，如果k不大于簇不大于簇的大小的話，則的大小的話，則k-距離將很接近距離將很接近l噪聲點由于不在簇中，其噪聲點由于不在簇中，其k-距離將相對較大距離將相對較大l對于某個對于某個k，計算所有點的，計算所有點的k-距離，以遞增次序將距離，以遞增次序將它們排序，然后繪制排序后的值，則預期

65、會看到它們排序，然后繪制排序后的值，則預期會看到k-距離的急劇變化處對應于合適的距離的急劇變化處對應于合適的Eps值值DBSCAN算法算法:確定確定EPS和和 MinPts第110頁DBSCAN算法算法:確定確定EPS和和 MinPts第111頁簇評估簇評估 l對于有監督的分類，我們可以有多種方式評價模型對于有監督的分類，我們可以有多種方式評價模型的優劣的優劣準確度準確度,精度精度,召回率召回率l對于聚類分析對于聚類分析,相應的問題是如何評價聚類結果是否相應的問題是如何評價聚類結果是否是是“好好”的的l評估簇的目的評估簇的目的避免尋找噪聲中的模式避免尋找噪聲中的模式比較不同的聚類算法比較不同的

66、聚類算法比較兩個聚類的結果比較兩個聚類的結果比較兩個簇比較兩個簇第112頁在隨機數據中發現的簇在隨機數據中發現的簇00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy100個個隨機分隨機分布的點布的點00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyK-均值均值00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyDBSCAN00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy全鏈聚類全鏈聚類第113頁1.確定數據的聚類趨勢確定數據的聚類趨勢(clustering tendency),即即識別數據中是否實際存在非隨機結構識別數據中是否實際存在非隨機結構.2.比較聚類分析的結果與通過外部知識得到的類標比較聚類分析的結果與通過外部知識得到的類標(確定正確的簇個數確定正確的簇個數).3.評估聚類分析的結果在不引用附加信息的情況下評估聚類分析的結果在不引用附加信息的情況下是否能較好擬合數據是否能較好擬合數據.4.比較兩個不同的聚類結果的優劣比較