---
title: "Short note: K-means clustering"
subject: "Data Mining"
chapter: 5
key: "semester_7/data_mining:kmeans-note"
source: https://www.bctengineer.com/q/semester_7/data_mining/kmeans-note
site: BCT Engineering
---

# Short note: K-means clustering

Data Mining · Chapter 5: Cluster Analysis

- Asked in: 2066 Bhadra, 3 marks
- Video: [K Means Clustering Algorithm | K Means Solved Numerical Example Euclidean Distance by Mahesh Huddar](https://www.youtube.com/watch?v=KzJORp8bgqs) — Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/kmeans-note
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-5

## Question

Write a short note on K-Means Clustering.

## Short answer

K-means minimizes sum of squared errors by iteratively assigning points to nearest centroid (Euclidean) and recomputing centroids as means. It is O(nkt), requires pre-specified k, sensitive to initial centroids and outliers, and finds spherical clusters.

## Answer

**K-means** is the most popular **partitioning** clustering algorithm. It divides n objects into **k clusters** so that each object belongs to the cluster with the nearest mean (the **centroid**), and the **sum of squared errors** SSE = Σᵢ Σ_{x∈Cᵢ} ‖x − cᵢ‖² is minimised.

#### Algorithm
```text
1. Choose k and select k initial centroids (random objects).
2. Repeat
   a. Assign each object to the nearest centroid
      (Euclidean distance) -> k clusters.
   b. Recompute each centroid as the mean of its cluster.
3. Until no object changes cluster (centroids stable).
```

#### Example
Points 1, 2, 9, 10, with k = 2 and initial centroids 1 and 2. Iteration 1: clusters {1} and {2, 9, 10}, so the new centroids are 1 and 7. Iteration 2: point 2 moves to the first cluster, giving {1, 2} and {9, 10} with centroids 1.5 and 9.5. Iteration 3 changes nothing, so these are the final clusters.

#### Features
- Simple and fast: complexity O(n·k·t) for t iterations, and t is usually small.
- Needs k in advance; depends on the initial centroids; converges to a local optimum (so it is run several times).
- Sensitive to noise and outliers because the mean is used; finds convex, spherical clusters of similar size; works only on numeric data.

## Check yourself

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

1. What does K-means minimise?
   A. The sum of squared errors from each object to its cluster centroid
   B. The number of clusters
   C. The distance between centroids
   D. The number of iterations only
   Answer: A. SSE = sum of squared distances to centroids. (Key point: Objective)

2. How is a centroid recomputed?
   A. As the median
   B. As the mean of the objects in its cluster
   C. As the farthest point
   D. As a random member
   Answer: B. K-means uses the mean. (Key point: Update step)

3. Why is K-means sensitive to outliers?
   A. Because it uses hierarchical merging
   B. Because it needs no k
   C. Because the mean is used for centroids
   D. Because it uses density
   Answer: C. A far point pulls the mean toward it. (Key point: Limitations)

4. Which is a feature of K-means?
   A. Finds clusters of any shape
   B. Works with categorical data directly
   C. Always finds the global optimum
   D. Needs k in advance and depends on initial centroids
   Answer: D. It converges to a local optimum, so it is run several times. (Key point: Requirement)

## 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
- [Likelihood and distance; K-means drawbacks](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Alikelihood-distance-clustering-kmeans-drawbacks) — Data Mining, chapter 3
- [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
- [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 strengths and weaknesses](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Akmeans-strengths-weaknesses) — Data Mining, chapter 5