Cluster analysis 集群分析

簡介 集群分析(cluster analysis)將資料分成許多有意義或有用的群體(群集)。 若data set中有n個個體(individuals)，每個個體有p個測量值，群集分析是要將個體加以分群成數個群集(cluster)，使得在每個群集中的成員間相似，但與其它群集中成員的不相似。

例題-15位學生的身高和體重

例題-銀行根據收入與負債將客戶分群

集群分析(cluster analysis) 根據資料的相似性(similarity)或不相似性(dissimilarity)將資料分群歸屬到數個集群 使同一群內的資料或個體相似程度大，各群間的相似程度小

Clustering is subjective分群是主觀的 What is a natural grouping among these objects? Clustering is subjective分群是主觀的 Simpson's Family School Employees Females Males

集群分析(cluster analysis) 也稱為沒監督學習(unsupervised learning) 統計學家也稱為分類(classification) 心理學家也稱為分類(sorting) 在行銷的人稱為市場區隔(segmentation)

Cluster analysis與Classification的不同

Cluster analysis與Classification的不同

集群分析的階段 資料準備與分群特徵選取：根據問題特性、資料類型及分群演算法，選取具代表性的變數做為分群特徵屬性。 相似度計算：在選擇測量相似性時的方式時，需考慮資料的類型以及後續使用分群的演算法。 分群演算法：為集群分析中最重要的階段，利用分群演算法將資料分組，有些分群演算法可能需要自行決定群數。 分群結果評估與解釋：當分群結束後需檢視分群結果是否合理。由於分群結果可能是另一個方法的輸入資料，需對集群結果進行定義或命名。

集群分析的應用 生物學：分類物種 醫學：疾病分類 消費行為：消費型態分類 集群分析在心理學與其他社會科學、生物學、統計學、樣式辨識（pattern recognition）、資訊檢索、機器學習與資料探勘等領域上，都扮演很重要的角色。

Similarity Measures 相似性量數 許多統計方法, 如集群分析, 多元尺度法…等, 都由兩兩變數(variables)或項目(items)的相似性或不相似性矩陣為開始點 假設有n個個體(項目), 每個個體有p個測量值

Similarity Measures 相似性量數 許多量數可用來量化相似性或不相似性 距離與相似性量數計算公式的選擇，與資料特徵、測量尺度和集群方法有關 在選擇量數前，要先考慮data的特徵 Data的特徵可分為三種: Interval data:資料都是定量的,數字有數量上的意思 Frequency count data:資料都是次數 Binary data :資料是0或1。(資料是0或1只代表類別，沒有數量上的意義)。

Distance and similarity measures for pairs of items 兩兩項目的相似性與不相似性

Distance Measure 不相似性量數 For Interval Data

Distance Measure 不相似性量數 For Interval Data

歐式距離與曼哈頓距離在二維空間上的物理意義 會員1=(20, 20) 與會員2=(21, 26)之間的歐式距離與曼哈頓距離分別如下所示 歐式距離 曼哈頓距離 曼哈頓距離 歐式距離

例題-美22家水電公司事業

例題-美22家水電公司事業

Distance Measure 不相似性量數 For binary Data

Distance Measure 不相似性量數 For binary Data

Distance Measure 不相似性量數 For binary Data

Distance Measure 不相似性量數 For binary Data

Similarity Measure相似性量數 For binary Data

Similarity Measure相似性量數 For binary Data

Similarity Measure相似性量數 For binary Data

Similarity Measure相似性量數 For binary Data 除了這8個外，還有很多….

例題-5個人有下面特徵 Individual Height 身高 Weight 體重 Eye color 眼睛顏色 Hair color頭髮顏色 Handedness 左右撇子 Gende 性別 1 68 140 Green Blond Right Female 2 73 185 Brown Male 3 67 165 Blue 4 64 120 5 76 210 Left

例題-5個人有下面特徵

例題-5個人有下面特徵 1 2 3 4 5 Individual Height 身高 Weight 體重 Eye color 眼睛顏色 Hair color頭髮顏色 Handedness 左右撇子 Gende 性別 1 2 3 4 5

例題-5個人有下面特徵

例題-5個人有下面特徵 2, 5兩個人最相似, 1, 5兩個人最不相似 5個人分成2組(1,3,4) , (2,5)

例題-11種語言的1-10

例題-11種語言的1-10

前面這些例子，在求出相似性或不相似性矩陣後，分組是採用很主觀的視覺印象 下面介紹一些比較不是那麼主觀的分群的方法

集群法

兩種類型的集群法 Hierarchical Partitional

集群法 集群分析的方法，可分為兩大類，五種方法： 1.階層集群方法(hierarchical methods) (1)單一連結法(single linkage method) (2)完全連結法(complete linkage method) (3)平均連結法(average linkage method) (4)華德法(Ward’s method) 2.非階層集群方法(non-hierarchical methods) (1)K平均數法(k-means method)

Hierarchical Clustering Methods 階層式集群法 離

Hierarchical Clustering Methods 階層式集群法 階層集群法通常可用樹狀圖表示(稱為dendrogram)，可顯示集群－子集群的關係，以及集群被合併(凝聚式觀點)或分離(分割式觀點)順序。

可用樹狀圖來偵測極端值 The single isolated branch is suggestive of a data point that is very different to all others 極端值

Hierarchical Clustering Methods 階層式集群法 Agglomerative Hierarchical Methods (凝聚階層式集群法) I.剛開始1人1組 II.在每一階段, 最相似的兩個合併成一個集群 III.在每一階段, 每個集群是前一階段集群的合併 IV.用樹狀圖(dendrogram)展示結果 V.最終cluster的個數的選擇是主觀的

兩群集間的相似程度 計算認兩集群間的距離，有許多不同的方法，假設兩集群維A與B，d AB表示A與B兩集群間的距離， 𝒅 𝒊𝒋 表示兩資料點𝒊和𝒋的距離，下面是三種常用來衡量集群間差異的方法： Single linkage: 𝒅 𝑨𝑩 = m𝑖𝑛 𝒊∈𝑨, 𝒋∈𝑩 ( 𝒅 𝒊𝒋 ) Complete linkage: 𝒅 𝑨𝑩 = m𝑎𝑥 𝒊∈𝑨, 𝒋∈𝑩 ( 𝒅 𝒊𝒋 ) Average linkage: 𝒅 𝑨𝑩 = 𝟏 𝑵 𝑨 𝑵 𝑩 𝒊∈𝑨 𝒋∈𝑩 𝒅 𝒊𝒋

單一連結(最近鄰居法) 單一連結法又稱為最近鄰居法(nearest neighbor)。最近法對A、B兩群距離的定義是以A群內每一點到B群內每一點的距離之最小值，作為A、B兩群的距離。而群集時是依據此值最小者做為選取下一步結合之對象，最近鄰居法的概念表示如下： B A

單一連結(最近鄰居法)範例

單一連結(最近鄰居法)範例

單一連結(最近鄰居法)範例

單一連結(最近鄰居法)範例

單一連結(最近鄰居法)範例

完全連結(最遠鄰居法) 完全連結法又稱為最遠鄰居法(farthest neighbor)。最遠距離法的計算是以A群內每一點到B群內每一點的距離中之最大值，作為A、B兩群的距離。而群集時依然是以此值最小者做為選取下一步結合之對象，而最遠法的概念可表示如下： B A

完全連結(最遠鄰居法)範例

完全連結(最遠鄰居法)範例

完全連結(最遠鄰居法)範例

完全連結(最遠鄰居法)範例

完全連結(最遠鄰居法)範例 {1}

6個資料點之完全鏈結集群

平均連結法 平均連結法也稱中心法，是以計算A群的中心點到B群中心點的距離，作為A、B兩群的距離。集群時也是以此中心距離最小者為選取下一步結合的對象，平均連結法的概念可表示如下： B A 𝒅 𝑨𝑩 = 𝟏 𝑵 𝑨 𝑵 𝑩 𝒊∈𝑨 𝒋∈𝑩 𝒅 𝒊𝒋

平均連結法範例

平均連結法範例

平均連結法範例

平均連結法範例

平均連結法範例 8.17 7 5 2

6個資料點的平均連結集群 Marge

Ward’s method華德法 華德法又稱最小變異數法(minimum variance method)。華德法的分群方式是先將每一個個體視為一個集群，然後將各集群依序合併，合併之順序完全視合併後集群之組內總變異數之大小而定。凡使群內總變異數產生最小增量的個體即予以優先合併，愈早合併之個體表示其間的相似性愈高。

Ward’s method華德法 第i組組內變異數 I. 剛開始一個人一組 II.在每一階段, 計算集群內到中心點的歐氏距離平方和 For the ith cluster : 第i組組內變異數

Ward’s method華德法 組內總變異數 III. 合併ESS增加最少的兩個集群

Ward’s method華德法

Ward’s method華德法

Ward’s method華德法

Ward’s method華德法

Ward’s method華德法

Ward’s method華德法

Ward’s method華德法 Step4:

Ward’s method華德法 20.4+53=73.4 6.5+14=20.4 6.5

Single linkage Average linkage Wards linkage

Nonhierarchical Clustering Methods 非階層式集群法 非階層集群方法是在各階段分群過程中，將原有的集群予以打散，並重新形成新的集群。其主要的運用方法是：K平均數法(k-means methods)。 K-means的 K 指的是集群數，而means則是集群中心。

K平均數法(k-means methods) 步驟2 計算每個項目到每群中心的平方歐 氏距離, 然後重新分派項目到距離最近的組 (若有項目由起初設定組別移出, 則此集群的中心在 進行到下一步前要重算) 重複步驟2直到沒有重新分派發生為止

K平均數法(k-means methods)

K平均數法(k-means methods)

K平均數法(k-means methods)

K平均數法(k-means methods)

分群的結果受到下面影響 集群數k 中心點的選擇-可用mean, median, …. 不相似性量數

集群數目的決定 在進行集群時，一個很重要的問題是要決定分為多少群才有意義，以下幾項準則可以用來作為參考： 1.集群之群數以在2~6群為宜，超過 6 群則其後續分析將變得相當瑣碎，因此除非另有特殊的考量，集群之群數以不超過 6 群為宜。 2.集群完成後，各群之觀察值應盡量接近，即各群之觀察值不要相差太遠。 (例如，若第一群有100個觀察值，第二群只有5個觀察值即非常不適當。)

集群數目的決定 3.當集群數減少，集群內各觀察值的同質性便會降低。研究者應權衡集群數與同質性兩者，儘可能找到較少的集群，但仍滿足同質性的必要水準。 4.集群時，各集群變數在各群之分數應具有顯著性，即集群變數應具有區分之效度，否則，該集群變數是否存在對於分群即沒有顯著的作用。

集群數目的決定 5.集群之後，實際分群與理論分群之比較結果，其命中率應達顯著之水準。 6.集群時，要盡量依照過去文獻之建議來決定集群數目。

例題 Person Homer 0” 250 36 M Marge 10” 150 34 F Bart 2” 90 10 Lisa 6” Hair Length Weight Age Class Homer 0” 250 36 M Marge 10” 150 34 F Bart 2” 90 10 Lisa 6” 78 8 Maggie 4” 20 1 Abe 1” 170 70 Selma 8” 160 41 Otto 180 38 Krusty 200 45 例題 Comic 8” 290 38 ?

例題 8 7 2 4 3 1 We begin with a distance matrix which contains the distances between every pair of objects in our database.由不相似性矩陣開始 D( , ) = 8 D( , ) = 1

Bottom-Up (agglomerative): Starting with each item in its own cluster, find the best pair to merge into a new cluster. Repeat until all clusters are fused together. Choose the best … Choose the best … Choose the best …

集群分析: 擷取數值變數 NumVars<-function(data){ nc<-ncol(data) keep<-numeric(nc) j<-0 for(I in 1:nc){ if(is.numeric(data)[,j])){ j<-j+1 keep[j]<-I } return(as.matrix(data[,keep]))

集群分析: 擷取數值變數 NumVars<-function(data){ nc<-ncol(data) keep<-numeric(nc) j<-0 for(I in 1:nc){ if(is.numeric(data[,j])){ j<-j+1 keep[j]<-I } return(as.matrix(data[,keep]))

付出最多的人，也是收穫最多的人 ~共勉之~