機(jī)器學(xué)習(xí)之聚類分析課件

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

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

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

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

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

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

第27頁(yè)/共48頁(yè)K均值法是麥奎因（MacQueen）127K均值聚類（K-means)【例】假定我們對(duì)A、B、C、D四個(gè)樣品分別測(cè)量?jī)蓚€(gè)變量和得到結(jié)果見(jiàn)表。試將以上的樣品聚成兩類。

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

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

中心坐標(biāo)是通過(guò)原始數(shù)據(jù)計(jì)算得來(lái)的，比如（A、B）類的，

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

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

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

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

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

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

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

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

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

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

第27頁(yè)/共48頁(yè)K均值法是麥奎因（MacQueen）175K均值聚類（K-means)【例】假定我們對(duì)A、B、C、D四個(gè)樣品分別測(cè)量?jī)蓚€(gè)變量和得到結(jié)果見(jiàn)表。試將以上的樣品聚成兩類。

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

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

中心坐標(biāo)是通過(guò)原始數(shù)據(jù)計(jì)算得來(lái)的，比如（A、B）類的，

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

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

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

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

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