Python機器學習項目化教程（微課視頻版）課件 第5章 聚類

第5章聚類目錄CONTENTS5.1聚類算法簡介5.2K-means聚類5.4基于層次的聚類5.6聚類算法比較5.3基于密度的聚類5.5高斯混合聚類5.7本章小結5.1聚類算法簡介學習基礎學習認知能力信息素養(yǎng)高聚類分析是一種無監(jiān)督學習（UnsupervisedLearning）的算法，它是將數(shù)據(jù)對象按照相似性劃分為多個子集的過程，每個子集稱為一個“簇”（Cluster）。假設樣本集合為，通過聚類把樣本劃分到不同的簇，使得相似特征的樣本在同一個簇中，不相似特征的樣本在不同簇中，最終形成k個不同簇，若各個簇互不相交，即對任意兩個簇，則稱為硬聚類，否則稱為軟聚類。同一個簇中的數(shù)據(jù)相似性高，不同簇中的數(shù)據(jù)相似性低。5.1聚類算法簡介5.1.1聚類算法分類1.基于劃分的方法基于劃分的方法是基于距離作為判斷依據(jù)，將數(shù)據(jù)對象劃分為不重疊的簇，使每個數(shù)據(jù)對象屬于且只屬于一個簇。首先要確定這些樣本點最后聚成幾類，然后挑選幾個樣本點作為初始中心點，通過不斷迭代，直到達到“類（簇）內(nèi)的樣本點都足夠近，類（簇）間的樣本點都足夠遠”的目標?；趧澐值木嚯x算法有K-means、K-medoids、kernelK-means等算法。5.1聚類算法簡介5.1.1聚類算法分類2.基于層次的方法基于層次的聚類可分為兩種：凝聚法和分裂法。凝聚法采用的是一種自底向上的方法，從最底層開始，每一次通過合并最相似的聚類來形成上一層次中的聚類，當全部數(shù)據(jù)都合并到一個簇或者達到某個終止條件時，算法結束。分裂法采用的是一種自頂向下的方法，從一個包含全部樣本數(shù)據(jù)的簇開始，逐層分裂為若干個簇，每個簇繼續(xù)不斷往下分裂，直到每個簇中僅包含一個樣本數(shù)據(jù)。5.1聚類算法簡介5.1.1聚類算法分類3.基于密度的方法在基于密度的聚類方法中，簇被看成是由低密度區(qū)域分隔開來的高密度對象區(qū)域?；诿芏鹊木垲惙椒ǘx了領域的范圍，當臨近區(qū)域的密度超過某個閾值，就繼續(xù)聚類，即某區(qū)域內(nèi)的對象個數(shù)超過一個給定范圍，則將其添加到簇中。基于密度的聚類方法可以對不規(guī)則形狀的數(shù)據(jù)樣本點進行聚類，同時過濾噪聲數(shù)據(jù)效果比較好。DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）就是典型的代表。5.1聚類算法簡介5.1.1聚類算法分類4.基于網(wǎng)格的方法基于網(wǎng)絡的聚類方法將數(shù)據(jù)空間劃分為由若干有限的網(wǎng)格單元（cell）組成的網(wǎng)格結構，將數(shù)據(jù)對象集映射到網(wǎng)格單元中，所有聚類操作都在該結構上進行。該方法的處理與數(shù)據(jù)對象個數(shù)無關，只依賴于每個量化空間中每一維上的單元數(shù)，處理速度快，但算法效率的提高是以聚類結果的準確率為代價的，經(jīng)常與基于密度的聚類算法結合使用。5.1聚類算法簡介5.1.1聚類算法分類5.基于模型的方法基于模型的方法包括基于概率模型的方法和基于神經(jīng)網(wǎng)絡模型的方法。概率模型主要指概率生成模型，同一“類”的數(shù)據(jù)屬于同一種概率分布，即假設數(shù)據(jù)是根據(jù)潛在的概率分布生成的。高斯混合模型（GaussianMixtureModels，GMM）就是最典型、常用基于概率模型的聚類方法。自組織映射（SelfOrganizedMaps，SOM）則是一種常見的基于神經(jīng)網(wǎng)絡模型的方法。5.1聚類算法簡介5.1.2距離度量方法1.閔可夫斯基距離閔可夫斯基距離（MinkowskiDistance）將樣本看作高維空間中的點進行距離度量。P和Q的閔可夫斯基距離定義為：5.1聚類算法簡介5.1.2距離度量方法2.馬氏距離與歐氏距離、曼哈頓距離一樣，馬氏距離（MahalanobisDistance）常被用于評定數(shù)據(jù)之間的相似度指標，它可以看作是歐氏距離的修正，修正了歐氏距離中各維度尺度不一致且相關的問題。單個數(shù)據(jù)點的馬氏距離定義為：5.1聚類算法簡介5.1.2距離度量方法3.漢明距離漢明距離（HammingDistance）需要將處理的樣本數(shù)據(jù)轉換為0和1表示的二進制串，樣本中各分量的取值只能是0或1，例如字符串“1110”與“1001”之間的漢明距離為3。對于任意樣本特征和，有，其漢明距離為：5.1聚類算法簡介5.1.2距離度量方法4.夾角余弦夾角余弦（Cosine）度量將樣本看成是高維空間中的向量進行度量，度量方法就是計算兩個向量的余弦夾角。對于任意兩個n維樣本和，其夾角余弦為：5.2K-means聚類假設簇劃分為(C1,C2,...,Ck)，則目標就是最小化平方誤差：k均值聚類算法描述如下：輸入：訓練數(shù)據(jù)集D={x1,x2,…,xN}，聚類個數(shù)k。過程：（1）從D中隨機選擇k個樣本作為初始的均值向量：。（2）重復執(zhí)行以下過程，直至當前均值向量不再更新：①令，其中1≤i≤k。②對于i=1,2,…,N，選擇每個樣本與各均值向量mj(1≤j≤k)的距離：，根據(jù)離均值距離最小的確定其聚類標記：，將樣本劃入相應的聚類。③對于i=1,2,…,k，計算新的均值向量：，如果新的均值向量與之前的均值向量不相等，則更新，即，否則不更新。5.2K-means聚類西瓜數(shù)據(jù)集5.2K-means聚類1利用Parzen矩形窗估計概率密度、分類假設聚類個數(shù)為k=3，首先隨機選取3個樣本x3=(0.634,0.264)、x8=(0.437,0.211)、x9=(0.666,0.091)作為初始的均值向量，分別對應于3個聚類C1、C2、C3中的均值向量，初始時每個聚類中元素為空?？疾鞓颖緓1=(0.697,0.460)，它與當前的均值向量、、距離分別為0.206、0.360、0.370，因此x1被劃入聚類C1中，類似地，對x2,x3,…,x30所有樣本都執(zhí)行類似的過程，將每個樣本進行了劃分，故有：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聚類針對三文魚和鱸魚數(shù)據(jù)的聚類，使用K-means進行聚類。5.3基于密度的聚類──DBSCAN聚類5.3.1DBSCAN算法原理及相關概念給出樣本數(shù)據(jù)集合D=(x1,x2,...,xN)，相關概念描述如下：（1）?-鄰域：對于任一樣本xj∈D，其?-鄰域包含的樣本集是D中與xj的距離不大于?的樣本，即N?(xj)={xi∈D|distance(xi,xj)≤?}，其樣本集個數(shù)記作|N?(xj)|。（2）核心對象：對于任一樣本xj∈D，如果其?-鄰域包含至少minPts個樣本，即當|N?(xj)|≥MinPts時，則xj為一個核心對象。（3）密度直達：如果xi位于xj的?-鄰域中，且xj是核心對象，則稱xi由xj密度直達。（4）密度可達：對于xi和xj，如果存在樣本序列p1,p2,...,pn，滿足p1=xi、pn=xj，且1≤i<n，其pi+1由pi密度直達，則稱xj由xi密度可達。密度可達滿足傳遞性。（5）密度相連：對于xi和xj，如果存在核心對象樣本xk，使xi和xj均由xk密度可達，則稱xi和xj密度相連。密度相連關系滿足對稱性。5.3基于密度的聚類──DBSCAN聚類4.3.2DBSCAN聚類算法DBSCAN聚類算法根據(jù)設置的鄰域參數(shù)?、minPts先確定核心對象集合，然后隨機選擇一個核心對象確定相應的聚類簇，直到所有的核心對象都被訪問過為止。DBSCAN聚類算法描述如下：輸入：訓練數(shù)據(jù)集D={x1,x2,…,xN}、鄰域參數(shù)?、minPts。過程：（1）初始化核心對象集合、聚類簇數(shù)k=0、未訪問樣本集合Γ=D。（2）對于j=1,2,…,N：①通過距離度量方式，找到樣本的?-鄰域集合M?(xj)。②如果樣本集中樣本個數(shù)滿足|N?(xj)|≥minPts，則將樣本xj加入核心對象樣本集合：。5.3基于密度的聚類──DBSCAN聚類（3）如果核心對象集合，則算法結束，否則執(zhí)行第（4）步。（4）在核心對象集合Ω中，隨機選擇一個核心對象o，初始化當前簇核心對象隊列，初始化類別序號k=k+1，初始化當前簇樣本集合Ck={o}，更新未訪問樣本集合Γ=Γ?{o}。（5）如果當前簇核心對象隊列，則當前聚類簇Ck生成完畢，更新簇劃分C={C1,C2,...,Ck}，更新核心對象集合Ω=Ω?Ck，轉到第（3）步，否則更新核心對象集合Ω=Ω?Ck。（6）在當前簇核心對象隊列中取出一個核心對象o′，通過鄰域距離閾值?找出所有的?-鄰域樣本集M?(o′)，令Δ=M?(o′)∩Γ，更新當前簇樣本集合Ck=Ck∪Δ，更新未訪問樣本集合Γ=Γ?Δ，更新，轉到第（5）步執(zhí)行。輸出：簇劃分。5.3基于密度的聚類──DBSCAN聚類利用DBSCAN對西瓜數(shù)據(jù)集進行聚類。5.4基于層次的聚類──AGNES聚類5.4.1AGNES聚類算法思想AGNES采用自底而上合并聚類簇，每次找到距離最短的兩個聚類簇，然后合并成一個大的聚類簇，以此類推，直到全部樣本數(shù)據(jù)合并為一個聚類簇。整個聚類過程就形成了一個樹形結構，如圖所示。5.4基于層次的聚類──AGNES聚類AGNES聚類算法描述如下：輸入：樣本數(shù)據(jù)集D={x1,x2,…,xN}、聚類簇個數(shù)k、聚類簇度量函數(shù)get_dist。過程：（1）將每個對象看成是一個聚類簇，即對于任意的1≤j≤N，有。（2）根據(jù)聚類簇度量函數(shù)get_dist確定各個簇之間的距離。（3）設置當前簇個數(shù)q=N。（4）當q>k時，重復執(zhí)行以下步驟：①找出距離最近的兩個簇和，合并和：。②對編號為j+1,j+2,…,q的簇重新編號，依次為j,j+1,…,q-1。③對j=1,2,…,q-1，更新聚類簇之間的距離。④根據(jù)約束條件，確定新參數(shù)的上下界。5.4基于層次的聚類──AGNES聚類AGNES聚類算法在西瓜數(shù)據(jù)集上的運行結果5.5高斯混合聚類其概率密度函數(shù)如圖5-7所示：5.5高斯混合聚類一個混合高斯概率密度函數(shù)如圖5-8所示。5.5高斯混合聚類求導5.5高斯混合聚類高斯混合聚類的算法描述如下：5.5高斯混合聚類5.6各種聚類算法的比較5.7本章小結K-mean