Question

Machine Learning - clustering

Having generated a dendrogram, can we “prune” it?

Answer 1

Prune is a technique in machine learning that reduces the size of clustering trees by removing branches of the tree. Pruning reduces the complexity of clustering trees and improves predictive accuracy by the reduction of overtraining.

Clustering having generated a dendrogram We can Prune it based on top down or bottom up fashion. A top down pruning will traverse nodes from top level nodes to bottom level nodes and cuts subtrees starting at the root, while a bottom up pruning will traverse nodes from bottom level nodes to top level nodes and cuts subtrees start at the leaf nodes.

There are two popular pruning algorithms.

1. Reduced error pruning: Reduced error pruning start at the leaf nodes, each node is replaced with its most popular class. If the prediction accuracy is not done then the change is kept.
2. Cost complexity pruning: Cost complexity pruning generates a series of trees y₀ to y_n y₀ is the initial tree and y_n is the root tree. At step i, the tree is created by removing a subtree from tree i-1 and replacing it with a leaf node with value chosen as in the tree building algorithm.

The function prune(T,t) defines the tree obtained by pruning the subtrees ‘t’ from the tree ‘T’. Once the series of trees has been created, the best tree is chosen based accuracy as measured by a training set or cross-validation.

We can prune a Clustering tree having generated a dendrogram based on the labels:

example:

par(mfrow = c(1,2))
dend15 %>% set("labels_colors") %>% 
   plot(main = "main tree", ylim = c(0,4))
dend15 %>% set("labels_colors") %>%
   prune(c("1","5")) %>% 
   plot(main = "Prune tree", ylim = c(0,4))