:dart: W3 - Hierarchical Cluster Analysis
===

<!-- ## Table of Content
[Toc] -->

## 名字：靖涵
### **Hierarchical Clustering Analysis (HCA)**

- **層次聚類 (Hierarchical clustering)**
以樹狀結構有層次地呈現分群(clustering)結果，適合階層式的數據(hierarchical data)，例如：生物學領域，以觀察資料的分群結構以便後續的相似度計算。

- **clustering (分群)**：不像分類 (classification) 任務的資料有明確的類別 (label)。原始資料沒有明確的類別，依照資料的相似性去分群（越近越容易分在同一群），再從分群結果中發現不同群之間的親疏遠近之別。例如常見的分群法：k-means。
- **Dendrogram:** 古希臘文 déndron（樹） 和 grámma（圖畫）組成，意旨「樹狀圖」。Hierarchical clustering 即以階層性為特色，因此很適合以樹狀圖的方式來圖像化。以便直觀了解每一簇之間的遠近關係。以下圖為例，在同一分支群(clade) 中的資料(leaf)就比起與另一分支群中的資料點相近。

* Hierarchical clustering 又可以依照資料是以 1.「聚合」方式合併還是以 2.「分裂」方式展開而分為以下兩者

**1. Agglomerative Hierarchical Clustering (AHC) 聚合式階層分群法:**

即每一個資料慢慢向上(bottom-up)一層一層合併，最後成為一簇 (cluster)。
AHC為一種概念，如何計算決定哪兩個資料點/群類要合併有許多不同的演算法。
以下為常見的 AHC 演算法：
- **single-linkage agglomerative algorithm 單一連結聚合演算法**
又稱「最近法」，即計算不同群聚中最接近兩點間的距離。
$C_i$ 、$C_j$ 代表 clustering i 和 clustering j，而 a 為 $C_i$ 中的一個點、b 為 $C_j$ 中的一個點。
$$d(C_i, C_j) = \min_{a \in C_i, b \in C_j} \text{d}(a, b)$$

- **complete-linkage agglomerative algorithm 完全連結聚合演算法**
又稱「最遠法」，計算不同群聚中最遠兩點間的距離。
$$d(C_i, C_j) = \max_{a \in C_i, b \in C_j} \text{d}(a, b)$$
- **average-linkage agglomerative algorithm 平均連結聚合演算法**
計算不同群聚間各點與各點間距離總和的平均。
$$d(C_i, C_j) = \sum_{a \in C_i,b \in C_j}\frac{\text{d}(a, b)}{|C_i||C_j|} $$
- **Ward's method 華德法**
將兩群合併後，各點到合併後的群中心的距離平方和。
μ 為 $C_i$ ∪$C_j$  的平均值；這裡 a 指兩群合併後 ($C_i$ ∪$C_j$) 群中的一個點。
$$ d(C_i,C_j) = \sum_{a \in C_i\cup C_j} ||a-μ||$$

**2. Divisive Hierarchical Clustering 分裂式階層分群法 :**

即AHC的相反，以一群資料出發，向下(top-down) 的方式慢慢分裂成為一個一個資料點。

* 如何**計算點和點之間的距離**也有很多方式，以下為常見的幾種方式：

- **Euclidean distance 歐幾里得距離：**
可用來計算空間中 點p 和 點q 之間的距離，公式中 n 為維度。

$$d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$$

- **Manhattan distance 曼哈頓距離：**
表明兩個點 (p,q) 在標準座標系統上的絕對值總和。原本是在計算像曼哈頓一班的方形建築區塊城市中最短的行車距離。n為維度。
$$ d(p, q) = \sum_{i=1}^{n} |p_i - q_i|$$
- **Canberra Distance 坎培拉距離：**
計算向量空間中 點p 和 點q 之間的距離，是 Manhattan distance 的加權版本。
p 和 q 皆為向量，n為維度。
$$d(p, q) = \sum_{i=1}^{n} \frac{|p_i - q_i|}{|p_i| + |q_i|}$$

[Reference_Clustering](https://web.ntnu.edu.tw/~algo/Fitting.html)
[Reference_HCA_1](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)
[Reference_HCA_2](https://tomohiroliu22.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-82-%E8%81%9A%E5%90%88%E5%BC%8F%E9%9A%8E%E5%B1%A4%E5%88%86%E7%BE%A4%E6%B3%95-agglomerative-hierarchical-clustering-5f064b996d20)
[Reference_AHC_1](https://r.qcbs.ca/workshop09/book-en/clustering.html)
[Reference_Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance)
[Reference_Manhattan_distance](https://zhuanlan.zhihu.com/p/101277851)
[Reference_Dendrogram](https://online.visual-paradigm.com/tw/knowledge/business-design/what-is-dendrogram/)

### **Multidimensional Scaling (MDS)** 多維/元尺度分析

- MDS為一種多變量分析，主要是把高維空間的資料映射到低維空間以減少計算上的複雜，以讓其可視化（人類只能看到三維空間的東西）、更好地進行分析。
可以分為：1. 數值(metric) 2. 非數值(Non-metric)。

**1. metric Multidimensional Scaling (MDS) 數值多元尺度分析**
MDS 在映射的時候更注重點和點之間的距離，盡可能讓點和點之間在低維空間的距離可以保持像在高維空間中一樣。使用迭代優化(iterative optimization)最小化**stress**。
- **stress：**
指**擬合度(goodness-of-fit)**，stress越小越接近0則代表擬合地更好。

**2. Non-metric multidimensional scaling (NMDS) 非數值多元尺度分析**
NMDS 更在意的是點和點之間的排名，即在降維成低維空間後點和點的誰比較近/遠，而非彼此之間的距離。

- 多維尺度分析可以用在多個領域，例如：行銷學。降維之後的結果也常被以 **感知圖/知覺圖(Perceptual Map)** 的方式呈現。以利圖視分析不同資料點的定位差異，如下圖。

[Reference_MDS_1](https://medium.com/marketingdatascience/%E5%AE%9A%E4%BD%8D%E6%8A%80%E8%A1%93-%E5%A4%9A%E5%85%83%E5%B0%BA%E5%BA%A6%E5%88%86%E6%9E%90-multidimensional-scaling-b21c8a99dfb4)
[Reference_MDS_2](https://www.youtube.com/watch?v=Yt0o8ukIOKU)
[Reference_stress_1](http://cda.psych.uiuc.edu/mds_509_2013/readings/systat_scaling_manual.pdf)

---

## 名字：俞辰
### K-Means Clustering (集群分析)
基本上Clustering的方法大都是非監督式學習(Unsupervised learning)，K-means也是非監督式學習。舉例，我給你一組身高和體重的資料，但沒有跟你說這組資料哪些是男生哪些是女生。我希望你用這組資料分出男生女生，這種時候就是用非監督式學習。

1. 我們先決定要分k組，並隨機選k個點做群集中心。
2. 將每一個點分類到離自己最近的群集中心(可用直線距離)。
3. 重新計算各組的群集中心(常用平均值)。

反覆 2、3 動作，直到群集不變，群集中心不動為止。


圖一: 黃色是群集中心的初始點，綠色為新的群集中心。


圖二: 新的群集中心會不斷的更新，直到不動為止。

[Reference 1](https://chih-sheng-huang821.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E9%9B%86%E7%BE%A4%E5%88%86%E6%9E%90-k-means-clustering-e608a7fe1b43)
[Reference 2](https://ithelp.ithome.com.tw/articles/10209058)

### Hopkins Statistic (霍普金斯統計量)
霍普金斯統計量是一種用來評估某一資料集是否適合於群集分析的統計量，也就是用來評估聚類效果的工具。透過比較任兩個物件到最近的聚類中心和到其他聚類中心的距離來決定一個資料集的聚類效果。霍普金斯統計量的取值範圍為[0,1]，值越接近0則表示資料集越趨向隨機分佈，值越接近1則表示資料集越趨向於聚類分佈。

[Reference 1](https://www.usplanking.com/article/321336)

### Cohen's Kappa Coefficient
Cohen’s kappa係數是用來分析兩個審查者對於類別項目評分的一致性。

Cohen’s kappa係數(Jacob Cohen, 1960)的公式如下：
其中Po為兩個審查者此次判定結果中相同的比例；Pe則為兩個審查者做獨立選擇時，做出相同判定的期望值。

舉例而言，A、B兩位檢驗員對100份產品的合格與否判斷如表1：A與B同時判定合格的有30份；A判定合格而B判定不合格的有10份；A判定不合格而B判定合格的有20份；A與B同時判定不合格的有45份。

則可計算出：

　一般將Kappa數值區分如下:

Kappa數值<0.4表示兩個審查者在資料判定上的一致性程度差
Kappa數值0.4~0.75表示兩個審查者在資料判定上的一致性程度一般
Kappa數值>0.75表示兩個審查者在資料判定上的一致性程度優良

[Reference 1](https://www.yongxi-stat.com/cohens-kappa/)

---
## 名字：瓈萱
### Hierarchical cluster analysis 層次聚類分析
* 定義：一種將資料分群的演算法，是一種非監督式學習的一種。

- 運作方式：一開始會將每筆資料視為獨立的一群(cluster)，之後兩兩相近的群會合併為更大的一群，這個模式會一直持續到所有群都合併為一大類。最後就會產出dendrogram 的結構（很像打比賽的賽程圖）
* 希望達到的目的：同一群裡面的個體差異越小越好，不同群跟不同群之間的差異越大越好

### optimal number of clusters 最佳分群數目
如何知道資料分成幾群是最好的？
* 可使用的方法：Elbow Method、gap statistic
* Elbow method 運作方式：找出一個數字x，讓資料分類的時候 群內的總差異最小，那個x就會是最佳分群數目

在圖中，x代表分群數目，y代表計算過後群內差異的值，轉折點（彎曲線）代表資料間的差異趨向穩定，所以轉折點的x值就代表最佳的分群數目。在這張圖中就是分群數為4是最佳分群處。

（有人說圖很像一個膝蓋 膝蓋彎曲處就是最佳分群處 但我看不太出來哪裡像膝蓋qq)

### Hopkins statistic
* 用法：用來評估一組資料之間分群是否是有意義，而不是用隨機分群的方法
（因為有時候就算資料之間沒有共通性，分群的方法還是會照樣把資料分成好幾群，所以用這個方法算出來的值就可以去評估這組資料分群的可能性）
* 目的：看資料是否是否符合均勻分布
* 結果代表：如果算出來的值結果H 結果會介於0～１。

### snowball principle 滾雪球抽樣
* 定義：一種非機率抽樣的方法
* 使用時機：樣本數比較特殊、難以取得的情況
* 方法：先找一批有符合要求特徵的樣本當作實驗對象，之後請他們提供認識的並且也符合特徵的人來做實驗，以此類推。（有點像直銷 一個拉一個 越拉越多）
### Gower distance
* 用來計算兩組資料的相近程度，測量值為0~1，數值越大代表差異性越大。

---
## 名字：予茜
### Hierarchical Cluster Analysis 階層式分析
**概念**：是資料分群的一種。其中一個方式是將距離最接近的樣本組成一群，一層層往上堆疊，直到所有的樣本被分在同一類，屬於由下而上；另一種方式是將所有的樣本逐次分裂，屬於由上而下的。屬於非監督式學習，也就是該分析沒有正確的答案可以參考。

**分析步驟**：
1.計算各樣本之間的距離
2.將距離(較相似)的樣本聚合在一起，變成一個新樣本的節點
3.重複步驟1和步驟2，直到所有的樣本被聚合在一起
4.依照距離切割，決定最後有幾個聚類

**四種定義距離的方式**：
1.single-linkage(單一連結)：從兩群之中分別選出使兩群的距離為最小的樣本為代表，以此兩點之間的距離代表群體的距離。


2.complete-linkage(完整連結)：從兩群中分別選出讓兩群的距離為最遠的樣本為代表，以此兩點之間的距離代表群體的距離。


3.average-linkage(平均連結)：計算兩個群所有的樣本之間的平均距離。


4.Ward's method(沃德法)：最小平方法。將兩群合併後，計算各樣本與合併後的群中心距離平方和。(群內的平方和距離小，群之間的距離較大)

不同的距離計算方式呈現出來的分類會不太一樣:


由上圖可以發現，single-linkage在群聚過程當中，較會顯現出單一個群體(單一一個顏色)，而 complete linkage 和 average linkage 較會顯現出不同的群聚結果。

**階層分析的優缺點**
優點：可以建構完整的樹狀分類，且計算距離時不需要樣本的實際座標。
缺點：只適用於少量的dataset，較難處理大量的資料。

[reference1 & pictures](https://pyecontech.com/2020/06/12/hierarchical_clustering/)
[reference2](https://mirlab.org/jang/books/dcpr/dcHierClustering.asp?title=3-2%20Hierarchical%20Clustering%20(%B6%A5%BCh%A6%A1%A4%C0%B8s%AAk)&language=chinese)

### Snowball sampling 滾雪球抽樣
是一種非隨機的抽樣方式。設計目的是要觀察母群中較難發現的隱藏資訊。樣本始於一個或少數人的個案，再根據初始個案的連結與下一個樣本逐漸擴展開來，像滾雪球一樣，越滾越多。

使用時機：適合觀察社區型的研究，即母群體中較難尋找或稀少的個案。

舉例：檢視社區中青少年的人際網路交友狀況。

優缺點：它讓研究員可接觸到那些可能很難通過其他方法識別或接觸到的人群。但它也可能存在偏見，因為個案通常是通過其他參與者的推薦而加入的，這可能導致樣本中可能存在某種類型的特定人群。

### Optimal number of clusters 分群的最佳數目。

前提:分群的目的是「使**群內**的總變異**最小**；使**群間**的總變異**最大**」(同一群裡的資料同質性高，不同群的資料同質性低。)

找出一個數字n，使資料被分成n群時，群內的總變異(SSE)會最小，那麼n就會是最佳的分群數目(optimal number for clusters)

這個方法，就是Elbow Method。是基於 SSE(誤差平方和）作為指標，計算每一個群中的每一個點，到該群的中心距離。

[reference](https://blog.v123582.tw/2019/01/20/K-means-怎麼選-K/)
[reference](https://rpubs.com/skydome20/R-Note9-Clustering)

### Hopkins statistic (H)
可以用來測量該資料庫的可聚集性(clusterability)
如果H值低於0.5，甚至接近於0，表示該資料庫具有可聚集性。

### Euclidean distance 歐式距離
用於評估k-means或kNN(?)。可用於任何空間的距離計算。

### Manhattan Distance 曼哈頓距離
適合計算水平或垂直距離，有維度的限制。

[reference3](https://yilishih.medium.com/機器學習-euclidean-distance歐氏距離-686ff7909dc0)

---
## 名字：植棻
### Hopkins statistic

用於計算一個資料集的 cluster tendency，也可說是資料集的 randomness。該計算用途是要判斷資料集是否適合進行集群分析，我們有兩個假設：

- **Null hypothesis**: 資料集均勻的分佈 → not clusterable
- **Alternative hypothesis**: 資料集不均勻的分佈 → clusterable

Hopkins statistic計算出來的數值介於0-1之間，取中間的0.5為分界

- H<0.5, close to 0 ⇒ reject the null hypothesis, **clusterable**
- H>0.5, close to 1 ⇒ not clusterable（就不用往下進行集群分析ㄌ）

[Reference](https://sushildeore99.medium.com/really-what-is-hopkins-statistic-bad1265df4b)

### Hierarchical Cluster Analysis

**Hierarchical clustering 階層式分群法**，有分為聚合、分裂兩種。是無標籤、無標準答案的非監督式學習法（Unsupervised Learning）

以聚合來解釋主要是用以下步驟來進行分群

1. 計算資料點之間的距離，距離可理解為資料點之間的相似度
2. 距離近的集合成群（物以類聚）變成新的的資料組合
3. 重複以上步驟，直到所有資料集成一大群
4. 切割組數

**優點：**
- 可以使用樹狀圖（Dendrogram）來呈現分群的過程，清楚易懂。
- 用資料點間的距離得到分群結果，不需標準答案。

**缺點：**
- 僅適合資料點較少的資料集，難以處理大量的資料，因為計算量會太過於龐大。

**Agglomerative 聚合：** 是一種 “ bottom-up” 的方法，將資料從自己獨立的個體慢慢聚合起來


**Divisive 分裂：** 是一種 “ top-down” 的方法，將資料集視為一個大的整體，再依照細節不同進行分裂


[Reference_1](https://medium.com/ai-academy-taiwan/clustering-method-4-ed927a5b4377)
[Reference_2](https://pyecontech.com/2020/06/12/hierarchical_clustering/)

---
## 名字：孟桁
### Clustered heatmap
Heatmaps are charts that depict values through a grid of colored squares by representing two variables across the two axes.
The clustered heatmap is a heatmap variation where clustering is applied as a part of the construction process. In a clustered heatmap, there are multiple variables on the horizontal axis instead of one, and the vertical axis represents individual observations of each variable. Dendrograms are depicted on the side of the chart to mark the clusters. This particular type of graph provides a means for associating potentially significant data points and relevant variables.
(If multiple variables are represented on both axes, the graph becomes a correlogram that shows the relationship between variables.)

### Cluster analysis
Cluster analysis is a term for the various techniques of grouping data for further analysis. Hierarchical cluster analysis (HCA) appears to be a common data classification method in linguistics. HCA gives a thorough calculation of possible clusters and doesn’t require the user defining clusters before running the analysis. However, this method is not ideal when there are too little data points and could be difficult to determine when the clustering is sufficient for further analysis. Other common cluster analysis algorithms include partition-based, density based, grid-based, model-based, and constraint-based. (Constraint-based algorithms state user’s preference of either grouping particular data together or separating particular data into different clusters.)

[Reference_1](https://www.atlassian.com/data/charts/heatmap-complete-guide)
[Reference_2](https://www.spotfire.com/glossary/what-is-cluster-analysis)

---

## 名字：喻璞
### Hierarchical cluster analysis (HCA) 階層式分群法

HCA透過不斷嘗試組合、分類資料集而建立出視覺化的樹狀的層次結構。
p.s. 缺點：只得到項目的結構/分類，而沒有深入了解是如何分組的。

建構HCA可採用兩種方法：
1. Agglomerative hierarchical clustering (AHC)
bottom-up approach，從個別資料開始慢慢合併其他資料，每次迭代(iteration)時將最近的兩個cluster合併為一個，直到所有資料合併成一個cluster。
而合併的方式有三種：
1. single-linkage agglomerative algorithm
2. complete-linkage agglomerative algorithm
3. average-linkage agglomerative algorithm

2. Divisive hierarchical clustering

top-down approach，將整體資料看成一個個體，每次迭代時選擇一個要分裂的cluster，然後慢慢細分成不同群體，直到最後每一群都只剩下一筆資料。

[Ref1](http://mirlab.org/jang/books/dcpr/dcHierClustering.asp?title=3-2%20Hierarchical%20Clustering%20(%B6%A5%BCh%A6%A1%A4%C0%B8s%AAk)&language=english) / [Ref2](https://tomohiroliu22.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-82-%E8%81%9A%E5%90%88%E5%BC%8F%E9%9A%8E%E5%B1%A4%E5%88%86%E7%BE%A4%E6%B3%95-agglomerative-hierarchical-clustering-5f064b996d20) / [Ref3](https://jamleecute.web.app/hierarchical-clustering-%E9%9A%8E%E5%B1%A4%E5%BC%8F%E5%88%86%E7%BE%A4/)

### dendrograms 樹狀結構圖
Dendrogram是一種樹狀圖，由多個節點組成，可用於資料集的分層(hierarchical)或聚類(clustering)。

[Ref6](https://r-graph-gallery.com/dendrogram.html) / [Ref7](https://bioinformatics.ccr.cancer.gov/docs/data-visualization-with-r/Lesson5_intro_to_ggplot/)

### Euclidean Distance Formula 歐式距離/歐幾里得距離
計算空間中，兩點之間的距離。是最常用也是最重要的距離計算法！
公式：

[Ref7](https://jamleecute.web.app/hierarchical-clustering-%E9%9A%8E%E5%B1%A4%E5%BC%8F%E5%88%86%E7%BE%A4/)
[Ref8](https://www.geeksforgeeks.org/how-to-calculate-euclidean-distance-in-excel/)

### dialect levelling 語言均一化
意指一個語言整體減少方言多樣性的過程。
如，方言的assimilation(同化)、mixture(混合)、merging(合併)，逐漸形成語言均一化的一種過程。

### koineization phenomena 共化現象
在sociolinguistics中，koineization 是指透過不同方言的混合、均衡和簡化而產生**新的語言變體**的過程，又稱dialect mixing(方言混合)或structural nativization(結構本土化)。

[Ref4](https://www.thoughtco.com/koineization-dialect-mixing-1691093)

### Snowball principle/ The snowball effect
滾雪球效應：重大變化是由最初的微小變化引起的。
- 滾雪球效應在社會學的解釋：
社會影響力，可以解釋少數人如何影響多數人。這是一個小群體影響較大群體的行為和信念的情況。

[Ref5](https://www.simplypsychology.org/snowball-effect.html)

---

<!-- ## tags, 拜託不要刪除以下 -->
###### tags: `QL2024`

<!-- ---

## 名字：
### 以下如果要用到標題請打三個以上的井字號 -->