k_means算法

C语言代码

#include <iostream>
using namespace std;

// 定义点的结构体
struct point {
    double x;  // 点的x坐标
    double y;  // 点的y坐标
    int centroid;  // 点所属的质心
};

// 定义计算两点之间距离的函数
double dist(struct point a, struct point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

/// <summary>
/// 定义kmeans算法函数
/// </summary>
/// <param name="dataset">需要分类的数据点</param>
/// <param name="N">定义数据点的数量</param>
/// <param name="K">定义质心的数量</param>
/// <param name="centroids">k个质心坐标</param>
/// <param name="iter">迭代次数</param>
void kmeans(point* dataset, int N, int K, point* centroids, int* iter) {
    // 初始化质心为数据集中的前k个元素
    for (int i = 0; i < K; i++) {
        centroids[i] = dataset[i];
    }

    // 重复直到收敛
    while (1) {
        int changed = 0;  // 标记是否有点的质心发生改变

        // 将每个点分配给最近的质心
        for (int i = 0; i < N; i++) {
            int closest = 0;  // 最近的质心
            double closest_dist = dist(dataset[i], centroids[0]);  // 最近的距离
            for (int j = 1; j < K; j++) {
                double dist_j = dist(dataset[i], centroids[j]);  // 计算到质心j的距离
                if (dist_j < closest_dist) {  // 如果到质心j的距离小于当前最近的距离
                    closest = j;  // 更新最近的质心
                    closest_dist = dist_j;  // 更新最近的距离
                }
            }
            if (dataset[i].centroid != closest) {  // 如果点的质心发生改变
                dataset[i].centroid = closest;  // 更新点的质心
                changed = 1;  // 标记有点的质心发生改变
            }
        }

        // 更新质心
        for (int i = 0; i < K; i++) {
            double sum_x = 0, sum_y = 0;  // 质心的x坐标和y坐标的和
            int count = 0;  // 属于该质心的点的数量
            for (int j = 0; j < N; j++) {
                if (dataset[j].centroid == i) {  // 如果点属于该质心
                    sum_x += dataset[j].x;  // 累加x坐标
                    sum_y += dataset[j].y;  // 累加y坐标
                    count++;  // 累加点的数量
                }
            }
            centroids[i].x = sum_x / count;  // 更新质心的x坐标
            centroids[i].y = sum_y / count;  // 更新质心的y坐标
        }

        if (!changed) {  // 如果没有点的质心发生改变
            break;  // 结束循环
        }
        (*iter)++;//迭代次数加一
    }
}
int main()
{
    const int N = 4;  // 定义数据集中的点的数量
    const int K = 2;  //定义质心的数量

    // 定义数据集
    struct point dataset[N] = {
        {2.0, 3.0, -1},
        {7.0, 8.0, -1},
        {9.0, 10.0, -1},
        {4.0, 5.0, -1},
    };

    // 定义质心
    struct point centroids[K];
    //定义迭代次数
    int iter = 0;
    kmeans(dataset, N, K, centroids, &iter);  // 执行kmeans算法
    //打印测试结果
    printf("迭代次数：%d\n", iter);
    for (int i = 0; i < K; i++) {
        printf("质心 %d 坐标 (%0.2f,%0.2f)\n", i, centroids[i].x, centroids[i].y);
        printf("属于该质心的点：\n");
        for (int j = 0; j < N; j++) {
            if (dataset[j].centroid == i)
                printf("(%0.1f,%0.1f)", dataset[j].x, dataset[j].y);
        }
        printf("\n\n");
    }
    return 0;
}

运行结果如下