大數(shù)據(jù)管理與應(yīng)用 課件 第八章 數(shù)據(jù)聚類分析

第八章數(shù)據(jù)聚類分析大數(shù)據(jù)管理與應(yīng)用——主編：王剛副主編：劉婧、邵臻聚類分析方法能夠不依賴數(shù)據(jù)的標(biāo)簽信息，將大量數(shù)據(jù)歸并成若干個(gè)性質(zhì)相同的簇，已經(jīng)成為大數(shù)據(jù)管理與應(yīng)用的一個(gè)重要方法。在本章中您將了解聚類分析的基本概念、相似性度量、聚類分析的基本類型、性能度量，認(rèn)識(shí)不同類型聚類分析的主要特點(diǎn)，掌握典型聚類分析算法的主要思想和建模過程，以及如何在實(shí)際場(chǎng)景中進(jìn)行應(yīng)用。數(shù)據(jù)聚類分析概述基于層次的聚類分析基于劃分的聚類分析基于密度的聚類分析基于網(wǎng)格的聚類分析基于模型的聚類分析集成聚類分析第八章

數(shù)據(jù)聚類分析01數(shù)據(jù)聚類分析概述02基于層次的聚類分析03基于劃分的聚類分析04基于密度的聚類分析05基于網(wǎng)格的聚類分析06基于模型的聚類分析07集成聚類分析聚類分析（ClusteringAnalysis）是大數(shù)據(jù)管理與應(yīng)用的一個(gè)重要內(nèi)容。它能夠依據(jù)一定的準(zhǔn)則將大規(guī)模雜亂無(wú)序的數(shù)據(jù)歸并成若干個(gè)有意義的類別，使得同一個(gè)類別內(nèi)數(shù)據(jù)的差異盡可能小，不同類別間數(shù)據(jù)的差異盡可能大，進(jìn)而揭示出海量數(shù)據(jù)之間的深層次結(jié)構(gòu)信息聚類分析中得到的一組數(shù)據(jù)對(duì)象的集合，稱其為簇（Cluster）。同一簇中的數(shù)據(jù)彼此相似，不同簇的數(shù)據(jù)彼此相異，具有良好的簇內(nèi)相似性與簇間分離性。一個(gè)完整的聚類分析過程主要包括數(shù)據(jù)預(yù)處理、特征構(gòu)建、相似度計(jì)算、聚類分析算法選擇、聚類結(jié)果性能度量等。1.1數(shù)據(jù)聚類分析的基本概念圖8-1聚類分析過程樣本的相似性度量樣本之間的相似性描述樣本之間的親疏遠(yuǎn)近程度，是歸并類的一個(gè)重要準(zhǔn)則。其中，距離是把樣本看成向量空間中的點(diǎn)，以該空間點(diǎn)與點(diǎn)之間的距離描述樣本與樣本之間的相似性程度，這是一種常用的度量樣本相似性的方法。簇間的相似性度量除了需要定義樣本之間相似度，聚類分析中還需要度量簇與簇之間的相似度。簇是一組相似樣本的集合?？梢酝ㄟ^樣本之間的距離來定義簇。簇的特征可以從不同角度進(jìn)行構(gòu)建，常用的有簇中心，即簇中所有樣本的均值；簇直徑，即簇中任意兩個(gè)樣本的最大距離。簇間的相似性一般采用距離進(jìn)行度量，一般有最小距離，最大距離，平均距離，中心距離四種。1.2相似性度量在聚類研究領(lǐng)域中，已經(jīng)存在大量的聚類算法，具體選擇某種聚類算法主要取決于數(shù)據(jù)的類型、聚類分析的場(chǎng)景。大體上，現(xiàn)有的聚類分析方法可以分為：基于劃分的聚類分析基于層次的聚類分析基于密度的聚類算法基于網(wǎng)格的聚類分析基于模型的聚類分析基于集成的聚類分析1.3數(shù)據(jù)聚類分析的基本類型聚類的性能度量大致可以分為兩類：外部指標(biāo)（ExternalIndex）：需要利用數(shù)據(jù)結(jié)構(gòu)的先驗(yàn)知識(shí)進(jìn)行評(píng)價(jià)，即將聚類結(jié)果與某個(gè)參考標(biāo)簽進(jìn)行比較；內(nèi)部指標(biāo)（InternalIndex）：直接利用數(shù)據(jù)的內(nèi)在結(jié)構(gòu)特性的進(jìn)行評(píng)價(jià)，即直接考察聚類結(jié)果而不利用任何參考標(biāo)簽。1.4聚類性能度量ACCNMIARINCCEntropyCompactnessSilhouetteIndex基于層次的聚類分析通過對(duì)樣本數(shù)據(jù)的遞歸劃分創(chuàng)建一個(gè)相應(yīng)的樹狀結(jié)構(gòu)層次進(jìn)行聚類。對(duì)于樣本數(shù)據(jù)的劃分，可以采用自下而上的凝聚策略，也可以采用自上而下的分裂策略。自下而上的凝聚式聚類首先將數(shù)據(jù)集中的每個(gè)樣本分別視為一個(gè)初始簇，然后根據(jù)距離大小不斷迭代合并相近的兩個(gè)簇，直至達(dá)到預(yù)設(shè)的簇個(gè)數(shù)，或者所有的樣本都在一個(gè)簇中。絕大多數(shù)的層次聚類算法都屬于這一類，如AGENS（AGlomerativeNESting）、ROCK（RObustClusteringusinglinKs）等。自上而下的分裂式聚類則與凝聚式聚類相反，它首先將數(shù)據(jù)集中的所有樣本視為一個(gè)初始簇，然后逐漸迭代分裂成越來越小的簇，直到達(dá)到預(yù)設(shè)的簇個(gè)數(shù)，或者每個(gè)樣本自成一簇。常見的分裂式聚類算法有單元分裂方法、DIANA（DIvisiveANAlysis）等。2.1基于層次的聚類分析的概念

2.1基于層次的聚類分析的概念圖8-2層次聚類的簡(jiǎn)單例子AGENS模型概述AGENS模型是一種典型的自下向上的凝聚式聚類分析方法。該聚類模型歷史比較悠久，1951年Florek等人依據(jù)最小距離作為簇距離實(shí)現(xiàn)聚類目標(biāo)，不久，不同學(xué)者選擇不同指標(biāo)度量簇距離，這些可以理解為AGENS模型的雛形。1990年，Kaufman和Rousseeuw對(duì)這些凝聚策略進(jìn)行總結(jié)，并提出AGENS模型以及其建模過程。AGENS模型的主要思想是采用自下向上的凝聚策略創(chuàng)建樹狀層次結(jié)構(gòu)，先對(duì)樣本數(shù)據(jù)進(jìn)行初始化，即把每個(gè)樣本當(dāng)成一個(gè)簇，然后不斷重復(fù)迭代合并簇間距離最小的兩個(gè)簇，直至達(dá)到終止條件。這樣一個(gè)樹狀的層次結(jié)構(gòu)已經(jīng)形成，每層鏈接一組聚類簇，在特定層次下進(jìn)行分割就可以得到相應(yīng)的聚類結(jié)果。2.2AGENS模型

2.2AGENS模型模型對(duì)于20個(gè)隨機(jī)數(shù)樣本上形成的樹狀結(jié)構(gòu)，每層鏈接一組類簇，根據(jù)給定聚類數(shù)目進(jìn)行分割，即可得到每一樣本相應(yīng)的簇標(biāo)簽。AGENS是一個(gè)構(gòu)建層次樹狀結(jié)構(gòu)的過程，其模型也就是特定的樹狀層次結(jié)構(gòu)。

2.2AGENS模型圖8-3AGENS樹狀圖策略AGENS模型首先需要確定簇間距離的度量標(biāo)準(zhǔn)，當(dāng)根據(jù)最小距離、最大距離和平均距離計(jì)算簇間距離時(shí)，AGENS模型又可分別稱為“單鏈接”、“全鏈接”、“均鏈接”算法。AGENS模型主要采用貪心策略每次合并簇間距離最小的兩個(gè)簇，最終形成一種層次的樹狀結(jié)構(gòu)，使得該樹狀結(jié)構(gòu)在任一層次的同一分支上的簇內(nèi)距離最小，且每一層次對(duì)應(yīng)的簇的數(shù)目也不相同。2.2AGENS模型算法AGNES模型先初始化數(shù)據(jù)集中的簇，再通過不斷迭代地遍歷所有簇并合并最小簇間距離的兩個(gè)簇，直至達(dá)到一定停止條件。AGNES模型的算法偽代碼：2.2AGENS模型基于劃分的聚類分析把聚類問題轉(zhuǎn)化成一個(gè)組合優(yōu)化問題，一般先對(duì)數(shù)據(jù)集進(jìn)行初始化分，接下來通過不斷迭代優(yōu)化目標(biāo)函數(shù)來調(diào)整劃分，直至逐漸收斂，得到一個(gè)最終劃分作為聚類結(jié)果。該方法需要事先確定初始聚類劃分和聚類數(shù)目，根據(jù)一定的劃分準(zhǔn)則，使得每個(gè)樣本與其簇中心的差異性之和最小，進(jìn)而實(shí)現(xiàn)簇內(nèi)樣本相似、簇間樣本相異的目標(biāo)。根據(jù)在聚類過程中樣本是否僅能屬于一個(gè)簇，可以進(jìn)一步分為硬劃分聚類分析和模糊劃分聚類分析。硬劃分聚類分析方法假定樣本能夠明確地劃分到一個(gè)簇中，如K-Means、K-Medoids等；模糊劃分聚類分析方法則以隸屬度將樣本分配到不同的簇中，簇與簇之間邊界的嚴(yán)格性大大降低，如FuzzyC-Means（FCM）等。

3.1基于劃分的聚類分析的概念K-Means模型概述K-Means模型的發(fā)展歷史比較悠久。20世紀(jì)50年代，HugoSteinhaus提出K-Means模型的基本想法，1957年StuartLloyd設(shè)計(jì)出第一個(gè)可行的算法，1967年JamesMacQueen正式提出并使用這一術(shù)語(yǔ)。經(jīng)過60多年的發(fā)展，K-Means模型已經(jīng)被公認(rèn)為經(jīng)典的劃分聚類方法，在圖像分割、模式識(shí)別、客戶行為分析等領(lǐng)域中有著廣泛的應(yīng)用。此外，針對(duì)該算法存在的缺陷以及為了日益變化的數(shù)據(jù)分析需求，不同領(lǐng)域的學(xué)者對(duì)其進(jìn)行改進(jìn)，衍生出多個(gè)變體。K-Means模型中的“K”指劃分簇的數(shù)量，即聚類類別數(shù)目，“Means”則代表選擇平均值作為定義聚類中心的策略。K-Means模型主要思想是先對(duì)給定的數(shù)據(jù)集初始劃分成K個(gè)互斥子集，構(gòu)成K個(gè)簇，使得每個(gè)簇至少包含一個(gè)對(duì)象，每個(gè)對(duì)象僅屬于一個(gè)簇，然后不斷迭代更新求解，使得每個(gè)簇內(nèi)數(shù)據(jù)的相似度盡可能高，每個(gè)簇間數(shù)據(jù)的相似度盡可能低。3.2K-Means模型

3.2K-Means模型

3.2K-Means模型算法K-Means模型的算法是一種迭代求解的過程，需要不斷更新簇中心和簇集合。

K-Means模型的算法偽代碼：3.2K-Means模型基于密度的聚類分析假設(shè)數(shù)據(jù)分布的緊密程度能夠確定隱藏的聚類結(jié)構(gòu)，基于樣本密度來考察樣本之間的可連接性，并根據(jù)可連接樣本不斷擴(kuò)展聚類簇，使得高密度的數(shù)據(jù)集合成為一個(gè)簇，不同簇由低密度的區(qū)域分割開來。該算法能夠過濾噪聲或異常點(diǎn)，很好地識(shí)別出任意形狀的聚類簇，對(duì)數(shù)據(jù)分布沒有偏好。其代表算法有：DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）、OPTICS（OrderingPointToIdentifytheClusterStructure）等。4.1基于密度的聚類分析的概念

4.2DBSCAN模型圖8-4DBSCAN聚類效果圖基本概念密度相連、密度可達(dá)、密度直達(dá)依次對(duì)樣本之間的可連接性條件逐漸嚴(yán)格。其中，密度直達(dá)關(guān)系通常不滿足對(duì)稱性；密度可達(dá)關(guān)系滿足直遞性，但可能不滿足對(duì)稱性；密度相連關(guān)系滿足對(duì)稱性。4.2DBSCAN模型

4.2DBSCAN模型

4.2DBSCAN模型算法DBSCAN模型主要通過遍歷搜索顯式產(chǎn)生最佳的類簇集合。DBSCAN模型的算法偽代碼：4.2DBSCAN模型基于網(wǎng)格的聚類分析對(duì)數(shù)據(jù)空間劃分成有限數(shù)目的網(wǎng)格單元，形成多分辨率的網(wǎng)格結(jié)構(gòu)，并在這個(gè)網(wǎng)格結(jié)構(gòu)上執(zhí)行所有的聚類操作，發(fā)現(xiàn)任意形狀的簇。一般而言，該算法在每一網(wǎng)格單元保存落入其中的數(shù)據(jù)的相關(guān)統(tǒng)計(jì)信息，并假設(shè)在同一網(wǎng)格單元的數(shù)據(jù)屬于同一個(gè)簇。這種方式具有快速的處理速度，計(jì)算時(shí)間與樣本數(shù)量獨(dú)立，只與網(wǎng)絡(luò)結(jié)構(gòu)上的單元數(shù)目有關(guān)，但簇劃分的準(zhǔn)確度與精度也與網(wǎng)格單元的大小緊密相關(guān)，若網(wǎng)格單元的粒度較細(xì)，則聚類結(jié)果的準(zhǔn)確性較高，同時(shí)也會(huì)提高算法的計(jì)算復(fù)雜度。網(wǎng)格聚類方法適用于比較分散、并不密集的空間多維數(shù)據(jù)的挖掘，具有廣闊的發(fā)展空間。目前常見的網(wǎng)格聚類方法有STING（StatisticalInformationGrid）、WaveCluster、CLIQUE（ClusteringInQuest）等。5.1基于網(wǎng)格的聚類分析的概念STING模型概述STING模型是一個(gè)典型的基于網(wǎng)格的聚類分析方法。它于1997被Wang等人提出，通過創(chuàng)建多層次的網(wǎng)格結(jié)構(gòu)將空間區(qū)域劃分為多分辨率的矩形單元，每一單元存放著關(guān)于數(shù)據(jù)的統(tǒng)計(jì)信息。該模型中，網(wǎng)格計(jì)算與查詢處理這兩步驟彼此獨(dú)立，效率較高，但聚類質(zhì)量受網(wǎng)格結(jié)構(gòu)最底層的粒度影響較大。5.2STING模型

模型STING模型基于多分辨率網(wǎng)格結(jié)構(gòu)進(jìn)行聚類的操作，所以其模型是數(shù)據(jù)的多分辨率網(wǎng)格結(jié)構(gòu)。該網(wǎng)格結(jié)構(gòu)在每一分辨率下將空間區(qū)域劃分為互不相交的矩形單元，不同分辨率下的單元形成一個(gè)層次結(jié)構(gòu)，且一個(gè)高層的矩形單元可以相應(yīng)地被劃分成低層的多個(gè)矩形單元（一般是4個(gè)單元，稱為四象限子單元）。每一矩形單元預(yù)先計(jì)算并存儲(chǔ)一些統(tǒng)計(jì)信息用以描述單元屬性，一般最底層單元的統(tǒng)計(jì)信息從數(shù)據(jù)中計(jì)算得到，而高層單元從其對(duì)應(yīng)的底層單元中計(jì)算出相應(yīng)的統(tǒng)計(jì)信息。5.2STING模型圖8-6STING模型的多分辨率網(wǎng)格結(jié)構(gòu)策略STING模型一般采取自上向下的策略對(duì)預(yù)先存儲(chǔ)數(shù)據(jù)統(tǒng)計(jì)信息的網(wǎng)格結(jié)構(gòu)進(jìn)行查詢處理，得到相應(yīng)的聚類結(jié)果。一般采用類似SQL的查詢語(yǔ)言進(jìn)行自上而下的單元查詢。一般選定其中一層（并非一定是根層）作為查詢處理的起點(diǎn)，對(duì)當(dāng)前層次的每一單元計(jì)算其與查詢條件的置信水平，并依據(jù)置信水平分為相關(guān)單元和無(wú)關(guān)單元，接下來對(duì)相關(guān)單元的下一層矩形單元進(jìn)行上述步驟，直至查詢到最底層。5.2STING模型算法STING模型主要包括網(wǎng)格結(jié)構(gòu)建立和自上向下查詢的過程。STING模型的算法偽代碼：5.2STING模型基于模型的聚類分析為每個(gè)簇假定了一個(gè)模型，根據(jù)數(shù)據(jù)對(duì)模型參數(shù)進(jìn)行不斷優(yōu)化得到最佳擬合，進(jìn)而實(shí)現(xiàn)聚類的目標(biāo)。該算法可以通過數(shù)據(jù)的特定模型來定位聚類，考慮到噪聲和異常值，可以產(chǎn)生更加魯棒健壯的聚類算法。但現(xiàn)有算法大都假設(shè)每一簇的分布是高斯分布，這使得該算法僅在具有凸形結(jié)構(gòu)的數(shù)據(jù)上有良好的聚類效果，難以推廣到具有任意分布的復(fù)雜形式的聚類問題上。常用的基于模型聚類算法有：COBWEB、SOM聚類（Self-organizingMapsClustering）、EM聚類（Expectation-maximizationClustering）等。6.1基于模型的聚類分析的概念EM聚類模型概述EM聚類模型是EM算法在無(wú)監(jiān)督學(xué)習(xí)的一個(gè)重要應(yīng)用。EM算法是1997年由Dempster等人總結(jié)提出的一種迭代算法，主要用于含有隱變量的概率模型的參數(shù)估計(jì)問題。EM聚類模型首先假設(shè)數(shù)據(jù)的分布滿足一種有限混合模型，一般為高斯混合模型。其每個(gè)簇都可以用高斯密度函數(shù)進(jìn)行描述，主要參數(shù)有均值和協(xié)方差矩陣，不同簇之間相互獨(dú)立。通過擬合該混合模型的參數(shù)計(jì)算出樣本屬于每一簇的概率，進(jìn)而得到相應(yīng)的簇標(biāo)記。由于在優(yōu)化過程中使用EM算法進(jìn)行參數(shù)估計(jì)，因此該方法稱為EM聚類模型。6.2EM聚類模型圖8-7混合高斯分布的概率密度函數(shù)圖

6.2EM聚類模型

6.2EM聚類模型

6.2EM聚類模型

6.2EM聚類模型集成學(xué)習(xí)通過集成多個(gè)不同的學(xué)習(xí)器來解決同一個(gè)問題，能夠提高其學(xué)習(xí)能力和表現(xiàn)性能，逐漸成為機(jī)器學(xué)習(xí)中最熱門的研究領(lǐng)域之一，被廣泛用于神經(jīng)網(wǎng)絡(luò)、統(tǒng)計(jì)學(xué)等領(lǐng)域。它于20世紀(jì)九十年代中期被提出，最開始主要研究有監(jiān)督學(xué)習(xí)的集成，后來在21世紀(jì)開始逐漸研究無(wú)監(jiān)督學(xué)習(xí)的集成，其中，集成聚類的概念便是在2002年被Strehl等人首次提出。7.1集成聚類分析的概念

7.1集成聚類分析的概念圖8-8集成聚類過程圖集成聚類需要兩個(gè)關(guān)鍵步驟：一是生成多個(gè)聚類結(jié)果，另一是對(duì)這些聚類結(jié)果進(jìn)行集成。相應(yīng)地，集成聚類主要研究?jī)煞矫娴膯栴}：其一是如何生成多個(gè)不同的聚類結(jié)果，其二是如何設(shè)計(jì)有效的共識(shí)函數(shù)對(duì)聚類結(jié)果進(jìn)行集成，得到一個(gè)能反映數(shù)據(jù)集結(jié)構(gòu)的數(shù)據(jù)劃分。聚類成員生成集成聚類的第一步就是生成多個(gè)聚類結(jié)果，即生成聚類成員?？紤]到集體的差異度是影響集成結(jié)果的關(guān)鍵因素之一，在生成聚類成員這一步驟中希望聚類結(jié)果間具有一定的差異度，可以從不同方面反映數(shù)據(jù)的結(jié)構(gòu)，進(jìn)而提高最終的集成聚類結(jié)果。一般而言，生成聚類成員主要包括：7.1集成聚類分析的概念圖8-9聚類成員生成方式圖共識(shí)函數(shù)設(shè)計(jì)共識(shí)函數(shù)是對(duì)聚類成員進(jìn)行集成進(jìn)而得到統(tǒng)一的聚類結(jié)果的函數(shù)。共識(shí)函數(shù)的方法主要分為基于ObjectsCo-Occurrence的方法和基于MedianPartition方法，分別對(duì)應(yīng)兩種解決集成問題的思路。7.1集成聚類分析的概念圖8-10共識(shí)函數(shù)設(shè)計(jì)圖基于共聯(lián)矩陣的Voting-k-means概述2001年，F(xiàn)red提出一種基于共聯(lián)矩陣的共識(shí)函數(shù)，并在此基礎(chǔ)上實(shí)現(xiàn)Voting-k-means模型。這是一種基于ObjectsCo-Occurrence的集成聚類模型，主要通過把聚類集體中的成員映射到一種中間表示形式，即共聯(lián)矩陣，再根據(jù)多數(shù)投票法進(jìn)行集成并得到最終的聚類結(jié)果。該模型利用K-Means算法的隨機(jī)性生成具有差異度的聚類集體，以樣本對(duì)在同一類出現(xiàn)的比例構(gòu)建共聯(lián)矩陣并作為標(biāo)準(zhǔn)化的投票，根據(jù)一定閾值確定最終的集成聚類結(jié)果。7.2基于共聯(lián)矩陣的Voting-k-means模型圖8-11共聯(lián)矩陣構(gòu)建過程圖

7.2基于共聯(lián)矩陣的Voting-k-means模型

7.2基于共聯(lián)矩陣的Voting-k-means模型策略Voting-k-means模型遍歷聚類集體中所有樣本，計(jì)算任意兩個(gè)樣本共同出現(xiàn)在同一個(gè)簇的次數(shù)，并進(jìn)行歸一化，得到樣本的共聯(lián)矩陣。矩陣中的每一元素可以理解為歸一化后的投票，然后根據(jù)多數(shù)投票的策略選擇一定的閾值判斷樣本是否屬于同一個(gè)簇，生成最終的集成聚類結(jié)果。這樣的策略可以不需要對(duì)聚類集體中的標(biāo)簽進(jìn)行預(yù)處理便能得到反映樣本之間相似度的信息，再根據(jù)投票的策略集成聚類集體中共同信息，得到最終的預(yù)測(cè)結(jié)果。7.2基于共聯(lián)矩陣的Voting-k-means模型算法Voting-k-means模型的算法包括聚類成員生成和共識(shí)函數(shù)設(shè)計(jì)這兩個(gè)步驟。第一步是生成具有差異度的聚類集體；第二步是根據(jù)共識(shí)函數(shù)集成聚類結(jié)果。Voting-k-means模型的算法偽代碼：7.2基于共聯(lián)矩陣的Voting-k-means模型基于信息論的集成聚類概述2005年，Tophy等人把集成聚類問題當(dāng)成基于互信息的優(yōu)化問題，提出了基于信息論的集成聚類方法，稱為QuadraticMutualInformationclust