k-means编辑历史

# k-means

## 1 Introduction

### 1.1 Definition and purpose
**k-means** is a centroid-based unsupervised learning algorithm that partitions a dataset of \( n \) observations into \( k \) distinct clusters. Each observation is assigned to the cluster whose mean (centroid) is nearest, using a distance metric—typically Euclidean distance. The algorithm’s primary goal is to minimize the within-cluster sum of squares (WCSS), a measure of intra-cluster variance. By grouping similar data points, k-means serves as a tool for exploratory data analysis, pattern recognition, and data compression.

### 1.2 Historical context
The k-means concept was independently proposed in the 1950s and 1960s. The term "k-means" was first used by James MacQueen in 1967, though earlier formulations (e.g., Lloyd’s algorithm in 1957 for pulse-code modulation) laid the groundwork. The algorithm became widely used in statistics and computer science due to its simplicity and speed, later spawning numerous variants to address its inherent limitations.

## 2 Algorithm details

### 2.1 Steps of the standard algorithm

#### 2.1.1 Initialization
The algorithm begins by selecting \( k \) initial centroids, one per cluster. The choice of initial centroids significantly affects the final clustering.

##### 2.1.1.1 Random initialization
A straightforward approach is to randomly pick \( k \) distinct observations from the dataset as initial centroids. This method is simple but can lead to suboptimal results if the selected points are close together or lie in low-density regions.

##### 2.1.1.2 Forgy method and MacQueen method
- **Forgy method** (1965): Randomly selects \( k \) observations as centroids, ensuring they are often distinct and spread across the data space.
- **MacQueen method** (1967): Assigns each observation to one of \( k \) initially random centroids, then updates centroids incrementally after each assignment. This approach is more dynamic but can be sensitive to the order of points.