Wiki

定义

层次聚类的策略一般分为两类

1. Agglomerative: This is "bottom-up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
   这是一种“自底向上”的方法：每个观测值都是单独的一个簇，并且当一个簇向上移动时，成对的簇被合并为一个簇。

2. Divisive: This is a "top-down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.
   这是一种“自顶向下”的方法：所有的观测都从一个簇开始，当一个观察向下移动时，递归地执行分裂为多个簇。

The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of \(O(n^3)\) and requires \(O(n^2)\) memory, which makes it too slow for even medium data sets.

标准的层次聚类算法（自底向上）需要\(O(n^3)\)的时间，\(O(n^2)\)的空间。

Metric

For text or other non-numeric data, metrics such as the Hamming distance or Levenshtein distance are often used.

对于文本或其他非数字数据，通常使用诸如Hamming距离或Levenshtein距离之类的度量。

Linkage criteria

链接标准用于确定两个观测集合之间的距离计算。

The linkage criterion determines the distance between sets of observations as a function of the pairwise distances between observations.

常见的链接标准有：

Example

Agglomerative clustering example

For example, suppose this data is to be clustered, and the Euclidean distance is the distance metric.

UPGMA

Wiki

UPGMA (unweighted pair group method with arithmetic mean) is a simple agglomerative (bottom-up) hierarchical clustering method.

UPGMA是一种简单的聚合型（自底向上）层次聚类方法。

算法步骤

第一步：

我们假设我们有5个元素，和他们两两之间距离矩阵。

在这个例子中，\(D_1 (a,b) = 17\)是最小的值，所以我们首先合并元素a和b。

• First branch length estimation

  第一次分支长度估算

  假设 \(u\) 当做连接a和b的节点，有\(\delta(a,u)=\delta(b,u)=D_1(a,b)/2=8.5\).

  因此连接a,b与 \(u\) 的分支长度为8.5

• First distance matrix update

  第一次距离矩阵更新

  \[D_2((a,b),c) = (D_1(a,c)+D_1(b,c))/2=25.5 \\ D_2((a,b),d) = (D_1(a,d)+D_1(b,d))/2=32.5 \\ D_2((a,b),e) = (D_1(a,e)+D_1(b,e))/2=22 \]

第二步：

更新之后的距离矩阵

(a,b) 与 e 的距离最小，所以合并这两个元素

• Second branch length estimation

  第二次分支长度估算

  假设 \(v\) 当做连接(a,b)和e的节点，有

  \(\delta(a,v)=\delta(b,v)=\delta(e,v)=D_2((a,b),e)/2=11\)

  \(\delta(u,v)=\delta(e,v)-\delta(a,u) = 11-8.5 = 2.5\)

  因此连接a,b与 \(u\) 的分支长度为8.5

• Second distance matrix update

  第二次距离矩阵更新

  \[D_3(((a,b),e),c) = (D_2((a,b),c)*2+D_2(e,c))/(2+1)=30 \\ D_3(((a,b),e),d) = (D_2((a,b),d)*2+D_2(e,d))/(2+1)=36 \]

第三步：

c和d的距离最小，合并cd

• Third branch length estimation

  第三次分支长度估算

  \(\delta(c,w)=\delta(d,w)=D_1(c,d)/2=14\)

• Third distance matrix update

  第三次距离矩阵更新

  \[D_4((c,d),((a,b),e)) = (D_3(c,((a,b),e))+D_3(d,((a,b),e)))/2=33 \]

第四步

直接合并两个节点

• 分支长度估算

最终生成的树

其中每个节点到根节点的距离是一样的。