--- title: "Need of clustering; hierarchical vs partitioning; K-means" subject: "Data Mining" chapter: 5 key: "semester_7/data_mining:cluster-need-hier-vs-partition-kmeans" source: https://www.bctengineer.com/q/semester_7/data_mining/cluster-need-hier-vs-partition-kmeans site: BCT Engineering --- # Need of clustering; hierarchical vs partitioning; K-means Data Mining · Chapter 5: Cluster Analysis - Asked in: 2063, 2+10 marks - Video: [#24 Partitioning Clustering - K Means Algorithm |DM|](https://www.youtube.com/watch?v=190xjQHVdrE) — Trouble- Free - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/data_mining/cluster-need-hier-vs-partition-kmeans - Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-5 ## Question Why do we need cluster analysis? Differentiate between hierarchical and partitioning clustering technique. Identify the cluster of the following instances using K-Means clustering algorithm. | Instance | X | Y | | --- | --- | --- | | 1 | 1.0 | 1.5 | | 2 | 2.5 | 5.5 | | 3 | 1.5 | 1.0 | | 4 | 2.0 | 3.0 | | 5 | 2.5 | 3.5 | | 6 | 4.0 | 6.2 | ## Short answer Clustering discovers natural groups; hierarchical builds a tree without k, partitioning needs k. With initial centroids (1,1.5) and (2.5,5.5), final clusters: {1,3,4} centroid (1.50,1.83) and {2,5,6} centroid (3.00,5.07). ## Answer #### Need for cluster analysis **Cluster analysis** groups unlabelled objects so that objects in a cluster are similar and those in different clusters are dissimilar. It is needed because: - Large data sets have **no class labels**; clustering discovers natural groups and the structure of the data (e.g. customer segments for marketing). - It **summarises and compresses** data: each cluster can be represented by its centre. - It is a **preprocessing step** for other methods and helps detect **outliers** (objects far from every cluster). - Applications: image segmentation, document grouping, biology (gene groups), city planning, fraud detection. #### Hierarchical vs partitioning clustering | Basis | Hierarchical | Partitioning | | --- | --- | --- | | Output | Tree of nested clusters (dendrogram) | One flat set of k clusters | | k required? | No; cut the dendrogram at a level | Yes, given in advance | | Approach | Agglomerative (bottom-up) / divisive (top-down) | Iterative relocation of objects (k-means, k-medoids) | | Undo steps | A merge or split cannot be undone | Objects can move between clusters | | Complexity | At least O(n²), not for very large data | O(nkt), scalable | | Shape | Can find non-spherical clusters (single link) | Spherical, similar sized | | Examples | AGNES, DIANA, BIRCH | k-means, PAM | #### K-means on the data (K = 2) | Instance | X | Y | | --- | --- | --- | | 1 | 1.0 | 1.5 | | 2 | 2.5 | 5.5 | | 3 | 1.5 | 1.0 | | 4 | 2.0 | 3.0 | | 5 | 2.5 | 3.5 | | 6 | 4.0 | 6.2 | **Assumption**: K = 2, and the first two instances are the initial centroids: C1 = (1.0, 1.5) and C2 = (2.5, 5.5). Euclidean distance d = √[(x − cx)² + (y − cy)²]. **Iteration 1** (centroids C1 = (1.0, 1.5), C2 = (2.5, 5.5)) | Instance | (X, Y) | d to C1 | d to C2 | Cluster | | --- | --- | --- | --- | --- | | 1 | (1.0, 1.5) | 0.00 | 4.27 | C1 | | 2 | (2.5, 5.5) | 4.27 | 0.00 | C2 | | 3 | (1.5, 1.0) | 0.71 | 4.61 | C1 | | 4 | (2.0, 3.0) | 1.80 | 2.55 | C1 | | 5 | (2.5, 3.5) | 2.50 | 2.00 | C2 | | 6 | (4.0, 6.2) | 5.58 | 1.66 | C2 | Clusters: C1 = {1, 3, 4}, C2 = {2, 5, 6}. New centroids: C1 = ((1.0 + 1.5 + 2.0)/3, (1.5 + 1.0 + 3.0)/3) = **(1.50, 1.83)**; C2 = ((2.5 + 2.5 + 4.0)/3, (5.5 + 3.5 + 6.2)/3) = **(3.00, 5.07)**. **Iteration 2** (centroids C1 = (1.50, 1.83), C2 = (3.00, 5.07)) | Instance | d to C1 | d to C2 | Cluster | | --- | --- | --- | --- | | 1 | 0.60 | 4.09 | C1 | | 2 | 3.80 | 0.66 | C2 | | 3 | 0.83 | 4.33 | C1 | | 4 | 1.27 | 2.30 | C1 | | 5 | 1.94 | 1.64 | C2 | | 6 | 5.03 | 1.51 | C2 | The assignment is unchanged, so the algorithm has converged (the centroids would stay the same). **Answer: Cluster 1 = {instances 1, 3, 4} with centroid (1.50, 1.83); Cluster 2 = {instances 2, 5, 6} with centroid (3.00, 5.07).** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why is cluster analysis needed? A. Data has no class labels and clustering discovers natural groups B. It predicts class labels from labelled data C. It removes all outliers D. It sorts data Answer: A. Clustering is unsupervised. (Key point: Need) 2. Which is true of hierarchical clustering? A. It produces one flat set of k clusters B. Produces nested clusters (dendrogram) and k is not required in advance C. Merges can be undone D. Complexity is O(nkt) Answer: B. Partitioning needs k and allows moves between clusters. (Key point: Hierarchical vs partitioning) 3. Which clusters are formed with initial centroids (1.0,1.5) and (2.5,5.5)? A. C1 = {1, 3}, C2 = {2, 4, 5, 6} B. C1 = {1, 3, 4, 5}, C2 = {2, 6} C. C1 = {1, 3, 4}, C2 = {2, 5, 6} D. C1 = {1}, C2 = {2, 3, 4, 5, 6} Answer: C. Instance 5 is closer to C2 (2.00 vs 2.50). (Key point: Iteration 1) 4. What is the new centroid of C2 = {2, 5, 6}? A. (2.5, 5.5) B. (3.00, 3.50) C. (1.50, 1.83) D. (3.00, 5.07) Answer: D. x = (2.5+2.5+4)/3 = 3.0; y = (5.5+3.5+6.2)/3 = 5.07. (Key point: New centroid) ## Related in Data Mining - [Cluster analysis; K-means on height/width](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Akmeans-height-width) — Data Mining, chapter 5 - [K-means on six 2-D instances (K=2)](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Akmeans-x-y-k2) — Data Mining, chapter 5 - [Short note: Partitioning and hierarchical clustering](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Apartition-hierarchical-clustering-note) — Data Mining, chapter 5 - [Cluster analysis applications; K-means](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Acluster-application-kmeans) — Data Mining, chapter 5 - [K-means on six 2-D instances (B65)](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Akmeans-b65) — Data Mining, chapter 5 - [Clustering, need and qualities](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aclustering-define-qualities) — Data Mining, chapter 5 ## Related in other subjects - [Why do we need DFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Awhy-need-dft) — Digital Signal Analysis and Processing, chapter 7, asked 6× - [Why do we need FFT](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Awhy-need-fft) — Digital Signal Analysis and Processing, chapter 7, asked 2× - [Need for equalization and basic technique](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aequalization-need-basic) — Wireless Communication, chapter 5 - [Need of energy audit and technique](https://www.bctengineer.com/question.md?key=semester_6%2Findustrial_power_distribution_and_illumination%3Aenergy-audit-need-technique) — Industrial Power Distribution and Illumination, chapter 10, asked 3×