---
title: "Short note: Partitioning and hierarchical clustering"
subject: "Data Mining"
chapter: 5
key: "semester_7/data_mining:partition-hierarchical-clustering-note"
source: https://www.bctengineer.com/q/semester_7/data_mining/partition-hierarchical-clustering-note
site: BCT Engineering
---

# Short note: Partitioning and hierarchical clustering

Data Mining · Chapter 5: Cluster Analysis

- Asked in: 2065 Baisakh
- Video: [Partitional Vs Hierarchical  Clustering in Machine Learning](https://www.youtube.com/watch?v=ISD8OvuQasY) — ThinkX Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/partition-hierarchical-clustering-note
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-5

## Question

Write a short note on Partitioning and Hierarchical Clustering.

## Short answer

Partitioning methods like k-means divide data into k clusters via iterative relocation; hierarchical builds a dendrogram by agglomeration or division. Partitioning needs k, is faster but may be a local optimum; hierarchical requires no k, O(n²), merges irreversible.

## Answer

#### Partitioning clustering
It divides n objects into **k non-overlapping groups** (k ≤ n), each with at least one object. An initial partition is created, then objects are moved between clusters again and again (**iterative relocation**) to improve an objective, such as minimum sum of squared distances to the cluster centres.
- **k-means**: the cluster centre is the mean.
- **k-medoids (PAM)**: the centre is an actual object (medoid), more robust to outliers.
- Needs k in advance; suits spherical clusters; efficient for large data (O(nkt)); may reach a local optimum.

#### Hierarchical clustering
It builds a hierarchy of clusters, drawn as a **dendrogram**, with no need to give k in advance (cut the dendrogram at the desired level).
- **Agglomerative (AGNES)**: bottom-up; start with each object as a cluster and repeatedly merge the two closest clusters.
- **Divisive (DIANA)**: top-down; start with one cluster and repeatedly split.
- Cluster distance: single link (minimum), complete link (maximum), average link, centroid.
- A merge or split cannot be undone; cost at least O(n²).

```text
 a b c d e          Agglomerative ->
 (a)(b)(c)(d)(e)  -> (ab)(c)(de) -> (abc)(de) -> (abcde)
                          <- Divisive
```

| Basis | Partitioning | Hierarchical |
| --- | --- | --- |
| Result | Flat k clusters | Tree of clusters |
| k | Needed | Not needed |
| Speed | Faster | Slower |
| Undo | Possible | Not possible |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does 'iterative relocation' mean in partitioning clustering?
   A. Objects are moved between clusters again and again to improve an objective
   B. Clusters are merged one pair at a time until one remains
   C. The dendrogram is cut at different heights
   D. Each object is copied into several clusters
   Answer: A. Partitioning starts with an initial partition and repeatedly moves objects between clusters to improve an objective such as minimum sum of squared distances. (Key point: Iterative relocation)

2. Why is k-medoids (PAM) more robust to outliers than k-means?
   A. It uses the mean of the cluster as the centre
   B. Its centre is an actual object (medoid), not an average pulled by extreme values
   C. It does not need k in advance
   D. It builds a dendrogram
   Answer: B. A medoid is a real object, so extreme values do not shift it the way they shift a mean. (Key point: k-medoids vs k-means)

3. How does hierarchical clustering give a desired number of clusters without k being specified in advance?
   A. By running k-means several times
   B. By moving objects between clusters
   C. By cutting the dendrogram at the desired level
   D. By choosing random centroids
   Answer: C. Hierarchical clustering builds a full tree; cutting it at a chosen level gives the required clusters. (Key point: Dendrogram and k)

4. Which statement about undoing steps is correct?
   A. Both methods can undo any step
   B. Hierarchical merges/splits cannot be undone, but partitioning can move objects between clusters
   C. Partitioning cannot undo, hierarchical can
   D. Neither has any steps to undo
   Answer: B. Partitioning relocates objects freely, whereas a hierarchical merge or split is final. (Key point: Undo in clustering)

## Related in Data Mining

- [Need of clustering; hierarchical vs partitioning; K-means](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Acluster-need-hier-vs-partition-kmeans) — Data Mining, chapter 5
- [Hierarchical clustering: AGNES and DIANA](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aagnes-diana) — Data Mining, chapter 5
- [Short note: Hierarchical clustering](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Ahierarchical-clustering-note) — Data Mining, chapter 5
- [Short note: Partitioning clustering](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Apartitioning-clustering-note) — Data Mining, chapter 5
- [Major clustering approaches](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aclustering-approaches) — Data Mining, chapter 5