Python機(jī)器學(xué)習(xí)項(xiàng)目化教程（微課視頻版）課件 第5章 聚類

第5章聚類目錄CONTENTS5.1聚類算法簡(jiǎn)介5.2K-means聚類5.4基于層次的聚類5.6聚類算法比較5.3基于密度的聚類5.5高斯混合聚類5.7本章小結(jié)5.1聚類算法簡(jiǎn)介學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力信息素養(yǎng)高聚類分析是一種無(wú)監(jiān)督學(xué)習(xí)（UnsupervisedLearning）的算法，它是將數(shù)據(jù)對(duì)象按照相似性劃分為多個(gè)子集的過(guò)程，每個(gè)子集稱為一個(gè)“簇”（Cluster）。假設(shè)樣本集合為，通過(guò)聚類把樣本劃分到不同的簇，使得相似特征的樣本在同一個(gè)簇中，不相似特征的樣本在不同簇中，最終形成k個(gè)不同簇，若各個(gè)簇互不相交，即對(duì)任意兩個(gè)簇，則稱為硬聚類，否則稱為軟聚類。同一個(gè)簇中的數(shù)據(jù)相似性高，不同簇中的數(shù)據(jù)相似性低。5.1聚類算法簡(jiǎn)介5.1.1聚類算法分類1.基于劃分的方法基于劃分的方法是基于距離作為判斷依據(jù)，將數(shù)據(jù)對(duì)象劃分為不重疊的簇，使每個(gè)數(shù)據(jù)對(duì)象屬于且只屬于一個(gè)簇。首先要確定這些樣本點(diǎn)最后聚成幾類，然后挑選幾個(gè)樣本點(diǎn)作為初始中心點(diǎn)，通過(guò)不斷迭代，直到達(dá)到“類（簇）內(nèi)的樣本點(diǎn)都足夠近，類（簇）間的樣本點(diǎn)都足夠遠(yuǎn)”的目標(biāo)。基于劃分的距離算法有K-means、K-medoids、kernelK-means等算法。5.1聚類算法簡(jiǎn)介5.1.1聚類算法分類2.基于層次的方法基于層次的聚類可分為兩種：凝聚法和分裂法。凝聚法采用的是一種自底向上的方法，從最底層開(kāi)始，每一次通過(guò)合并最相似的聚類來(lái)形成上一層次中的聚類，當(dāng)全部數(shù)據(jù)都合并到一個(gè)簇或者達(dá)到某個(gè)終止條件時(shí)，算法結(jié)束。分裂法采用的是一種自頂向下的方法，從一個(gè)包含全部樣本數(shù)據(jù)的簇開(kāi)始，逐層分裂為若干個(gè)簇，每個(gè)簇繼續(xù)不斷往下分裂，直到每個(gè)簇中僅包含一個(gè)樣本數(shù)據(jù)。5.1聚類算法簡(jiǎn)介5.1.1聚類算法分類3.基于密度的方法在基于密度的聚類方法中，簇被看成是由低密度區(qū)域分隔開(kāi)來(lái)的高密度對(duì)象區(qū)域?；诿芏鹊木垲惙椒ǘx了領(lǐng)域的范圍，當(dāng)臨近區(qū)域的密度超過(guò)某個(gè)閾值，就繼續(xù)聚類，即某區(qū)域內(nèi)的對(duì)象個(gè)數(shù)超過(guò)一個(gè)給定范圍，則將其添加到簇中。基于密度的聚類方法可以對(duì)不規(guī)則形狀的數(shù)據(jù)樣本點(diǎn)進(jìn)行聚類，同時(shí)過(guò)濾噪聲數(shù)據(jù)效果比較好。DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）就是典型的代表。5.1聚類算法簡(jiǎn)介5.1.1聚類算法分類4.基于網(wǎng)格的方法基于網(wǎng)絡(luò)的聚類方法將數(shù)據(jù)空間劃分為由若干有限的網(wǎng)格單元（cell）組成的網(wǎng)格結(jié)構(gòu)，將數(shù)據(jù)對(duì)象集映射到網(wǎng)格單元中，所有聚類操作都在該結(jié)構(gòu)上進(jìn)行。該方法的處理與數(shù)據(jù)對(duì)象個(gè)數(shù)無(wú)關(guān)，只依賴于每個(gè)量化空間中每一維上的單元數(shù)，處理速度快，但算法效率的提高是以聚類結(jié)果的準(zhǔn)確率為代價(jià)的，經(jīng)常與基于密度的聚類算法結(jié)合使用。5.1聚類算法簡(jiǎn)介5.1.1聚類算法分類5.基于模型的方法基于模型的方法包括基于概率模型的方法和基于神經(jīng)網(wǎng)絡(luò)模型的方法。概率模型主要指概率生成模型，同一“類”的數(shù)據(jù)屬于同一種概率分布，即假設(shè)數(shù)據(jù)是根據(jù)潛在的概率分布生成的。高斯混合模型（GaussianMixtureModels，GMM）就是最典型、常用基于概率模型的聚類方法。自組織映射（SelfOrganizedMaps，SOM）則是一種常見(jiàn)的基于神經(jīng)網(wǎng)絡(luò)模型的方法。5.1聚類算法簡(jiǎn)介5.1.2距離度量方法1.閔可夫斯基距離閔可夫斯基距離（MinkowskiDistance）將樣本看作高維空間中的點(diǎn)進(jìn)行距離度量。P和Q的閔可夫斯基距離定義為：5.1聚類算法簡(jiǎn)介5.1.2距離度量方法2.馬氏距離與歐氏距離、曼哈頓距離一樣，馬氏距離（MahalanobisDistance）常被用于評(píng)定數(shù)據(jù)之間的相似度指標(biāo)，它可以看作是歐氏距離的修正，修正了歐氏距離中各維度尺度不一致且相關(guān)的問(wèn)題。單個(gè)數(shù)據(jù)點(diǎn)的馬氏距離定義為：5.1聚類算法簡(jiǎn)介5.1.2距離度量方法3.漢明距離漢明距離（HammingDistance）需要將處理的樣本數(shù)據(jù)轉(zhuǎn)換為0和1表示的二進(jìn)制串，樣本中各分量的取值只能是0或1，例如字符串“1110”與“1001”之間的漢明距離為3。對(duì)于任意樣本特征和，有，其漢明距離為：5.1聚類算法簡(jiǎn)介5.1.2距離度量方法4.夾角余弦?jiàn)A角余弦（Cosine）度量將樣本看成是高維空間中的向量進(jìn)行度量，度量方法就是計(jì)算兩個(gè)向量的余弦?jiàn)A角。對(duì)于任意兩個(gè)n維樣本和，其夾角余弦為：5.2K-means聚類假設(shè)簇劃分為(C1,C2,...,Ck)，則目標(biāo)就是最小化平方誤差：k均值聚類算法描述如下：輸入：訓(xùn)練數(shù)據(jù)集D={x1,x2,…,xN}，聚類個(gè)數(shù)k。過(guò)程：（1）從D中隨機(jī)選擇k個(gè)樣本作為初始的均值向量：。（2）重復(fù)執(zhí)行以下過(guò)程，直至當(dāng)前均值向量不再更新：①令，其中1≤i≤k。②對(duì)于i=1,2,…,N，選擇每個(gè)樣本與各均值向量mj(1≤j≤k)的距離：，根據(jù)離均值距離最小的確定其聚類標(biāo)記：，將樣本劃入相應(yīng)的聚類。③對(duì)于i=1,2,…,k，計(jì)算新的均值向量：，如果新的均值向量與之前的均值向量不相等，則更新，即，否則不更新。5.2K-means聚類西瓜數(shù)據(jù)集5.2K-means聚類1利用Parzen矩形窗估計(jì)概率密度、分類假設(shè)聚類個(gè)數(shù)為k=3，首先隨機(jī)選取3個(gè)樣本x3=(0.634,0.264)、x8=(0.437,0.211)、x9=(0.666,0.091)作為初始的均值向量，分別對(duì)應(yīng)于3個(gè)聚類C1、C2、C3中的均值向量，初始時(shí)每個(gè)聚類中元素為空。考察樣本x1=(0.697,0.460)，它與當(dāng)前的均值向量、、距離分別為0.206、0.360、0.370，因此x1被劃入聚類C1中，類似地，對(duì)x2,x3,…,x30所有樣本都執(zhí)行類似的過(guò)程，將每個(gè)樣本進(jìn)行了劃分，故有：C1={x1,x2,x3,x4,x5,x14,x21,x22,x25,x26,x27,x29}C2={x6,x7,x8,x10,x11,x12,x15,x18,x19,x20,x23,x24,x28,x30}C3={x9,x13,x16,x17}25.2K-means聚類3（3）根據(jù)得到的C1、C2、C3更新均值向量：

5.2K-means聚類針對(duì)三文魚和鱸魚數(shù)據(jù)的聚類，使用K-means進(jìn)行聚類。5.3基于密度的聚類──DBSCAN聚類5.3.1DBSCAN算法原理及相關(guān)概念給出樣本數(shù)據(jù)集合D=(x1,x2,...,xN)，相關(guān)概念描述如下：（1）?-鄰域：對(duì)于任一樣本xj∈D，其?-鄰域包含的樣本集是D中與xj的距離不大于?的樣本，即N?(xj)={xi∈D|distance(xi,xj)≤?}，其樣本集個(gè)數(shù)記作|N?(xj)|。（2）核心對(duì)象：對(duì)于任一樣本xj∈D，如果其?-鄰域包含至少minPts個(gè)樣本，即當(dāng)|N?(xj)|≥MinPts時(shí)，則xj為一個(gè)核心對(duì)象。（3）密度直達(dá)：如果xi位于xj的?-鄰域中，且xj是核心對(duì)象，則稱xi由xj密度直達(dá)。（4）密度可達(dá)：對(duì)于xi和xj，如果存在樣本序列p1,p2,...,pn，滿足p1=xi、pn=xj，且1≤i<n，其pi+1由pi密度直達(dá)，則稱xj由xi密度可達(dá)。密度可達(dá)滿足傳遞性。（5）密度相連：對(duì)于xi和xj，如果存在核心對(duì)象樣本xk，使xi和xj均由xk密度可達(dá)，則稱xi和xj密度相連。密度相連關(guān)系滿足對(duì)稱性。5.3基于密度的聚類──DBSCAN聚類4.3.2DBSCAN聚類算法DBSCAN聚類算法根據(jù)設(shè)置的鄰域參數(shù)?、minPts先確定核心對(duì)象集合，然后隨機(jī)選擇一個(gè)核心對(duì)象確定相應(yīng)的聚類簇，直到所有的核心對(duì)象都被訪問(wèn)過(guò)為止。DBSCAN聚類算法描述如下：輸入：訓(xùn)練數(shù)據(jù)集D={x1,x2,…,xN}、鄰域參數(shù)?、minPts。過(guò)程：（1）初始化核心對(duì)象集合、聚類簇?cái)?shù)k=0、未訪問(wèn)樣本集合Γ=D。（2）對(duì)于j=1,2,…,N：①通過(guò)距離度量方式，找到樣本的?-鄰域集合M?(xj)。②如果樣本集中樣本個(gè)數(shù)滿足|N?(xj)|≥minPts，則將樣本xj加入核心對(duì)象樣本集合：。5.3基于密度的聚類──DBSCAN聚類（3）如果核心對(duì)象集合，則算法結(jié)束，否則執(zhí)行第（4）步。（4）在核心對(duì)象集合Ω中，隨機(jī)選擇一個(gè)核心對(duì)象o，初始化當(dāng)前簇核心對(duì)象隊(duì)列，初始化類別序號(hào)k=k+1，初始化當(dāng)前簇樣本集合Ck={o}，更新未訪問(wèn)樣本集合Γ=Γ?{o}。（5）如果當(dāng)前簇核心對(duì)象隊(duì)列，則當(dāng)前聚類簇Ck生成完畢，更新簇劃分C={C1,C2,...,Ck}，更新核心對(duì)象集合Ω=Ω?Ck，轉(zhuǎn)到第（3）步，否則更新核心對(duì)象集合Ω=Ω?Ck。（6）在當(dāng)前簇核心對(duì)象隊(duì)列中取出一個(gè)核心對(duì)象o′，通過(guò)鄰域距離閾值?找出所有的?-鄰域樣本集M?(o′)，令Δ=M?(o′)∩Γ，更新當(dāng)前簇樣本集合Ck=Ck∪Δ，更新未訪問(wèn)樣本集合Γ=Γ?Δ，更新，轉(zhuǎn)到第（5）步執(zhí)行。輸出：簇劃分。5.3基于密度的聚類──DBSCAN聚類利用DBSCAN對(duì)西瓜數(shù)據(jù)集進(jìn)行聚類。5.4基于層次的聚類──AGNES聚類5.4.1AGNES聚類算法思想AGNES采用自底而上合并聚類簇，每次找到距離最短的兩個(gè)聚類簇，然后合并成一個(gè)大的聚類簇，以此類推，直到全部樣本數(shù)據(jù)合并為一個(gè)聚類簇。整個(gè)聚類過(guò)程就形成了一個(gè)樹(shù)形結(jié)構(gòu)，如圖所示。5.4基于層次的聚類──AGNES聚類AGNES聚類算法描述如下：輸入：樣本數(shù)據(jù)集D={x1,x2,…,xN}、聚類簇個(gè)數(shù)k、聚類簇度量函數(shù)get_dist。過(guò)程：（1）將每個(gè)對(duì)象看成是一個(gè)聚類簇，即對(duì)于任意的1≤j≤N，有。（2）根據(jù)聚類簇度量函數(shù)get_dist確定各個(gè)簇之間的距離。（3）設(shè)置當(dāng)前簇個(gè)數(shù)q=N。（4）當(dāng)q>k時(shí)，重復(fù)執(zhí)行以下步驟：①找出距離最近的兩個(gè)簇和，合并和：。②對(duì)編號(hào)為j+1,j+2,…,q的簇重新編號(hào)，依次為j,j+1,…,q-1。③對(duì)j=1,2,…,q-1，更新聚類簇之間的距離。④根據(jù)約束條件，確定新參數(shù)的上下界。5.4基于層次的聚類──AGNES聚類AGNES聚類算法在西瓜數(shù)據(jù)集上的運(yùn)行結(jié)果5.5高斯混合聚類其概率密度函數(shù)如圖5-7所示：5.5高斯混合聚類一個(gè)混合高斯概率密度函數(shù)如圖5-8所示。5.5高斯混合聚類求導(dǎo)5.5高斯混合聚類高斯混合聚類的算法描述如下：5.5高斯混合聚類5.6各種聚類算法的比較5.7本章小結(jié)K-mean