C语言聚类算法中discard_set指针值异常变动问题排查

问题概述 #

开发聚类算法时，集群初始化完成进入K-Means阶段后，出现discard_set->values值异常变动的问题：

• 某次迭代中candidate==1时，discard_set[2].values的值也被修改；
• 偶尔dataset->values的值也会被改动。

运行程序时使用参数："db.csv" 3 3 1 10，修改块读取代码后问题仍未解决。需求为移除已加入集群的指针，仅在内存中保留离群点，需排查指针值异常变动的根源。

原始完整代码 #

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <float.h>
#include <stdbool.h>

struct point{
    int id;
    double* values;
};

struct cluster{
    int n_tot;
    int n_act;
    int *ids;
    double* values;
};

struct temp_cluster{
    int n;
    struct point *points;
    double* values;
};

struct compressed{
    int n_tot;
    int *ids;
    double* values;
};


#define randnum(min, max) ((rand() % (int)(((max) + 1) - (min))) + (min))

/**
 * Error code:
 * 11 bad parameters
 * 12 Memory allocation error
 * 13 File opening error
 */

int main(int argc, char **argv) {
    if (argc < 6) {
        printf("Error parameters! Usage: ./main <input_file> <points_dimension> <cluster_number> <alpha> <threshold>");
        exit(11);
    }

    char *filename = argv[1];
    int dimension = atoi(argv[2]);
    int k = atoi(argv[3]);
    float alpha = atof(argv[4]);
    float threshold = alpha * atof(argv[5]);

    int idx;
    int elem_idx;
    double temp;
    double distance;
    double beta;
    int k_cs = 0;
    int processd_point;
    int chunk_size = 20;
    int pinr = 0;
    int k_cs_temp = 7;
    bool stop = false;


    struct compressed *compressed_set = NULL;
    struct point *retained_set = NULL;

    /** CHUNK READING **/

    struct point *dataset = malloc(chunk_size * sizeof(struct point));

    if (!dataset)
        exit(12);

    for (int i = 0; i < chunk_size; i++) {
        dataset[i].values = malloc(dimension * sizeof(double));
        if (!dataset[i].values)
            exit(12);
    }

    FILE *file;
    file = fopen(filename, "r");
    if (!file)
        exit(13);

    char *line = NULL, *token;
    size_t len = 0;

    idx = -1;
    elem_idx = -1;
    while ((getline(&line, &len, file)) != -1 && idx < chunk_size) {
        if (idx > -1) { //跳过表头行
            while ((token = strsep(&line, ","))) {
                if (elem_idx == -1) //点的ID
                    dataset[idx].id = atoi(token);
                else //点的数值
                    dataset[idx].values[elem_idx] = atof(token);
                elem_idx++;
            }
            elem_idx = -1;
            idx++;
        } else
            idx++;
    }
    fclose(file);
    processd_point = chunk_size;

    /** END **/


    /** CLUSTER INIZIALIZATION **/

    struct cluster *discard_set = malloc(k * sizeof(struct cluster));

    if (!discard_set)
        exit(12);

    /*
     * 第一个聚类中心从数据集中随机选择，后续中心选择不属于已有集群的点
     */
    
    chunk_size--;

    srand(time(NULL));
    elem_idx = randnum(0, chunk_size);

    discard_set[0].n_tot = 1;
    discard_set[0].n_act = 1;

    discard_set[0].ids = malloc(sizeof(int));
    if (!discard_set[0].ids)
        exit(12);
    discard_set[0].ids[0] = dataset[elem_idx].id;

    discard_set[0].values = malloc(dimension * sizeof(double));
    if (!discard_set[0].values)
        exit(12);

    for (int j = 0; j < dimension; ++j) {
        discard_set[0].values[j] = dataset[elem_idx].values[j];
        discard_set[0].values[j + dimension] = pow(dataset[elem_idx].values[j], 2);
    }

    /*
     * 从数据集中删除已选作聚类中心的点（无需再存储）
    */

    free(dataset[elem_idx].values);
    if (elem_idx < chunk_size)
        memcpy(dataset + elem_idx, dataset + elem_idx + 1, (chunk_size - elem_idx) * sizeof(struct point));

    dataset = realloc(dataset, chunk_size * sizeof(struct point));
    if (!dataset)
        exit(12);

    /*
     * 后续聚类中心选择
     */

    int pos;

    for (int i = 1; i < k; ++i) {

        for (int j = 0; j < chunk_size; ++j) {
            bool checked = true;

            for (int l = 0; l < i && checked; ++l) {
                temp = 0;

                for (int m = 0; m < dimension; ++m) {
                    temp += pow(discard_set[l].values[m] - dataset[j].values[m], 2);
                }
                distance = sqrt(temp);
                if (distance < threshold)
                    checked = false;
            }

            if (checked) {
                pos = j;
                break;
            }
        }

        chunk_size--;

        discard_set[i].n_tot = 1;
        discard_set[i].n_act = 1;

        discard_set[i].ids = malloc(sizeof(int));
        if (!discard_set[i].ids)
            exit(12);
        discard_set[i].ids[0] = dataset[pos].id;

        discard_set[i].values = malloc(dimension * sizeof(double));
        if (!discard_set[i].values)
            exit(12);

        for (int j = 0; j < dimension; ++j) {
            discard_set[i].values[j] = dataset[pos].values[j];
            discard_set[i].values[j + dimension] = pow(dataset[pos].values[j], 2);
        }

        free(dataset[pos].values);
        if (pos < chunk_size)
            memcpy(dataset + pos, dataset + pos + 1, (chunk_size - pos) * sizeof(struct point));
        dataset = realloc(dataset, chunk_size * sizeof(struct point));
        if (!dataset)
            exit(12);
    }

    /** ------END------- **/

    /** KMEANS **/

    /*
     * 从数据集最后一个点开始处理，若点到聚类中心的欧氏距离小于threshold且是最近集群，则分配给该集群
     */

    while (chunk_size > 0) {
        chunk_size--;

        /*
         * 寻找候选集群
         */

        temp = DBL_MAX;
        int candidate = -1;

        for (int i = 0; i < k; ++i) {
            distance = 0;
            for (int j = 0; j < dimension; ++j) {
                distance += pow(dataset[chunk_size].values[j] - discard_set[i].values[j], 2);
            }

            if (sqrt(distance) < temp && sqrt(distance) < threshold) {
                temp = distance;
                candidate = i;
            }
        }


        /*
         * 若candidate > -1则将点分配给候选集群，否则加入离群点集合retained_set
         */


        if (candidate > -1) {
            for (int i = 0; i < dimension; i++) {
                discard_set[candidate].values[i] = ((discard_set[candidate].values[i] * discard_set[candidate].n_tot) +
                                                    dataset[chunk_size].values[i]) / (discard_set[candidate].n_tot + 1);
                discard_set[candidate].values[i + dimension] =
                        ((discard_set[candidate].values[i + dimension] * discard_set[candidate].n_tot) +
                         pow(dataset[chunk_size].values[i], 2)) / (discard_set[candidate].n_tot + 1);
            }

            discard_set[candidate].n_tot++;
            discard_set[candidate].n_act++;

            discard_set[candidate].ids = realloc(discard_set[candidate].ids,
                                                 discard_set[candidate].n_act * sizeof(int));
            if (!discard_set[candidate].ids)
                exit(12);

            discard_set[candidate].ids[discard_set[candidate].n_act - 1] = dataset[chunk_size].id;

        } else {
            pinr++;
            retained_set = realloc(retained_set, pinr * sizeof(struct point));
            if (!retained_set)
                exit(-2);
            memcpy(retained_set + pinr - 1, dataset + chunk_size, sizeof(struct point));

        }
        dataset = realloc(dataset, chunk_size * sizeof(struct point));
    }
    /** ------END------- **/
    return 0;
}

修改后的块读取代码 #

while ((getline(&line, &len, file)) != -1 && idx < chunk_size) {
    if (idx > -1) { //跳过表头行
        char *copy = line;
        while ((token = strsep(&copy, ","))) {
            if (elem_idx == -1) //点的ID
                dataset[idx].id = atoi(token);
            else if (elem_idx < dimension) //点的数值
                dataset[idx].values[elem_idx] = atof(token);
            else
                exit(14);
            elem_idx++;
        }
        elem_idx = -1;
        idx++;
    } else
        idx++;
}

问题根源分析 #

1. 缓冲区溢出（核心问题） #

每个cluster的values字段需要存储**dimension个均值和dimension个平方均值**，共2*dimension个double值，但代码中初始化时仅分配了dimension * sizeof(double)的内存：

discard_set[i].values = malloc(dimension * sizeof(double));

后续代码中访问discard_set[i].values[j + dimension]时，超出了分配的内存范围，直接写入到相邻的内存区域，导致其他集群的values或dataset的数据被篡改，这就是出现跨集群值变动、dataset值异常的根本原因。

2. 浅拷贝导致的悬空指针问题 #

将数据集中的点复制到retained_set时，使用memcpy直接复制struct point结构体：

memcpy(retained_set + pinr - 1, dataset + chunk_size, sizeof(struct point));

这会复制values指针而非指针指向的内容，后续dataset中的点被free或realloc移除后，retained_set中的values指针变为悬空指针，可能引发内存访问错误或数据混乱。

3. 内存泄漏风险 #

处理dataset中的点时，仅在聚类初始化阶段free了选中的点的values，但K-Means阶段处理完点后，未free对应的values，导致内存泄漏。

修复方案 #

1. 修复discard_set.values的内存分配 #

为每个集群的values分配足够的内存（2*dimension个double），修改所有初始化discard_set[i].values的代码：

// 替换原有的malloc语句
discard_set[i].values = malloc(2 * dimension * sizeof(double));
if (!discard_set[i].values)
    exit(12);

2. 修复retained_set的深拷贝问题 #

复制点到retained_set时，为values重新分配内存并拷贝内容，避免浅拷贝：

else {
    pinr++;
    retained_set = realloc(retained_set, pinr * sizeof(struct point));
    if (!retained_set)
        exit(12);
    // 深拷贝点的ID和数值
    retained_set[pinr-1].id = dataset[chunk_size].id;
    retained_set[pinr-1].values = malloc(dimension * sizeof(double));
    if (!retained_set[pinr-1].values)
        exit(12);
    memcpy(retained_set[pinr-1].values, dataset[chunk_size].values, dimension * sizeof(double));
}

3. 清理dataset中处理完的点的内存 #

无论点被分配到集群还是retained_set，处理完成后都要free其values，避免内存泄漏：

if (candidate > -1) {
    // ...原有的集群更新代码...
    // 释放当前点的values
    free(dataset[chunk_size].values);
} else {
    // ...原有的retained_set复制代码...
    // 释放当前点的values
    free(dataset[chunk_size].values);
}

内容的提问来源于stack exchange，提问作者Luca Marchio