Clustering method 3

Spectral Clustering

非監督式學習（Unsupervised Learning）的目標是透過不同的方法去擬合資料集，並找到其潛在的分布以便分群或分類。之前已經介紹過基於密度及核密度估計（kernel density estimation，KDE）的分群方法，此篇將會說明另一種基於圖論的分群方法 —— 譜分群（Spectral Clustering）。

結合圖論的分析，可以將資料點間的關係建構權重圖（weighted graph），也就是將頂點（vertex）作為資料點，邊（edge）則表示資料點間的距離。以下將會介紹如何建構關係圖進而去做分群，以及其演算法和實作。

－ 基本概念 －

譜分群的想法是將所有的資料視為空間中的點（vertex），而點與點之間可以邊（edge）相接。而點間的距離較近，便賦予較大的權重；反之，則給予較小的權重。最後，對建構好的圖去做裁切，使得圖間的權重和（weighted sum）盡可能的低，同時讓圖內的權重和盡可能的高，達到分群的效果。

圖（graph）

基本上，〝圖〞由頂點 V（vertex）及邊 E（edge）構成，即為 G（V, E）。其中 V = ｛v_1 , v_2 , … , v_n｝及 E={e_1, e_2, …, e_m}，e_i ＝｛v_j , v_k｝表示頂點 v_j 和頂點 v_k 相接。

鄰接矩陣（Affinity matrix）

除了基本圖的元素，也會透過鄰接矩陣去表示任意兩點間的連接關係。在無權圖（unweighted graph）中，鄰接矩陣被定義為

頂點 v_i 和頂點 v_j 有相接則給值 1

但對於兩點間的關係僅有 1 或 0，並無法表示不同的強度。因此在權重圖（weighted graph）中是利用兩點間的距離去給權重表示連接的強度。其中的想法是距離較遠給低權重，而較近的兩點則給較高的權重。常用的方法是 k 鄰近法及全連接法。

• k 鄰近法是先透過 k-nearest neighbor （KNN）方法篩選兩點間是否要連接，則可定義鄰接矩陣為

knn(v_i) 表示與頂點 v_i 最近的 k 個頂點。若頂點 v_i 及頂點 v_j 互不在對方的鄰近區域內，則不連接v_i 和 v_j（給值 0）；反之，以高斯核函數表示權重。

• 全連接法則是將所有點連接，以核函數表示點間的距離關係。以下以最常使用的高斯核函數表示鄰接矩陣，可寫成

對所有點間的權重依據核函數去賦予。

切圖（Cut）

透過鄰接矩陣，則可把兩點間連接的強度一一表示。接下來將圖切割成數個子圖以達到分群的效果。然而，裁切的方式應最小化子圖間的連接關係，同時最大化每個子圖內的連接關係。對於切圖的概念，能以數學式表示為以下的式子

G_i 表示為子圖，G_i^C 為 G_i 的補集（G \ G_i）

其中子圖間的權重可表示為

因此目標則為

但直接最小化切圖間的連接關係，會導致算法直接對權重和最小的點做裁切。

紅色線為直接最小化切圖值的切圖方法，但較好的應該是黃色線

以下有兩種方法藉由規範每個子圖的大小解決此問題。

• Ratio Cut

RatioCut 不僅最小化 Cut（G_1 , G_2 , … , G_k），同時最大化子圖的點數。則可表示為

利用子圖的節點數控制規模（權重）

對於某個子圖 G_i，

令 f_i 定義為下，

然而，對每個子圖 G_i 的 RatioCut 則可寫成

其中 D 為度矩陣（degree matrix），定義其對角元素為

即為相似矩陣的列總和，組成對角矩陣D

而 L 則為拉普拉斯矩陣（Laplacian matrix），定義如下

拉普拉斯定義為度矩陣與鄰接矩陣之差

因此最小化 RatioCut 的值，即為最小化 f ’Lf 。

假設存在 lambda 使得

lambda 即為 L 的特徵值

同時左乘 f '，則會得到

也就是說，僅需找到最小的特徵值 lambda 對應的特徵向量即可最小化 f 'Lf。

• Normalized Cut

然而，NormalizedCut 則是另一種切圖的方法，其算法不僅最小化 Cut（G_1 , G_2 , … , G_k），同時最大化子圖的連接權重值。則可表示為

找到目標函數的最小值如上述推導，僅在權重上有所改變。而此做法多考慮了距離的因素，為譜分群使用的切圖算法。

找出的特徵向量如同 PCA 等降維方法一般，但此對應著最佳劃分圖的方法。最終需要再將連續的特徵向量離散化，即為特徵的劃分，進而得到欲達成的分群。

－ 演算法 －

輸入：資料集 V ，以及分群數目 k

輸出：目標分群集合 Clusters

1. 求出資料點的鄰接矩陣 A（Affinity matrix）。
2. 對鄰接矩陣 A 的第 i 列加總作為對角矩陣 D 第（i, i）的元素值，並算出矩陣拉普拉斯矩陣 L 。
3. 從矩陣 L 中找出對應前 l 個特徵值的特徵向量 x_1 , x_2 , … , x_l ，並建構 n x l 維的矩陣 X = [ x_1 | x_2 | … | x_l ]。
4. 對矩陣 X 的每一列做正規化（R → [0 , 1]），得到 Y 矩陣。
5. 將矩陣 Y 的每一列做為新資料點（即原資料點降維成 l 維的資料點），透過 K-means 或其他分群方法分成 k 類。
6. 若 Y 的第 i 列被歸為第 j 類，則原資料點 s_i 即為第 j 類。

－ 算法實作 －

使用Sklearn.cluster.MeanShift套件：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import SpectralClustering
from sklearn import datasets
#create datasets
X,y = datasets.make_blobs(n_samples=50, centers=3, n_features=2, random_state= 20, cluster_std = 1.5)
#parameter setting
n = 3 #number of clusters
#Spectral Clustering method
model = SpectralClustering(n_clusters = n, 
                           assign_labels = 'discretize')
model.fit(X)
labels = model.fit_predict(X)
#results visualization
plt.figure()
plt.scatter(X[:,0], X[:,1], c = labels)
plt.axis('equal')
plt.title('Prediction')
plt.show()

左圖為原始資料集，右圖為譜分群設定 n = 3 時的結果。

n = 2 時，譜分群就會將距離較近的兩群合為一類。

用於影像分割 …

import numpy as np
import matplotlib.pyplot as plt
from skimage.transform import rescale
from sklearn.cluster import SpectralClustering
import cv2
#load image
img = cv2.imread('AIA.png')
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
img = rescale(img, 0.2)
rows, cols, chs= img.shape
#convert image shape [rows, cols, 3] into [rows*cols, 3]
feature_img = np.reshape(img, [-1, 3])
#consider the data without density-dependent factor
uni_feature_img, idx = np.unique(feature_img, axis=0, return_inverse = True)
#parameters setting
n = 15 #number of clusters
#Spectral Clustering method
model = SpectralClustering(n_clusters = n, random_state = 40)
model.fit(uni_feature_img)
labels = model.fit_predict(uni_feature_img)
#results visualization
fig = plt.figure(figsize = (20, 12))
ax = fig.add_subplot(121)
ax1 = fig.add_subplot(122)    
    
ax.imshow(img)
ax1.imshow(np.reshape(labels[idx], [rows, cols]))
plt.show()

此例僅考慮顏色的因素，並不考慮密度，因此同顏色的像素都將視為同一點。

左圖僅顯示被歸為背景藍色的像素；右圖則表示被歸為白色系的像素

－ Spectral Clustering算法總結－

優點：

1. 只需要資料點間的相似矩陣，因此對於稀疏資料點的分群有顯著的效果。
2. 此算法利用拉普拉斯矩陣降維，所以對高維度的資料集的分群計算複雜度相對低。

缺點：

1. 若降維後的維度依舊很高，則會影響分群的速度也會導致分群的效果不好，因此選擇降維的 k 值尤為重要。
2. 亦會因為相似矩陣的計算方式得到不同的分群效果。

－ 參考資料 －

• Spectral Clustering 原始論文： Ng, Andrew Y., Michael I. Jordan, and Yair Weiss. “On spectral clustering: Analysis and an algorithm.” Advances in neural information processing systems. 2002.
• Spectral Clustering 維基百科：https://en.wikipedia.org/wiki/Spectral_clustering
• Graph 維基百科：https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
• Similarity measure 維基百科：https://en.wikipedia.org/wiki/Similarity_measure