AI - Ch19 機器學習(7), 分群/聚類：階層式分群法 Clustering: Hierarchical Clustering

階層式分群法（Hierarchical Clustering）
階層式分群法透過一種階層架構的方式，將資料層層反覆地進行分裂或聚合，以產生最後的樹狀結構，常見的方式有兩種：

聚合式階層分群法 (Bottom-up, agglomerative) : 如果採用聚合的方式，階層式分群法可由樹狀結構的底部開始，將資料或群聚逐次合併。
分裂式階層分群法 (Top-down, divisible) : 如果採用分裂的方式，則由樹狀結構的頂端開始，將群聚逐次分裂。

聚合式階層分群法（Hierarchical Agglomerative Clustering, HAC）
由樹狀結構的底部開始層層聚合，一開始我們將每一筆資料視為一個群聚（cluster），假設我們現在擁有n筆資料，則將這n筆資料視為n個群聚，亦即每個群聚包含一筆資料：

將每筆資料視為一個群聚 $C_i, i=1\ to\ n$
找出所有群聚間，距離最接近的兩個群聚 $C_i$、$C_j$
合併 $C_i$、$C_j$ 成為一個新的群聚
假如目前的群聚數目多於我們預期的群聚數目，則反覆重複步驟二至四，直到群聚數目已將降到我們所要求的數目。

Hierarchical Clustering 最後可以表示成一個Tree，來展示聚合式階層分群法所產生的樹狀圖(dendrogram)。

定義兩個群聚之間的距離

單一連結聚合演算法(single-linkage agglomerative algorithm)：群聚與群聚間的距離可以定義為不同群聚中最接近兩點間的距離。
完整連結聚合演算法(complete-linkage agglomerative algorithm）：群聚間的距離定義為不同群聚中最遠兩點間的距離，這樣可以保證這兩個集合合併後, 任何一對的距離不會大於 d。
平均連結聚合演算法(average-linkage agglomerative algorithm)：群聚間的距離定義為不同群聚間各點與各點間距離總和的平均。
沃德法（Ward's method）：群聚間的距離定義為在將兩群合併後，各點到合併後的群中心的距離平方和。

[用心去感覺] 群聚距離特性

Complete linkage : 和 average linkage 比較容易產生「齊頭並進」的效果。
Single linkage : 會在群聚的過程中產生「大者恆大」的效果。

Kruskal's algorithm : 事實上我們可以證明，如果資料集是二維平面上的點所成的集合，而且我們採用 single linkage，則所得到的連結圖即是這些點的 minimum spanning tree。

[tiny lab] Agglomerative Nesting (Hierarchical Clustering)
Description : Computes agglomerative hierarchical clustering of the dataset.
Usage:

agnes(x, diss = inherits(x, "dist"), metric = "euclidean",
stand = FALSE, method = "average", par.method,
keep.diss = n < 100, keep.data = !diss, trace.lev = 0)

library("cluster")

# import data
x <- read.table("data.txt")

# run AGNES
ag <- agnes (x, FALSE, metric="euclidean", FALSE, method ="single")

# print components of ag
print(ag)

# plot clusters
plot(ag, ask = FALSE, which.plots = NULL)

#input data
#      BA FI MI VO RM TO
#BA 0 662 877 255 412 996
#FI 662 0 295 468 268 400
#MI 877 295 0 754 564 138
#VO 255 468 754 0 219 869
#RM 412 268 564 219 0 669
#TO 996 400 138 869 669 0

COBWEB: Incremental Conceptual Clustering
COBWEB為一個漸增式的階層概念分群演算法，是一種非監督式學習(Unsupervised Learning)，採用了一個啟發式的類別效度(Category Utility)評估函數，並以此類別效度來引導一個分類樹的建立。

漸增式 : 資料會陸續加入系統中，而不是一次完整加入(batch)
階層概念分群 : 不必事先給定叢集數目的參數，系統會在資料陸續加入的過程中自動搜尋整個分類樹，並調整叢集的數目找到最佳的叢集。

類別效度 (Category Utility, CU)
類別效度的函數量測了某一特定物件被置放於給定類別之正確屬性值期望。
CU is a tradeoff between intra-class similarity and inter- class dissimilarity of objects.

Probability-theoretic definition of Category Utility : The probability-theoretic definition of category utility given in Fisher (1987) and Witten & Frank (2005) is as follows:

$CU(C,F) = \tfrac{1}{p} \sum_{c_j \in C} p(c_j) \left [\sum_{f_i \in F} \sum_{k=1}^m p(f_{ik}|c_j)^2 - \sum_{f_i \in F} \sum_{k=1}^m p(f_{ik})^2\right ]$

也就是$\Sigma_C \Sigma_A \Sigma_v P(A_i=V_{ij}) \times P(A_i=V_{ij}|C_k) \times P(C_k|A_i=V_{ij})$

類別效度的方程式包含了三個機率。

$P(A_i=V_{ij})$ : 首先是量測屬性 $A_i=V_{ij}$ 時，在整個資料庫中的條件機率。
$P(A_i=V_{ij}|C_k)$ : 在類別 $C_k$ 下,屬性 $A_i=V_{ij}$ 的條件機率。如果此值為1時，表示類別為 $C_k$ 的資料中屬性 $A_i$ 的值皆為 $V_{ij}$。屬性 $A_i$ 的值為 $V_{ij}$ 為定義類別的必要條件。
$P(C_k|A_i=V_{ij})$ : 某一資料在 $A_i=V_{ij}$ 時，存在類別 $C_k$ 中的條件機率。如果此值為1時，表示當 $A_i=V_{ij}$ 時，包含此值的類別必為 $C_k$。屬性 $A_i$ 的值為 $V_{ij}$ 被稱為定義類別 $C_k$ 的充要條件。

階層式分群法結論

優點

概念簡單，可用樹狀結構來表現整個計算過程。
只需要資料點兩兩之間的距離，就可以建構分群結果，而不需要資料點的實際座標。（因此每一個資料點可以示一個物件，而不必是空間中的一點。）

缺點

通常只適用於少量資料，很難處理大量資料。

References

Hierarchical Clustering (階層式分群法)
http://mirlab.org/jang/books/dcpr/dcHierClustering.asp?title=3-2%20Hierarchical%20Clustering%20(%B6%A5%BCh%A6%A1%A4%C0%B8s%AAk)&language=chinese

Data Mining Algorithms In R/Clustering/Hierarchical Clustering
https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/Hierarchical_Clustering

Wiki - Conceptual clustering
https://en.wikipedia.org/wiki/Conceptual_clustering

Wiki - Cobweb (clustering)
https://en.wikipedia.org/wiki/Cobweb_(clustering)

周仲愚 - 適用於COBWEB 演算法之屬性挑選與預先排序策略研究
http://ir.lib.stust.edu.tw/bitstream/987654321/960/2/093stut0396035.pdf

Pages

2015年6月16日星期二