This algorithm is the most optimal way to implement agglomerative clustering. It reduces the naive implementation's runtime O($n^3$) to O($n^2$). It is detailed below : 

1. Initalize all data points as Clusters
2. Initialize a stack K
3. While there are more than 1 clusters :
   a. If K is empty, add an arbitrary cluster to K
   b. Let A be K.top(). Find the cluster closest to A, say B.
   c. If B is already in K, it must have been added just before A (since it is closest to A). Thus, pop off A and B and merge them. 
   d. If B is not already in K, add it to K.


Nearest Neighbor Chain Algorithm

Goes over three distinct algorithms and discusses them in great detail : 
[arxiv.org/pdf/1109.2378.pdf](https://arxiv.org/pdf/1109.2378.pdf) 

Really Good Paper on Agglomerative Clustering Algorithms

1. Consider all data points to be their own cluster
2. Identify and merge pairs of clusters that are most similar
 3. Continue merging pairs until only one cluster remains

link: [towardsdatascience.com/understanding-the-concept-of-hierarchical-clustering-technique-c6e8243758ec](https://towardsdatascience.com/understanding-the-concept-of-hierarchical-clustering-technique-c6e8243758ec)  

University of Michigan - Ann Arbor

One cluster for each observation, then clusters are moved together as one moves up the hierarchy of clusters

Steps: 
1. Each data point is initially in its own cluster with one item 
2. Most similar cluster of each stage is merged 
3. Stopping measure: number of clusters 

Linkage criteria
- Ward's method
- least increase in total variance (around cluster centroids) 
2. Average linkage 
- average distance between clusters
3. Complete linkage 
- max distance between clusters




Agglomerative: Bottom-up approach

```Python
# imports
from sklearn.cluster import AgglomerativeClustering
import numpy as np

#create 100 samples with 10 features
X = np.random.rand(100,10)

# create model, then fit the data to the model, then generate clustering predictions
clustering = AgglomerativeClustering().fit_predict(X)

# show cluster labels for each sample
clustering
```


Python Code for Agglomerative Clustering

Medium: Agglomerative Hierarchical Clustering Algorithm

A really good paper that goes into the implementations of agglomerative clustering.
[arxiv.org/pdf/1109.2378.pdf](https://arxiv.org/pdf/1109.2378.pdf) 

Modern Heirarchical, agglomerative clustering methods

- Divisive Clustering takes into account the global distribution of data and so forms more accurate clusters ( i.e. doesn't get thrown off by local minima/maxima ) than Agglomerative Clustering.
- Agglomerative Clustering has O($n^2$) complexity in the most efficient implementation of the algorithm. Divisive Clustering is linear in the number of clusters.

Learn Before

Related

Learn After