深入理解 KMeans 聚類算法：原理、實現與應用

在機器學習領域，聚類算法作為無監督學習的核心技術之一，一直以來都是數據挖掘和模式識別的重要工具。其中，KMeans 算法以其簡潔的原理、高效的計算性能和廣泛的適用性，成為最受歡迎的聚類算法之一。本文將從算法原理、數學推導、實現細節到實際應用，全方位解析 KMeans 算法，并通過完整的代碼案例幫助讀者深入理解其工作機制。

一、聚類算法與 KMeans 的定位

聚類算法的核心目標是將數據集中具有相似特征的樣本自動劃分到同一類別，使得類內相似度最大化且類間相似度最小化。與監督學習不同，聚類不需要預先標注的訓練數據，而是通過數據本身的分布特征發現潛在的結構模式。這種特性使其在客戶分群、異常檢測、圖像分割等無標簽數據場景中發揮著不可替代的作用。

在眾多聚類算法中，KMeans 占據著舉足輕重的地位。自 1967 年由 MacQueen 提出以來，經過半個多世紀的發展，其衍生出了 KMeans++、MiniBatchKMeans 等改進版本，但核心思想始終保持一致。據 KDnuggets 2023 年的調研數據顯示，KMeans 在工業界的使用率高達 68%，遠超層次聚類（23%）和 DBSCAN（19%）等其他算法，這與其簡單易懂、計算高效、可擴展性強的特點密不可分。

二、KMeans 算法的核心原理

2.1 基本思想

KMeans 算法的工作流程可以概括為 "初始化 - 分配 - 更新" 的迭代過程：

1. 確定聚類數量 K：用戶需要預先指定將數據劃分為 K 個類別

1. 初始化質心：從數據集中隨機選擇 K 個樣本作為初始聚類中心（質心）

1. 分配樣本：計算每個樣本與 K 個質心的距離，將樣本分配到距離最近的質心所在的簇

1. 更新質心：計算每個簇內所有樣本的均值，將其作為新的質心

1. 迭代優化：重復步驟 3 和 4，直到質心位置不再顯著變化或達到最大迭代次數

這種基于原型的聚類方法通過不斷調整質心位置，最終使得各樣本到其所屬質心的距離之和最小化。

2.2 距離度量方式

KMeans 算法的性能很大程度上依賴于距離度量的選擇，常用的距離計算方式包括：

1. 歐氏距離（Euclidean Distance）：最常用的距離度量方式，適用于連續型數據，計算兩個 n 維向量\(X=(x_1,x_2,...,x_n)\)和\(Y=(y_1,y_2,...,y_n)\)之間的直線距離：

\(d(X,Y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}\)

1. 曼哈頓距離（Manhattan Distance）：適用于高維數據或需要降低計算復雜度的場景，計算各維度差值的絕對值之和：

\(d(X,Y)=\sum_{i=1}^{n}|x_i-y_i|\)

1. 余弦相似度（Cosine Similarity）：常用于文本聚類等特征向量稀疏的場景，通過向量夾角的余弦值衡量相似度：

\(cos\theta=\frac{X\cdot Y}{||X||\cdot||Y||}=\frac{\sum_{i=1}^{n}x_iy_i}{\sqrt{\sum_{i=1}^{n}x_i^2}\sqrt{\sum_{i=1}^{n}y_i^2}}\)

在默認情況下，KMeans 算法采用歐氏距離作為度量標準，這也是大多數場景下的最優選擇。

2.3 目標函數與收斂性

KMeans 算法的優化目標是最小化所有樣本到其所屬質心的距離平方和（Sum of Squared Errors，SSE），目標函數定義為：

\(J=\sum_{k=1}^{K}\sum_{x_i\in C_k}||x_i-\mu_k||^2\)

其中，\(C_k\)表示第 k 個簇，\(\mu_k\)是第 k 個簇的質心，\(||x_i-\mu_k||^2\)是樣本\(x_i\)到質心\(\mu_k\)的歐氏距離平方。

由于目標函數\(J\)是非凸函數，算法可能收斂到局部最優解而非全局最優解。這也是為什么 KMeans 算法通常需要多次運行并選擇 SSE 最小的結果作為最終聚類方案的原因。理論上，隨著迭代次數的增加，\(J\)的值會單調遞減并最終收斂，因為每次更新質心時都會選擇使\(J\)最小化的新質心位置。

三、KMeans 算法的優缺點分析

3.1 優點

1. 計算效率高：時間復雜度約為\(O(nkt)\)，其中 n 是樣本數量，k 是聚類數，t 是迭代次數，通常遠小于 n，適合大規模數據集

1. 實現簡單：核心邏輯僅包含距離計算和均值更新，易于理解和實現

1. 可擴展性強：能夠處理百萬級甚至更大規模的數據集，通過 MiniBatch 等變體可進一步提升處理速度

1. 結果易于解釋：聚類中心具有明確的物理意義（簇內樣本的均值），便于后續分析

3.2 缺點

1. 需要預先指定 K 值：K 值的選擇對聚類結果影響巨大，而在實際應用中往往難以確定最優 K 值

1. 對初始質心敏感：不同的初始質心可能導致完全不同的聚類結果，容易陷入局部最優

1. 對噪聲和異常值敏感：異常值會顯著影響質心的計算，導致聚類偏差

1. 難以處理非凸形狀簇：對于呈環形、條形等復雜分布的數據，聚類效果較差

1. 對特征尺度敏感：不同量級的特征會主導距離計算，需要預先進行標準化處理

3.3 改進版本

針對上述缺點，研究者們提出了多種改進算法：

• KMeans++：通過改進初始質心的選擇方式（使初始質心盡可能遠離），提高了算法收斂到全局最優的概率

• MiniBatchKMeans：使用隨機抽樣的小批量數據更新質心，大幅提升處理大規模數據的效率

• ISODATA：能夠自動調整聚類數量，通過合并和分裂操作優化聚類結果

• Kernel KMeans：通過核函數將數據映射到高維空間，解決非凸形狀簇的聚類問題

四、K 值的確定方法

K 值的選擇是 KMeans 算法應用中的關鍵難題，以下是幾種常用的確定方法：

4.1 肘部法（Elbow Method）

肘部法通過繪制不同 K 值對應的 SSE 曲線，選擇曲線開始趨于平緩的 "肘部" 位置對應的 K 值作為最優解。當 K 值較小時，隨著 K 的增加，SSE 會急劇下降；當 K 值超過某個臨界點后，SSE 的下降速度明顯放緩，此時再增加 K 值對聚類效果的提升有限，該臨界點即為最優 K 值。

4.2 輪廓系數法（Silhouette Score）

輪廓系數綜合考慮了樣本的類內相似度和類間相似度，取值范圍為 [-1,1]。對于每個樣本 i，計算：

• \(a_i\)：樣本 i 與其同簇內其他樣本的平均距離（類內不相似度）

• \(b_i\)：樣本 i 與最近異簇內所有樣本的平均距離（類間不相似度）

樣本 i 的輪廓系數為：\(s_i=\frac{b_i-a_i}{max(a_i,b_i)}\)

整體數據集的輪廓系數為所有樣本輪廓系數的平均值，越接近 1 表示聚類效果越好。通過計算不同 K 值對應的輪廓系數，選擇系數最大的 K 值作為最優解。

4.3 Gap 統計量（Gap Statistic）

Gap 統計量通過比較實際數據的聚類效果與參考數據（通常是隨機生成的均勻分布數據）的聚類效果來確定最優 K 值。定義為：

\(Gap(k)=E[log(D_k)]-log(D_k)\)

其中\(D_k\)是實際數據的聚類分散度，\(E[log(D_k)]\)是參考數據的期望分散度。當 Gap 統計量趨于穩定時的 K 值即為最優解。

五、KMeans 算法的實現步驟

5.1 數據預處理

在應用 KMeans 算法前，需要對數據進行必要的預處理：

1. 缺失值處理：通過均值填充、中位數填充或插值法處理缺失數據

1. 標準化 / 歸一化：由于 KMeans 對特征尺度敏感，需將數據轉換到相同量級，常用方法包括：

• • 標準化：\(x'=\frac{x-\mu}{\sigma}\)（均值為 0，標準差為 1）

• • 歸一化：\(x'=\frac{x-min}{max-min}\)（映射到 [0,1] 區間）

1. 異常值檢測：使用 Z-score、IQR 等方法識別并處理異常值，避免其影響聚類中心

5.2 算法實現流程

以下是 KMeans 算法的詳細實現步驟：

1. 初始化參數：設置聚類數量 K、最大迭代次數、收斂閾值等

1. 選擇初始質心：

• • 隨機選擇 K 個樣本作為初始質心（傳統方法）

• • 采用 KMeans++ 策略選擇初始質心（改進方法）

1. 分配樣本到最近簇：

• • 計算每個樣本與所有質心的距離

• • 將樣本分配到距離最近的質心所在簇

1. 更新質心位置：

• • 計算每個簇內所有樣本的均值

• • 將均值作為新的質心位置

1. 檢查收斂條件：

• • 若質心位置變化小于收斂閾值，或達到最大迭代次數，則停止迭代

• • 否則返回步驟 3 繼續迭代

1. 輸出結果：返回最終的聚類標簽和質心位置

六、完整代碼案例與解析

下面將通過 Python 實現 KMeans 算法，并使用真實數據集進行聚類分析。我們將分別展示使用自定義實現和 Scikit-learn 庫的兩種方式，以便讀者更好地理解算法細節。

6.1 自定義 KMeans 實現

首先，我們手動實現 KMeans 算法的核心邏輯，包括距離計算、質心更新和迭代優化等步驟：

import numpy as np

import matplotlib.pyplot as plt

from sklearn.datasets import make_blobs

from sklearn.metrics import silhouette_score

from sklearn.preprocessing import StandardScaler

class CustomKMeans:

def __init__(self, n_clusters=2, max_iter=100, tol=1e-4, random_state=None):

"""

初始化KMeans模型

參數:

n_clusters: 聚類數量

max_iter: 最大迭代次數

tol: 收斂閾值，當質心變化小于該值時停止迭代

random_state: 隨機數種子，保證結果可復現

"""

self.n_clusters = n_clusters

self.max_iter = max_iter

self.tol = tol

self.random_state = random_state

self.centroids_ = None # 質心

self.labels_ = None # 聚類標簽

self.inertia_ = None # SSE值

def _euclidean_distance(self, X, centroids):

"""計算樣本與質心之間的歐氏距離"""

distances = []

for centroid in centroids:

# 計算每個樣本到當前質心的距離

dist = np.sqrt(np.sum((X - centroid) ** 2, axis=1))

distances.append(dist)

# 轉換為形狀為(n_samples, n_clusters)的數組

return np.array(distances).T

def _initialize_centroids(self, X):

"""隨機選擇K個樣本作為初始質心"""

np.random.seed(self.random_state)

# 從數據集中隨機選擇K個不同的樣本索引

indices = np.random.choice(X.shape[0], self.n_clusters, replace=False)

return X[indices]

def fit(self, X):

"""訓練KMeans模型"""

# 初始化質心

self.centroids_ = self._initialize_centroids(X)

for _ in range(self.max_iter):

# 計算每個樣本到各質心的距離

distances = self._euclidean_distance(X, self.centroids_)

# 為每個樣本分配最近的簇

self.labels_ = np.argmin(distances, axis=1)

# 計算新的質心

new_centroids = np.array([X[self.labels_ == k].mean(axis=0)

for k in range(self.n_clusters)])

# 計算質心變化量

centroid_shift = np.sum(np.sqrt(np.sum((new_centroids - self.centroids_) **2, axis=1)))

# 更新質心

self.centroids_ = new_centroids

# 檢查是否收斂

if centroid_shift < self.tol:

break

# 計算最終的SSE

self.inertia_ = np.sum([np.sum((X[self.labels_ == k] - self.centroids_[k])** 2)

for k in range(self.n_clusters)])

return self

def predict(self, X):

"""預測新樣本的聚類標簽"""

distances = self._euclidean_distance(X, self.centroids_)

return np.argmin(distances, axis=1)

# 生成測試數據

X, y_true = make_blobs(n_samples=500, centers=4, cluster_std=0.60, random_state=0)

# 數據標準化

scaler = StandardScaler()

X_scaled = scaler.fit_transform(X)

# 測試自定義KMeans

custom_kmeans = CustomKMeans(n_clusters=4, max_iter=100, random_state=42)

custom_kmeans.fit(X_scaled)

custom_labels = custom_kmeans.labels_

custom_centroids = custom_kmeans.centroids_

# 計算輪廓系數

silhouette_avg = silhouette_score(X_scaled, custom_labels)

print(f"自定義KMeans的輪廓系數: {silhouette_avg:.4f}")

print(f"自定義KMeans的SSE值: {custom_kmeans.inertia_:.4f}")

# 可視化聚類結果

plt.figure(figsize=(10, 6))

plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=custom_labels, s=50, cmap='viridis')

plt.scatter(custom_centroids[:, 0], custom_centroids[:, 1], s=200, marker='X',

c='red', label='質心')

plt.title('自定義KMeans聚類結果', fontsize=15)

plt.xlabel('特征1', fontsize=12)

plt.ylabel('特征2', fontsize=12)

plt.legend()

plt.grid(True, linestyle='--', alpha=0.7)

plt.show()

6.2 使用 Scikit-learn 實現 KMeans

Scikit-learn 庫提供了高效的 KMeans 實現，包含了 KMeans++ 初始化等優化特性，實際應用中推薦使用：

from sklearn.cluster import KMeans

from sklearn.datasets import load_iris, make_moons, make_circles

from sklearn.model_selection import train_test_split

from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score

import seaborn as sns

# 1. 測試經典數據集

iris = load_iris()

X_iris = iris.data

y_iris = iris.target

# 數據標準化

X_iris_scaled = StandardScaler().fit_transform(X_iris)

# 使用KMeans++初始化

kmeans_iris = KMeans(n_clusters=3, init='k-means++', n_init=10,

max_iter=300, random_state=42)

kmeans_iris.fit(X_iris_scaled)

iris_labels = kmeans_iris.labels_

# 評估聚類效果（已知真實標簽時）

ari = adjusted_rand_score(y_iris, iris_labels)

nmi = normalized_mutual_info_score(y_iris, iris_labels)

print(f"鳶尾花數據集的調整蘭德指數: {ari:.4f}")

print(f"鳶尾花數據集的標準化互信息: {nmi:.4f}")

# 可視化聚類結果（使用前兩個特征）

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)

plt.scatter(X_iris_scaled[:, 0], X_iris_scaled[:, 1], c=y_iris, s=50, cmap='viridis')

plt.title('真實標簽', fontsize=15)

plt.xlabel(iris.feature_names[0], fontsize=12)

plt.ylabel(iris.feature_names[1], fontsize=12)

plt.grid(True, linestyle='--', alpha=0.7)

plt.subplot(1, 2, 2)

plt.scatter(X_iris_scaled[:, 0], X_iris_scaled[:, 1], c=iris_labels, s=50, cmap='viridis')

plt.scatter(kmeans_iris.cluster_centers_[:, 0</doubaocanvas>