Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 8: Cluster Analysis - Coggle Diagram
Chapter 8: Cluster Analysis
集群類型
Well-separated clusters
Center-based (Prototype-based) clusters
: 任何一筆資料到其所屬的群中心，比到其他群的中心都還要近
Contiguous clusters
: 點與其最近的點一定屬於同一群
Density-based clusters
: 當群是不規則或交織的，以及有雜訊或例外的時候可以使用
Property or Conceptual
K-means以及其變形
K-means
作法
任選K點作為起始中心(隨機選擇)
repeat
看點位於哪個群心最近，就分配到哪一群
重新計算群心
until 群心不再改變
時間複雜度
O(n ＊ K ＊ Ｉ ＊ d)
資料筆數、群數、Iteration數、屬性數目
評估方法 : 採用
SSE
(Sum of Squared Error)
實作問題
起始中心的選擇
說明 : 起始中心選得好不好很重要
解決方法
Multiple runs
一開始就選超過K個點，再從這些點裡面挑
Empty Clusters
解決方法 : 把空的那個群組的中心點取代掉
策略
選擇貢獻最大SSE的那個點
從SSE最大的那個群組裡面挑一個點
若有多的空群，就重複多次
逐步更新群心
說明
在最基本的K-means中，群心的更新是發生在點被assigned之後
另一種做法是Each assignment updates zero or two centroids
優缺點 : 成本高、引入order dependency、不會產生空群、可以使用權重
Bisecting K-means
(對分的)
作法
初始化一個cluster的list，裡面包含了所有的點
repeat
until list中有K個群
從list中挑一個群拆成兩部分，把SSE最小的那兩群加入list
優點 : 沒有選初始中心的問題、不會產生空群
K-means的限制
群集的資料筆數(初始中心沒選好，另一個群點數太少拉不回去)、密度不同、有outliers或分布形狀非球形時會有問題
如何解決 : 分多群一點，之後再把它合起來
Hierarchical clustering
優點 : 透過樹狀圖的切割，想分幾群就分幾群
方法(兩種)
Agglomerative
(集聚)
Divisive
(分裂)
集聚
分群演算法
更新方式
MIN (Single linkage)
: update max, merge max
MAX (Complete linkage)
: update min, merge max
Group Average
: 兩群中任兩點距離 O(n*n)
Distance Between Centroids
: 與Group Average結果差不多，但計算簡單
Other methods driven by an objective function
Ward’s Method uses squared error
: 兩群合併起來SSE會增加，找增加幅度最小的合併
分析
MIN
優點 : 可以處理非橢圓形
缺點 : 易受雜訊及例外干擾
MAX
優點 : 較不受雜訊及例外干擾
缺點 : 分群結果偏向球狀、會把大群拆開(兩群資料差很多時效果不好)
Group Average
MIN、MAX的折衷
優點 : 較不受雜訊及例外干擾
缺點 : 分群結果偏向球狀
Ward’s Method
優點 : 較不受雜訊及例外干擾
缺點 : 分群結果偏向球狀
複雜度
空間 : O(N^2)
時間 : O(N^3)，透過一些方法可能可以降到O(N^2*logN)
問題
一旦combine了兩個群，就無法undo
對雜訊及離群值敏感
在不同大小或非圓形的形狀上，表現不好
傾向拆散大群
分裂
分群演算法
MST(Minimum Spanning Tree)
作法
建立最小生成樹(每次都找離群組最近的點連起來)
如何分兩群? 找最長的線段砍下去
優點 :速度快
DBSCAN
說明
density-based algorithm
點
core point
(核心點) : 範圍內的點數 > MinPts
border point
(邊界點): 至少有一個鄰居是核心點
noise point
(雜訊點) : 以上皆非
作法
將點分為核心點、邊界點、雜訊點三種
刪除雜訊點
對剩下的點開始進行分群
將彼此距離小於Eps的核心點連起來
把相連的核心點群組分群
把邊界點分配到與其有關的核心點的那群
分析
優點 : 較不受雜訊及例外干擾、可以跑形狀及大小不同的資料
缺點 : 密度不同、欄位多時效果差
問題
對Eps及MinPts很敏感
如何決定Eps及MinPts
算出所有點與其第K近點的距離，進行排序 => 找轉折點，就是EPs
Cluster Validity
指標
External Index
(外部指標)
衡量分群標籤與外部提供標籤的匹配程度(supervised measure)
e.g. Entropy
Internal Index
(內部指標)
在沒有參考外部資訊的情況下評估分群的好壞(unsupervised measure)
e.g. SSE、Silhouette Coefficient
Relative Index
(相對指標)
用於比較兩個不同的群集
通常將內部與外部指標用在此function
e.g. SSE or Entropy
SSE
也可以被用來評估群集數目
通常越多群，SSE越小。可找最大轉折點來當分群數目
內聚與分離
Cluster Cohesion
(內聚)
評估群內資料靠得多近
WSS
SUM(dist(群心,點)^2)
越小越好
Cluster Separation
(分離)
BSS
群數 * SUM(dist(所有群的中心,群心)^2)
越大越好
評估各群組間分得多開
BSS + WSS = constant
Silhouette Coefficient
說明 : 結合內聚與分離
計算方式
For an individual point, i
a
: 到自己群中所有點的平均距離
b
: min(到別群所有點的平均距離)
s = 1 – a/b if a<b, (or s = b/a - 1 if a>=b, not the usual case)
s通常在0~1之間，離1越近越好