Hierarchical Agglomerative Clustering (HAC) === ###### tags: `Clustering` --- ## *介紹* ### 演算法 上一篇講了分群演算法 (Clustering Algorithm)中的 K-Means，這次我們要講的是另一種常見的演算法，***階層式凝聚分群 (HAC)***。 HAC是階層式分群的一種，方法是由下至上建立起樹狀的分群層次結構（又稱作dendrogram）。最下層是將每一筆資料是作為一個群集 (稱為**leaf**)，隨著階層向上移動，資料會相互成為一個個較小的群集，再往上，成對的群集相互合併，使群集總數遞減，最後合為一群我們稱為**Root**。 <center><img src='https://i.imgur.com/iWhaoI7.png' width='350'></center><br/> <center><img src='https://i.imgur.com/zC6PcFs.png' width='600'> </center> ### 度量標準 群集合併時，我們需要度量群集間的相異度(dissimilarity)，來做為合併的依據。其中，相異度即群之間的距離度量，用距離以及鏈結標準 (linkage) 來實現，在不同的距離計算方式與鏈結標準下，分群的結果也會不同。 (想像一下，在資料分布上，相似的資料會有相似的特徵表現，代表他們在分布上距離相近。所以，資料之間的相異程度可以用距離來度量，距離越遠的代表他們的相異程度越大。) <center><img src='https://i.imgur.com/WQqgW4r.png' width=360></center> <center> <font size=2>圖中，對data 1來說，與data 3的相似度比data 2高</font></center> * <strong>對數字資料來說，常用的距離的算法有 : </strong> Euclidean distance : $\parallel a-b \parallel_2=\sqrt{\sum_{i}(a_i-b_i)^2}$<br/> Squared Euclidean distance : $\parallel a-b \parallel_2^2=\sum_{i}(a_i-b_i)^2$<br/> Manhattan distance : $\|a-b\|_1=\sum_{i}|a_i-b_i|$<br/> * <strong>鏈結標準(即如何定義群集之間的距離) </strong><br/> 對群集$C_i$與$C_j$之間，決定合併的鏈結標準有:<br/> <strong>1. single-linkage agglomerative algorithm : 選定兩群集內最近的兩筆資料之間的距離作為參考標準</strong> $$d(C_i,C_j)=\min_{a_k \in C_i,b_t \in C_j}d(a_k,b_t)$$ <center><img src='https://i.imgur.com/QeKama8.png' width='360'></center> <strong>2. complete-linkage agglomerative algorithm : 選定兩群集內最遠的兩筆資料之間的距離作為參考標準</strong> $$d(C_i,C_j)=\max_{a_k \in C_i,b_t \in C_j}d(a_k,b_t)$$ <center><img src='https://i.imgur.com/doS8xkc.png' width=360></center> <strong>3. average-linkage agglomerative algorithm : 選定兩群集之間資料的平均距離作為參考標準</strong></br> $$d(C_i,C_j)=\sum_{a_k \in C_i}\sum_{b_t \in C_j}\frac{d(a_k,b_t)}{|C_i||C_j|}$$ <center><img src='https://i.imgur.com/oVpyq4b.png' width='400'></center> <font size=2>其中$|C_i|,|C_j|$代表群集裡的資料個數</font><br/> <strong>4. centroid-linkage agglomerative algorithm : 選定兩群集質心之間的距離作為參考的標準</strong><br/> $$d(C_i,C_j)=d(c_i,c_j)_{c_i\in C_i,c_j\in C_j}$$$$其中，質心 c_i=\frac{1}{|C_i|}\sum_{a_k\in C_i}a_k$$<br/> <center><img src='https://i.imgur.com/oAy1LKo.png' width='400'></center><br/> <strong>5. Ward’s Minimum Variance Method (Ward's Method) : 選定兩個群集合併後，群集中每一筆資料到群集中心的距離平方和作為參考標準</strong><br/>(ward's Method 的距離標準只限於歐式距離)<br/> $$d(C_i,C_j)=\sum_{x\in C_i\bigcup C_j}(x-\mu)^2,其中\mu=\frac{1}{|C_k|}\sum_{C_i\bigcup C_j}x$$<br/> ## *運作流程* #### 1. 選定分群數 N #### 2. 每一筆資料視為一個群集<br/> <center><img src='https://i.imgur.com/wTXWLpt.png' width='360'></center><br/> #### 3. 計算群集之間的距離<br/><pre>&nbsp;其中，決定距離的標準就是linkage，但最開始皆是由歐式距離來決定</pre> <center><img src='https://i.imgur.com/gSEOGnG.png' width='360'></center><br/> #### 4. 選擇linkage最小的兩個群集合併(每一次合併一定只有兩個群集合併)<br/> <center><img src='https://i.imgur.com/SN4L6WQ.png' width='360'></center><br/> #### 5. 重複步驟3.4.直到總分群數為N ![]() <center><img src='https://i.imgur.com/7g2OlcH.png' width='360'><img src='https://i.imgur.com/1SeJy5t.png' width='360'></center><br/> <center><img src='https://i.imgur.com/byL8MNs.png' width='360'><img src='https://i.imgur.com/8zIGdLW.png' width='360'></center> ## *檢驗(Validation)* <strong>檢驗方式與K-means的方法相同，分為三種:</strong> <strong> 1. Internal cluster validation 2. External cluster validation 3. Relative cluster validation </strong> ### Internal measure <strong> 1. Silhouette Coefficient 2. Calinski-Harabasz Index(CH Index) 3. Davies-Bounldin Index(DBI) </strong> ### Relative measure <strong> 1. Elbow Method 2. Average Silhouette Method </strong> --- [複習連結 - -詳細介紹](https://hackmd.io/0vxwwPqdSzCQ7taN_CfgdA?view#%E5%88%86%E7%BE%A4%E7%B5%90%E6%9E%9C%E6%AA%A2%E9%A9%97Clustering-Validation) ## *HAC 範例* #### <font size=4>引入套件</font> ```python= import pandas as pd import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import AgglomerativeClustering from sklearn.metrics import silhouette_score,calinski_harabasz_score,davies_bouldin_score ``` #### <font size=4>從sklearn的資料集，引入鳶尾花的資料集(iris dataset)</font> ```python= from sklearn.datasets import load_iris iris=load_iris() ``` #### 初始假定分群個數K(例中K=5)，利用散點圖觀察分群結果 ```python= agg_5=AgglomerativeClustering(n_clusters=5,linkage='ward').fit(iris.data) label_5=agg_5.labels_ plt.scatter(iris.data[:,2],iris.data[:,3],c=label_5,cmap='brg') plt.show() ``` <center><img src='https://i.imgur.com/LfKb2EG.png' width='400'></center> #### 但觀察指標發現分群的結果並不是很好 ```python= #用驗證指標，觀查分群的好壞 method=[silhouette_score,calinski_harabasz_score,davies_bouldin_score] name=['silhouette_score','calinski_harabasz_score','davies_bouldin_score'] score_5=[] for validation in method: score_5.append(validation(iris.data,label_5)) Tb_5=pd.DataFrame(data=score_5,columns=['score(k=5)'],index=name) Tb_5 ``` <center><img src='https://i.imgur.com/hg8LGlk.png' width='300'></center> #### 當我們不知道應該如何分群的時候，可以利用Relative mesure來找到最好的分群數。<br/>但因為HAC的套件裡沒有計算群集內的距離平方和的特性(Attribute)，所以我們需要自己定義函式 ```python= #找出各群集質心 def centroid(model,centroid_num): sum=[[0]]*centroid_num count=[0]*centroid_num for i in range(centroid_num): for index,Class in enumerate(model.labels_): if Class == i: sum[i]+=(iris.data[index]) count[i]+=1 center=np.array(sum)/np.array(count).reshape((centroid_num,1)) return center #計算群集內資料到對應的群集質心的距離平方和 def Inertia(model,centroid_num): from scipy.spatial import distance_matrix from scipy.spatial import distance lt=[] for index,Class in enumerate(model.labels_): lt.append(distance.euclidean(iris.data[index],centroid(model,centroid_num)[Class])**2) inertia=np.array(lt).sum() return inertia ``` #### 定義好函式後，我們就可以開式計算，找出最好的分群數了 ```python= distoration=[] sil_score=[] cal_score=[] dav_score=[] K=range(2,10) for k in K: Hac = AgglomerativeClustering(n_clusters=k,linkage='ward').fit(iris.data) distoration.append(Inertia(Hac,k)) for k in K: Hac = AgglomerativeClustering(n_clusters=k,linkage='ward').fit(iris.data) sil_score.append(silhouette_score(iris.data,Hac.labels_)) for k in K: Hac = AgglomerativeClustering(n_clusters=k,linkage='ward').fit(iris.data) cal_score.append(calinski_harabasz_score(iris.data,Hac.labels_)) for k in K: Hac = AgglomerativeClustering(n_clusters=k,linkage='ward').fit(iris.data) dav_score.append(davies_bouldin_score(iris.data,Hac.labels_)) #將圖畫出來 plt.figure(figsize=(10,5)) plt.title('Elbow method',fontsize=16) plt.xlabel('cluster number(k)',fontsize=14) plt.ylabel('distoration',fontsize=14) plt.plot(K,distoration,'bx-') plt.axvline(x=3,linestyle='dashed') plt.show() plt.figure(figsize=(10,5)) plt.title('Silhouette coefficient',fontsize=16) plt.xlabel('cluster number(k)',fontsize=14) plt.ylabel('silhoue score',fontsize=14) plt.plot(K,sil_score,'bx-') plt.axvline(x=3,linestyle='dashed') plt.show() plt.figure(figsize=(10,5)) plt.title('CH index',fontsize=16) plt.xlabel('cluster number(k)',fontsize=14) plt.ylabel('CH score',fontsize=14) plt.plot(K,cal_score,'bx-') plt.axvline(x=3,linestyle='dashed') plt.show() plt.figure(figsize=(10,5)) plt.title('DBI',fontsize=16) plt.xlabel('cluster number(k)',fontsize=14) plt.ylabel('DB score',fontsize=14) plt.plot(K,dav_score,'bx-') plt.axvline(x=3,linestyle='dashed') plt.show() ``` ![](https://i.imgur.com/n9dc2vo.png)<br/> ![](https://i.imgur.com/4TxTVU0.png)<br/> ![](https://i.imgur.com/IYswrxA.png)<br/> ![](https://i.imgur.com/2LN4FVU.png)<br/> #### 可以從上圖知道，綜合起來，最佳的分群數是3群，我們將分群數設為3群，再做一次HAC觀察結果 ```python= #將群數設定為3，對資料做K-means分群 agg_3=AgglomerativeClustering(n_clusters=3,linkage='ward').fit(iris.data) label_3=agg_3.labels_ #將分群的結果用分布圖顯示 plt.title('Petal(Predict)',fontsize=16) plt.xlabel(iris.feature_names[2],fontsize=14) plt.ylabel(iris.feature_names[3],fontsize=14) plt.scatter(iris.data[:,2],iris.data[:,3],c=label_3,cmap='brg') plt.show() ``` <center><img src='https://i.imgur.com/srXaDp5.png' width='400'></center> #### 與之前分5群做比較觀察分群結果是否有變好 ```python= method=[silhouette_score,calinski_harabasz_score,davies_bouldin_score] name=['silhouette_score','calinski_harabasz_score','davies_bouldin_score'] score_3=[] for validation in method: score_3.append(validation(iris.data,label_3)) Tb_3=pd.DataFrame(data=score_3,columns=['score(k=3)'],index=name) table=pd.concat([Tb_5,Tb_3],axis=1) table['Variability']=table['score(k=3)']-table['score(k=5)'] table ``` <center><img src='https://i.imgur.com/ukUr2OX.png' width='500'></center> #### 由上面的表格可以看出分3群的結果確實比分5群的結果要來的好 #### 接下來，我們還可以對linkage的方法去作分析，找出iris的資料集使用哪一種linkage，分群結果會最好 ```python= Linkage=['single','complete','average','ward'] #算出檢驗指標 score=[] for validation in method: lt=[] for link in Linkage: model=AgglomerativeClustering(n_clusters=3,linkage=link).fit(iris.data) model_label=model.labels_ lt.append(validation(iris.data,model_label)) score.append(lt) #算出距離平方和 iner=[] for link in Linkage: model=AgglomerativeClustering(n_clusters=3,linkage=link).fit(iris.data) model_label=model.labels_ iner.append(Inertia(model=model,centroid_num=3)) iner=np.array(iner).reshape((1,4)) #因為計算方法不同，所以將Inertia與其他指標分開算，再將它們合併 Iner=pd.DataFrame(data=iner,columns=Linkage,index=['Inertia']) Score=pd.DataFrame(data=score,columns=Linkage,index=name) table_link=pd.concat([Score,Iner],axis=0) #找出各指標下最好的方法 Value=np.array(table_link) better=[] for i in range(2): better.append(table_link.columns[Value[i].argmax()]) for j in range(2,4): better.append(table_link.columns[Value[j].argmin()]) table_link['Better']=better table_link ``` <center><img src='https://i.imgur.com/ML42Zmn.png' width='580'></center><br/> #### 由上面的圖可以看出來，對iris的資料即來說，Ward's Method 的結果是較好的 --- 參考: [維基百科 - Hierarchical clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering#cite_note-6) [AI - Ch19 機器學習(7), 分群/聚類：階層式分群法 Clustering: Hierarchical Clustering](https://mropengate.blogspot.com/2015/06/ai-ch17-6-clustering-hierarchical.html) [sklearn-clustering](https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering) [Hierarchical Clustering 階層式分群 | Clustering 資料分群 |](https://jamleecute.web.app/%e7%b5%b1%e8%a8%88-r%e8%aa%9e%e8%a8%80-%e5%88%86%e7%be%a4%e5%88%86%e6%9e%90-clustering-hierarchical-clustering-%e9%9a%8e%e5%b1%a4%e5%bc%8f%e5%88%86%e7%be%a41/)