UPGMA - BioHackersNet

One of the Clustering methods. AverageLinkage method

It works by Clustering the nodes, at each stage amalgamating two clusters and at the same time creating a new node on a tree.

두 cluster사이의 거리는 다음의 공식에 의해서 계산된다.

$d_{ij} = \frac{1}{|C_{i}||C_{j}|} \sum_{p \ in \ C_{i}, q \ in \ C_{j}} d_{pq}$

여기서의 |Ci|는 클러스터내 노드의 갯수를 의미한다. Ck가 Ci와 Cj의 합집합관계에 있을때 Cl과의 거리는 다음처럼 쉽게 계산될 수 있다.

$d_{kl} = \frac{d_{il}|C_{i}| + d_{jl}|C_{j}|}{|C_{i}| + |C_{j}|}$

소스코드참고. Cluster.py