Clustering method 7

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）

之前提及過階層式分群法依據定義的兩資料點間的距離來做切割或聚合，但每階層都須重新計算所有資料點間的距離關係，才能進行近一步的處理。然而，BIRCH 的算法記錄每群的群聚特徵，以便進行分群並達到減少計算量的效果。此算法也是一種增量的分群方法，意即每一次的決策是基於當前已處理過的資料點來做決定。

以下將會介紹此算法如何轉換成便於分群的特徵以及其分群的依據，也提供相同的範例以便進行比較。

－ 基本概念 －

BIRCH 算法的主要概念是，依據每群資料點集合的群聚特徵（Clustering Feature, CF）建構聚類特徵樹（Clustering Feature-Tree, CF Tree），直接對此特徵進行分群，因此只須看過一次資料集即可進行分群。然而群聚特徵以及聚類特徵樹會在下面一一說明。

群聚特徵（Clustering Feature, CF）

CF =（N, LS, SS），每群的特徵以三個維度表示，分別為資料點集合的個數N，所有資料點的和 LS，以及所有資料點的平方和 SS。

LS 為資料點的和， SS 則為資料點的平方和。

此種表示每群的特徵有計算上的好處，對於不相交的兩群合併，CF 有可加性。因此針對一個群僅需保留一個 CF 的信息，以減少儲存空間，而分群的決策也是依據此特徵去做運算。

CF 可加性定理

度量方法（metric）

若 N 個資料點 X_i , i=1, …, N，表達每個群的基本量有

半徑 (R) 及直徑 (D) 為測量靠近中心點的密集程度

若兩群資料點分別為 x_i , i=1, …, N_1，x_j , j=1, …, N_2，則兩群間的距離有下列幾種測量方式

兩群 (clusters) 間的距離測量方式

聚類特徵樹（Clustering Feature Tree, CF Tree）

每群的特性由 Clustering Feature 去表示，而樹的節點由好幾群去長成，然而樹的深度以及寬度由三個參數決定，分別是

1. 非葉子節點（Non-leaf Nodes）可容納最大的子群數 B（最大 CF 數）。
2. 葉子節點（Leaf Nodes）可容納最大的子群數 L（最大 CF 數）。
3. 葉子節點每群最大半徑 T，意即群中的所有資料點將落在半徑為 T 的超球體內。

此 Clustering Feature-Tree 參數設定為 B = 6, L = 5, T

聚類特徵樹（Clustering Feature Tree）的生成，可由以下步驟去建構：

1. 選擇跟節點（Root），初始由資料集中處理的第一點擔任。

p1 為初始的根結點，此時 CF1 = (1, LS1, SS1)

2. 從根節點向下搜尋，根據選擇的度量方法判斷距離最近的群。若距離此群在 T 以內，則合併群。

若距離小於T則合併成同一群，因此 p2 合併至 p1 內，而更新後的 CF1=(2, LS1', SS1')

若距離大於 T，則另成新的一群，因此在根節點下有兩個 CF，分別為 CF1=(2, LS1', SS1'), CF2=(1, LS2, SS2)

3. 若群數大於葉子節點的所能容納的數目（L），則分裂節點。由距離最遠的兩個群做為種子，剩下的群則重新分配，與最近的群分在同一個葉子節點下。

若 L=2，且新資料點 p4 距離 CF1 及 CF2 皆大於 T，則需分裂節點。

假設 CF1_1 與 CF2_1 為最遠的群，且CF1_2 與 CF1_1 距離最近，則重新分配的結果為上。

4. 持續處理下一個新資料點，若葉子節點數目大於所能容納的非葉子節點數（B），則進行分裂，與上述方法相同。

新資料點 p5 與 Leaf Node 1 的 距離較近，但因設定的參數 L = 2，所以需進行分裂

Leaf Node 1分裂為兩個 Leaf Nodes。若 B = 2，則節點需再進行分裂。

若 Leaf Node 的數目超過可容納的最大值（B=2），則需要重新分配節點，結果如左圖。右圖為上下連結關係圖。

（命名方式為容易看出節點上下關係，因此有所變動，但實際上在重新分配時，僅更改指標方向而已。）

總結以上過程，插入CF Tree 新節點即是以下的迭代步驟：

1. 從根節點向下尋找與新資料點距離最近的群（葉子節點內的 CF 節點）。
2. 若新資料點加入後，此群後半徑不超過所定的閾值 T，則加入資料點並更新所有影響的 CF 值。
3. 若當前節點內包含的 CF 節點數小於 L，則創建 CF；若大於 L，則以最遠兩個節點作為種子分裂成兩節點，其餘分配至最近的節點中，並更新所有的 CF 值。
4. 若非葉子節點數目大於 B，則以最遠兩個子節點做為種子分裂成兩節點，其餘分配至最近的節點中，並更新所有的 CF 值。

建構聚類特徵樹（Clustering Feature Tree）流程圖

藉由設定的參數以及定義的距離關係即可建構聚類特徵樹（Clustering Feature Tree），而後續的應用則與階層式分類法相同。

－ 演算法 －

• 輸入：資料集 D，建構聚類特徵樹參數 B（非葉子節點可容納最大的子群數）、L（葉子節點可容納最大的子群數）、T（葉子節點每群最大半徑），分群數目 k（非必要）以及定義距離 metrics
• 輸出目標分群集合 Clusters

1. 將所有資料點依次讀入，建構聚類特徵樹（Clustering Feature Tree, CF Tree）（設定 B、L、T 等參數，依照上述步驟建構）。
2. 去除異常的節點（節點內的資料點很少，可視為異常），與最近的群合併。
3. 為了消除資料點處理順序所造成的不合理結構，可以利用其他分群演算法進一步的分類，得到較好的 CF Tree。
4. 利用新的 CF Tree 中所有子群的質心作為起始點，按距離再重新分群。

對於 BIRCH 算法中最重要的步驟即是建構 CF Tree，其他接續的步驟皆為了對樹的結構做最佳化處理。

－ 算法實例 －

使用 Sklearn.cluster.Birch 套件：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import Birch
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
T = 2 # maximum radius of CF
n = 3 # number of clusters (not essential)
#BIRCH method
model = Birch(threshold=T, n_clusters = n)
# If type(n_clusters)=int, then the model is AgglomerativeClustering # with n_clusters
model.fit(X)
labels = model.fit_predict(X)
c = model.subcluster_labels_
#results visualization
plt.figure()
plt.scatter(X[:,0], X[:,1], c = labels)
plt.scatter(c[:,0], c[:,1], marker='x', c=model.subcluster_labels_)
plt.axis('equal')
plt.title('Prediction')
plt.show()

（標示顏色僅是分群結果，沒有順序性）右圖為 T=2 的結果，’x’為葉子節點的質心。

若 n_cluster 設為 None，則算法不執行最後一個以 Agglomerative 分群算法去重新分群。

右圖算法的 n_clusters 設為 None，則依照 CF Tree 的葉子節點作為分群結果

用於影像分割…

import numpy as np
import matplotlib.pyplot as plt
from skimage.transform import rescale
from sklearn.cluster import Birch
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
T = 0.01 # maximum radius of CF
n = 15   # number of clusters (not essential)
#BIRCH Clustering method
model = Birch(threshold=T, n_clusters=n) 
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()

左圖為原圖，右圖為分割的結果。

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

－ BIRCH 算法總結－

優點：

1. 節省儲存空間，Leaf Nodes 以外的節點僅儲存 Cluster Feature（CF）值以及指向 Child 和 parent 的指標。
2. 計算速度快，合併兩個群僅需將對應的 CF 值相加，而計算兩群的距離只需 CF 值去判別。
3. 可辨識雜訊點。包含較少資料點的群視為離群值。

缺點：

1. 分群結果依賴資料點的處理順序。
2. 對於非球狀的分布效果不佳，取決於距離的計算方式（大多與歐式距離去做計算）。
3. 每個子節點數有經由參數限制，因此得出的分群結果可能與實際的分布情況相差很大。

－ 參考資料 －

• BIRCH 原始論文： Zhang, Tian, Raghu Ramakrishnan, and Miron Livny. “BIRCH: an efficient data clustering method for very large databases.” ACM Sigmod Record. Vol. 25. №2. ACM, 1996.
• 相關論文： Zhang, Tian, Raghu Ramakrishnan, and Miron Livny. “BIRCH: A new data clustering algorithm and its applications.” Data Mining and Knowledge Discovery 1.2 (1997): 141–182.
• BIRCH 維基百科： https://en.wikipedia.org/wiki/BIRCH
• sklearn.cluster.Birch 套件： https://scikit-learn.org/stable/modules/generated/sklearn.cluster.Birch.html