C语言中K-means算法实现代码

下面我们就来详细讲解一下“C语言中K-means算法实现代码”的完整攻略。

一、K-means算法概述

K-means算法是一种聚类算法，它将样本划分为K个簇，每个簇由距离最近的质心（centroid）来表示。算法流程如下：

随机选择K个样本作为初始质心。
将每个样本归为距离最近的质心所在的簇。
重新计算每个簇的质心。
重复2、3步骤，直到质心不再变化或者达到一定迭代次数。

二、K-means算法实现步骤

对于C语言中的K-means算法实现，我们可以采用以下步骤：

步骤1：输入数据

首先，我们需要从输入文件中读取样本数据，并将其存储到一个浮点数组中。

// 读取数据集文件
void read_data(char* filename, int n, int d, float* data) {
    FILE* fp = fopen(filename, "r");
    if (fp == NULL) {
        printf("Failed to open data file %s!\n", filename);
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            fscanf(fp, "%f", &data[i*d+j]);
        }
    }
    fclose(fp);
}

步骤2：初始化质心

接下来，我们需要随机从样本数据中选择K个样本作为初始质心，并将其存储到一个浮点数组中。

// 初始化质心
void init_centroids(int k, int d, float* data, float* centroids) {
    int* indices = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        indices[i] = rand() % n;
        for (int j = 0; j < d; j++) {
            centroids[i*d+j] = data[indices[i]*d+j];
        }
    }
    free(indices);
}

步骤3：计算样本距离

在K-means算法中，我们需要计算每个样本与各个质心之间的距离。我们可以使用欧几里得距离来度量样本之间的距离。

// 计算样本与质心之间的距离
float dist(float* x, float* y, int d) {
    float d2 = 0.0;
    for (int i = 0; i < d; i++) {
        d2 += (x[i]-y[i]) * (x[i]-y[i]);
    }
    return sqrt(d2);
}

// 计算每个样本与各个质心之间的距离
void calc_distances(int n, int k, int d, float* data, float* centroids, int* labels, float* distances) {
    for (int i = 0; i < n; i++) {
        float min_distance = FLT_MAX;
        int label = 0;
        for (int j = 0; j < k; j++) {
            float distance = dist(&data[i*d], &centroids[j*d], d);
            if (distance < min_distance) {
                min_distance = distance;
                label = j;
            }
        }
        labels[i] = label;
        distances[i] = min_distance;
    }
}

步骤4：重新计算质心

在每次对样本进行分类之后，我们需要重新计算每个簇的质心，并将其存储到一个浮点数组中。

// 重新计算质心
void update_centroids(int n, int k, int d, float* data, int* labels, float* centroids) {
    int* counts = (int*)calloc(k, sizeof(int));
    for (int i = 0; i < n; i++) {
        int label = labels[i];
        for (int j = 0; j < d; j++) {
            centroids[label*d+j] += data[i*d+j];
        }
        counts[label]++;
    }
    for (int i = 0; i < k; i++) {
        if (counts[i] == 0) {
            counts[i] = 1;
        }
        for (int j = 0; j < d; j++) {
            centroids[i*d+j] /= counts[i];
        }
    }
    free(counts);
}

步骤5：迭代K-means算法

最后，我们需要对K-means算法进行迭代，直到质心不再变化或者达到一定迭代次数。

// K-means算法迭代
void kmeans(int n, int k, int d, float* data, float* centroids, int* labels, float* distances, int max_iter) {
    for (int iter = 0; iter < max_iter; iter++) {
        // 计算样本与质心之间的距离
        calc_distances(n, k, d, data, centroids, labels, distances);
        // 重新计算质心
        update_centroids(n, k, d, data, labels, centroids);
    }
}

三、代码示例

下面给出两个示例代码，分别是对Iris数据集和Wisconsin Breast Cancer数据集进行聚类。

示例1：Iris数据集聚类

Iris数据集是一个经典的分类和聚类数据集，包含150个样本和4个特征。我们可以将其分为3个簇。

int main(int argc, char* argv[]) {
    // 读取数据集
    int n = 150, d = 4, k = 3, max_iter = 100;
    float* data = (float*)malloc(n*d*sizeof(float));
    read_data("iris.dat", n, d, data);
    float* centroids = (float*)malloc(k*d*sizeof(float));
    init_centroids(k, d, data, centroids);
    int* labels = (int*)malloc(n*sizeof(int));
    float* distances = (float*)malloc(n*sizeof(float));
    // 执行K-means算法
    kmeans(n, k, d, data, centroids, labels, distances, max_iter);
    // 输出聚类结果
    for (int i = 0; i < n; i++) {
        printf("Sample %d: Cluster %d\n", i, labels[i]);
    }
    // 释放内存
    free(data);
    free(centroids);
    free(labels);
    free(distances);
    return 0;
}

示例2：Wisconsin Breast Cancer数据集聚类

Wisconsin Breast Cancer数据集是一个用于肿瘤检测的数据集，包含569个样本和30个特征。我们可以将其分为2个簇。

int main(int argc, char* argv[]) {
    // 读取数据集
    int n = 569, d = 30, k = 2, max_iter = 100;
    float* data = (float*)malloc(n*d*sizeof(float));
    read_data("wdbc.dat", n, d, data);
    float* centroids = (float*)malloc(k*d*sizeof(float));
    init_centroids(k, d, data, centroids);
    int* labels = (int*)malloc(n*sizeof(int));
    float* distances = (float*)malloc(n*sizeof(float));
    // 执行K-means算法
    kmeans(n, k, d, data, centroids, labels, distances, max_iter);
    // 输出聚类结果
    for (int i = 0; i < n; i++) {
        printf("Sample %d: Cluster %d\n", i, labels[i]);
    }
    // 释放内存
    free(data);
    free(centroids);
    free(labels);
    free(distances);
    return 0;
}

四、总结

通过以上的详细讲解，我们相信你已经掌握了C语言中实现K-means算法的方法和过程。同时，在两个示例代码的帮助下，你也可以通过K-means算法对不同的数据集进行聚类分析。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言中K-means算法实现代码 - Python技术站