1 聚類解決的問題

• 知識發(fā)現(xiàn)，發(fā)現(xiàn)事物之間的潛在關(guān)系
• 異常值檢測
• 特征提取 數(shù)據(jù)壓縮的例子
• 新聞自動(dòng)分組、用戶分群、圖像分割、像素壓縮等等

2 與監(jiān)督學(xué)習(xí)比較

監(jiān)督學(xué)習(xí)是需要給定X、Y，X為特征，Y為標(biāo)簽，選擇模型，學(xué)習(xí)（目標(biāo)函數(shù)最優(yōu)化問題），生成模型，這個(gè)模型本質(zhì)上是一組參數(shù)，

無監(jiān)督機(jī)器學(xué)習(xí)的數(shù)據(jù)只有X，沒有標(biāo)簽，只根據(jù)X的相似度來做一些事情，相似度的計(jì)算一般通過距離來度量。相似度高的聚類在一起，進(jìn)而可以對數(shù)據(jù)降維

3 聚類算法

主流的聚類算法可以分為兩類：劃分聚類（Partitioning Clustering）和層次聚類（Hierarchical Clustering）。他們主要的區(qū)別是

• 劃分聚類是一系列扁平的結(jié)構(gòu)，它們之間沒有任何顯式的結(jié)構(gòu)來表名彼此的關(guān)聯(lián)性。常見算法有K-means、K-medoids、Gaussian Mixture Model（高斯混合模型）、Spectral Clustering（譜聚類）、Centroid-based Clustering等
• 層次聚類是具有層次結(jié)構(gòu)的簇集合，因此能夠輸出比劃分聚類輸出的無結(jié)構(gòu)簇集合提供更豐富的信息。層次聚類可以認(rèn)為是嵌套的劃分聚類，常見算法有Single-linkage、Complete-linkage、Connectivity-based Clustering等

4 相似度

X中的每一條數(shù)據(jù)都可以理解為多維空間中的一個(gè)點(diǎn)

相似度用點(diǎn)和點(diǎn)之間的距離衡量

• 歐氏距離

  $$O_p=\sqrt{(x_1?x_2{)}^2+(y_1?y_2{)}^2)}$$

  $$|x|=\sqrt{x^2+y^2}$$

• 明可夫斯基距離

  $$d(X,Y)=\sqrt[p]{(x_1?y_1{)}^p+(x_2?y_2{)}^p+(x_3?y_3{)}^p+...+(x_p?y_p{)}^p}$$

  • p=1時(shí)，曼哈頓距離
  • p=2時(shí)，歐氏距離
  • p=無窮，切比雪夫距離，哪個(gè)緯度值最大就是哪個(gè)差值作為距離

• 余弦距離

  $$cos\theta =\frac{a?b}{||a||||b||}$$

  $$cos\theta =\frac{x_1{x}_2+y_1{y}_2}{\sqrt{x_1^2+y_1^2}\times \sqrt{x_2^2+y_2^2}}$$

  拓展：如何通過向量夾角理解不同“維度”？ 三角函數(shù) sinx, cosx 的泰勒展開推導(dǎo)及兩個(gè)巧妙應(yīng)用_三角函數(shù)泰勒展開-CSDN博客

  

  

  從圖中很容易看出a/b/c之間的關(guān)系，將a^2+b2-c^2作為一個(gè)判定因子Δ，則Δ是a，b，c三個(gè)變量的函數(shù)。對于同樣一個(gè)角，如果三角形邊長過長，則Δ會(huì)變動(dòng)很大，如果過小，則Δ會(huì)變動(dòng)很小，也就是說沒有歸一化。為了消除邊長的影響，需要除以2ab，保證Δ的范圍在-1到+1之間

  為什么要用Δ除以2ab ？

  1. 根據(jù)三角形的公理：兩邊之和大于第三邊，兩邊之差小于第三邊，得出a+b>c>a-b
  2. 那么c^{2的取值范圍為(a+b)}2>c^2>(a-b)2，展開就是a^2+b2+2ab>c^2>a2+b^2- 2ab
  3. 于是判定因子Δ=a^2+b2-c^2的范圍在-2ab到2ab之間
  4. 這樣就把Δ規(guī)范到了-1到1之間

  cosθ=(a^2+b2-c^2)/2ab

  余弦距離在文本分類中使用很廣，余弦距離通過評價(jià)文章相似度

  1. 將文章分詞
  2. 將文章轉(zhuǎn)變?yōu)樵~向量（TFIDF，逆文檔頻率，如果將文章分詞通過one-hot編碼，會(huì)產(chǎn)生稀疏的問題，而TFIDF很好的解決了這個(gè)問題）
  3. 轉(zhuǎn)換為詞向量后，將文章映射到高維空間變?yōu)橐粋€(gè)向量
  4. 文章之間的向量的余弦距離代表文章之間的相似度

4.1 文本相似度

TF-IDF

TF：在給定文檔中某個(gè)詞出現(xiàn)的概率，即：在謀篇文章中 某次出現(xiàn)的次數(shù)/謀篇文章的總次數(shù)。
DF：語料庫中包含某詞的總文章數(shù)
IDF：I 是inverse的意思，代表某詞在語料庫中的重要程度，為了減少經(jīng)常用的詞對于相似度的貢獻(xiàn)，比如“的”，“是”這一類的詞
TF-IDF: TF*IDF

4.2 數(shù)據(jù)相似度

• Jaccard相似系數(shù)

  主要用于計(jì)算符號度量或布爾值度量的個(gè)體間的相似度，個(gè)體的特征屬性由符號度量或者布爾值表示無法衡量差異具體值的大小，只能獲得“是否相同”這個(gè)結(jié)果，所以Jaccard系數(shù)只判斷個(gè)體間共同具有的特征是否一致的問題

  用于網(wǎng)頁去重、文本相似度分析

• Pearson相關(guān)系數(shù)

  線性相關(guān)系數(shù)，對數(shù)據(jù)分布要求較高

  理解pearson相關(guān)系數(shù)，首先要理解協(xié)方差（Covariance），協(xié)方差是反映兩個(gè)隨機(jī)變量相關(guān)程度的指標(biāo)，如果一個(gè)變量跟隨另一個(gè)變量同時(shí)變大或者變小，那么這兩個(gè)變量的協(xié)方差就是正值，反之相反，公式：

  

  pearson公式：

  

  

  范圍：-1 到 1

  缺點(diǎn)：

  1）與樣本數(shù)量有關(guān)，如果n過小，很有可能出現(xiàn)接近1，n過大可能小于1；且顯著性檢測時(shí)采用t檢驗(yàn)要求數(shù)據(jù)來自正態(tài)分布，樣本過小可能導(dǎo)致要求不滿足

  2）從含義上看，如果出現(xiàn)X=（1，1, 1）向量，其標(biāo)準(zhǔn)差為0，分母為0所以無法計(jì)算pearson相關(guān)系數(shù)

  應(yīng)用：

  1）求兩樣品的不同特征之間的相關(guān)系數(shù)，從而用于降維

  2）根據(jù)相關(guān)度進(jìn)行聚類

  與余弦的聯(lián)系：

  pearson相關(guān)系數(shù)實(shí)際上是做了標(biāo)準(zhǔn)化的cos，pearson是余弦相似度在維度缺失情況下的一種改進(jìn)如何理解皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）？

5 K-means聚類

5.1 基本思想

1. 先給定K個(gè)劃分，迭代樣本與簇的隸屬關(guān)系，每次都比之前一次好一些
2. 迭代若干次后，就能得到比較好的結(jié)果

5.2 步驟

1. 初始化：選擇K個(gè)初始的簇中心（怎么選）
2. 分配：逐個(gè)計(jì)算每個(gè)樣本到中心的距離，將樣本歸屬到距離最小的那個(gè)簇中心的簇中
3. 更新：每個(gè)簇內(nèi)部計(jì)算平均值，更新簇中心
4. 迭代：重復(fù)步驟2和步驟3，知道滿足停止條件，比如集群中心不再顯著變化，或者達(dá)到設(shè)定的迭代次數(shù)

5.3 K-means特點(diǎn)

• 優(yōu)點(diǎn)
  • 簡單，效果不錯(cuò)
• 缺點(diǎn)
  • 對異常值敏感：計(jì)算距離時(shí)我們使用L2距離的平方。這樣對離群點(diǎn)很敏感，會(huì)把中心點(diǎn)拉偏
  • 對初始值敏感
  • 對某些分布聚類效果不好

5.4 K-means的變種

• K-medoids：針對K-means的缺點(diǎn)改進(jìn)

  • 計(jì)算新的簇中心的時(shí)候不再選擇均值，而是選擇中位數(shù)
  • 抗噪能力得到加強(qiáng)
  • 為避免平方計(jì)算對離群點(diǎn)的敏感，把平方變成絕對值
  • 限制聚類中心點(diǎn)必須來自數(shù)據(jù)點(diǎn)
    • 求中心點(diǎn)的計(jì)算方法，由原來的直接計(jì)算重心，變成計(jì)算完重心后，在重心附近找一個(gè)數(shù)據(jù)點(diǎn)作為新的中心點(diǎn)
    • K-medoids重?cái)M合步驟直接求平均的K-means要復(fù)雜一些

  

  

• 二分K-means

  • K-means的損失函數(shù)， 每個(gè)點(diǎn)到中心點(diǎn)位置的MSE
  • 分別計(jì)算四個(gè)簇的MSE，會(huì)發(fā)現(xiàn)有兩個(gè)簇的MSE很小，一個(gè)簇的MSE很大
  • 選擇合并簇中心點(diǎn)比較近，MSE很小的簇，切分簇中心離其他簇中心比較遠(yuǎn)，MSE比較大的簇，重新進(jìn)行K-means聚類

• K-means++

  • 現(xiàn)在目前的模型基本使用的是K-means++
  • K-means++改變初始中心點(diǎn)的位置
    • 目標(biāo)：初始化簇中心點(diǎn)稍微遠(yuǎn)一些
    • 步驟：1）隨機(jī)選擇第一個(gè)中心點(diǎn)； 2）計(jì)算每個(gè)樣本到第一個(gè)中心點(diǎn)的距離；3）將距離轉(zhuǎn)化為概率；4）概率化選擇

5.5 K-means的損失函數(shù)

• K-means的理論基礎(chǔ)是假設(shè)各簇之間符合同方差的高斯分布模型

• 通過最大似然估計(jì)得到K-means的迭代方法
• 這個(gè)函數(shù)是個(gè)非凸函數(shù)，根據(jù)初始值不同只能得到局部最優(yōu)解

5.6 K的選擇

K值的選擇是執(zhí)行K均值聚類時(shí)需要仔細(xì)考慮的問題，選擇的不合適可能導(dǎo)致聚類結(jié)果不準(zhǔn)確或不具有實(shí)際意義

5.6.1 肘部法（Elbow Method）

K=n的時(shí)候，損失函數(shù)為0

K=1的時(shí)候，損失函數(shù)=原始數(shù)據(jù)的方差

所以，K應(yīng)選擇一個(gè)最佳的拐點(diǎn)，肘部法

5.6.2 輪廓系數(shù)（Silhouette Coefficient）

輪廓系數(shù)結(jié)合了聚類的凝聚度（Cohesion）和分離度（Separation），用于評估聚類的結(jié)果：

• 簇內(nèi)距離：同一簇內(nèi)，其他點(diǎn)到某個(gè)點(diǎn)的距離的平局值
• 簇間距離：某個(gè)點(diǎn)到其他簇每個(gè)點(diǎn)的平均值

最終目的是為了使簇內(nèi)部距離最小化，簇間距離最大化。所以SC越靠近1，說明b越大于a，即外部距離大，內(nèi)部距離小，說明分類效果越好

然而，當(dāng)我們根據(jù)不同的K計(jì)算出幾個(gè)SC值差不多時(shí)，并不是盲目選更大的SC，如下面的例子：

n_clusters = 2 SC : 0.7049

n_clusters = 3，SC : 0.5882

n_clusters = 4，SC : 0.6505

n_clusters = 5，SC : 0.5637

n_clusters = 6，SC: 0.4504

每次聚類后，每個(gè)樣本得到一個(gè)輪廓系數(shù)，當(dāng)SC=1時(shí)，說明這個(gè)點(diǎn)與周圍簇距離較遠(yuǎn)，結(jié)果非常好，當(dāng)SC=0時(shí)，說明這個(gè)點(diǎn)可能處在兩個(gè)簇的邊界上，當(dāng)值為負(fù)時(shí)，該點(diǎn)可能被誤分

從上面結(jié)果來說，K取2和4其實(shí)都不錯(cuò)，但可以從下圖看出，K取2的話，第0簇的寬度遠(yuǎn)寬于第1簇（也就是說黑色數(shù)量比綠色多太多），而K取4的話，每個(gè)簇其差別不大。所以選K=4更好

5.6.3 誤差平方和（SSE）

誤差平方和（The sum of squares due to error）:真實(shí)值和誤差值的差的平方，再求整體和

例如：數(shù)據(jù)-0.2、0.4、-0.8、1.3、-0.7為真實(shí)值和誤差值的差

SSE是松散度的衡量，所以SSE越小越好。隨著聚類迭代，其值越來越小，知道最后區(qū)域穩(wěn)定

5.6.4 CH系數(shù)（Calinski-Harabasz Index）

CH系數(shù)：類別內(nèi)部數(shù)據(jù)的協(xié)方差越小越好，類別之間的協(xié)方差越大越好，這樣的Calinski-Harabasz分?jǐn)?shù)s會(huì)高，分?jǐn)?shù)s高則聚類效果好。

其中，tr為矩陣的跡，Bk是類別之間的協(xié)方差矩陣，Wk是類別內(nèi)部數(shù)據(jù)的協(xié)方差矩陣，m是訓(xùn)練集樣本數(shù)量，k是類別數(shù)量

5.6.5 小結(jié)

• SSE：誤差平方和越小越好
• 肘部法：下降突然變緩時(shí)即認(rèn)為是最佳K值
• SC系數(shù)：取值為[-1, 1]，其值越大越好
• CH系數(shù)：分?jǐn)?shù)S高則聚類效果越好，CH需要達(dá)到的目的，用盡量少的類別聚類盡量多的樣本，同時(shí)獲取較好的聚類效果

6 Canopy聚類

Canopy聚類只進(jìn)行一次劃分聚類，是基于距離閾值進(jìn)行的快速聚類算法，而這些閾值通常需要進(jìn)行調(diào)整以得到滿意的聚類結(jié)果。實(shí)際應(yīng)用中適合K-means聚類結(jié)合使用，一般是先用Canopy聚類，將K值計(jì)算出來，然后用K-means進(jìn)行迭代

Canopy聚類步驟：

1. 設(shè)置超參數(shù)T1、T2 T1>T2
2. while D 非空：
   1. 隨機(jī)產(chǎn)生d屬于D作為中心點(diǎn)
   2. 計(jì)算所有點(diǎn)到d的距離
   3. 所有距離<t1的點(diǎn)歸屬于d的中心點(diǎn)
   4. 從D中刪除d及距離小于t2的點(diǎn)

聚類效果：

7 層次聚類

    層次聚類（Hierarchical Clustering）是聚類算法的一種，通過計(jì)算不同類別的數(shù)據(jù)點(diǎn)間的相似度來創(chuàng)建一顆有層次的嵌套聚類樹，在聚類樹中，不同類別的原始數(shù)據(jù)點(diǎn)是樹的最低層，樹的頂層是一個(gè)聚類的根節(jié)點(diǎn)，創(chuàng)建聚類樹有自上而下和自下而上分列兩種方法。

7.1 層次聚類的步驟

假設(shè)有6個(gè)樣本點(diǎn)（A/B/C/D/E/F），層次聚類步驟如下：

1. 最開始假設(shè)每個(gè)樣本點(diǎn)是一個(gè)簇，計(jì)算每個(gè)樣本間的相似度（也就是距離），得到一個(gè)相似矩陣
2. 尋找各個(gè)類之間的最近的兩個(gè)類，即若B、C的相似度最高，合并簇B和C，現(xiàn)在變?yōu)锳,BC,D,E,F
3. 更新簇類間的相似矩陣，若BC和D相似度最高，歸為一個(gè)簇類，則變?yōu)锳,BCD,E,F
4. 更新簇類間的相似矩陣，若簇類E和F的相似度最高，歸為一類，則變?yōu)锳,BCD,EF
5. 重復(fù)第四步，簇類BCD和EF相似度最高，合并為一個(gè)簇，則變?yōu)锳,BCDEF
6. 最后合并A,BCDEF為一個(gè)簇類，結(jié)束

7.2 層次聚類算法分類

• 自頂向下

  先上圖

  

  自頂鄉(xiāng)下的層次聚類，最開始所有的對象均屬于一個(gè)cluster，每次按一定的準(zhǔn)則將某個(gè)cluster劃分為多個(gè)cluster，如此往復(fù)，直至每個(gè)數(shù)據(jù)點(diǎn)均屬于一個(gè)cluster

• 自底向上

  

  自底向上，是將每個(gè)數(shù)據(jù)點(diǎn)看做一個(gè)簇，每次計(jì)算相似度，合并，如此循環(huán)下去，直至屬于一個(gè)簇為止

7.3 層次聚類相關(guān)模型

7.3.1 Single-Linkage算法

此算法是構(gòu)造一個(gè)棵二叉樹，用葉節(jié)點(diǎn)代表數(shù)據(jù)，而二叉樹的每一個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)聚類，這是一個(gè)自下而上的聚類。

7.3.2 Complete-Linkage算法

與Single-Linkage算法相似，Complete-Linkage的迭代思想是一樣的，不同的是合并類時(shí)，Single-Linkage是用兩個(gè)類中距離最小的兩個(gè)點(diǎn)作為類之間的距離，而Complete-Linkage恰恰相反，用距離最遠(yuǎn)的兩個(gè)數(shù)據(jù)點(diǎn)之間的距離作為兩個(gè)類之間的距離

8 密度聚類

前面介紹了劃分聚類和層次聚類算法，下面介紹密度聚類算法：DB-SCAN算法

DB-SCAN是一個(gè)基于密度的聚類。在聚類不規(guī)則形態(tài)的點(diǎn)，如果用K-means，效果不會(huì)很好。而通過DB-SCAN就可很好地把同一密度區(qū)域的點(diǎn)聚在一起

8.1 關(guān)鍵概念

• 核心對象（Core Object），也就是密度達(dá)到一定程度的點(diǎn)

  • 若 xj 的∈ - 鄰域至少包含 MinPts 個(gè)樣本，即 ，則 是一個(gè)核心對象

• 密度直達(dá)（directly-density-reachable），密度可達(dá)（directly-reachable）：核心對象之間可以是密度直達(dá)或密度可達(dá)

  

• 密度相連（density-connected）：所有密度可達(dá)的和點(diǎn)點(diǎn)就是構(gòu)成密度相連

  • 對xi和xj，若存在xk使得xi與xj，均由xk密度可達(dá)，則稱xi和xj密度相連

8.2 算法偽代碼

這個(gè)過程用直白的語言描述就是：

• 對于一個(gè)數(shù)據(jù)集，先規(guī)定最少點(diǎn)密度 MinPts 和半徑范圍。
• 先找出核心對象：如果在半徑范圍內(nèi)點(diǎn)密度大于 MinPts，則這個(gè)點(diǎn)是核心對象。把所有的核心對象放到一個(gè)集合中。
• 從這個(gè)核心對象集合中，隨機(jī)找一個(gè)核心對象，判斷其它的數(shù)據(jù)點(diǎn)與它是否密度直達(dá)，如果是，則歸入聚類簇中。
• 繼續(xù)判斷其它點(diǎn)與聚類簇中的點(diǎn)是否密度直達(dá)，直到把所有的點(diǎn)都檢查完畢，這時(shí)候歸入聚類簇中的所有點(diǎn)是一個(gè)密度聚類。