“1+X”(中級(jí))08-聚類分析

聚類分析課程目錄8.1.聚類分析概述

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應(yīng)用場景

8.1.5.聚類算法的分類8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題聚類分析的定義聚類分析是一組將研究對(duì)象分為相對(duì)同質(zhì)的群組的統(tǒng)計(jì)分析技術(shù)。聚類分析對(duì)具有共同趨勢(shì)或結(jié)構(gòu)的數(shù)據(jù)進(jìn)行分組，將數(shù)據(jù)項(xiàng)分組成多個(gè)簇（類），簇之間的數(shù)據(jù)差別盡可能大，簇內(nèi)的數(shù)據(jù)差別盡可能小，即“最小化”簇內(nèi)的相似性，最大化簇間的相似性。它主要解決的是把一群對(duì)象劃分成若干個(gè)組的問題。劃分的依據(jù)是聚類問題的核心。所謂“物以類聚，人以群分”，故得名聚類。聚類分析的定義課程目錄8.1.聚類分析概述

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應(yīng)用場景

8.1.5.聚類算法的分類8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題聚類分析提出的背景聚類是在預(yù)先不知道分類的情況下，根據(jù)信息相似度原則進(jìn)行信息聚類的一種方法。聚類的目的是將大量的數(shù)據(jù)通過“屬于同類別的對(duì)象之間的差別盡可能的小，而不同類別上的對(duì)象的差別盡可能的大”的原則進(jìn)行分類。因此，聚類的意義就在于將觀察到的內(nèi)容組織成類分層結(jié)構(gòu)，把類似的事物組織在一起。通過聚類分析，人們能夠識(shí)別密集的和稀疏的區(qū)域因而發(fā)現(xiàn)全局的分布模式以及數(shù)據(jù)屬性之間的有趣的關(guān)系。聚類分析的過程示意課程目錄8.1.聚類分析概述

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應(yīng)用場景

8.1.5.聚類算法的分類8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題聚類分析的原理聚類分析是將樣品或變量按照它們?cè)谛再|(zhì)上的親疏程度進(jìn)行分類的數(shù)據(jù)分析方法。它是典型的無監(jiān)督分析方法，也就是沒有關(guān)于樣品或變量的分類標(biāo)簽，分類需要依據(jù)樣品或者變量的親疏程度進(jìn)行。聚類分析的原理描述樣品或變量親疏程度的兩個(gè)途徑個(gè)體間差異度個(gè)體間相似度把每個(gè)樣品或變量看成是多維空間上的一個(gè)點(diǎn)，在多維坐標(biāo)中，定義點(diǎn)與點(diǎn)、類和類之間的距離，用點(diǎn)與點(diǎn)間距離來描述樣品或變量之間的親疏程度。計(jì)算樣品或變量的簡單相關(guān)系數(shù)或者等級(jí)相關(guān)系數(shù)，用相似系數(shù)來描述樣品或變量之間的親疏程度。課程目錄8.1.聚類分析概述

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應(yīng)用場景

8.1.5.聚類算法的分類8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題聚類分析的應(yīng)用場景商業(yè)方面用來將用戶根據(jù)其性質(zhì)分類，從而發(fā)現(xiàn)不同的客戶群，并且通過購買模式刻畫不同的客戶群特征。計(jì)算生物學(xué)領(lǐng)域用來對(duì)動(dòng)植物和對(duì)基因進(jìn)行分類，從而獲得更加準(zhǔn)確的生物分類。保險(xiǎn)領(lǐng)域根據(jù)住宅類型、價(jià)值、地理位置來鑒定一個(gè)城市的房產(chǎn)分組。電子商務(wù)發(fā)現(xiàn)具有相似瀏覽行為的客戶，并分析客戶的共同特征，可以更好地幫助電子商務(wù)的用戶了解自己的客戶，向客戶提供更合適的服務(wù)。聚類分析在不同領(lǐng)域有著廣泛應(yīng)用。課程目錄8.1.聚類分析概述

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應(yīng)用場景

8.1.5.聚類算法的分類8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題聚類算法的分類基于劃分的聚類基于層次的聚類基于密度的聚類基于網(wǎng)格的聚類基于模型的聚類對(duì)給定的數(shù)據(jù)集合，事先指定劃分為k個(gè)類別。典型算法：k-均值法和k-中心點(diǎn)算法等。對(duì)給定的數(shù)據(jù)集合進(jìn)行層次分解，不需要預(yù)先給定聚類數(shù)，但要給定終止條件，包括凝聚法和分裂法。典型算法：CURE、Chameleon、BIRCH、Agglomerative。只要某簇鄰近區(qū)域的密度超過設(shè)定的閾值，則擴(kuò)大簇的范圍，繼續(xù)聚類。這類算法可以獲得任意形狀的簇。典型算法：DBSCAN、OPTICS和DENCLUE等。首先將問題空間量化為有限數(shù)目的單元，形成一個(gè)空間網(wǎng)格結(jié)構(gòu)，隨后聚類在這些網(wǎng)格之間進(jìn)行。典型算法：STING、WareCluster和CLIQUE等。為每個(gè)簇假定一個(gè)模型，尋找數(shù)據(jù)對(duì)模型的最佳擬合?；诘募僭O(shè)是：數(shù)據(jù)是根據(jù)潛在的概率分布生成的。典型算法：COBWEB和神經(jīng)網(wǎng)絡(luò)算法等。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類

8.2.1.k-均值算法

8.2.2.k-medoids算法8.2.3.k-prototype算法8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題k-均值算法概述K均值聚類（Kmeans）算法是無監(jiān)督聚類算法中的代表，該算法的主要作用是將相似的樣本自動(dòng)歸到一個(gè)類別中。所謂的無監(jiān)督算法，就是輸入樣本沒有對(duì)應(yīng)的輸出或標(biāo)簽。K均值聚類算法十分簡單易懂而且非常有效，但是合理的確定K值和K個(gè)初始類簇中心點(diǎn)對(duì)于聚類效果的好壞有很大的影響。k-均值算法適用場景K-means算法是集簡單和經(jīng)典于一身的基于距離的聚類算法采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為類簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。k-均值算法原理及步驟第一步第二步第三步第四步設(shè)定K值，即確定聚類數(shù)；確定各類中心；計(jì)算每個(gè)記錄到類中心的距離，并將該記錄歸到最近的類中；然后重新計(jì)算K類的中心點(diǎn)，更新原類族的中心；重復(fù)第二、三步，迭代到收斂標(biāo)準(zhǔn)停止。指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。k-均值算法原理及步驟第一步設(shè)定K值，即確定聚類數(shù)；確定各類中心；第一步，確定聚類個(gè)數(shù)、確定聚類中心、確定距離計(jì)算公式:觀察法枚舉法其他技術(shù)手段指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。k-均值算法原理及步驟第一步設(shè)定K值，即確定聚類數(shù)；確定各類中心；第一步，確定聚類個(gè)數(shù)、確定聚類中心、確定距離計(jì)算公式:觀察法枚舉法其他技術(shù)手段指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。k-均值算法原理及步驟第二步計(jì)算每個(gè)記錄到類中心的距離，并將該記錄歸到最近的類中；第二步，計(jì)算每個(gè)點(diǎn)到中心的距離,歸類指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。k-均值算法原理及步驟第三步然后重新計(jì)算K類的中心點(diǎn)，更新原類族的中心；第三步，計(jì)算每個(gè)點(diǎn)到中心的距離,歸類指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。第四步重復(fù)第二、三步，迭代到收斂標(biāo)準(zhǔn)停止。重復(fù)第二步，將各樣本點(diǎn)重新歸類劃分；重復(fù)第三步，根據(jù)新分類重新計(jì)算類中心；直到聚類中心不發(fā)生變化（達(dá)到收斂標(biāo)準(zhǔn)）或循環(huán)次數(shù)到達(dá)設(shè)置數(shù)值，迭代停止k-均值算法原理及步驟指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。k-均值算法偽代碼創(chuàng)建k個(gè)點(diǎn)作為初始的質(zhì)心點(diǎn)（隨機(jī)選擇）當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)

對(duì)數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)點(diǎn)

對(duì)每一個(gè)質(zhì)心

計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)的距離

將數(shù)據(jù)點(diǎn)分配到距離最近的簇

對(duì)每一個(gè)簇，計(jì)算簇中所有點(diǎn)的均值，并將均值作為質(zhì)心k-均值算法偽代碼k-均值算法python實(shí)現(xiàn)python實(shí)現(xiàn)的k-均值算法核心代碼機(jī)器學(xué)習(xí)PAI中對(duì)應(yīng)的組件機(jī)器學(xué)習(xí)PAI中對(duì)應(yīng)的組件為K均值聚類組件k-均值算法的特點(diǎn)小結(jié)指定聚類數(shù)目K確定K個(gè)數(shù)據(jù)中心，每個(gè)點(diǎn)分到距離最近的類中，重新計(jì)算K個(gè)類的中心，然后要么結(jié)束，要么重算所有點(diǎn)到新中心的距離聚類。其結(jié)束準(zhǔn)則包括迭代次數(shù)超過指定或者新的中心點(diǎn)距離上一次中心點(diǎn)的偏移量小于指定值。原理簡單、容易理解、容易實(shí)現(xiàn)聚類結(jié)果容易解釋聚類結(jié)果相對(duì)較好k值選擇不同，聚類結(jié)果相差較大初始聚類中心不同，聚類結(jié)果可能不同只能發(fā)現(xiàn)球狀簇，非球狀聚類效果差對(duì)于離群點(diǎn)和孤立點(diǎn)敏感樣本點(diǎn)較多，計(jì)算量偏大優(yōu)點(diǎn)缺點(diǎn)課程目錄8.1.聚類分析概述8.2.基于劃分的聚類

8.2.1.k-均值算法

8.2.2.k-medoids算法

8.2.3.k-prototype算法8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題k-medoids算法概述medoids算法是對(duì)k-means算法的一種改進(jìn)算法。由于對(duì)k-means算法對(duì)于異常值十分敏感，因此具有極大值的對(duì)象可能會(huì)產(chǎn)生嚴(yán)重扭曲的數(shù)據(jù)分布。所以我們可以使用k-medoids算法，它是集群中位于最中心的對(duì)象，而不是將集群中的平均值作為參考點(diǎn)。因此，分區(qū)的方法仍然可以基于最小化每個(gè)對(duì)象與其參考點(diǎn)之間的不相似程度之和的原理來進(jìn)行。這構(gòu)成了k-medoids方法的基礎(chǔ)。k-medoids算法與k-均值算法的差異及比較k-均值算法（即k-means）與k-medoids之間的差異就是可以理解為對(duì)于數(shù)據(jù)樣本的平均值和中位數(shù)之間的差異。原因：k-均值算法對(duì)于數(shù)據(jù)樣本的要求太高，要求所有數(shù)據(jù)樣本處在一個(gè)歐式空間中，對(duì)于有很多噪聲的數(shù)據(jù)就會(huì)造成極大的誤差。但對(duì)于非數(shù)值型數(shù)據(jù)樣本，不能夠計(jì)算平均值等實(shí)數(shù)型變量。取值范圍可以是連續(xù)空間中的任意值取值只能是數(shù)據(jù)樣本范圍中的樣本k-均值算法k-medoids算法PKk-medoids算法原理及步驟不采用簇中對(duì)象的平均值作為參照點(diǎn)，可以選用簇中位置最中心的對(duì)象，即medoid。這樣劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來執(zhí)行的。隨機(jī)選擇K個(gè)對(duì)象作為初始的代表對(duì)象；指派每個(gè)剩余的對(duì)象給離它最近的代表對(duì)象所代表的簇；隨意地選擇一個(gè)非代表對(duì)象；計(jì)算用代替的總代價(jià)ＳStep1Step2Step3Step4如果，則用替換，形成新的k個(gè)代表對(duì)象的集合。直到不發(fā)生變化。Step5迭代循環(huán)課程目錄8.1.聚類分析概述8.2.基于劃分的聚類

8.2.1.k-均值算法

8.2.2.k-medoids算法8.2.3.k-prototype算法8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題k-prototype算法概述K-prototype是處理混合屬性聚類的典型算法，它繼承了Kmean算法和Kmode算法的思想，并且加入了描述數(shù)據(jù)簇的原型和混合屬性數(shù)據(jù)之間的相異度計(jì)算公式。K-prototype算法是設(shè)定了一個(gè)目標(biāo)函數(shù)，類似于kmean的SSE（誤差平方和），不斷迭代，直到目標(biāo)函數(shù)值不變。K-prototype算法提出了混合屬性簇的原型，我們可以理解原型就是數(shù)值屬性聚類的質(zhì)心?；旌蠈傩灾写嬖跀?shù)值屬性和分類屬性，其原型的定義是數(shù)值屬性原型用屬性中所有屬性取值值的均值，分類屬性原型是分類屬性中選取屬性值取值頻率最高的屬性。合起來就是原型。k-prototype算法步驟K-prototype的算法步驟是：從數(shù)據(jù)集中隨機(jī)選取k個(gè)對(duì)象作為初始的k個(gè)簇的原型；遍歷數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)，計(jì)算數(shù)據(jù)與k個(gè)簇的相異度。然后將該數(shù)據(jù)分配到相異度最小的對(duì)應(yīng)的簇中，每次分配完畢后，更新簇的原型；然后計(jì)算目標(biāo)函數(shù)，然后對(duì)比目標(biāo)函數(shù)值是否改變，循環(huán)直到目標(biāo)函數(shù)值不在變化為止。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.3.1.BIRCH聚類

8.3.2.CURE算法8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題BIRCH算法基本概念BIRCH的全稱是：利用層次方法的平衡迭代規(guī)約和聚類（BalancedIterativeReducingandClusteringUsingHierarchies）BIRCH算法比較適合于數(shù)據(jù)量大，類別數(shù)K也比較多的情況。它運(yùn)行速度很快，只需要單遍掃描數(shù)據(jù)集就能進(jìn)行聚類BIRCH算法利用了一個(gè)樹結(jié)構(gòu)來幫助我們快速的聚類，這個(gè)數(shù)結(jié)構(gòu)類似于平衡B+樹，一般將它稱之為聚類特征樹(ClusteringFeatureTree，簡稱CFTree)。CFCFCF12B…RootNodeCFCFCF12B…Non-leafNodeLeafNodeCF1CF2…CFLLeafNodeCF1CF2…CFLLeafNodeCF1CF2…CFLBIRCH算法原理在聚類特征樹中，一個(gè)聚類特征CF是這樣定義的：每一個(gè)CF是一個(gè)三元組，可以用（N，LS，SS）表示。其中N代表了這個(gè)CF中擁有的樣本點(diǎn)的數(shù)量；LS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的和向量，SS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的平方和。1.從根節(jié)點(diǎn)向下尋找和新樣本距離最近的葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)里最近的CF節(jié)點(diǎn)；2.如果新樣本加入后，這個(gè)CF節(jié)點(diǎn)對(duì)應(yīng)的超球體半徑仍然滿足小于閾值T，則更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入3；3.如果當(dāng)前葉子節(jié)點(diǎn)的CF節(jié)點(diǎn)個(gè)數(shù)小于閾值L，則創(chuàng)建一個(gè)新的CF節(jié)點(diǎn)，放入新樣本，將新的CF節(jié)點(diǎn)放入這個(gè)葉子節(jié)點(diǎn)，更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入4；4.將當(dāng)前葉子節(jié)點(diǎn)劃分為兩個(gè)新葉子節(jié)點(diǎn)，選擇舊葉子節(jié)點(diǎn)中所有CF元組里超球體距離最遠(yuǎn)的兩個(gè)CF元組，作為兩個(gè)新葉子節(jié)點(diǎn)的第一個(gè)CF節(jié)點(diǎn)。將其他元組和新樣本元組按照距離遠(yuǎn)近原則放入對(duì)應(yīng)的葉子節(jié)點(diǎn)。依次向上檢查父節(jié)點(diǎn)是否也要分裂，如果需要按和葉子節(jié)點(diǎn)分裂方式相同。聚類特征樹CFTree的插入流程BIRCH算法流程及步驟BIRCH算法的主要過程就是建立CFTree的過程。除了建立CFTree來聚類，還有一些可選的算法步驟。整個(gè)BIRCH算法流程如下：第１步第２步（可選）第３步（可選）第４步（可選）將所有的樣本依次讀入，在內(nèi)存中建立一顆CFTree將第一步建立的CFTree進(jìn)行篩選，去除一些異常CF節(jié)點(diǎn)，這些節(jié)點(diǎn)一般里面的樣本點(diǎn)很少。對(duì)于一些超球體距離非常近的元組進(jìn)行合并。利用其它的一些聚類算法比如K-Means對(duì)所有的CF元組進(jìn)行聚類，得到一顆比較好的CFTree。利用第3步生成的CFTree的所有CF節(jié)點(diǎn)的質(zhì)心，作為初始質(zhì)心點(diǎn)，對(duì)所有的樣本點(diǎn)按距離遠(yuǎn)近進(jìn)行聚類。BIRCH算法的關(guān)鍵就是步驟1，也就是CFTree的生成，其他步驟都是為了優(yōu)化最后的聚類結(jié)果。BIRCH算法python實(shí)現(xiàn)Python實(shí)現(xiàn)算法示例：BIRCH聚類算法特點(diǎn)小結(jié)123123主要優(yōu)點(diǎn)主要缺點(diǎn)節(jié)約內(nèi)存，所有的樣本都在磁盤上，CFTree僅僅存了CF節(jié)點(diǎn)和對(duì)應(yīng)的指針。聚類速度快，只需要一遍掃描訓(xùn)練集就可以建立CFTree，CFTree的增刪改都很快。可以識(shí)別噪音點(diǎn)，還可以對(duì)數(shù)據(jù)集進(jìn)行初步分類的預(yù)處理由于CFTree對(duì)每個(gè)節(jié)點(diǎn)的CF個(gè)數(shù)有限制，導(dǎo)致聚類的結(jié)果可能和真實(shí)的類別分布不同。對(duì)高維特征的數(shù)據(jù)聚類效果不好。此時(shí)可以選擇MiniBatchK-Means如果數(shù)據(jù)集的分布簇不是類似于超球體，或者說不是凸的，則聚類效果不好。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.3.1.BIRCH聚類

8.3.2.CURE算法8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題CURE算法概述CURE對(duì)孤立點(diǎn)的處理更加健壯，而且能夠識(shí)別非球形和大小變化比較大的類。針對(duì)大型數(shù)據(jù)庫，CURE采用隨機(jī)取樣和劃分兩種方法組合：一個(gè)隨機(jī)樣本首先被劃分，每個(gè)劃分被部分聚類。絕大多數(shù)聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點(diǎn)時(shí)變得比較脆弱。CURE采用了一種新穎的層次聚類算法，該算法選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略。它不同于單個(gè)質(zhì)心或?qū)ο髞泶硪粋€(gè)類，而是選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)。CURE算法原理及步驟123456從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本S。將樣本S分割為一組劃分。對(duì)每個(gè)劃分局部的聚類。通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個(gè)類增長太慢，就去掉它。對(duì)局部的類進(jìn)行聚類。落在每個(gè)新形成的類中的代表點(diǎn)根據(jù)用戶定義的一個(gè)收縮因子收縮或向類中心移動(dòng)。這些點(diǎn)代表和捕捉到了類的形狀。用相應(yīng)的類標(biāo)簽來標(biāo)記數(shù)據(jù)。CURE算法偽代碼Procedurecluster(S,k)Begin1.T:=build_kd_tree(S)2.Q:=build_heap(S)3:whilesize(Q)>kdo{u:=extract_min(Q)v:=u.closet()Delete(Q,v)w:=merge(u,v)delete_rep(T,u);delete_rep(T,v);insert_rep(T,w)w.closet:=xforeachx∈Qdo{ifdist(w,x)<dist(w,w.closet)w.closet:=x

ifx.closetiseitheruorv{ifdist(x,x.closet)<dist(x,w)

x.closet:=closet_cluster(T,x,dist(x,w))16.else17.x.closet:=w;18.

relocate(Q,x)19.}20.elseifdist(x,x.close)>dist(x,w){21.x.closet:=w;22.relocate(Q,x)23.}24.}25.Insert(Q,w)26.}end課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題DBSCAN算法概述DBSCAN，英文全寫為Density-basedspatialclusteringofapplicationswithnoise，是一種基于數(shù)據(jù)密度的無監(jiān)督聚類算法。在聚類空間中的一定區(qū)域內(nèi)，用給定的半徑閾值和數(shù)量閾值，篩選出核心點(diǎn)及核心點(diǎn)的領(lǐng)域點(diǎn)，通過密度可達(dá)、密度相連的定義，實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的聚類。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大集合。DBSCAN算法原理及步驟DBScan需要兩個(gè)參數(shù)：掃描半徑(eps)和最小包含點(diǎn)數(shù)(minPts)，實(shí)現(xiàn)偽碼如下：檢測樣本集中尚未檢查過的樣本p，如果p未被處理(歸為某個(gè)簇或者標(biāo)記為噪聲)，則檢查其鄰域，若包含的樣本數(shù)不小于minPts，建立新簇C，將其中的所有點(diǎn)加入候選集N；對(duì)候選集N中所有尚未被處理的樣本q，檢查其鄰域，若至少包含minPts個(gè)樣本，則將這些樣本加入N；如果q未歸入任何一個(gè)簇，則將q加入C；重復(fù)上步驟，繼續(xù)檢查N中未處理的樣本，當(dāng)前候選集N為空；重復(fù)上三步驟，直到所有樣本都?xì)w入了某個(gè)簇或標(biāo)記為噪聲。DBSCAN算法python實(shí)現(xiàn)Python實(shí)現(xiàn)算法示例：機(jī)器學(xué)習(xí)PAI中對(duì)應(yīng)的組件機(jī)器學(xué)習(xí)PAI中對(duì)應(yīng)的組件為DBSCAN算法組件DBSCAN算法特點(diǎn)小結(jié)基于密度的聚類DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大集合。優(yōu)點(diǎn)：不需要提前設(shè)定K值大??；對(duì)噪聲不敏感；可以發(fā)現(xiàn)任意形狀的簇類相對(duì)K-Means，聚類結(jié)果無偏倚缺點(diǎn):對(duì)兩個(gè)參數(shù)的設(shè)置敏感，即圈的半徑eps、閾值MinPtsDBSCAN使用固定的參數(shù)識(shí)別聚類樣本集越大，收斂時(shí)間越長,計(jì)算量越大課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題OPTICS算法概述OPTICS：OrderingPointstoidentifytheclusteringstructure，點(diǎn)排序識(shí)別聚類結(jié)構(gòu)對(duì)于真實(shí)的、高維的數(shù)據(jù)集合而言，參數(shù)的設(shè)置通常是依靠經(jīng)驗(yàn)，難以確定。絕大多數(shù)算法對(duì)參數(shù)值是非常敏感的，設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。OPTICS算法通過對(duì)象排序識(shí)別聚類結(jié)構(gòu)。－OPTICS沒有顯式地產(chǎn)生一個(gè)數(shù)據(jù)集合簇，它為自動(dòng)和交互的聚類分析計(jì)算一個(gè)簇排序。－這個(gè)次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。OPTICS算法提出的背景在前面介紹的DBSCAN算法中，有兩個(gè)初始參數(shù)E（鄰域半徑）和minPts(E鄰域最小點(diǎn)數(shù))需要用戶手動(dòng)設(shè)置輸入，并且聚類的類簇結(jié)果對(duì)這兩個(gè)參數(shù)的取值非常敏感，不同的取值將產(chǎn)生不同的聚類結(jié)果，其實(shí)這也是大多數(shù)其他需要初始化參數(shù)聚類算法的弊端。為了克服DBSCAN算法這一缺點(diǎn)，提出了OPTICS算法。OPTICS并不顯示的產(chǎn)生結(jié)果類簇，而是為聚類分析生成一個(gè)增廣的簇排序（比如，以可達(dá)距離為縱軸，樣本點(diǎn)輸出次序?yàn)闄M軸的坐標(biāo)圖），這個(gè)排序代表了各樣本點(diǎn)基于密度的聚類結(jié)構(gòu)。它包含的信息等價(jià)于從一個(gè)廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類，換句話說，從這個(gè)排序中可以得到基于任何參數(shù)E和minPts的DBSCAN算法的聚類結(jié)果。

OPTICS算法原理及步驟創(chuàng)建兩個(gè)隊(duì)列，有序隊(duì)列和結(jié)果隊(duì)列。（有序隊(duì)列用來存儲(chǔ)核心對(duì)象及其該核心對(duì)象的直接可達(dá)對(duì)象，并按可達(dá)距離升序排列；結(jié)果隊(duì)列用來存儲(chǔ)樣本點(diǎn)的輸出次序）；如果所有樣本集D中所有點(diǎn)都處理完畢，則算法結(jié)束。否則，選擇一個(gè)未處理（即不在結(jié)果隊(duì)列中）且為核心對(duì)象的樣本點(diǎn)，找到其所有直接密度可達(dá)樣本點(diǎn)，如過該樣本點(diǎn)不存在于結(jié)果隊(duì)列中，則將其放入有序隊(duì)列中，并按可達(dá)距離排序；OPTICS算法原理及步驟如果有序隊(duì)列為空，則跳至步驟2，否則，從有序隊(duì)列中取出第一個(gè)樣本點(diǎn)（即可達(dá)距離最小的樣本點(diǎn)）進(jìn)行拓展，并將取出的樣本點(diǎn)保存至結(jié)果隊(duì)列中，如果它不存在結(jié)果隊(duì)列當(dāng)中的話。3.1

判斷該拓展點(diǎn)是否是核心對(duì)象，如果不是，回到步驟3，否則找到該拓展點(diǎn)所有的直接密度可達(dá)點(diǎn)；3.2

判斷該直接密度可達(dá)樣本點(diǎn)是否已經(jīng)存在結(jié)果隊(duì)列，是則不處理，否則下一步；3.3

如果有序隊(duì)列中已經(jīng)存在該直接密度可達(dá)點(diǎn)，如果此時(shí)新的可達(dá)距離小于舊的可達(dá)距離，則用新可達(dá)距離取代舊可達(dá)距離，有序隊(duì)列重新排序；3.4

如果有序隊(duì)列中不存在該直接密度可達(dá)樣本點(diǎn)，則插入該點(diǎn)，并對(duì)有序隊(duì)列重新排序；算法結(jié)束，輸出結(jié)果隊(duì)列中的有序樣本點(diǎn)。OPTICS算法python實(shí)現(xiàn)Python實(shí)現(xiàn)算法示例：課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.4.1.DBSCAN算法

8.4.2.OPTICS算法8.4.3.DENCLUE算法8.5.基于網(wǎng)格的聚類8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題DENCLUE算法DENCLUE算法：密度分布函數(shù)的聚類DENCLUE是對(duì)k-means聚類算法的一個(gè)推廣：－DENCLUE算法得到的是全局最優(yōu)劃分。DENCLUE主要基于：－每個(gè)數(shù)據(jù)點(diǎn)的影響可以用一個(gè)數(shù)學(xué)函數(shù)來形式化地模擬，它描述了一個(gè)數(shù)據(jù)點(diǎn)在領(lǐng)域內(nèi)的影響，被稱為影響函數(shù)；－數(shù)據(jù)空間的整體密度可以被模型化為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的總和；－然后聚類可以通過確定密度吸引點(diǎn)來得到，這里的密度吸引點(diǎn)是全局密度函數(shù)的局部最大。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類

8.5.1.STING算法

8.5.2.CLIQUE算法8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題STING算法概述STING算法是一種基于網(wǎng)格聚類的算法基于網(wǎng)格聚類的算法核心思想是將數(shù)據(jù)空間劃分為一個(gè)個(gè)網(wǎng)格，將數(shù)據(jù)按照一定的規(guī)則映射到網(wǎng)格單元中，然后計(jì)算每個(gè)單元的密度。根據(jù)預(yù)先設(shè)定的閾值判斷出每個(gè)網(wǎng)格單元是否為高密度單元，由臨近的高密度單元組成一個(gè)類。常見算法有STING、wave-cluster、clique。不同算法本質(zhì)上只是劃分網(wǎng)格的方法不同而已:STING：基于網(wǎng)格多分辨率，將空間劃分為方形單元，對(duì)應(yīng)不同分辨率CLIQUE：結(jié)合網(wǎng)格和密度聚類的思想，子空間聚類處理大規(guī)模高維度數(shù)據(jù)WaveCluster：用小波分析使簇的邊界變得更加清晰說明：

網(wǎng)格聚類算法一般和基于密度的算法結(jié)合使用具體實(shí)施步驟如下：（1）從一個(gè)層次開始（2）對(duì)于這一個(gè)層次的每個(gè)單元格，我們計(jì)算查詢相關(guān)的屬性值。（3）從計(jì)算的屬性值以及約束條件下，我們將每一個(gè)單元格標(biāo)記成相關(guān)或者不想關(guān)。(不相關(guān)的單元格不再考慮，下一個(gè)較低層的處理就只檢查剩余的相關(guān)單元)（4）如果這一層是底層，那么轉(zhuǎn)（6），否則轉(zhuǎn)（5）（5）我們由層次結(jié)構(gòu)轉(zhuǎn)到下一層，依照步驟2進(jìn)行（6）查詢結(jié)果得到滿足，轉(zhuǎn)到步驟8，否則（7）（7）恢復(fù)數(shù)據(jù)到相關(guān)的單元格進(jìn)一步處理以得到滿意的結(jié)果，轉(zhuǎn)到步驟（8）（8）停止；

STING是一個(gè)基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息（例如平均值，最大值，和最小值）被預(yù)先計(jì)算和存儲(chǔ)。這些統(tǒng)計(jì)變量可以方便下面描述的查詢處理使用。STING算法原理及步驟STING算法特點(diǎn)小結(jié)基于網(wǎng)格聚類優(yōu)點(diǎn)：1、聚類速度快。

缺點(diǎn)：1、對(duì)參數(shù)敏感2、無法處理不規(guī)則分布的數(shù)據(jù)3、會(huì)產(chǎn)生維度災(zāi)難4、算法精度不高基于網(wǎng)格的聚類方法采用空間驅(qū)動(dòng)的方法，把嵌入空間劃分成獨(dú)立于輸入對(duì)象分布的單元?；诰W(wǎng)格的聚類方法使用一種多分辨率的網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)。它將對(duì)象空間量化成有限數(shù)目的單元，這些網(wǎng)格形成了網(wǎng)格結(jié)構(gòu)，所有的聚類結(jié)構(gòu)都在該結(jié)構(gòu)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是處理速度快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象數(shù)，而僅依賴于量化空間中的每一維的單元數(shù)。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網(wǎng)格的聚類

8.5.1.STING算法

8.5.2.CLIQUE算法8.6.k-均值聚類分析實(shí)驗(yàn)8.7.本章小結(jié)8.8.本章習(xí)題CLIQUE算法概述

CLIQUE算法是基于網(wǎng)格的空間聚類算法，但它同時(shí)也非常好的結(jié)合了基于密度的聚類算法，因此既能夠發(fā)現(xiàn)任意形狀的簇，又可以像基于網(wǎng)格的算法一樣處理較大的多維數(shù)據(jù)。算法需要兩個(gè)參數(shù)：一個(gè)是網(wǎng)格的步長，第二個(gè)是密度的閾值。網(wǎng)格步長確定了空間的劃分，而密度閾值用來定義密集網(wǎng)格。

CLIQUE算法原理首先掃描所有網(wǎng)格。當(dāng)發(fā)現(xiàn)第一個(gè)密集網(wǎng)格時(shí)，便以該網(wǎng)格開始擴(kuò)展，擴(kuò)展原則是若一個(gè)網(wǎng)格與已知密集區(qū)域內(nèi)的網(wǎng)格鄰接并且其自身也是密集的，則將該網(wǎng)格加入到該密集區(qū)域中，直到不再有這樣的網(wǎng)格被發(fā)現(xiàn)為止。（密集網(wǎng)格合并）算法再繼續(xù)掃描網(wǎng)格并重復(fù)上述過程，知道所有網(wǎng)格被遍歷。以自動(dòng)地發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中，