第33章 KMeans

#include <stdio.h>
#include <math.h>
#include <float.h>

#define N 8        // 数据点的数量
#define K 2        // 要分成几组
#define DIM 2      // 每个点的维度（二维）
#define MAX_ITER 100  // 最多迭代多少轮

struct Point {
    float x[DIM];  // 坐标
    int cluster;    // 属于哪个组（0 到 K-1）
};

float distance(const float a[DIM], const float b[DIM])
{
    float sum = 0.0f;                       // 平方差累加器
    for (int i = 0; i < DIM; i++) {         // 遍历每个维度
        float diff = a[i] - b[i];           // 当前维度的差值
        sum += diff * diff;                 // 累加差值的平方
    }
    return sqrtf(sum);                      // 开方得到欧氏距离
}

void assign_clusters(struct Point points[N], float centers[K][DIM])
{
    for (int i = 0; i < N; i++) {
        float min_dist = FLT_MAX;
        int best = 0;
        for (int c = 0; c < K; c++) {
            float d = distance(points[i].x, centers[c]);
            if (d < min_dist) {
                min_dist = d;
                best = c;
            }
        }
        points[i].cluster = best;  // 分给最近的中心
    }
}

void update_centers(struct Point points[N], float centers[K][DIM])
{
    float sum[K][DIM] = {0};   // 每组的坐标总和
    int count[K] = {0};        // 每组有多少个点

    for (int i = 0; i < N; i++) {
        int c = points[i].cluster;
        for (int d = 0; d < DIM; d++) {
            sum[c][d] += points[i].x[d];
        }
        count[c]++;
    }

    for (int c = 0; c < K; c++) {
        if (count[c] == 0) continue;  // 空组不更新，避免除零
        for (int d = 0; d < DIM; d++) {
            centers[c][d] = sum[c][d] / count[c];  // 平均值
        }
    }
}

for (int iter = 1; iter <= MAX_ITER; iter++) {
    copy_centers(old_centers, centers);      // 保存旧中心

    assign_clusters(points, centers);        // 每个点分给最近中心
    update_centers(points, centers);         // 中心移到组内平均位置

    print_state(points, centers, iter);      // 观察这一轮

    if (!centers_changed(old_centers, centers)) {
        break;
    }
}

void copy_centers(float dst[K][DIM], float src[K][DIM])
{
    for (int c = 0; c < K; c++) {         // 遍历 K 个中心
        for (int d = 0; d < DIM; d++) {   // 遍历每个维度
            dst[c][d] = src[c][d];        // 逐元素复制
        }
    }
}

int centers_changed(float old_centers[K][DIM], float centers[K][DIM])
{
    for (int c = 0; c < K; c++) {
        if (distance(old_centers[c], centers[c]) >= 0.001f) {
            return 1;  // 还有中心移动得比较明显
        }
    }
    return 0;
}

void print_state(struct Point points[N], float centers[K][DIM], int iter)
{
    if (iter == 0) {                                 // 第 0 轮打印初始状态
        printf("Initial state:\n");
    } else {                                         // 其他轮打印轮次标题
        printf("=== Round %d ===\n", iter);
    }

    for (int c = 0; c < K; c++) {                    // 打印每个中心的坐标
        printf("  Center %d: (%.2f, %.2f)\n",
               c, centers[c][0], centers[c][1]);
    }

    for (int i = 0; i < N; i++) {                    // 打印每个点及其所属组
        printf("  Point %d (%.0f, %.0f) -> Group %d\n",
               i, points[i].x[0], points[i].x[1], points[i].cluster);
    }
    printf("\n");
}

void print_groups(struct Point points[N])
{
    printf("=== Final Groups ===\n");
    for (int c = 0; c < K; c++) {                    // 遍历每个组
        printf("Group %d:", c);                          // 打印组号
        for (int i = 0; i < N; i++) {                // 遍历所有点，找出属于当前组的
            if (points[i].cluster == c) {             // 该点属于当前组
                printf(" (%d, %.0f, %.0f)",
                       i, points[i].x[0], points[i].x[1]);  // 打印点序号和坐标
            }
        }
        printf("\n");
    }
}

int main(void)
{
    struct Point points[N] = {                                  // 8个点，cluster 初始化为 -1 表示未分配
        {{2, 30}, -1}, {{3, 35}, -1}, {{4, 28}, -1}, {{5, 40}, -1},
        {{15, 80}, -1}, {{16, 85}, -1}, {{17, 78}, -1}, {{18, 90}, -1}
    };

    float centers[K][DIM] = {                                   // 初始中心选点 A 和点 E
        {2, 30},   // 点 A
        {15, 80}   // 点 E
    };
    float old_centers[K][DIM] = {0};                            // 用于保存上一轮的中心

    print_state(points, centers, 0);                            // 打印初始状态

    for (int iter = 1; iter <= MAX_ITER; iter++) {              // 迭代主循环
        copy_centers(old_centers, centers);                     // 保存旧中心，用于判断收敛

        assign_clusters(points, centers);                       // 分配：每个点归入最近的中心
        update_centers(points, centers);                        // 更新：中心移到组内平均位置

        print_state(points, centers, iter);                     // 打印本轮结果

        if (!centers_changed(old_centers, centers)) {           // 中心不再移动则提前结束
            printf("Centers no longer change, iteration complete.\n\n");
            break;
        }
    }

    print_groups(points);                                       // 打印最终分组
    return 0;
}