聚類方法聚類方法聚類屬于無監(jiān)督學(xué)習(xí)問題，目標(biāo)是確定每個(gè)樣本所屬的類別，這里的類別不是人工預(yù)定好的，而是由聚類算法確定的。無標(biāo)注數(shù)據(jù)針對(duì)給定的樣本，根據(jù)它們特征的相似度或距離，將其歸并到若干個(gè)“類”或“簇”的數(shù)據(jù)分析問題相似的樣本聚集在相同的類，不相似的樣本分散在不同的類01聚類的基本概念一：相似度或距離聚類的對(duì)象是觀測(cè)數(shù)據(jù)或樣本集合假設(shè)有n個(gè)樣本，每個(gè)樣本由m個(gè)屬性的特征向量組成樣本集合可以用矩陣X表示01聚類的基本概念聚類的核心概念是相似度或距離，有多種相似度或距離的定義。因?yàn)樗鼈冎苯佑绊懢垲惖慕Y(jié)果，所以其選擇是聚類的根本問題。具體哪種更適合取決于應(yīng)用問題的特性在聚類中，可以將樣本集合看作是向量空間中點(diǎn)的集合，以該空間的距離表示樣本之間的相似度01聚類的基本概念1.閔可夫斯基距離閔可夫斯基距離越大相似度越小，距離越小相似度越大。定義14.1給定樣本集合X,X是m維實(shí)數(shù)向量空間Rm中點(diǎn)的集合，其中01聚類的基本概念樣本xi與樣本xj的閔可夫斯基距離（Minkowskidistance）定義為01聚類的基本概念當(dāng)p=2時(shí)稱為歐氏距離當(dāng)p=1時(shí)稱為曼哈頓距離當(dāng)p=時(shí)稱為切比雪夫距離01聚類的基本概念2.馬哈拉諾比斯距離簡(jiǎn)稱馬氏距離，是另一種常用的相似度。距離越大相似度越小，距離越小相似度越大定義14.2給定一個(gè)樣本集合X，其協(xié)方差矩陣記作S。樣本xi與樣本xj之間的馬哈拉諾比斯距離dij定義為01聚類的基本概念當(dāng)S為單位矩陣時(shí)，即樣本數(shù)據(jù)的各個(gè)分量相互獨(dú)立且各個(gè)分量的方差為1時(shí)，馬氏距離就是歐氏距離，所以馬氏距離是歐氏距離的推廣01聚類的基本概念3.相關(guān)系數(shù)樣本之間的相似度也可以用相關(guān)系數(shù)（correlationcoefficient）來表示。相關(guān)系數(shù)的絕對(duì)值越接近于1，表示樣本越相似越接近于0，表示樣本越不相似。14.3樣本xi與樣本xj之間的相關(guān)系數(shù)定義為01聚類的基本概念4.夾角余弦樣本之間的相似度也可以用夾角余弦（cosine）來表示。夾角余弦越接近于1，表示樣本越相似越接近于0，表示樣本越不相似。定義14.4樣本xi與樣本xj之間的夾角余弦定義為01聚類的基本概念由上定義可以看出用距離度量相似度時(shí)，距離越小樣本越相似用相關(guān)系數(shù)時(shí)，相關(guān)系數(shù)越大樣本越相似注意不同相似度度量得到的結(jié)果并不一定一致從右圖可以看出，如果從距離的角度看，A和B比A和C更相似但從相關(guān)系數(shù)的角度看，A和C比A和B更相似。01聚類的基本概念二:類或簇通過聚類得到的類或簇，本質(zhì)是樣本的子集。用G表示類或簇（cluster)，用xi,xj表示類中的樣本，用nG表示G中樣本的個(gè)數(shù)，用dij表示樣本xi與樣本xj之間的距離。類或簇有多種定義，下面給出幾個(gè)常見的定義。定義14.501聚類的基本概念以上四個(gè)定義，第一個(gè)定義最常用，并且由它可以推出其他三個(gè)定義01聚類的基本概念類的特征可以通過不同角度來刻畫，常用的特征有下面三種1.類的均值，又稱類的中心nG是類G的樣本個(gè)數(shù)2.類的直徑：類中任意兩個(gè)樣本之間的最大距離01聚類的基本概念3.類的樣本散布矩陣與樣本協(xié)方差矩陣類的樣本散布矩陣樣本協(xié)方差矩陣01聚類的基本概念三、類與類之間的距離類與類之間的距離，也稱為連接。類與類之間的距離也有多種定義1.最短距離或單連接定義類Gp的樣本與Gq的樣本之間的最短距離為兩類之間的距離01聚類的基本概念2.最長(zhǎng)距離或完全連接定義類Gp的樣本與Gq的樣本之間的最長(zhǎng)距離為兩類之間的距離3.中心距離定義類Gp與Gq的中心與之間的距離為兩類之間的距離01聚類的基本概念4.平均距離定義類Gp與Gq任意兩個(gè)樣本之間距離的平均值為兩類之間的距離02常見的聚類算法（1）連通性聚類。典型的代表是層次聚類算法，它是根據(jù)樣本之間的連通性來構(gòu)建簇，所有連通的樣本屬于同一簇。（2）基于概率分布的聚類。這種算法假設(shè)每種類型的樣本服從某一概率分布，如多維正態(tài)分布，典型的代表是EM算法。（3）基于圖的算法。這類算法用樣本點(diǎn)構(gòu)造出帶權(quán)重的無向圖，每個(gè)樣本是圖中的一個(gè)頂點(diǎn)，然后使用圖論中的方法完成聚類02常見的聚類算法（4）基于質(zhì)心的聚類。典型的代表是k均值算法，它用類中心向量來表示一個(gè)簇，樣本所屬的簇由它到每個(gè)簇的中心向量的距離確定（5）基于密度的聚類。典型的代表是DBSCAN算法、OPTICS算法和均值漂移（MeanShift）算法，它們將簇定義為空間中樣本密集的區(qū)域02--1連通性聚類：層次聚類層次聚類假設(shè)類別之間存在層次結(jié)構(gòu)，將樣本聚到層次化的類中層次聚類又有聚合或自下而上聚類、分裂（divisive）或自上而下聚類兩種方法。因?yàn)槊總€(gè)樣本只屬于一個(gè)類，所以層次聚類屬于硬聚類當(dāng)不知道應(yīng)該分為幾類時(shí)，使用層次聚類比較適合。02--1連通性聚類：層次聚類層次聚類會(huì)構(gòu)建一個(gè)多層嵌套的分類，類似一個(gè)樹狀結(jié)構(gòu)。可以選擇一個(gè)聚類數(shù)量，根據(jù)需求對(duì)樹狀圖中畫一條水平線,得到對(duì)應(yīng)的聚類。02--1連通性聚類：層次聚類聚合聚類開始將每個(gè)樣本各自分到一個(gè)類然后按照一定的規(guī)則，例如類間距離最小，將滿足規(guī)則條件的兩個(gè)類進(jìn)行合并，建立一個(gè)新的類如此反復(fù)進(jìn)行，每次減少一個(gè)類，直到滿足停止條件02--1連通性聚類：層次聚類聚合聚類需要預(yù)先確定下面三個(gè)要素距離或相似度閔可夫斯基距離馬哈拉諾比斯距離相關(guān)系數(shù)夾角余弦合并規(guī)則類間距離最小類間距離可以是最短距離、最長(zhǎng)距離、中心距離、平均距離停止條件停止條件可以是類的個(gè)數(shù)達(dá)到閉值（極端情況類的個(gè)數(shù)是1)類的直徑超過閡值02--1連通性聚類：層次聚類根據(jù)這些要素的不同組合，就可以構(gòu)成不同的聚類方法如果我們采用歐氏距離為樣本之間距離類間距離最小為合并規(guī)則。類間距離選擇最短距離所有樣本聚為一類為停止條件那么聚合聚類的算法如下：02--1連通性聚類：層次聚類算法14.1（聚合聚類算法）02--1連通性聚類：層次聚類下面通過一個(gè)例子說明聚合層次聚類算法給定5個(gè)樣本的集合，樣本之間的歐氏距離由如下矩陣D表示其中dij表示第i個(gè)樣本與第j個(gè)樣本之間的歐氏距離顯然D為對(duì)稱矩陣。應(yīng)用聚合層次聚類法對(duì)這5個(gè)樣本進(jìn)行聚類。02--1連通性聚類：層次聚類（1）首先用5個(gè)樣本構(gòu)建5個(gè)類，于是樣本之間的距離也就變成類之間的距離，所以5個(gè)類之間的距離矩陣亦為D（2）由矩陣D可以看出， 為最小，所以把G3和G5合并為一個(gè)新類，記作02--1連通性聚類：層次聚類（3）計(jì)算G6與G1,G2,G4之間的最短距離，有最短距離：Gp的樣本與Gq的樣本之間的最短距離02--1連通性聚類：層次聚類又注意到其余兩類之間的距離是顯然，D61=2最小，所以將G1與G6合并成一個(gè)新類，記作02--1連通性聚類：層次聚類（4）計(jì)算G7與G2,G4之間的最短距離，又注意到顯然，其中D24=4最小，所以將G2與G4合并成一個(gè)新類，記作02--1連通性聚類：層次聚類（5）將G7與G8合并成一個(gè)新類，記作即將全部樣本聚成1類，聚類終止02--1連通性聚類：層次聚類02--1連通性聚類：層次聚類02--1連通性聚類：層次聚類分裂聚類開始將所有樣本分到一個(gè)類之后將已有類中相距最遠(yuǎn)的樣本分到兩個(gè)新的類重復(fù)此操作直到滿足停止條件得到層次化的類別02--1連通性聚類：層次聚類02--2基于概率分布的聚類：EM算法例子：小明是一名語文老師，有一次考試結(jié)束了，需要統(tǒng)計(jì)兩個(gè)班級(jí)同學(xué)的成績(jī)但是這兩個(gè)班同學(xué)的成績(jī)由于某些原因，沒有名字和班級(jí)，而是相互混合那能不能猜一猜這些成績(jī)里面，哪些是一班的？哪些是二班的呢？02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法

02--2基于概率分布的聚類：EM算法現(xiàn)在我們來回歸一下高斯混合模型首先使用高斯混合模型的時(shí)候，我們并沒有使用點(diǎn)的類別來學(xué)習(xí)模型參數(shù)，或者說我們使用的是無標(biāo)注數(shù)據(jù)所以它是一個(gè)無監(jiān)督的分類模型對(duì)于這個(gè)模型來說，EM算法中的E步驟是用來預(yù)測(cè)每個(gè)數(shù)據(jù)點(diǎn)屬于不同類別的概率M步驟就是利用估計(jì)的分類，去更新每個(gè)高斯分布的參數(shù)（均值和方差）以及當(dāng)前類別的先驗(yàn)概率重復(fù)以上兩個(gè)步驟，直到分布收斂02--2基于概率分布的聚類：EM算法需要注意的是：EM算法根據(jù)不同的初始化，可能會(huì)得到不同的結(jié)果所以選擇初始化方案，也是非常重要的02--3基于圖的算法：譜聚類算法基于圖的算法，把樣本數(shù)據(jù)看作圖的頂點(diǎn)，根據(jù)數(shù)據(jù)點(diǎn)之間的距離構(gòu)造邊，形成帶權(quán)重的圖邊一定程度上可以表示兩個(gè)樣本之間的聯(lián)系它借助圖進(jìn)行聚類。帶權(quán)重的無向圖權(quán)重怎么取？用相似度來表示相似度矩陣如果兩個(gè)子圖之間沒有邊連接，則這值是002--3基于圖的算法：譜聚類算法怎么利用圖進(jìn)行聚類呢？分割將圖切分成多