聚類分析

• 目標：將數據樣本劃分為若干個通常不相交的“簇”，使簇內數據之間具有高的相似性，不同簇數據之間具有高的差異性

  

一、相似性度量方法

歐氏距離	馬氏距離
標準化歐式距離	海明距離
哈曼頓距離	杰卡德距離
切比雪夫距離	相關距離
閔可夫斯基距離	信息熵
余弦距離	基于核函數的度量

1. 歐氏距離(歐幾里得距離)

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的歐氏距離為：
d 12 = ∑ k = 1 n ( x 1 k ? x 2 k ) 2 d_{12}=\sqrt{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{2}} d12?=k=1∑n?(x1k??x2k?)2 ?

歐式距離就是我們平時用的兩點間的距離

2. 標準化歐氏距離

根據數據各維分量的分布不同將各個分量都標準化到均值、方差相等。

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的歐氏距離為：
d 12 = ∑ k = 1 n ( x 1 k ? x 2 k s k ) 2 d_{12}=\sqrt{\sum_{k=1}^{n}\left(\frac{x_{1 k}-x_{2 k}}{s_k}\right)^{2}} d12?=k=1∑n?(sk?x1k??x2k??)2 ?
這個 s k s_k sk?是個方差，在標準化歐式距離中，方差的倒數我們可以視為一種權重，因此標準化的歐式距離也可以視為一種加權的歐式距離。

3. 曼哈頓距離

曼哈頓距離也稱為L1-距離或城市距離，對于兩個$n$維向量$\alpha ,\beta$來說他們的曼哈頓距離，指的是每一個分量的差值的絕對值，然后再次求和。

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的曼哈頓距離為：
d 12 = ∑ k = 1 n ∣ x 1 k ? x 2 k ∣ d_{12}=\sum_{k=1}^{n}{\left | x_{1k}-x_{2k} \right | } d12?=k=1∑n?∣x1k??x2k?∣

4. 切比雪夫距離

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的切比雪夫距離為：
d 12 = max ? i ( ∣ x 1 i ? x 2 i ∣ ) d_{12}=\max _{i}\left(\left|x_{1 i}-x_{2 i}\right|\right) d12?=imax?(∣x1i??x2i?∣)
即，在$\alpha ,\beta$他們對應的分量的差值的絕對值當中最大的那個，就是切比雪夫距離

該公式等價于：
d 12 = lim ? k → ∞ ( ∑ i = 1 n ∣ x 1 i ? x 2 i ∣ k ) 1 / k d_{12}=\lim _{k \rightarrow \infty}\left(\sum_{i=1}^{n}\left|x_{1 i}-x_{2 i}\right|^{k}\right)^{1 / k} d12?=k→∞lim?(i=1∑n?∣x1i??x2i?∣k)1/k

5.閔可夫斯基距離

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的閔可夫斯基距離為：
d 12 = ∑ k = 1 n ( x 1 k ? x 2 k ) p p d_{12}=\sqrt[p]{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{p}} d12?=pk=1∑n?(x1k??x2k?)p ?

• p=1時，它是曼哈頓距離
• p=2時，它是歐氏距離
• p=$\infty$時，它是切比雪夫距離

閔可夫斯基類的距離缺陷
舉例：在a和b之間他們的身高差10公分。在a和c之間，他們的體重差10公斤。發現，實際上，兩個10，他們單位是不同的，即量綱不同，不能在一起衡量。 缺陷： - 將各個分量的量綱，當做相同看待 - 沒有考慮各個分量的分布（如期望、方差等）可能不同

6. 余弦距離

余弦距離的幾何意義不僅能包含長度也包含方向。

余弦距離是度量兩個向量方向差異的一種方法。

兩個向量 α ( x 11 , x 12 , … , x 1 n ) \alpha\left(x_{11}, x_{12}, \ldots, x_{1 n}\right) α(x11?,x12?,…,x1n?)和 β ( x 21 , x 22 , … , x 2 n ) \beta\left(x_{21}, x_{22}, \ldots, x_{2 n}\right) β(x21?,x22?,…,x2n?)之間的夾角余弦度量為：
cos ? ( θ ) = α ? β ∣ α ∣ ∣ β ∣ \cos (\theta)=\frac{\alpha \cdot \beta}{|\alpha||\beta|} cos(θ)=∣α∣∣β∣α?β?

7. 馬氏距離

馬氏距離是基于樣本分布的一種距離。剛才講到的距離都是指的是兩個不同的向量$\alpha ,\beta$之間一個距離的度量。

在馬氏距離中，它是基于樣本分布的這樣一種度量方法。

它是規范化主成分空間當中的歐式距離。

什么是規范化主成分空間？
規范化的主成分空間就是利用主成分分析對一些數據進行主成分分解，再對所有主成分分解軸做歸一化，形成新的坐標軸，由這些坐標軸組成的空間就是規范化的主成分空間。
視頻：用最直觀的方式告訴你：什么是主成分分析PCA_嗶哩嗶哩_bilibili

向量 X i ， X j X_{i}，X_{j} Xi?，Xj?之間的馬氏距離為：
D ( X i , X j ) = ( X i ? X j ) T S ? 1 ( X i ? X j ) D\left(X_{i}, X_{j}\right)=\sqrt{\left(X_{i}-X_{j}\right)^{\mathrm{T}} S^{-1}\left(X_{i}-X_{j}\right)} D(Xi?,Xj?)=(Xi??Xj?)TS?1(Xi??Xj?) ?
其中$S$是協方差矩陣。

當$S$是對角矩陣時，馬氏距離就變成了標準化的歐式距離。

總結一下馬氏距離的特點：

• 量綱無關
• 馬氏距離的計算是建立在總體樣本的基礎上
• 計算馬氏距離過程中，要求總體樣本數大于樣本的維數。

8. 海明距離

兩個等長二進制字符串將其中一個變為另一個所需要的最小變換次數。

例如：字符串1111與1001之間的海明距離為2

9.杰卡德距離

杰卡德相似系數：兩個集合A和B的交集元素在A、B的并集中所占的比例，稱為兩個集合的杰卡德相似系數，用符號$J(A,B)$表示：
J ( A , B ) = ∣ A ∩ B ∣ ∣ A ∪ B ∣ J(A, B)=\frac{|A \cap B|}{|A \cup B|} J(A,B)=∣A∪B∣∣A∩B∣?
杰卡德距離：與杰卡德相似系數相反，用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度：
J δ ( A , B ) = 1 ? J ( A , B ) = ∣ A ∪ B ∣ ? ∣ A ∩ B ∣ ∣ A ∪ B ∣ J_{\delta}(A, B)=1-J(A, B)=\frac{|A \cup B|-|A \cap B|}{|A \cup B|} Jδ?(A,B)=1?J(A,B)=∣A∪B∣∣A∪B∣?∣A∩B∣?

10. 相關距離

相關系數：衡量隨機變量$X$與$Y$相關程度的一種方法，相關系數的取值范圍是$[?1,1]$。
ρ X Y = Cov ? ( X , Y ) D ( X ) D ( Y ) = E ( ( E ? E X ) ( Y ? E Y ) ) D ( X ) D ( Y ) \rho_{X Y}=\frac{\operatorname{Cov}(X, Y)}{\sqrt{D(X)} \sqrt{D(Y)}}=\frac{E((E-E X)(Y-E Y))}{\sqrt{D(X)} \sqrt{D(Y)}} ρXY?=D(X) ?D(Y) ?Cov(X,Y)?=D(X) ?D(Y) ?E((E?EX)(Y?EY))?
相關系數的絕對值越大，則表明$X$與$Y$相關度越高。當$X$與$Y$線性相關時，相關系數取值為1（正線性相關）或-1（負線性相關）

相關距離：
D X Y = 1 ? ρ X Y D_{X Y}=1-\rho_{X Y} DXY?=1?ρXY?

11. 信息熵

以上的距離度量方法度量皆為兩個樣本（向量）之間的距離

12. 基于核函數的度量

把原始樣本空間中線性不可分的數據點采用核函數映射到高維空間中使其線性可分的一種度量方法。

二、經典的聚類方法

聚類方法往往學術界對聚類算法并沒有一個公共的分類方法

• 劃分方法
• 層次方法
• 基于密度方法
• 基于網格方法
• 基于網絡方法
• 基于模型方法

劃分方法

經典方法：K-means及其變種、K-中心點、CLARA、CLARANS

1. K-means

K-means算法流程：

1. 從數據集D中隨機選擇K個對象作為初始簇中心
2. 將每個對象分配到與其最近的簇中心的簇中
3. 重新計算簇的均值，使用新的均值作為當前簇的中心
4. 重復步驟2、3，直到所有簇中的對象不再變化。

K-means算法的局限性：

• 算法可能終止于局部最優解
• 算法只有當簇均值可求或可定義時才能使用
• 簇數目必須事先給定，而在一些實際應用中K是很難事先知道的
• 不適合發現非凸形狀的簇，或者大小差別很大的簇
• K-means算法，對噪聲和離群點的數據敏感

原因在于度量方法基于的是歐拉距離，因此，對噪聲和離群點是比較敏感的。

2. K中心點算法(K-Medoide)

K-中心點算法也是一種常用的聚類算法，K-中心點聚類的基本思想和K-Means的思想相同，實質上是對K-means算法的優化和改進。在K-means中，異常數據對其的算法過程會有較大的影響。在K-means算法執行過程中，可以通過隨機的方式選擇初始質心，也只有初始時通過隨機方式產生的質心才是實際需要聚簇集合的中心點，而后面通過不斷迭代產生的新的質心很可能并不是在聚簇中的點。如果某些異常點距離質心相對較大時，很可能導致重新計算得到的質心偏離了聚簇的真實中心。

K-Medoide算法流程：

1. 從數據集D中隨機選擇K個對象作為初始簇中心
2. 計算其余所有點到K個中心點的距離，并把每個點到K個中心點最短的聚簇作為自己所屬的聚簇
3. 在每個聚簇中按照順序依次選取點，計算該點到當前聚簇中所有點距離之和，最終距離之和最小的點，則視為新的中心點。
4. 重復2，3步驟，直到各個聚簇的中心點不再改變。

3. 核K-means

就是將數據點都投影到了一個高維的特征空間中（為了凸顯不同樣本中的差異），然后再在這個高維的特征空間中，進行傳統的k-means聚類。

4. EM聚類

我們知道，K-means方法是硬分聚類方法的一種。 什么是硬分聚類方法呢？就是指一個點只能屬于一個簇。 EM算法，是一種軟分聚類方法，這種方法，指的是每一個點， 都有屬于某個簇的概率，這是硬分聚類與軟分聚類不同的地方。 EM聚類是典型的軟分聚類方法。

5. 譜聚類

為了凸顯不同樣本中的差異），然后再在這個高維的特征空間中，進行傳統的k-means聚類。

4. EM聚類

我們知道，K-means方法是硬分聚類方法的一種。 什么是硬分聚類方法呢？就是指一個點只能屬于一個簇。 EM算法，是一種軟分聚類方法，這種方法，指的是每一個點， 都有屬于某個簇的概率，這是硬分聚類與軟分聚類不同的地方。 EM聚類是典型的軟分聚類方法。

5. 譜聚類

譜聚類（spectral clustering)及其實現詳解_yycc-CSDN博客_譜聚類實現