【聚類】譜聚類詳解、代碼示例

1. 介紹

譜聚類的基本原理：

• 把所有數(shù)據(jù)看成空間中的點，這些點之間可以用變連接起；
• 距離較遠的兩個點之間的邊權(quán)重較低，而距離較近的兩個點之間的邊權(quán)重較高；
• 通過對所有數(shù)據(jù)點組成的圖進行切圖，讓切圖后的不同的子圖間邊權(quán)重和盡可能小（即距離遠），而子圖內(nèi)的邊權(quán)重和盡可能高（即距離近）。

難點：

• 如何構(gòu)建圖？
• 如何切分圖？

2. 方法解讀

2.1 先驗知識

2.1.1 無向權(quán)重圖

2.1.2 拉普拉斯矩陣

2.2 構(gòu)建圖（第一步）

2.2.1 $?$ 鄰近法

2.2.2 k 近鄰法

2.2.3 全連接法

比前兩種方法，第三種方法所有的點之間的權(quán)重值都大于0，因此稱之為全連接法。

• 可以選擇不同的核函數(shù)來定義邊權(quán)重，常用的有多項式核函數(shù)，高斯核函數(shù)和Sigmoid核函數(shù)。
• 最常用的是高斯核函數(shù) RBF。
  

2.3 切圖（第二步）

其中$\overline{{\text{A}}_i}$ 為 $\text{A}$ 的補集。

進而，如何切圖使子圖內(nèi)的點權(quán)重高，子圖之間的點權(quán)重低？

2.3.1 最小化 $\text{cut?(A1,?A2,?.?.?.?Ak)}$

一個自然的想法就是最小化 $\text{cut?(A1,?A2,?.?.?.?Ak)}$，但是可以發(fā)現(xiàn)，這種極小化的切圖存在問題，如下圖：

• 為了避免最小切圖導(dǎo)致的切圖效果不佳，我們需要對每個子圖的規(guī)模做出限定；
• 一般來說，有兩種切圖方式，第一種是 RatioCut，第二種是 Ncut。

2.3.2 RatioCut 切圖

對于每個切圖，不僅要考慮最小化 $\text{cut?(A1,?A2,?.?.?.?Ak)}$，還要考慮最大化每個子圖樣本的個數(shù)，即最小化 RatioCut函數(shù)：

• 這里需要提一下，$h_i$是正交基，但并不是單位正交基，因為${h_i}^T{h}_i=\frac{1}{|A_j|}$，而不是1。但是不影響后面結(jié)論。

2.3.3 Ncut切圖

3. 譜聚類流程

3.1 輸入與輸出

• 輸入：樣本集 $D=(x_1,x_2,...,x_n)$，鄰接矩陣的生成方式，降維后的維度k1，聚類方法，聚類后的簇個數(shù)k2；
• 輸出： 簇劃分$C(c_1,c_2,...,c_{k2})$

3.2 一般流程

• 根據(jù)鄰接矩陣生成方式構(gòu)建鄰接矩陣W，構(gòu)建度矩陣D；
• 計算出拉普拉斯矩陣L；
• 構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣$D^{?\frac{1}{2}}L{D}^{?\frac{1}{2}}$；
• ?計算$D^{?\frac{1}{2}}L{D}^{?\frac{1}{2}}$最小的k1個特征值所各自對應(yīng)的特征向量f；
• 將各自對應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化，最終組成n × k1 維矩陣F；
• 對F 中的每一行作為一個k1維樣本，共n個樣本，用輸入的聚類方法進行聚類，聚類個數(shù)為k2；
• 得到簇劃分$C(c_1,c_2,...,c_{k2})$。

4. 代碼演示

import numpy as np 
import matplotlib.pyplot as plt 
from sklearn import cluster, datasets
from sklearn.preprocessing import StandardScalernp.random.seed(0)# 數(shù)據(jù)構(gòu)造
n_samples = 1500
noisy_circles = datasets.make_circles(n_samples=n_samples, factor=0.2, noise=0.05)
noisy_moons = datasets.make_moons(n_samples=n_samples, noise=0.05)
blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)data_sets = [(noisy_circles, {"n_clusters": 3}),(noisy_moons, {"n_clusters": 2}), (blobs, {"n_clusters": 3})
]
colors = ["#377eb8", "#ff7f00", "#4daf4a"]
affinity_list = ['rbf', 'nearest_neighbors']plt.figure(figsize=(20, 15))for i_dataset, (dataset, algo_params) in enumerate(data_sets):params = algo_paramsX, y = datasetX = StandardScaler().fit_transform(X)for i_affinity, affinity_strategy in enumerate(affinity_list):spectral = cluster.SpectralClustering(n_clusters=params['n_clusters'],eigen_solver='arpack', affinity=affinity_strategy)spectral.fit(X)y_pred = spectral.labels_.astype(int)y_pred_colors = []for i in y_pred:y_pred_colors.append(colors[i])plt.subplot(3, 4, 4*i_dataset+i_affinity+1)plt.title(affinity_strategy)plt.scatter(X[:, 0], X[:, 1], color=y_pred_colors)# plt.show()
plt.savefig("a.jpg")

5. 總結(jié)

• 優(yōu)點：
  • 譜聚類只需要數(shù)據(jù)之間的鄰接矩陣，因此對于處理稀疏數(shù)據(jù)的聚類很有效。這點傳統(tǒng)聚類算法比如K-Means很難做到；
  • 由于使用了降維，因此在處理高維數(shù)據(jù)聚類時的復(fù)雜度比傳統(tǒng)聚類算法好。
• 缺點：
  • 如果最終聚類的維度非常高，則由于降維的幅度不夠，譜聚類的運行速度和最后的聚類效果均不好；
  • 聚類效果依賴于鄰接矩陣，不同的鄰接矩陣得到的最終聚類效果可能很不同。

6. 參考

【1】https://blog.csdn.net/qq_42735631/article/details/121010760