Clustering method 4

Hierarchical Clustering — Agglomerative Clustering

之前介紹的分群方法都有較複雜的演算過程，此次的階層式分群法（hierarchical clustering）僅需資料點兩兩間的距離，即可達到分群效果，相對容易，但也較依賴定義的距離關係，而有不同的群聚結果。

以下將會介紹階層式分群法的基本概念以及常見於階層式分群法定義距離的算法，最後亦會用此算法處理相同的例子來比較差異。

－ 基本概念 －

階層式分群法（hierarchical clustering）即是一種階層架構的方式，將資料反覆分裂或聚合，最後產生目標的分群集合。常見的階層式分群法有兩種：

• 聚合（agglomerative）：是一種 “ bottom-up” 的方法，也就是先準備好解決問題可能所需的基本元件或方案，再將這些基本元件組合起來，由小而大最後得到整體。因此在階層式分群法中，就是將每個資料點都視為一個個體，在一一聚合。

由下到上的聚合方式（Agglomerative）

• 分裂（divisive）：是一種 “ top-down” 的方法，先對問題有整體的概念，然後再逐步加上細節，最後讓整體的輪廓越來越清楚。而此法在階層式分群法中，先將整個資料集視為一體，再一一的分裂。

由上到下的分裂方式（Divisive）

此次將會介紹以聚合的方式呈現階層式分群法，而群間的距離演算法會是階層式分群法中最重要的一環，因距離的算法衡量兩群的相似程度，分群也會依據此量測方式來做決策。以下將會有幾種最常見的群間的距離算法：

• 單一連結聚合演算法（single-linkage agglomerative algorithm）：群間的距離定義為兩群中最近點的距離。

紅色線的長度即為單一鏈結聚合算法的距離

• 完整連結聚合演算法（complete-linkage agglomerative algorithm）：群間的距離定義為兩群中最遠點間的距離。

紅色線的長度即為完整鏈結聚合算法的距離

• 平均連結聚合演算法（average-linkage agglomerative algorithm）： 群間的距離定義為兩群間各點間的距離總和平均

• 中心聚合演算法（centroid method）：群間的距離定義為兩群中心點間的距離

mu_C指的是C集合中的平均值

紅色線的長度即為中心聚合算法的距離（藍色點為紫色資料點的中心點，橘色則為綠色資料點的中心點）

• 沃德法（Ward’s method）： 群間的距離定義為兩群合併後，各點到合併群中心的距離平方和

根據上述算法來定義群間的距離，也可視為測量群間的相似性，來合併同質性較高的群，以達到聚合的目的。

－ 演算法 －

輸入：資料集 D ，分群數目 k（非必要）以及定義距離 metrics

輸出：目標分群集合 Clusters

1. 每個資料點都視為一個分群集合 C_i，i = 1, …, n。
2. 利用距離函數 metrics 計算兩兩集合間的距離，並將最近的兩個集合合併為一個新的集合。
3. 重複步驟 2. 直到分群集合 Clusters 以達到目標分群數目 k（或合併為同一類為止）

－ 算法實作 －

使用Sklearn.cluster.AgglomerativeClustering套件：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
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 (not essential)
#Agglomerative Clustering method
model = AgglomerativeClustering(n_clusters = n, linkage = 'ward')
#linkage: ['ward', 'complete', 'average']
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()

• Ward’s method

左圖為原始資料集，右圖為階層式分群法利用 “ Ward’s method “ 計算距離的分群結果。

• Complete-linkage agglomerative algorithm

左圖為原始資料集，右圖為階層式分群法利用 “ complete-linkage “ 計算距離的分群結果。

• Average-linkage agglomerative algorithm

左圖為原始資料集，右圖為階層式分群法利用 “ average-linkage “ 計算距離的分群結果。

因為有較明顯群聚分布的資料集，選用測量距離的方式對於結果較無差別。也可利用樹狀圖來看分群的策略為何：

from scipy.cluster.hierarchy import dendrogram, linkage
# Performs hierarchical/agglomerative clustering on X by using "Ward's method"
linkage_matrix = linkage(X, 'ward')
figure = plt.figure(figsize=(7.5, 5))
# Plots the dendrogram
dendrogram(linkage_matrix, labels = labels)
plt.title('Hierarchical Clustering Dendrogram (Ward)')
plt.xlabel('sample index')
plt.ylabel('distance')
plt.tight_layout()
plt.show()

• Ward’s method

以樹狀圖呈現階層式分群法的分群策略（利用 Ward's method 聚類）

• Complete-linkage agglomerative algorithm

以樹狀圖呈現階層式分群法的分群策略（利用 Complete-linkage 聚類算法）

• Average-linkage agglomerative algorithm

以樹狀圖呈現階層式分群法的分群策略（利用 Average-linkage 聚類算法）

以上三種聚類方法，因為資料集較有群聚的分布，因此大致分類的決策非常相近，僅有些微的不同（對於 “ Ward's method ＂距離的差距較大， “Average-linkage ＂聚類方式所計算的距離範圍較小，意即三種方法間距離比例的差異）。

用於影像分割 …

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 = 10 #number of clusters (not essential)
#Agglomerative Clustering method
model = SpectralClustering(n_clusters = n, linkage = 'ward') 
#linkage: ['ward', 'complete', 'average']
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()

• Ward's method

利用 “ Ward’s method “ 定義距離，從而得出的分群結果。此例僅考慮顏色的因素，並不考慮密度，因此同顏色的像素都將視為同一點。

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

以樹狀圖呈現階層式分群法的分群策略（利用 Ward’s method 聚類）

• Complete-linkage agglomerative algorithm

利用 “ complete-linkage “ 定義距離，從而得出的分群結果。此例僅考慮顏色的因素，並不考慮密度，因此同顏色的像素都將視為同一點。

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

以樹狀圖呈現階層式分群法的分群策略（利用 Complete-linkage 聚類算法）

• Average-linkage agglomerative algorithm

利用 “ average-linkage “ 定義距離，從而得出的分群結果。此例僅考慮顏色的因素，並不考慮密度，因此同顏色的像素都將視為同一點。

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

以樹狀圖呈現階層式分群法的分群策略（利用 Average-linkage 聚類算法）

此例中，每一不同顏色都視為一點，而有較複雜的分布，對於不同的量測距離的方式所做出的聚合決策將會有較大的差異。

影像中，顏色的分布圖。（在影像中的每一種顏色都視為一資料點）

Complete-linkage 可能會導致大小不一的分群集合產生，相對而言，Ward's method 可以有較均衡的分群集合，但是僅能使用歐幾里得距離公式才符合假設條件。使用其他距離公式進行分群，並均衡集合大小，則能使用 Average-linkage的方式進行，因此一般較常使用此種方式去量測集合間的距離。

－ Hierarchical Clustering 算法總結－

優點：

1. 可以使用樹狀結構圖（Dendrogram）來呈現分群的過程。
2. 僅需要資料點間的距離，便可有分群的結果。

缺點：

1. 僅適合資料點較少的資料集，難以處理大量的資料，意即計算複雜度較大。
2. 定義群聚的距離很依賴資料集，而有不同的效果。

－ 參考資料 －

• Hierarchical Clustering 維基百科：https://en.wikipedia.org/wiki/Hierarchical_clustering
• Ward's method 維基百科：https://en.wikipedia.org/wiki/Ward%27s_method
• Dendrogram 維基百科：https://en.wikipedia.org/wiki/Dendrogram
• Johnson, Stephen C. “Hierarchical clustering schemes.” Psychometrika 32.3 (1967): 241–254.
• sklearn.cluster.AgglomerativeClustering套件：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html#sklearn.cluster.AgglomerativeClustering