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

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

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應用場景

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

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應用場景

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

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應用場景

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

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應用場景

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

8.1.1.聚類分析的定義

8.1.2.聚類分析提出的背景

8.1.3.聚類分析的原理8.1.4.聚類分析的應用場景

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

8.2.1.k-均值算法

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

對數(shù)據(jù)集中的每一個數(shù)據(jù)點

對每一個質心

計算質心與數(shù)據(jù)點的距離

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

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

8.2.1.k-均值算法

8.2.2.k-medoids算法

8.2.3.k-prototype算法8.3.基于層次的聚類8.4.基于密度的聚類8.5.基于網格的聚類8.6.k-均值聚類分析實驗8.7.本章小結8.8.本章習題k-medoids算法概述medoids算法是對k-means算法的一種改進算法。由于對k-means算法對于異常值十分敏感，因此具有極大值的對象可能會產生嚴重扭曲的數(shù)據(jù)分布。所以我們可以使用k-medoids算法，它是集群中位于最中心的對象，而不是將集群中的平均值作為參考點。因此，分區(qū)的方法仍然可以基于最小化每個對象與其參考點之間的不相似程度之和的原理來進行。這構成了k-medoids方法的基礎。k-medoids算法與k-均值算法的差異及比較k-均值算法（即k-means）與k-medoids之間的差異就是可以理解為對于數(shù)據(jù)樣本的平均值和中位數(shù)之間的差異。原因：k-均值算法對于數(shù)據(jù)樣本的要求太高，要求所有數(shù)據(jù)樣本處在一個歐式空間中，對于有很多噪聲的數(shù)據(jù)就會造成極大的誤差。但對于非數(shù)值型數(shù)據(jù)樣本，不能夠計算平均值等實數(shù)型變量。取值范圍可以是連續(xù)空間中的任意值取值只能是數(shù)據(jù)樣本范圍中的樣本k-均值算法k-medoids算法PKk-medoids算法原理及步驟不采用簇中對象的平均值作為參照點，可以選用簇中位置最中心的對象，即medoid。這樣劃分方法仍然是基于最小化所有對象與其參照點之間的相異度之和的原則來執(zhí)行的。隨機選擇K個對象作為初始的代表對象；指派每個剩余的對象給離它最近的代表對象所代表的簇；隨意地選擇一個非代表對象；計算用代替的總代價ＳStep1Step2Step3Step4如果，則用替換，形成新的k個代表對象的集合。直到不發(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.基于網格的聚類8.6.k-均值聚類分析實驗8.7.本章小結8.8.本章習題k-prototype算法概述K-prototype是處理混合屬性聚類的典型算法，它繼承了Kmean算法和Kmode算法的思想，并且加入了描述數(shù)據(jù)簇的原型和混合屬性數(shù)據(jù)之間的相異度計算公式。K-prototype算法是設定了一個目標函數(shù)，類似于kmean的SSE（誤差平方和），不斷迭代，直到目標函數(shù)值不變。K-prototype算法提出了混合屬性簇的原型，我們可以理解原型就是數(shù)值屬性聚類的質心。混合屬性中存在數(shù)值屬性和分類屬性，其原型的定義是數(shù)值屬性原型用屬性中所有屬性取值值的均值，分類屬性原型是分類屬性中選取屬性值取值頻率最高的屬性。合起來就是原型。k-prototype算法步驟K-prototype的算法步驟是：從數(shù)據(jù)集中隨機選取k個對象作為初始的k個簇的原型；遍歷數(shù)據(jù)集中的每一個數(shù)據(jù)，計算數(shù)據(jù)與k個簇的相異度。然后將該數(shù)據(jù)分配到相異度最小的對應的簇中，每次分配完畢后，更新簇的原型；然后計算目標函數(shù)，然后對比目標函數(shù)值是否改變，循環(huán)直到目標函數(shù)值不在變化為止。課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.3.1.BIRCH聚類

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

8.3.2.CURE算法8.4.基于密度的聚類8.5.基于網格的聚類8.6.k-均值聚類分析實驗8.7.本章小結8.8.本章習題CURE算法概述CURE對孤立點的處理更加健壯，而且能夠識別非球形和大小變化比較大的類。針對大型數(shù)據(jù)庫，CURE采用隨機取樣和劃分兩種方法組合：一個隨機樣本首先被劃分，每個劃分被部分聚類。絕大多數(shù)聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點時變得比較脆弱。CURE采用了一種新穎的層次聚類算法，該算法選擇基于質心和基于代表對象方法之間的中間策略。它不同于單個質心或對象來代表一個類，而是選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性的點。CURE算法原理及步驟123456從源數(shù)據(jù)對象中抽取一個隨機樣本S。將樣本S分割為一組劃分。對每個劃分局部的聚類。通過隨機取樣剔除孤立點。如果一個類增長太慢，就去掉它。對局部的類進行聚類。落在每個新形成的類中的代表點根據(jù)用戶定義的一個收縮因子收縮或向類中心移動。這些點代表和捕捉到了類的形狀。用相應的類標簽來標記數(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.基于網格的聚類8.6.k-均值聚類分析實驗8.7.本章小結8.8.本章習題DBSCAN算法概述DBSCAN，英文全寫為Density-basedspatialclusteringofapplicationswithnoise，是一種基于數(shù)據(jù)密度的無監(jiān)督聚類算法。在聚類空間中的一定區(qū)域內，用給定的半徑閾值和數(shù)量閾值，篩選出核心點及核心點的領域點，通過密度可達、密度相連的定義，實現(xiàn)數(shù)據(jù)點的聚類。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點的最大集合。DBSCAN算法原理及步驟DBScan需要兩個參數(shù)：掃描半徑(eps)和最小包含點數(shù)(minPts)，實現(xiàn)偽碼如下：檢測樣本集中尚未檢查過的樣本p，如果p未被處理(歸為某個簇或者標記為噪聲)，則檢查其鄰域，若包含的樣本數(shù)不小于minPts，建立新簇C，將其中的所有點加入候選集N；對候選集N中所有尚未被處理的樣本q，檢查其鄰域，若至少包含minPts個樣本，則將這些樣本加入N；如果q未歸入任何一個簇，則將q加入C；重復上步驟，繼續(xù)檢查N中未處理的樣本，當前候選集N為空；重復上三步驟，直到所有樣本都歸入了某個簇或標記為噪聲。DBSCAN算法python實現(xiàn)Python實現(xiàn)算法示例：機器學習PAI中對應的組件機器學習PAI中對應的組件為DBSCAN算法組件DBSCAN算法特點小結基于密度的聚類DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點的最大集合。優(yōu)點：不需要提前設定K值大??；對噪聲不敏感；可以發(fā)現(xiàn)任意形狀的簇類相對K-Means，聚類結果無偏倚缺點:對兩個參數(shù)的設置敏感，即圈的半徑eps、閾值MinPtsDBSCAN使用固定的參數(shù)識別聚類樣本集越大，收斂時間越長,計算量越大課程目錄8.1.聚類分析概述8.2.基于劃分的聚類8.3.基于層次的聚類8.4.基于密度的聚類8.4.1.DBSCAN算法

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

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

判斷該拓展點是否是核心對象，如果不是，回到步驟3，否則找到該拓展點所有的直接密度可達點；3.2

判斷該直接密度可達樣本點是否已經存在結果隊列，是則不處理，否則下一步；3.3

如果有序隊列中已經存在該直接密度可達點，如果此時新的可達距離小于舊的可達距離，則用新可達距離取代舊可達距離，有序隊列重新排序；3.4

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

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

8.5.1.STING算法

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

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

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

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

8.5.1.STING算法

8.5.2.CLIQUE算法8.6.k-均值聚類分析實驗8.7.本章小結8.8.本章習題CLIQUE算法概述

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

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