K-Means 聚類演算法 C 語言通用實作：支援任意維度資料

演算法流程圖解

1. 初始化：從資料中隨機抽取 K 點作為初始質心
2. 分配步驟 (E-step)：計算每點到所有質心的歐氏距離，歸屬最近者
3. 更新步驟 (M-step)：重新計算各群質心 = 群內所有點的算術平均
4. 收斂判斷：質心移動總距離 Δ < ε 或達最大迭代次數則停止

核心資料結構

int K, N, D;                 // 群數、樣本數、維度
float **data;                // [N][D] 原始資料
int *cluster_id;             // [N] 每點所屬群索引
float **centroids;           // [K][D] 當前質心

關鍵函數實作

// 連續記憶體二維陣列配置
float **alloc2d(int rows, int cols) {
    float **p = malloc(rows * sizeof(float *));
    p[0] = malloc(rows * cols * sizeof(float));
    for (int i = 1; i < rows; ++i) p[i] = p[i-1] + cols;
    return p;
}

// 歐氏距離
float dist(float *a, float *b, int d) {
    float sum = 0;
    for (int i = 0; i < d; ++i) sum += (a[i]-b[i])*(a[i]-b[i]);
    return sqrtf(sum);
}

// E-step：分配最近質心
void assign_clusters() {
    for (int i = 0; i < N; ++i) {
        float best = 1e9; int best_k = 0;
        for (int k = 0; k < K; ++k) {
            float d = dist(data[i], centroids[k], D);
            if (d < best) { best = d; best_k = k; }
        }
        cluster_id[i] = best_k;
    }
}

// M-step：重算質心
void update_centroids() {
    float **sum = alloc2d(K, D);
    int *cnt = calloc(K, sizeof(int));
    for (int k = 0; k < K; ++k)
        for (int d = 0; d < D; ++d) sum[k][d] = 0;
    
    for (int i = 0; i < N; ++i) {
        int k = cluster_id[i];
        for (int d = 0; d < D; ++d) sum[k][d] += data[i][d];
        cnt[k]++;
    }
    for (int k = 0; k < K; ++k)
        for (int d = 0; d < D; ++d)
            centroids[k][d] = cnt[k] ? sum[k][d]/cnt[k] : centroids[k][d];
    
    free(sum[0]); free(sum); free(cnt);
}

// 收斂指標：質心位移平方和
float centroid_shift() {
    float shift = 0;
    for (int k = 0; k < K; ++k)
        shift += dist(centroids[k], prev_centroids[k], D);
    return shift;
}

主迴圈與資料輸入格式

data.txt 首行：K=3,D=3,N=15，其後 15 行各 3 維浮點數。

int main() {
    data = load_data("data.txt", &K, &D, &N);  // 解析首行並讀入
    centroids = alloc2d(K, D);
    cluster_id = malloc(N * sizeof(int));
    
    // 隨機初始化質心
    srand(time(NULL));
    for (int k = 0; k < K; ++k)
        for (int d = 0; d < D; ++d)
            centroids[k][d] = data[rand()%N][d];
    
    int iter = 0;
    float prev_shift = 1e9;
    do {
        assign_clusters();
        update_centroids();
        float shift = centroid_shift();
        printf("Iter %3d  centroid shift = %.6f\n", ++iter, shift);
        if (fabs(shift - prev_shift) < 1e-4) break;
        prev_shift = shift;
        // 備份質心供下輪比較
        memcpy(prev_centroids[0], centroids[0], K*D*sizeof(float));
    } while (iter < 1000);
    
    // 輸出結果
    for (int i = 0; i < N; ++i)
        printf("Point %3d → Cluster %d\n", i, cluster_id[i]);
    
    // 釋放記憶體
    free(data[0]); free(data);
    free(centroids[0]); free(centroids);
    free(prev_centroids[0]); free(prev_centroids);
    free(cluster_id);
    return 0;
}

實驗結果範例

Iter   1  centroid shift = 123.456
Iter   2  centroid shift =  45.210
Iter   3  centroid shift =  12.870
...
Iter  12  centroid shift =   0.00012  ← 收斂
Point   0 → Cluster 2
Point   1 → Cluster 0
...

工程化優化方向

• K-Means++ 初始化：以概率 ∝ 距離² 選質心，大幅減少迭代次數
• Elkan 演算法：利用三角不等式避免冗餘距離計算，加速 10-100 倍
• Mini-batch K-Means：每輪僅抽樣子集更新，適合海量資料
• 平行化：OpenMP 平行化距離計算與質心累加，線性加速

本實作以 150 行核心代碼 完整呈現 K-Means 全流程，無第三方依賴，適合嵌入式部署、教學演示或作為高效能庫的基礎模組。