聚類(lèi)算法

• 聚類(lèi)的概念：
  • 無(wú)監(jiān)督問(wèn)題：我們手里沒(méi)有標(biāo)簽了
  • 聚類(lèi)：相似的東西分到一組，跟分類(lèi)問(wèn)題相似。

  • 剛開(kāi)始的數(shù)據(jù)集上沒(méi)有顏色的標(biāo)記，也沒(méi)有告訴我們綠色的是哪些，紅色的是哪些，藍(lán)色的是哪些，根據(jù)一種相似度度量的方式，把相似的東西歸到一類(lèi)。從圖中可以看出，數(shù)據(jù)集明顯被分為3類(lèi)。
    image.png
  • 難點(diǎn)：如何評(píng)估，如何調(diào)參

1. K-MEANS算法

• 基本概念：
  • 要得到簇的個(gè)數(shù)，需要指定K值，例如k=3,把數(shù)據(jù)集聚為3堆。如上圖所示。
  • 質(zhì)心：均值，即向量各維取平均值即可。
  • 距離的度量：常用歐幾里得距離和余弦相似度（先標(biāo)準(zhǔn)化），計(jì)算兩個(gè)點(diǎn)有多相似。
  • 步驟：
    1. 隨機(jī)選擇K個(gè)特征空間內(nèi)的點(diǎn)作為初始的聚類(lèi)中心
    2. 對(duì)于其他每個(gè)點(diǎn)計(jì)算到K個(gè)中心的距離，未知的點(diǎn)選擇最近的一個(gè)中心作為標(biāo)記類(lèi)別
    3. 分別計(jì)算這K個(gè)簇群的平均值，把新的平均值與舊的中心點(diǎn)進(jìn)行比較，結(jié)果相同：結(jié)束聚類(lèi)。如果不相同：把新的平均值當(dāng)做新的中心點(diǎn)，重復(fù)第二步。
  • 評(píng)估標(biāo)準(zhǔn)：
    • 輪廓系數(shù)：
      輪廓系數(shù)公式
    • 注：對(duì)于每個(gè)點(diǎn)i為已聚類(lèi)數(shù)據(jù)中的樣本，bi為i到其他簇群的所有樣本的距離最小值，ai為i到本身簇群的距離平均值（i到其他樣本點(diǎn)的距離取平均值）。最終計(jì)算出所有樣本點(diǎn)的輪廓系數(shù)平均值。
    • 如果sc??小于0，說(shuō)ai 的平均距離大于最近的其他簇。聚類(lèi)效果不好
    • 如果sci越大，說(shuō)明ai的平均距離小于最近的其他簇。聚類(lèi)效果好。
    • 輪廓系數(shù)的值是介于[-1,1]，越趨近于1，代表內(nèi)聚度和分離度都相對(duì)較好。

    • 舉個(gè)例子：

      
      
      例子
      • 對(duì)于上圖：
        1. 計(jì)算藍(lán)1到自身類(lèi)別的點(diǎn)距離的平均值ai.
        2. 計(jì)算藍(lán)1分別到紅色類(lèi)別，綠色類(lèi)別所有的點(diǎn)的距離，求出平均b1,b2,取其中最小的值當(dāng)做bi。
  • 總結(jié)：
    • 優(yōu)勢(shì)：簡(jiǎn)單，快速，適合常規(guī)數(shù)據(jù)集。
    • 劣勢(shì)：
      • K值難確定
      • 復(fù)雜度與樣本呈線性關(guān)系
      • 很難發(fā)現(xiàn)任意形狀的簇

2. DBSCAN（含噪聲的基于密度的空間聚類(lèi)方法）

Density-Based Spatial Clustering of Applications with Noise

• 基本概念：
  • 核心對(duì)象：若某個(gè)點(diǎn)的密度達(dá)到算法設(shè)定的閾值則其為核心點(diǎn)。（即r領(lǐng)域內(nèi)點(diǎn)的數(shù)量不小于minPts）。指定一個(gè)點(diǎn)，以改點(diǎn)為中心，r為半徑畫(huà)圓，圓里面的點(diǎn)的個(gè)數(shù)超過(guò)設(shè)置的閾值，則稱(chēng)改點(diǎn)為核心對(duì)象。
  • 領(lǐng)域的距離閾值：設(shè)定的半徑r
  • 直接密度可達(dá)：若某點(diǎn)p在點(diǎn)q的r領(lǐng)域內(nèi)，且q是核心點(diǎn)則p-q直接密度可達(dá)。
  • 密度可達(dá)：若有一個(gè)點(diǎn)的序列q0,q1,q2,...,qk,對(duì)任意q_i - q_i-1是直接密度可達(dá)的，則稱(chēng)從q0到qk密度可達(dá)，這實(shí)際上是直接密度可達(dá)的“傳播”。
  • 密度相連：若從某核心點(diǎn)p出發(fā)，點(diǎn)q和點(diǎn)k都是密度可達(dá)的，則稱(chēng)q和k是密度相連的。
  • 邊界點(diǎn)：屬于某一個(gè)類(lèi)的非核心點(diǎn)，不能發(fā)展下線了
    • 核心對(duì)象發(fā)展它的下線，下線再發(fā)展下線，知道下線圈出的點(diǎn)小于閾值，則該下線點(diǎn)為邊界點(diǎn)。
  • 噪聲點(diǎn)：不屬于任何一個(gè)類(lèi)簇的點(diǎn)，從任何一個(gè)核心點(diǎn)出發(fā)都是密度不可達(dá)的。
  • 舉個(gè)例子：
  • 如下如所示，首先A為核心對(duì)象，A發(fā)展它的下線，即與A相鄰的3個(gè)點(diǎn)，這3個(gè)點(diǎn)又發(fā)展它的下線。

    • 從圖中可以看出：A為核心對(duì)象；B，C為邊界點(diǎn)；N為離群點(diǎn)。
      DBSCAN
  • 工作流程：
    • 需要輸入的參數(shù)
      • D：數(shù)據(jù)集
      • 指定半徑
      • MinPts：密度閾值

    • 迭代過(guò)程：
      工作流程