Python數(shù)據(jù)分析與數(shù)據(jù)挖掘 課件 第9章 聚類

第9章聚類13-10月-23主講人：***Python數(shù)據(jù)分析與數(shù)據(jù)挖掘目錄contents聚類概述0102基于劃分的K-means聚類算法03基于層次的聚類04基于密度的聚類聚類概述01

將一群物理的或抽象的對象，根據(jù)它們之間的相似程度分成不同的類(簇)，使得各簇之間的相似度盡可能小，而簇內(nèi)數(shù)據(jù)之間則具有較高的相似度，這一過程就稱為聚類。

一個類(簇)就是由彼此相似的一組對象所構(gòu)成的集合，每個簇可能對應(yīng)于一些潛在的我們已知的概念(類別)，但這類概念對于聚類算法而言事先是未知的，聚類過程僅能自動形成簇結(jié)構(gòu)，簇所對應(yīng)的概念語義需由使用者來把握和命名。

采用聚類分析技術(shù)，可以把無標識數(shù)據(jù)對象自動劃分為不同的類，并且可以不受先驗知識的約束和干擾，獲取屬于數(shù)據(jù)集合中原本存在的信息。

聚類分析的數(shù)據(jù)沒有分類標記，由聚類算法自動確定，屬無監(jiān)督學習。9.1.1聚類的基本概念9.1.1聚類的基本概念數(shù)據(jù)矩陣(datamatrix)：又稱為對象屬性結(jié)構(gòu)，它用p個變量(也稱為屬性)來表現(xiàn)對象，例如用年齡、身高、性別等屬性來表現(xiàn)對象“人”。這種數(shù)據(jù)結(jié)構(gòu)是二維關(guān)系表(對象和屬性)的形式，或者看為p維(n個對象對應(yīng)的p個屬性)的矩陣。

相異度矩陣(dissimilaritymatrix)：又稱為對象-對象結(jié)構(gòu)，是存儲對象間的近似性的矩陣，表現(xiàn)形式是一個n維的矩陣。聚類代表性的數(shù)據(jù)結(jié)構(gòu)

性能度量，亦可稱聚類有效性指標(validityindex)。與有監(jiān)督學習中的性能度量相似，對聚類結(jié)果，需要通過某種性能度量來評估其好壞；另一方面，若明確了最終將要使用的性能度量，則可直接將其作為聚類過程的優(yōu)化目標，從而更好地得到符合要求的聚類結(jié)果。性能度量9.1.2聚類的距離度量

一般而言，會定義一個距離函數(shù)d(x，y)來確定對象之間的距離，而這個距離函數(shù)需要滿足以下幾個準則。

(1)d(x，x)=0，即一個對象與自身的距離為0。 (2)d(x，y)≥0，即距離是一個非負的數(shù)值。(3)d(x，y)=d(y，x)，即距離函數(shù)具有對稱性。 (4)d(x，y)≤d(x，k)+d(k，y)，即距離函數(shù)需要滿足三角不等式。

這些準則的作用是，即使在同一空間中定義了多個滿足這些準則的距離函數(shù)時，這些不同的距離函數(shù)能夠保持同樣的變化趨勢，也就是說不同的距離函數(shù)反映出的變化趨勢是相同的。

歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。它定義了多維空間中點與點之間的“直線距離”，其注重各個對象的特征在數(shù)值上的差異，適合用于從維度的數(shù)值中分析個體差異。歐氏距離加權(quán)歐式距離標準化歐氏距離歐氏距離（Sk是該維度的樣本標準差）9.1.2聚類的距離度量[例9-1]計算歐氏距離9.1.2聚類的距離度量9.1.3聚類的常用算法基于劃分的聚類算法，如：K-means、K-medoids等。基于層次的聚類算法，如：BIRCH、CURE等?；诿芏鹊木垲愃惴?，如：DBSCAN、OPTICS、DENCLUE等?；诰W(wǎng)格的聚類算法，如：STING、CLIQUE等。9.1.4聚類的評估

聚類評估用于評估在數(shù)據(jù)集上進行聚類的可行性，以及聚類算法產(chǎn)生結(jié)果的質(zhì)量。聚類評估主要包括：估計聚類趨勢、確定聚類簇數(shù)以及度量聚類質(zhì)量。9.1.4聚類的評估

聚類趨勢的估計，用于確定給定的數(shù)據(jù)集是否具有可以導致有意義聚類的非隨機結(jié)構(gòu)。聚類要求數(shù)據(jù)具有非均勻分布，一個沒有任何非隨機結(jié)構(gòu)的數(shù)據(jù)集（如數(shù)據(jù)空間中均勻分布的點），盡管聚類算法可以為這樣的數(shù)據(jù)集返回簇，但這些簇是隨機的，沒有任何意義?；羝战鹚菇y(tǒng)計量(HopkinsStatistic)是一種空間統(tǒng)計量，可以用來檢驗空間分布的變量的空間隨機性。1、估計聚類趨勢9.1.4聚類的評估

2、確定聚類簇數(shù)9.1.4聚類的評估

聚類質(zhì)量的度量指標通常有兩種。一種是外部指標，通常是有監(jiān)督的情況下，有參考標準的指標。外部指標將聚類算法的聚類結(jié)果和已知標準（有標簽的、人工標準或?qū)＜覙?gòu)建的理想聚類結(jié)果）相比較，來度量聚類算法和各參數(shù)的指標。另一類是內(nèi)部指標，通常是無監(jiān)督的方法，無需基準數(shù)據(jù)集，通過聚類之后，簇內(nèi)聚集程度和簇間離散程度來評估聚類的質(zhì)量。3、度量聚類質(zhì)量9.1.4聚類的評估

外部指標是基于已知分類標簽數(shù)據(jù)集（基準）進行評價的，這樣可以將原有標簽數(shù)據(jù)與聚類輸出結(jié)果進行對比?；谕獠恐笜说睦硐刖垲惤Y(jié)果是：具有不同類標簽的數(shù)據(jù)聚合到不同的簇中，具有相同類標簽的數(shù)據(jù)聚合相同的簇中。

主要的外部指標有：Jaccard系數(shù)（JaccardCoefficient,JC）、FM指數(shù)（FowlkesandMallowsIndex,FMI）、F值（F-measure）、Rand指數(shù)（RandIndex,RI）及調(diào)整蘭德系數(shù)（AdjustedRandIndex，ARI）等。上述指標的結(jié)果值均在[0,1]區(qū)間內(nèi)，值越大表明聚類算法和參考模型的聚類結(jié)果越接近，聚類質(zhì)量相對越好。3、度量聚類質(zhì)量——外部指標9.1.4聚類的評估

內(nèi)部指標主要基于無監(jiān)督的方法，無需基準數(shù)據(jù)，主要根據(jù)數(shù)據(jù)集的集合結(jié)構(gòu)信息，從緊密度、分離度、連通性和重疊度等方面對聚類劃分進行評價。內(nèi)部指標通過計算總體的相似度、簇間平均相似度或簇內(nèi)平均相似度等方面來評價聚類質(zhì)量。這類指標常用的有誤差平方和SSE、CH（Calinski-Harabasz）指標、輪廓系數(shù)等。誤差平方和SSE，又稱為inertia，計算簇中所有樣本點到質(zhì)心（centroids）距離的平方和。CH（Calinski-Harabasz）指標，通過計算類中各點與類中心距離的平方和來度量類內(nèi)的緊密度，通過計算各類中心點與數(shù)據(jù)集中心點距離的平方和來度量數(shù)據(jù)集的分離度。輪廓系數(shù)（SilhouetteCoefficient）指標：計算簇內(nèi)不相似度a，簇間不相似度b，單個樣本的輪廓系數(shù)s定義為：3. 度量聚類質(zhì)量——內(nèi)部指標基于劃分的K-means算法029.2.1k-means的基本概念

K-means聚類算法是一種無監(jiān)督分類算法，通過分離k個相等方差組的樣本來聚集數(shù)據(jù)，最小化簇內(nèi)誤差平方和SSE(SumoftheSquaredError,SSE)。

簡單來說，就是根據(jù)指定的簇的數(shù)量，分離出n組數(shù)據(jù)，并令它們每組的標準(簇內(nèi)誤差平方和)最小化。

對于給定一個包含n個對象的數(shù)據(jù)： K-means聚類算法會構(gòu)建初始的k個劃分，每個劃分表示一個簇，k≤n，并且每個簇滿足:①至少包含一個對象;②每個對象必須屬于且只屬于一個簇。然后采用迭代的重定位方法，通過在劃分間移動對象來改進劃分的質(zhì)量。

一個好的劃分的一般準則：在同一聚類中的對象之間盡可能“接近”，而不同聚類的對象之間盡可能“遠離”。9.2.1k-means的基本概念具體過程如下：mi是Ci的質(zhì)心，。Je是所有樣本的誤差平方和。9.2.1k-means的基本概念簇：表示數(shù)據(jù)的類。質(zhì)心：簇的中心，即中心點，通常使用簇內(nèi)各個對象的均值表示。聚類結(jié)果評價：簇內(nèi)誤差平方和(SSE)，公式如下所示：9.2.2k-means算法過程1、選擇隨機的k個簇的初始劃分，計算這些簇的質(zhì)心。2、根據(jù)歐氏距離把剩余的每個樣本分配到離它最近的簇質(zhì)心的一個劃分。3、計算被分配到每個簇的樣本的均值向量，做為新的簇的質(zhì)心。4、重復2,3步，直到k個簇的質(zhì)心點不再發(fā)生變化或誤差平方和最小。

時間復雜度：每一次迭代會把每一個對象劃分到離它最近的聚類中心所在的簇，這個過程的時間復雜度為O(nkd)，n是指總的數(shù)據(jù)對象個數(shù)，k是指定的聚類數(shù)，d是指數(shù)據(jù)對象的維數(shù)。1、質(zhì)心數(shù)量k是事先確定的，這個k值很難估計。很難知道給定的數(shù)據(jù)集應(yīng)該分成多少類才最合適。2、常采用誤差平方和函數(shù)作為聚類準則函數(shù)，常適用于各類之間區(qū)別明顯且數(shù)據(jù)分布稠密的樣本。但如果各類的形狀和大小差別很大，有可能出現(xiàn)將大的聚類分割的現(xiàn)象。3、在運用誤差平方和準則函數(shù)測度聚類效果時，最佳聚類結(jié)果對應(yīng)于目標函數(shù)的極值點，由于目標函數(shù)存在著許多局部極小點，而算法的每一步都沿著目標函數(shù)減小的方向進行，若初始化落在一個局部極小點附近，就會造成算法在局部極小點處收斂。因此初始聚類中心的隨機選取可能會陷入局部最優(yōu)解，而難以獲得全局最優(yōu)解。4、該算法需要不斷地對樣本聚類進行調(diào)整，不斷地計算新的聚類中心。因此，當數(shù)據(jù)量非常大時，算法的時間開銷將是非常大的。9.2.2k-means算法過程k-means算法的不足之處：9.2.3 scikit-learn中的K-means應(yīng)用sklearn.cluster模塊中KMeans函數(shù)用于K-means聚類。該函數(shù)主要參數(shù)如表9-1所示。表9-1KMeans函數(shù)的主要參數(shù)9.2.3 scikit-learn中的K-means應(yīng)用[例9-2]使用K-means對鳶尾花(iris)數(shù)據(jù)集進行聚類。

從結(jié)果圖可知，聚類分析產(chǎn)生的結(jié)果還是非常可靠的，雖然有一部分聚類的結(jié)果與實際情況不符，但是總體上非常接近。

第一類的聚類結(jié)果與實際情況完全相同，對第二類的聚類結(jié)果與第三類有些混淆，但僅僅是少數(shù)，多數(shù)的聚類結(jié)果還是正確的，存在的誤差可以接受。[例9-2]使用K-means對鳶尾花(iris)數(shù)據(jù)集進行聚類。圖9-1鳶尾花數(shù)據(jù)集K-Means聚類結(jié)果9.2.3 scikit-learn中的K-means應(yīng)用[例9-3]使用scikit中的make_blobs方法，生成聚類的樣本數(shù)據(jù)并用K-means進行聚類。9.2.3 scikit-learn中的K-means應(yīng)用[例9-3]使用scikit中的make_blobs方法，生成聚類的樣本數(shù)據(jù)并用K-means進行聚類。圖9-2make_blobs生成數(shù)據(jù)集的K-Means聚類結(jié)果9.2.3 scikit-learn中的K-means應(yīng)用基于層次的聚類039.3.1基于層次的聚類的基本原理1、核心思想

對數(shù)據(jù)集按照層次，把數(shù)據(jù)劃分到不同層的簇，從而形成一個樹形的聚類結(jié)構(gòu)，可以使用畫圖函數(shù)將樹形的聚類結(jié)構(gòu)輸出。2、基本原理

一開始將每個點都看成一個簇，然后計算各個數(shù)據(jù)點間的相似性，將所有數(shù)據(jù)點中最相似的兩個數(shù)據(jù)點進行組合，并反復迭代這一過程。

簡單的說，基于層次的聚類是通過計算每一個數(shù)據(jù)點與所有數(shù)據(jù)點之間的距離來確定它們之間的相似性，距離越小，相似度越高，并將距離最近的兩個數(shù)據(jù)點或類別進行組合，生成聚類樹。3、分類聚合聚類：特點：自底向上代表：BIRCH、ROCK算法聚類過程：將每個樣本看作一個簇，初始狀態(tài)下簇的數(shù)目等于樣本的數(shù)目，然后根據(jù)算法的規(guī)則對樣本進行合并，直到滿足算法的終止條件。分裂聚類：特點：自頂向下代表：DIANA算法聚類過程：先將所有樣本看作屬于同一個簇，然后逐漸分裂成更小的簇，直到滿足算法終止條件為止。9.3.1基于層次的聚類的基本原理9.3.2基于層次的聚類過程

CURE算法的具體過程為：（1）從總數(shù)據(jù)中隨機選取一個樣本；（2）利用層次聚類算法把這個樣本聚類，形成最初的簇；（3）生成“代表點”：對于每個簇，選取代表點（例如4個），這些點盡量分散，按照固定的比例α（收縮因子），把每個樣本點向簇的“質(zhì)心”收縮，生成代表點；（4）合并距離最近的簇直至簇個數(shù)為所要求的個數(shù)為止。1、CURE算法

CURE算法(ClusteringUsingRepresentative)是一種針對大型數(shù)據(jù)庫的高效聚類算法，它屬于凝聚層次聚類方法，可適應(yīng)非球形的幾何形狀數(shù)據(jù)的聚類，且對孤立點的處理更加健壯。（1）初始化，將每個樣本歸為一簇，計算每兩個簇之間的距離，也就是樣本與樣本之間的相似度。（2）尋找各個類之間最近的兩個簇，把他們歸為一簇。（3）重新計算新生成的這個簇與各個舊的簇之間的相似度。（4）重復(2)(3)直到所有樣本點都歸為一簇，結(jié)束。2、BIRCH算法

BIRCH(BalancedIterativeReducingandClusteringUsingHierarchies)全稱是：利用層次方法的平衡迭代規(guī)約和聚類，適合于數(shù)據(jù)量大、類別數(shù)較多的聚類任務(wù)。BIRCH采用了一種多階段聚類技術(shù)，是層次聚類和其他聚類算法的集成。BIRCH是一種基于距離的層次聚類算法，它最大的特點是能利用有限的內(nèi)存資源完成對大數(shù)據(jù)集的高質(zhì)量的聚類，同時通過單遍掃描數(shù)據(jù)集能最小化I/O代價。

BIRCH算法的具體過程為：9.3.2基于層次的聚類過程9.3.3 scikit-learn中的BIRCH應(yīng)用

sklearn.cluster模塊中Birch函數(shù)用于Birch聚類。該函數(shù)主要參數(shù)如表9-2所示：表9-2Birch函數(shù)的主要參數(shù)9.3.3 scikit-learn中的BIRCH應(yīng)用[例9-4]使用BIRCH對鳶尾花(iris)數(shù)據(jù)集進行聚類。

從結(jié)果上看，與K-means算法的結(jié)果基本相同，可以看出BIRCH算法在鳶尾花數(shù)據(jù)上的聚類效果也相對滿意。[例9-4]使用BIRCH對鳶尾花(iris)數(shù)據(jù)集進行聚類。圖9-3鳶尾花數(shù)據(jù)集BIRCH聚類結(jié)果9.3.3 scikit-learn中的BIRCH應(yīng)用[例9-5]使用make_blobs方法生成聚類的樣本數(shù)據(jù)，并用BIRCH進行聚類。9.3.3 scikit-learn中的BIRCH應(yīng)用9.3.3 scikit-learn中的BIRCH應(yīng)用圖9-4make_blobs生成數(shù)據(jù)集的BIRCH聚類結(jié)果[例9-5]使用make_blobs方法生成聚類的樣本數(shù)據(jù)，并用BIRCH進行聚類?；诿芏鹊木垲?41、定義

將樣本中的高密度區(qū)域(即樣本點分布稠密的區(qū)域)劃分為簇，將簇看作是樣本空間中被稀疏區(qū)域(噪聲)分隔開的稠密區(qū)域，是一種基于高密度連接區(qū)域的密度聚類算法。2、代表算法DBSCAN、OPTICS3、適用范圍

挖掘任意形狀的簇，并且能夠有效過濾掉噪聲樣本對于聚類結(jié)果的影響。9.4.1 基于密度的聚類的基本原理聚類過程—DBSCAN算法（1）以每一個樣本點xi為圓心，以eps為半徑畫一個圓。這個圓被稱為樣本點xi的eps鄰域。（2）對這個圓內(nèi)包含的點進行計數(shù)。如果一個圓中的樣本點的數(shù)目超過了我們設(shè)定的密度閾值MinPts，那么將該圓的樣本點圓心記為核心點，又稱核心對象。如果某個樣本點的eps鄰域內(nèi)樣本點的個數(shù)小于密度閾值但是其本身落在了核心點的鄰域內(nèi)，則稱該點為邊界點。除此之外，既不是核心點也不是邊界點的點，就是噪聲點。（3）核心點xi的eps鄰域內(nèi)的所有的點，都由xi密度直達(如果xi位于xj的eps鄰域中，且xj是核心對象，則稱xi由xj密度直達)。如果xj由xi密度直達，xk由xj密度直達。xn由xk密度直達，那么xn由xi密度可達。這個性質(zhì)說明了由密度直達的傳遞性，可以推導出密度可達。（4）如果對于xk，使xi和xj都可以由xk密度可達，那么就稱xi和xj密度相連。將密度相連的點連接在一起，就形成了我們的聚類簇。9.4.2 基于密度的聚類過程DBSCAN算法涉及兩個參數(shù)：半徑eps和密度閾值MinPts，算法的具體過程為：9.4.3 scikit-learn中的DBSCAN應(yīng)用

sklearn.cluster模塊中DBSCAN函數(shù)用于DBSCAN聚類。Sklearn中的DBSCAN模型主要參數(shù)有兩個：eps和min_samples，這兩個參數(shù)的組合對最終聚類效果有重要的影響，這兩個參數(shù)的含義如下：1. eps：float型，默認值為0.5。DBSCAN模型中最重要的參數(shù)，表示鄰域的距離閾值，即當將一個樣本視為在另一個樣本的鄰域中時，兩個樣本之間的最大距離。一般需要在多組值中選擇一個合適的閾值。若eps過大，則更多的點會落在核心對象的鄰域，此時簇數(shù)可能會減少，將不應(yīng)該聚為一類的樣本劃為一類。若eps過小，則類別數(shù)可能會增大，本應(yīng)是一類的樣本卻被劃分開。2. min_samples：int型，默認值為5。表示樣本點要成為核心對象所需要的鄰域樣本數(shù)閾值。通常和eps一起調(diào)參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內(nèi)部分本來是一類的樣本可能會被標為噪音點，類別數(shù)也會變多。反之min_samples過小的話，則會產(chǎn)生大量的核心對象，可能會導致類別數(shù)過少。9.4.3 scikit-learn中的DBSCAN應(yīng)用[例9-6]使用DBSCAN對鳶尾花(iris)數(shù)據(jù)集進行聚類。圖9-5鳶尾花數(shù)據(jù)集DBSCAN聚類結(jié)果[例9-6]使用DBSCAN對鳶尾花(iris)數(shù)據(jù)集進行聚類。9.4.3 scikit-learn中的DBSCAN應(yīng)用9.4.3 scikit-learn中的DBSCAN應(yīng)用[例9-7]使用make_blobs方法生成聚類的測試數(shù)據(jù)，并用DBSCAN進行聚類。9.4.3 scikit-learn中的DBSCAN應(yīng)用[例9-7]使用make_blobs方法生成聚類的測試數(shù)據(jù)，并用DBSCAN進行聚類。[例9-7]使用make_blobs方法生成聚類的測試數(shù)據(jù)，并用DBSCAN進行聚類。9.4.3 scikit-learn中的DBSCAN應(yīng)用圖9-6make_blobs生成數(shù)據(jù)集的DBSCAN聚類結(jié)果本章實踐例題本章實踐例題[例9-8]用肘方法為鳶尾花iris數(shù)據(jù)的K-means聚類選擇最優(yōu)的簇數(shù)k，并使用CH指標評價不同k時的聚類質(zhì)量。本章實踐例題[例9-8]用肘方法為鳶尾花iris數(shù)據(jù)的K-means聚類選擇最優(yōu)的簇數(shù)k，并使用CH指標評價不同k時的聚類質(zhì)量。本章實踐例題[例9-8]用肘方法為鳶尾花iris數(shù)據(jù)的K-means聚類選擇最優(yōu)的簇數(shù)k，并分別使用ARI和CH指標評價不同k時的聚類質(zhì)量。圖9-7用肘方法為iris的K-means聚類選擇最優(yōu)簇數(shù)k圖9-8簇數(shù)為3時K-means對iris數(shù)據(jù)的聚類結(jié)果本章實踐例題[例9-8]用肘方法為鳶尾花iris數(shù)據(jù)的K-means聚類選擇最優(yōu)的簇數(shù)k，并使用CH指標評價不同k時的聚類質(zhì)量。例9-9用PCA對iris數(shù)據(jù)進行降維，并用KMeans對降維后的數(shù)據(jù)進行聚類。本章實踐例題例9-9用PCA對iris數(shù)據(jù)進行降維，并用KMeans對降維后的數(shù)據(jù)進行聚類。本章實踐例題

圖9-9直接用KMeans對iris聚類的結(jié)果圖9-10對iri進行PCA降維后的聚類結(jié)果本章實踐例題[例9-10]非“球形簇”數(shù)據(jù)的不同聚類算法對比。本章實踐例題[