Python中怎么实现一个Kmeans均值聚类算法

# Python中怎么实现一个Kmeans均值聚类算法

## 一、Kmeans算法简介

K-means算法是一种经典的**无监督学习**聚类方法，由J.B. MacQueen在1967年提出。其核心思想是通过迭代将数据点划分为K个簇，使得每个数据点都属于离它最近的均值（质心）对应的簇。

### 算法核心特点
- **距离度量**：通常采用欧氏距离
- **需要预先指定K值**：即要形成的簇数量
- **迭代优化**：通过不断更新质心位置最小化簇内平方和
- **收敛性**：算法最终会收敛（但可能陷入局部最优）

## 二、算法实现步骤

### 1. 初始化阶段
随机选择K个数据点作为初始质心

```python
def initialize_centroids(X, k):
    """随机初始化质心"""
    indices = np.random.choice(len(X), k, replace=False)
    return X[indices]

2. 分配阶段

将每个数据点分配到最近的质心所在的簇

def assign_clusters(X, centroids):
    """分配数据点到最近的质心"""
    distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2)
    return np.argmin(distances, axis=0)

3. 更新阶段

重新计算每个簇的质心位置

def update_centroids(X, labels, k):
    """更新质心位置"""
    return np.array([X[labels == i].mean(axis=0) for i in range(k)])

4. 收敛判断

当质心不再变化或达到最大迭代次数时停止

def k_means(X, k, max_iters=100):
    centroids = initialize_centroids(X, k)
    for _ in range(max_iters):
        labels = assign_clusters(X, centroids)
        new_centroids = update_centroids(X, labels, k)
        if np.all(centroids == new_centroids):
            break
        centroids = new_centroids
    return labels, centroids

三、完整Python实现

import numpy as np
import matplotlib.pyplot as plt

class KMeans:
    def __init__(self, k=3, max_iters=100):
        self.k = k
        self.max_iters = max_iters
        self.centroids = None
    
    def _initialize_centroids(self, X):
        indices = np.random.choice(len(X), self.k, replace=False)
        return X[indices]
    
    def _assign_clusters(self, X):
        distances = np.sqrt(((X - self.centroids[:, np.newaxis])**2).sum(axis=2)
        return np.argmin(distances, axis=0)
    
    def _update_centroids(self, X, labels):
        return np.array([X[labels == i].mean(axis=0) for i in range(self.k)])
    
    def fit(self, X):
        self.centroids = self._initialize_centroids(X)
        for _ in range(self.max_iters):
            labels = self._assign_clusters(X)
            new_centroids = self._update_centroids(X, labels)
            if np.all(self.centroids == new_centroids):
                break
            self.centroids = new_centroids
        return labels
    
    def predict(self, X):
        return self._assign_clusters(X)

四、算法优化与改进

1. K-means++初始化

改进初始质心选择，降低陷入局部最优的概率

def initialize_centroids_pp(X, k):
    """K-means++初始化"""
    centroids = [X[np.random.randint(len(X))]]
    for _ in range(1, k):
        distances = np.array([min([np.linalg.norm(x-c)**2 for c in centroids]) for x in X])
        probabilities = distances / distances.sum()
        centroids.append(X[np.random.choice(len(X), p=probabilities)])
    return np.array(centroids)

2. Elbow方法确定最佳K值

通过寻找拐点确定最优簇数量

def find_optimal_k(X, max_k=10):
    distortions = []
    for k in range(1, max_k+1):
        km = KMeans(k=k)
        labels = km.fit(X)
        distortion = sum(np.min(cdist(X, km.centroids, 'euclidean'), axis=1)) / X.shape[0]
        distortions.append(distortion)
    
    # 绘制肘部曲线
    plt.plot(range(1, max_k+1), distortions, 'bx-')
    plt.xlabel('k')
    plt.ylabel('Distortion')
    plt.title('The Elbow Method')
    plt.show()

五、实际应用示例

1. 数据集准备

使用sklearn的make_blobs生成测试数据

from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
plt.scatter(X[:,0], X[:,1], s=50)

2. 聚类可视化

def plot_kmeans(X, k=3):
    km = KMeans(k=k)
    labels = km.fit(X)
    
    plt.scatter(X[:,0], X[:,1], c=labels, s=50, cmap='viridis')
    plt.scatter(km.centroids[:,0], km.centroids[:,1], c='red', s=200, alpha=0.8)
    plt.title(f'K-means Clustering (k={k})')
    plt.show()

plot_kmeans(X, k=4)

3. 与sklearn实现对比

from sklearn.cluster import KMeans as SKLearnKMeans

sk_kmeans = SKLearnKMeans(n_clusters=4)
sk_labels = sk_kmeans.fit_predict(X)

plt.scatter(X[:,0], X[:,1], c=sk_labels, s=50, cmap='viridis')
plt.scatter(sk_kmeans.cluster_centers_[:,0], sk_kmeans.cluster_centers_[:,1], 
            c='red', s=200, alpha=0.8)
plt.title('Sklearn K-means Implementation')
plt.show()

六、算法局限性及解决方案

1. 主要局限性

• 对初始质心敏感
• 需要预先指定K值
• 对异常值敏感
• 只适用于凸形数据分布

2. 常见解决方案

七、性能优化技巧

1. 向量化计算：利用NumPy广播机制
2. 提前终止：设置收敛阈值
3. 并行计算：对大数据集使用Mini-Batch K-means
4. 降维处理：对高维数据先进行PCA降维

# Mini-Batch K-means示例
from sklearn.cluster import MiniBatchKMeans

mbk = MiniBatchKMeans(n_clusters=4, batch_size=100)
mbk.fit(X)

八、总结

本文详细实现了K-means算法并讨论了： - 基础算法原理和实现步骤 - Python完整实现代码 - 常见优化方法 - 实际应用示例 - 算法局限性和解决方案

K-means因其简单高效，在客户分群、图像分割、异常检测等领域有广泛应用。理解其核心实现有助于更好地应用和调优这一经典算法。

延伸阅读： - Scikit-learn官方文档 - 《机器学习实战》Peter Harrington - 论文：k-means++: The Advantages of Careful Seeding “`

文章总计约2300字，包含： 1. 算法原理说明 2. 分步骤代码实现 3. 完整类封装 4. 优化方法和实际应用 5. 可视化示例 6. 性能讨论 7. 格式化的代码块和表格 8. 延伸学习资源