目錄什么是聚類距離度量方法幾種常見的聚類方法練習第1頁/共48頁目錄什么是聚類第1頁/共48頁1概述監督學習（supervisedlearning）無監督學習（unsupervisedlearning）半監督學習（Semi-SupervisedLearning）概述第2頁/共48頁概述監督學習（supervisedlearning）概述第2從給定的訓練數據集中學習出一個函數（模型參數），當新的數據到來時，可以根據這個函數預測結果監督學習就是最常見的分類問題監督學習的目標往往是讓計算機去學習我們已經創建好的分類模型最典型的算法是KNN和SVM監督學習（supervisedlearning）第3頁/共48頁從給定的訓練數據集中學習出一個函數（模型參數），當新的數據到3輸入數據沒有標記，也沒有確定的結果樣本數據類別未知，需要根據樣本間的相似性對樣本集進行聚類非監督學習目標不是告訴計算機怎么做，而是讓計算機自己去學習怎樣做非監督學習（unsupervisedlearning）第4頁/共48頁輸入數據沒有標記，也沒有確定的結果非監督學習（unsuper4無監督學習的方法分為兩大類：基于概率密度函數估計的直接方法基于樣本間相似性度量的簡介聚類方法：設法定出不同類別的核心或初始內核，然后依據樣本與核心之間的相似性度量將樣本聚集成不同的類別非監督學習（unsupervisedlearning）第5頁/共48頁無監督學習的方法分為兩大類：非監督學習（unsupervis5“物以聚類，人以群分”所謂聚類，就是將相似的事物聚集在一起，而將不相似的事物劃分到不同的類別的過程，是數據分析之中十分重要的一種手段。什么是聚類？第6頁/共48頁“物以聚類，人以群分”什么是聚類？第6頁/共48頁6在圖像分析中，人們希望將圖像分割成具有類似性質的區域在文本處理中，人們希望發現具有相同主題的文本子集在顧客行為分析中，人們希望發現消費方式類似的顧客群，以便制訂有針對性的客戶管理方式和提高營銷效率這些情況都可以在適當的條件下歸為聚類分析什么是聚類？第7頁/共48頁在圖像分析中，人們希望將圖像分割成具有類似性質的區域什么是聚7聚類就是將數據集中的樣本劃分為若干個通常不相交的子集，每個子集成為一個“簇”（Cluster）。聚類分析（ClusteringAnalysis）第8頁/共48頁聚類就是將數據集中的樣本劃分為若干個通常不相交的子集，每個子8聚類的相似性度量1.歐氏距離(EuclideanDistance)歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的歐氏距離：第9頁/共48頁聚類的相似性度量1.歐氏距離(EuclideanDis9聚類的相似性度量2.曼哈頓距離(ManhattanDistance)想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”，也稱為城市街區距離(CityBlockdistance)。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的曼哈頓距離第10頁/共48頁聚類的相似性度量2.曼哈頓距離(ManhattanDi10聚類的相似性度量3.切比雪夫距離(ChebyshevDistance)國際象棋中國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？你會發現最少步數總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的切比雪夫距離第11頁/共48頁聚類的相似性度量3.切比雪夫距離(Chebyshev11聚類的相似性度量4.馬氏距離(MahalanobisDistance)有M個樣本向量X1~Xm，協方差矩陣記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：5.漢明距離(HammingDistance)兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變為另外一個所需要作的最小替換次數。例如字符串“1111”與“1001”之間的漢明距離為2。第12頁/共48頁聚類的相似性度量4.馬氏距離(MahalanobisD12要考慮所選擇的距離公式在實際應用中有明確的意義。如歐氏距離就有非常明確的空間距離概念。馬氏距離有消除量綱影響的作用。距離選擇的原則第13頁/共48頁距離選擇的原則第13頁/共48頁13層次聚類凝聚方法（自底向上）：一開始將每個對象作為單獨的一組，然后根據同類相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終止條件為止。分裂方法（自頂向下）：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。

第14頁/共48頁層次聚類第14頁/共48頁14層次聚類特點：類的個數不需事先定好需確定距離矩陣運算量要大，適用于處理小樣本數據第15頁/共48頁層次聚類特點：第15頁/共48頁15層次聚類——最短距離法兩個類中距離最近的兩個樣本的距離作為這兩個集合的距離第16頁/共48頁層次聚類——最短距離法兩個類中距離最近的兩個樣本的距離作為這16

將類Gp與Gq合并為Gr，則Gr與任意一類Gk間的距離為：

層次聚類——最短距離法第17頁/共48頁層次聚類——最短距離法第17頁/共48頁17最短距離法進行聚類分析的步驟如下：（1）定義樣品之間距離，計算樣品的兩兩距離，得一距離陣記為D(0)，開始每個樣品自成一類，顯然這時Dij=dij。（2）找出距離最小元素，設為Dpq，則將Gp和Gq合并成一個新類，記為Gr，即Gr=｛Gp，Gq｝。（3）計算新類與其它類的距離。（4）重復（2）、（3）兩步，直到所有元素。并成一類為止。如果某一步距離最小的元素不止一個，則對應這些最小元素的類可以同時合并。層次聚類——最短距離法第18頁/共48頁最短距離法進行聚類分析的步驟如下：層次聚類——最短距離法第118層次聚類——最大距離法最大距離法（completelinkagemethod）第19頁/共48頁層次聚類——最大距離法最大距離法（completelink19層次聚類——最大距離法將類Gp與Gq合并為Gr，則Gr與任意一類Gk間的距離為：第20頁/共48頁層次聚類——最大距離法將類Gp與Gq合并為Gr，則Gr與任意20層次聚類——中間距離法中間距離法最短、最長距離定義表示都是極端情況，我們定義類間距離可以既不采用兩類之間最近的距離也不采用兩類之間最遠的距離，而是采用介于兩者之間的距離，稱為中間距離法。中間距離將類Gp與Gq類合并為類Gr，則任意的類Gk和Gr的距離公式為(1／40)設Dkq＞Dkp，如果采用最短距離法，則Dkr=Dkp，如果采用最長距離法，則Dkr=Dkq。第21頁/共48頁層次聚類——中間距離法中間距離法第21頁/共48頁21層次聚類【例】設有六個樣品，每個只測量一個指標，分別是1，2，5，7，9，10，試用最短距離法將它們分類。（1）樣品采用絕對值距離，計算樣品間的距離陣D（0），見表第22頁/共48頁層次聚類【例】設有六個樣品，每個只測量一個指標，分別是1，222層次聚類（2）D（0）中最小的元素是D12＝D56＝1，于是將G1和G2合并成G7，G5和G6合并成G8，并利用式計算新類與其它類的距離D(1)，見下表：第23頁/共48頁層次聚類（2）D（0）中最小的元素是D12＝D56＝1，于是23層次聚類（3）在D（1）中最小值是D34＝D48＝2，由于G4與G3合并，又與G8合并，因此G3、G4、G8合并成一個新類G9，其與其它類的距離D（2），見下表：第24頁/共48頁層次聚類（3）在D（1）中最小值是D34＝D48＝2，由于G24層次聚類（4）最后將G7和G9合并成G10，這時所有的六個樣品聚為一類，其過程終止。上述聚類的可視化過程見下圖所示，橫坐標的刻度表示并類的距離。這里我們應該注意，聚類的個數要以實際情況所定：第25頁/共48頁層次聚類（4）最后將G7和G9合并成G10，這時所有的六個樣25原型聚類（K-means、高斯混合聚類）密度聚類（DBSCAN）層次聚類聚類算法第26頁/共48頁原型聚類（K-means、高斯混合聚類）聚類算法第26頁26

K均值法是麥奎因（MacQueen）1967提出的基本思想是將每一個樣本分配給最近中心（均值）的類中，具體的算法至少包括以下四個步驟：

(1)從n個數據對象隨機選取k個對象作為初始簇中心。(2)計算每個簇的平均值，并用該平均值代表相應的簇。(3)計算每個對象與這些中心對象的距離，并根據最小距離重新對相應對象進行劃分。(4)轉步驟(2)，重新計算每個(自變化)簇的平均值。這個過程不斷重復直到某個準則函數不再明顯變化或者聚類的對象不再變化為止。K均值聚類（K-means)

第27頁/共48頁K均值法是麥奎因（MacQueen）127K均值聚類（K-means)【例】假定我們對A、B、C、D四個樣品分別測量兩個變量和得到結果見表。試將以上的樣品聚成兩類。

第28頁/共48頁K均值聚類（K-means)【例】假定我們對A、B、C、D四28K均值聚類（K-means)

第一步：按要求取K=2，為了實施均值法聚類，我們將這些樣品隨意分成兩類，比如（A、B）和（C、D），然后計算這兩個聚類的中心坐標，見下表所示。

中心坐標是通過原始數據計算得來的，比如（A、B）類的，

第29頁/共48頁K均值聚類（K-means) 第一步：按要求取K=2，為了29K均值聚類（K-means)

第二步：計算某個樣本到各類中心的歐氏平方距離，然后將該樣品分配給最近的一類。對于樣品有變動的類，重新計算它們的中心坐標，為下一步聚類做準備。先計算A到兩個類的平方距離：由于A到（A、B）的距離小于到（C、D）的距離，因此A不用重新分配。計算B到兩類的平方距離：第30頁/共48頁K均值聚類（K-means) 第二步：計算某個樣本到各類中心30K均值聚類（K-means)

由于B到（A、B）的距離大于到（C、D）的距離，因此B要分配給（C、D）類，得到新的聚類是（A）和（B、C、D）。更新中心坐標如下表所示。第31頁/共48頁K均值聚類（K-means)由于B到（A、B）31K均值聚類（K-means)

第三步：再次檢查每個樣品，以決定是否需要重新分類。計算各樣品到各中心的距離平方，結果見下表。到現在為止，每個樣品都已經分配給距離中心最近的類，因此聚類過程到此結束。最終得到K=2的聚類結果是A獨自成一類，B、C、D聚成一類。第32頁/共48頁K均值聚類（K-means)第三步：再次檢查每個樣品32K-means聚類的應用：圖像分割：SLIC算法文本分析K均值聚類（K-means)第33頁/共48頁K-means聚類的應用：K均值聚類（K-means)第3333基于密度的聚類主要有DBSCAN，OPTICS法思想：只要臨近區域的密度超過一定的閾值，就繼續聚類特點：可以過濾噪聲和孤立點outlier，發現任意形狀的類第34頁/共48頁基于密度的聚類主要有DBSCAN，OPTICS法第34頁/共34

DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(ε,MinPts)用來描述鄰域的樣本分布緊密程度。ε描述某一樣本的鄰域距離閾值，MinPts描述某一樣本的距離為ε的鄰域中樣本個數的閾值。假設我的樣本集是D=(x1,x2,...,xm)則DBSCAN具體：1）ε-鄰域：對于xj∈D，其ε-鄰域包含樣本集D中與xj的距離不大于ε的子樣本集，即Nε(xj)={xi∈D|distance(xi,xj)≤ε}2)核心對象：對于任一樣本xj∈D，如果其ε-鄰域對應的Nε(xj)至少包含MinPts個樣本，即如果|N?(xj)|≥MinPts，則xj是核心對象。密度聚類——DBSCAN第35頁/共48頁DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，353）密度直達：如果xi位于xj的ε-鄰域中，且xj是核心對象，則稱xi由xj密度直達。注意反之不一定成立，除非且xi也是核心對象。4）密度可達：對于xi和xj,如果存在樣本序列p1,p2,...,pT滿足p1=xi,pT=xj且pt+1由pt密度直達，則稱xj由xi密度可達。密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT?1均為核心對象，因為只有核心對象才能使其他樣本密度直達。5）密度相連：對于xi和xj,如果存在核心對象樣本xk，使xi和xj均由xk密度可達，則稱xi和xj密度相連。密度聚類——DBSCAN第36頁/共48頁3）密度直達：如果xi位于xj的ε-鄰域中，且xj是核心對象36密度聚類——DBSCANMinPts=5第37頁/共48頁密度聚類——DBSCANMinPts=5第37頁/共48頁37由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇。首先給定聚類對象的半徑-鄰域和-鄰域中最小包含的對象數MinPts然后檢查某個對象-鄰域中的對象數，如果對象數大于MinPts，該對象就是核心對象，就構建以該對象為核心的新簇然后，反復尋找從這些核心對象出發在-鄰域內的對象，這個尋找過程可能會合并一些簇。直到沒有新的對象可以添加到任何簇中為止密度聚類——DBSCAN第38頁/共48頁由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類38密度聚類——DBSCAN第39頁/共48頁密度聚類——DBSCAN第39頁/共48頁39第一步，在數據集中選擇一點1，以它為圓心的，以1為半徑的圓內包含2個點（小于4），因此它不是核心點，選擇下一個點。第二步，在數據集中選擇一點2，以它為圓心的，以1為半徑的圓內包含2個點（小于4），因此它不是核心點，選擇下一個點。第三步，在數據集中選擇一點3，以它為圓心的，以1為半徑的園內包含3個點（小于4），因此它不是核心點，選擇下一個點。密度聚類——DBSCAN第40頁/共48頁第一步，在數據集中選擇一點1，以它為圓心的，以1為半徑的圓內40密度聚類——DBSCAN第四步，在數據集中選擇一點4，由于在以它為圓心的，以1為半徑的圓內包含5個點，因此它是核心點，尋找從它出發可達的點（直接可達4個，間接可達3個），聚出的新類{1，3，4，5，9，10，12}，選擇下一個點。第41頁/共48頁密度聚類——DBSCAN第四步，在數據集中選擇一點4，由于在41密度聚類——DBSCAN第五步，在數據集中選擇一點5，已在簇1中，選擇下一個點。第六步，在數據集中選擇一點6，在以它為圓心的，以1為半徑的圓內包含3個點，因此它不是核心點，選擇下一個點。第42頁/共48頁密度聚類——DBSCAN第五步，在數據集中選擇一點5，已在簇42密度聚類——DBSCAN第七步，在數據集中選擇一點7，以它為圓心，以1為半徑的圓內包含5個點，因此它是核心點，尋找從它出發可達的點，聚出的新類{2，6，7，8，11}，選擇下一個點。第43頁/共48頁密度聚類——DBSCAN第七步，在數據集中選擇一點7，以它為43第八步，在數據集中選擇一點8，已經在簇2中了，選擇下一點。第九步，在數據集中選擇一點9，已經在簇1中了，選擇下一點。第十步，在數據集中選擇一點10，已經在簇1中了，選擇下一點。第十一步，在數據集中選擇一點11，已經在簇2中了，選擇下一點。第十二步，在數據集中選擇一點12，已經在簇1中了，結束。密度聚類——DBSCAN第44頁/共48頁第八步，在數據集中選擇一點8，已經在簇2中了，選擇下一點。密44密度聚類——DBSCAN第45頁/共48頁密度聚類——DBSCAN第45頁/共48頁45常用的外部指標Jaccard系數：主要判斷隸屬于相同類的個數。該個數越多，說明聚類效果越好。常用的內部聚類perplexity值：perplexity值（困惑度）主要計算特征的概率。通常用于LDA,HDP等模型上，值越小越好。距離計算：類內的樣本距離越小越好，類間的距離越大越好。評價指標第46頁/共48頁常用的外部指標評價指標第46頁/共48頁46K均值聚類DBSCAN層次聚類（歐式距離，最短距離法）實現并說明其優勢和劣勢。作業練習第47頁/共48頁K均值聚類作業練習第47頁/共48頁47感謝您的欣賞第48頁/共48頁感謝您的欣賞第48頁/共48頁48目錄什么是聚類距離度量方法幾種常見的聚類方法練習第1頁/共48頁目錄什么是聚類第1頁/共48頁49概述監督學習（supervisedlearning）無監督學習（unsupervisedlearning）半監督學習（Semi-SupervisedLearning）概述第2頁/共48頁概述監督學習（supervisedlearning）概述第50從給定的訓練數據集中學習出一個函數（模型參數），當新的數據到來時，可以根據這個函數預測結果監督學習就是最常見的分類問題監督學習的目標往往是讓計算機去學習我們已經創建好的分類模型最典型的算法是KNN和SVM監督學習（supervisedlearning）第3頁/共48頁從給定的訓練數據集中學習出一個函數（模型參數），當新的數據到51輸入數據沒有標記，也沒有確定的結果樣本數據類別未知，需要根據樣本間的相似性對樣本集進行聚類非監督學習目標不是告訴計算機怎么做，而是讓計算機自己去學習怎樣做非監督學習（unsupervisedlearning）第4頁/共48頁輸入數據沒有標記，也沒有確定的結果非監督學習（unsuper52無監督學習的方法分為兩大類：基于概率密度函數估計的直接方法基于樣本間相似性度量的簡介聚類方法：設法定出不同類別的核心或初始內核，然后依據樣本與核心之間的相似性度量將樣本聚集成不同的類別非監督學習（unsupervisedlearning）第5頁/共48頁無監督學習的方法分為兩大類：非監督學習（unsupervis53“物以聚類，人以群分”所謂聚類，就是將相似的事物聚集在一起，而將不相似的事物劃分到不同的類別的過程，是數據分析之中十分重要的一種手段。什么是聚類？第6頁/共48頁“物以聚類，人以群分”什么是聚類？第6頁/共48頁54在圖像分析中，人們希望將圖像分割成具有類似性質的區域在文本處理中，人們希望發現具有相同主題的文本子集在顧客行為分析中，人們希望發現消費方式類似的顧客群，以便制訂有針對性的客戶管理方式和提高營銷效率這些情況都可以在適當的條件下歸為聚類分析什么是聚類？第7頁/共48頁在圖像分析中，人們希望將圖像分割成具有類似性質的區域什么是聚55聚類就是將數據集中的樣本劃分為若干個通常不相交的子集，每個子集成為一個“簇”（Cluster）。聚類分析（ClusteringAnalysis）第8頁/共48頁聚類就是將數據集中的樣本劃分為若干個通常不相交的子集，每個子56聚類的相似性度量1.歐氏距離(EuclideanDistance)歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的歐氏距離：第9頁/共48頁聚類的相似性度量1.歐氏距離(EuclideanDis57聚類的相似性度量2.曼哈頓距離(ManhattanDistance)想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”，也稱為城市街區距離(CityBlockdistance)。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的曼哈頓距離第10頁/共48頁聚類的相似性度量2.曼哈頓距離(ManhattanDi58聚類的相似性度量3.切比雪夫距離(ChebyshevDistance)國際象棋中國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？你會發現最少步數總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的切比雪夫距離第11頁/共48頁聚類的相似性度量3.切比雪夫距離(Chebyshev59聚類的相似性度量4.馬氏距離(MahalanobisDistance)有M個樣本向量X1~Xm，協方差矩陣記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：5.漢明距離(HammingDistance)兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變為另外一個所需要作的最小替換次數。例如字符串“1111”與“1001”之間的漢明距離為2。第12頁/共48頁聚類的相似性度量4.馬氏距離(MahalanobisD60要考慮所選擇的距離公式在實際應用中有明確的意義。如歐氏距離就有非常明確的空間距離概念。馬氏距離有消除量綱影響的作用。距離選擇的原則第13頁/共48頁距離選擇的原則第13頁/共48頁61層次聚類凝聚方法（自底向上）：一開始將每個對象作為單獨的一組，然后根據同類相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終止條件為止。分裂方法（自頂向下）：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。

第14頁/共48頁層次聚類第14頁/共48頁62層次聚類特點：類的個數不需事先定好需確定距離矩陣運算量要大，適用于處理小樣本數據第15頁/共48頁層次聚類特點：第15頁/共48頁63層次聚類——最短距離法兩個類中距離最近的兩個樣本的距離作為這兩個集合的距離第16頁/共48頁層次聚類——最短距離法兩個類中距離最近的兩個樣本的距離作為這64

將類Gp與Gq合并為Gr，則Gr與任意一類Gk間的距離為：

層次聚類——最短距離法第17頁/共48頁層次聚類——最短距離法第17頁/共48頁65最短距離法進行聚類分析的步驟如下：（1）定義樣品之間距離，計算樣品的兩兩距離，得一距離陣記為D(0)，開始每個樣品自成一類，顯然這時Dij=dij。（2）找出距離最小元素，設為Dpq，則將Gp和Gq合并成一個新類，記為Gr，即Gr=｛Gp，Gq｝。（3）計算新類與其它類的距離。（4）重復（2）、（3）兩步，直到所有元素。并成一類為止。如果某一步距離最小的元素不止一個，則對應這些最小元素的類可以同時合并。層次聚類——最短距離法第18頁/共48頁最短距離法進行聚類分析的步驟如下：層次聚類——最短距離法第166層次聚類——最大距離法最大距離法（completelinkagemethod）第19頁/共48頁層次聚類——最大距離法最大距離法（completelink67層次聚類——最大距離法將類Gp與Gq合并為Gr，則Gr與任意一類Gk間的距離為：第20頁/共48頁層次聚類——最大距離法將類Gp與Gq合并為Gr，則Gr與任意68層次聚類——中間距離法中間距離法最短、最長距離定義表示都是極端情況，我們定義類間距離可以既不采用兩類之間最近的距離也不采用兩類之間最遠的距離，而是采用介于兩者之間的距離，稱為中間距離法。中間距離將類Gp與Gq類合并為類Gr，則任意的類Gk和Gr的距離公式為(1／40)設Dkq＞Dkp，如果采用最短距離法，則Dkr=Dkp，如果采用最長距離法，則Dkr=Dkq。第21頁/共48頁層次聚類——中間距離法中間距離法第21頁/共48頁69層次聚類【例】設有六個樣品，每個只測量一個指標，分別是1，2，5，7，9，10，試用最短距離法將它們分類。（1）樣品采用絕對值距離，計算樣品間的距離陣D（0），見表第22頁/共48頁層次聚類【例】設有六個樣品，每個只測量一個指標，分別是1，270層次聚類（2）D（0）中最小的元素是D12＝D56＝1，于是將G1和G2合并成G7，G5和G6合并成G8，并利用式計算新類與其它類的距離D(1)，見下表：第23頁/共48頁層次聚類（2）D（0）中最小的元素是D12＝D56＝1，于是71層次聚類（3）在D（1）中最小值是D34＝D48＝2，由于G4與G3合并，又與G8合并，因此G3、G4、G8合并成一個新類G9，其與其它類的距離D（2），見下表：第24頁/共48頁層次聚類（3）在D（1）中最小值是D34＝D48＝2，由于G72層次聚類（4）最后將G7和G9合并成G10，這時所有的六個樣品聚為一類，其過程終止。上述聚類的可視化過程見下圖所示，橫坐標的刻度表示并類的距離。這里我們應該注意，聚類的個數要以實際情況所定：第25頁/共48頁層次聚類（4）最后將G7和G9合并成G10，這時所有的六個樣73原型聚類（K-means、高斯混合聚類）密度聚類（DBSCAN）層次聚類聚類算法第26頁/共48頁原型聚類（K-means、高斯混合聚類）聚類算法第26頁74

K均值法是麥奎因（MacQueen）1967提出的基本思想是將每一個樣本分配給最近中心（均值）的類中，具體的算法至少包括以下四個步驟：

(1)從n個數據對象隨機選取k個對象作為初始簇中心。(2)計算每個簇的平均值，并用該平均值代表相應的簇。(3)計算每個對象與這些中心對象的距離，并根據最小距離重新對相應對象進行劃分。(4)轉步驟(2)，重新計算每個(自變化)簇的平均值。這個過程不斷重復直到某個準則函數不再明顯變化或者聚類的對象不再變化為止。K均值聚類（K-means)

第27頁/共48頁K均值法是麥奎因（MacQueen）175K均值聚類（K-means)【例】假定我們對A、B、C、D四個樣品分別測量兩個變量和得到結果見表。試將以上的樣品聚成兩類。

第28頁/共48頁K均值聚類（K-means)【例】假定我們對A、B、C、D四76K均值聚類（K-means)

第一步：按要求取K=2，為了實施均值法聚類，我們將這些樣品隨意分成兩類，比如（A、B）和（C、D），然后計算這兩個聚類的中心坐標，見下表所示。

中心坐標是通過原始數據計算得來的，比如（A、B）類的，

第29頁/共48頁K均值聚類（K-means) 第一步：按要求取K=2，為了77K均值聚類（K-means)

第二步：計算某個樣本到各類中心的歐氏平方距離，然后將該樣品分配給最近的一類。對于樣品有變動的類，重新計算它們的中心坐標，為下一步聚類做準備。先計算A到兩個類的平方距離：由于A到（A、B）的距離小于到（C、D）的距離，因此A不用重新分配。計算B到兩類的平方距離：第30頁/共48頁K均值聚類（K-means) 第二步：計算某個樣本到各類中心78K均值聚類（K-means)

由于B到（A、B）的距離大于到（C、D）的距離，因此B要分配給（C、D）類，得到新的聚類是（A）和（B、C、D）。更新中心坐標如下表所示。第31頁/共48頁K均值聚類（K-means)由于B到（A、B）79K均值聚類（K-means)

第三步：再次檢查每個樣品，以決定是否需要重新分類。計算各樣品到各中心的距離平方，結果見下表。到現在為止，每個樣品都已經分配給距離中心最近的類，因此聚類過程到此結束。最終得到K=2的聚類結果是A獨自成一類，B、C、D聚成一類。第32頁/共48頁K均值聚類（K-means)第三步：再次檢查每個樣品80K-means聚類的應用：圖像分割：SLIC算法文本分析K均值聚類（K-means)第33頁/共48頁K-means聚類的應用：K均值聚類（K-means)第3381基于密度的聚類主要有DBSCAN，OPTICS法思想：只要臨近區域的密度超過一定的閾值，就繼續聚類特點：可以過濾噪聲和孤立點outlier，發現任意形狀的類第34頁/共48頁基于密度的聚類主要有DBSCAN，OPTICS法第34頁/共82

DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(ε,MinPts)用來描述鄰域的樣本分布緊密程度。ε描述某一樣本的鄰域距離閾值，MinPts描述某一樣本的距離為ε的鄰域中樣本個數的閾值。假設我的樣本集是D=(x1,x2,...,xm)則DBSCAN具體：1）ε-鄰域：對于xj∈D，其ε-鄰域包含樣本集D中與xj的距離不大于ε的子樣本集，即Nε(xj)={xi∈D|distance(xi,xj)≤ε}2)核心對象：對于任一樣本xj∈D，如果其ε-鄰域對應的Nε(xj)至少包含MinPts個樣本，即如果|N?(xj)|≥MinPts，則xj是核心對象。密度聚類——DBSCAN第35頁/共48頁DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，833）密度直達：如果xi位于xj的ε-鄰域中，且xj是核心對象，則稱xi由xj密度直達。注意反之不一定成立，除非且xi也是核心對象。4）密度可達：對于xi和xj,如果存在樣本序列p1,p2,...,pT滿足p1=xi,pT=xj且pt+1由pt密度直達，則稱xj由xi密度可達。密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT?1均為核心對象，因為只有核心對象才能使其他樣本密度直達。5）密度相連：對于xi和xj,如果存在核心對象樣本xk，使xi和xj均由xk密度可達，則稱xi和xj密度相連。密度聚類——DBSCAN第36頁/共48頁3）密度直達：如果xi位于xj的ε-鄰域中，且xj是核心對象84密度聚類——DBSCANMinPts=5第37頁/共48頁密度聚類——DBSCAN