C语言实现K均值聚类

K均值聚类(K_means)基础理论

K_means聚类是一种简单且广泛使用的聚类算法，它旨在将数据集中的样本划分为k个不同的聚类，其中k是事先指定的聚类数量，该算法的核心思想是迭代地优化聚类中心，以最小化每个样本与其所属聚类中心之间的距离之和。这个算法的优点是简单易懂、计算效率高，适用于大规模数据集，但是嘞，它需要事先指定聚类数量k，同时这个算法对初始聚类中心的选择敏感，还可能陷入局部最优解，所以在实际使用之前还是需要先考虑使用场景。

计算公式

聚类中心的定义: 对于第 $i$ 个聚类中心 $\mu_i$ ，它是一个 $d$ 维向量，其中 $d$ 是数据点的维度。在K_means聚类算法中，聚类中心用于表示每个聚类的中心位置，是聚类内所有点的均值。
数据点与聚类中心的距离: 数据点与聚类中心的距离使用欧几里得距离公式计算，即：
$\mu_i) = \sqrt{\sum_{j=1}^{d} (x_j - \mu_{ij})^2}$
这里:
$x$ 是一个 $d$ 维的数据点，
$\mu_i$ 是第 $i$ 个聚类中心，
$x_j$ 是数据点 $x$ 的第 $j$ 个维度，
$\mu_{ij}$ 是第 $i$ 个聚类中心的第 $j$ 个维度。
聚类分配: 对于数据点 $x$ ，其所属的聚类 $c$ 是通过计算 $x$ 与所有聚类中心的距离，并选择距离最小的聚类中心所对应的聚类。具体地，聚类分配满足：
$\arg\min_{i} d(x, \mu_i)$
即 $c$ 是使得 $\mu_i)$ 最小的 $i$ 的值。
聚类中心的更新: 在每次迭代中，聚类中心会根据当前聚类内的数据点进行更新。对于第 $i$ 个聚类，其新的聚类中心 $\mu_i'$ 是该聚类内所有数据点的均值，即:
$\mu_i' = \frac{1}{|C_i|} \sum_{x \in C_i} x$
其中:
$C_i$ 表示第 $i$ 个聚类内的所有数据点，
$C_i|$ 表示第 $i$ 个聚类内的数据点数量。
算法终止条件: K_Means算法在两种情况下会终止：一是当聚类中心在迭代过程中不再发生变化时，即新的聚类中心与旧的聚类中心相同；二是当达到预定的迭代次数时。在这两种情况下，算法认为已经找到了稳定的聚类结构，并会停止迭代。

选择训练所使用的数据集

iris数据集，全称为安德森鸢尾花卉数据集（Anderson's Iris dataset），是R语言中一个非常经典且广泛使用的数据集，该数据集最初由迷糊老师(Teacher MiHu)收集，用于统计分类和聚类分析。iris数据集包含了150个样本，每个样本代表了不同种类的鸢尾花（Iris）的四个测量值：萼片长度（Sepal.Length）、萼片宽度（Sepal.Width）、花瓣长度（Petal.Length）和花瓣宽度（Petal.Width），以及对应的鸢尾花种类（Species），共有三种：山鸢尾（Setosa）、变色鸢尾（Versicolor）和维吉尼亚鸢尾（Virginica）。
由于iris数据集包含三个不同种类的鸢尾花，且这些种类在特征空间中存在明显的区分，因此非常适合用于练习k_means聚类算法。在实际应用中，k_means聚类算法需要事先指定聚类数k，而在iris数据集中，由于已知存在三个种类，因此可以设定k=3来进行聚类，从而验证聚类效果。
iris数据集的内容如下：
在这里插入图片描述

C语言实现

定义一个结构体iris,包含不同种类的鸢尾花（Iris）的四个测量值：萼片长度（sepal_length）、萼片宽度（sepal_width）、花瓣长度（petal_length）和花瓣宽度（petal_width）和簇( cluster)

typedef struct {double sepal_length;double sepal_width;double petal_length;double petal_width;int cluster;
} Iris;

定义一个名为calculate_distance的函数，这个函数接收两个指向 Iris 结构体的指针作为参数，并返回这两个实例之间的欧几里得距离。

double calculate_distance(const Iris *a, const Iris *b) {return sqrt(pow(a->sepal_length - b->sepal_length, 2) +pow(a->sepal_width - b->sepal_width, 2) +pow(a->petal_length - b->petal_length, 2) +pow(a->petal_width - b->petal_width, 2));
}

随后定义一个名为assign_to_clusters的函数，将数据集data中的每个数据点分配到最近的聚类中心(centroid),代码中的centroids是一个指向iris结构体数组的指针，该数组包含了当前的聚类中心位置data_size是数据点的总数k是聚类中心的数量。

void assign_to_clusters(Iris *data, Iris *centroids, int data_size, int k) {for (int i = 0; i < data_size; i++) {double min_distance = INFINITY;int closest_cluster = 0;for (int j = 0; j < k; j++) {double distance = calculate_distance(&data[i], &centroids[j]);if (distance < min_distance) {min_distance = distance;closest_cluster = j;}}data[i].cluster = closest_cluster;}
}

这段代码定义一个名为update_centroids的函数，其目的是更新K-means聚类算法中的聚类中心位置。

void update_centroids(Iris *data, Iris *centroids, int data_size, int k) {int *cluster_counts = (int *)malloc(k * sizeof(int));memset(cluster_counts, 0, k * sizeof(int));for (int i = 0; i < k; i++) {centroids[i].sepal_length = 0;centroids[i].sepal_width = 0;centroids[i].petal_length = 0;centroids[i].petal_width = 0;}for (int i = 0; i < data_size; i++) {int cluster = data[i].cluster;centroids[cluster].sepal_length += data[i].sepal_length;centroids[cluster].sepal_width += data[i].sepal_width;centroids[cluster].petal_length += data[i].petal_length;centroids[cluster].petal_width += data[i].petal_width;cluster_counts[cluster]++;}for (int i = 0; i < k; i++) {if (cluster_counts[i] > 0) {centroids[i].sepal_length /= cluster_counts[i];centroids[i].sepal_width /= cluster_counts[i];centroids[i].petal_length /= cluster_counts[i];centroids[i].petal_width /= cluster_counts[i];}}free(cluster_counts);
}

定义一个k_means函数初始化聚类中心。通过随机选择数据集中的点作为初始聚类中心，这里使用了srand(time(NULL))来初始化随机数生成器，但通常建议在程序开始时只调用一次srand，而不是在每次调用k_means时都调用。
迭代过程：

使用一个do-while循环来重复执行以下步骤，直到达到最大迭代次数或聚类中心不再发生变化。
使用memcpy复制当前聚类中心到old_centroids，以便后续比较。
调用assign_to_clusters函数，将每个数据点分配到最近的聚类中心。
调用update_centroids函数，根据当前分配更新聚类中心的位置。
通过比较old_centroids和centroids检查聚类中心是否发生了变化。
释放old_centroids占用的内存。

void k_means(Iris *data, Iris *centroids, double *cluster_ss, int data_size, int k, int max_iterations) {Iris *old_centroids = (Iris *)malloc(k * sizeof(Iris));int *cluster_counts = (int *)malloc(k * sizeof(int));srand(time(NULL));for (int i = 0; i < k; i++) {int index = rand() % data_size;// 确保选择不同的质心while (i > 0 && calculate_distance(&centroids[i], &data[index]) == 0.0) {index = rand() % data_size;}centroids[i] = data[index];}int iteration = 0;do {memcpy(old_centroids, centroids, k * sizeof(Iris));assign_to_clusters(data, centroids, cluster_counts, cluster_ss, data_size, k);update_centroids(data, centroids, cluster_counts, data_size, k);iteration++;} while (iteration < max_iterations &&(memcmp(old_centroids, centroids, k * sizeof(Iris)) != 0));free(old_centroids);free(cluster_counts);
}

定义一个calculate_global_mean函数计算给定数据集的全局平均值（即所有特征的平均值）。
函数的主要步骤如下：

初始化一个Iris结构体变量global_mean，其所有特征值都设置为0。
遍历数据集，累加每个数据点的特征值到global_mean中。
将累加后的特征值除以数据点的数量，计算出平均值。
返回计算得到的全局平均值。

Iris calculate_global_mean(Iris *data, int data_size) {Iris global_mean = {0};for (int i = 0; i < data_size; i++) {global_mean.sepal_length += data[i].sepal_length;global_mean.sepal_width += data[i].sepal_width;global_mean.petal_length += data[i].petal_length;global_mean.petal_width += data[i].petal_width;}global_mean.sepal_length /= data_size;global_mean.sepal_width /= data_size;global_mean.petal_length /= data_size;global_mean.petal_width /= data_size;return global_mean;
}

定义函数print_cluster_means用于打印聚类中心的均值

void print_cluster_means(Iris *centroids, int k) {  printf("集群均值:\n");  for (int i = 0; i < k; i++) {  printf("集群 %d: Sepal Length: %.2f, Sepal Width: %.2f, Petal Length: %.2f, Petal Width: %.2f\n",  i, centroids[i].sepal_length, centroids[i].sepal_width, centroids[i].petal_length, centroids[i].petal_width);  }  
}

定义函数calculate_within_cluster_ss计算所有聚类内部的平方和(Within-Cluster Sum of Squares, WCSS)

double calculate_within_cluster_ss(Iris *data, Iris *centroids, int data_size, int k) {  double within_ss = 0.0;  for (int i = 0; i < data_size; i++) {  within_ss += calculate_distance(&data[i], &centroids[data[i].cluster]) * calculate_distance(&data[i], &centroids[data[i].cluster]);  }  return within_ss;  
}

定义calculate_total_ss 函数计算数据集的总平方和（Total Sum of Squares, TSS）

double calculate_total_ss(Iris *data, Iris global_mean, int data_size) {  double total_ss = 0.0;  for (int i = 0; i < data_size; i++) {  total_ss += calculate_distance(&data[i], &global_mean) * calculate_distance(&data[i], &global_mean);  }  return total_ss;  
}

定义函数calculate_between_cluster_ss函数计算聚类间的平方和（Between-Cluster Sum of Squares, BSS）

double calculate_between_cluster_ss(Iris *centroids, Iris global_mean, int k) {  double between_ss = 0.0;  for (int i = 0; i < k; i++) {  between_ss += calculate_distance(&centroids[i], &global_mean) * calculate_distance(&centroids[i], &global_mean);  }  return between_ss;  
}

加入main主函数的完整版代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>typedef struct {double sepal_length;double sepal_width;double petal_length;double petal_width;int cluster;
} Iris;double calculate_distance(const Iris *a, const Iris *b) {return sqrt(pow(a->sepal_length - b->sepal_length, 2) +pow(a->sepal_width - b->sepal_width, 2) +pow(a->petal_length - b->petal_length, 2) +pow(a->petal_width - b->petal_width, 2));
}void assign_to_clusters(Iris *data, Iris *centroids, int *cluster_counts, double *cluster_ss, int data_size, int k) {memset(cluster_counts, 0, k * sizeof(int));  memset(cluster_ss, 0, k * sizeof(double));  for (int i = 0; i < data_size; i++) {double min_distance = INFINITY;int closest_cluster = -1;for (int j = 0; j < k; j++) {double distance = calculate_distance(&data[i], &centroids[j]);if (distance < min_distance) {min_distance = distance;closest_cluster = j;}}data[i].cluster = closest_cluster;cluster_ss[closest_cluster] += min_distance * min_distance;  // 累加每个集群的平方和cluster_counts[closest_cluster]++;}
}void update_centroids(Iris *data, Iris *centroids, int *cluster_counts, int data_size, int k) {for (int i = 0; i < k; i++) {centroids[i].sepal_length = 0;centroids[i].sepal_width = 0;centroids[i].petal_length = 0;centroids[i].petal_width = 0;}for (int i = 0; i < data_size; i++) {int cluster = data[i].cluster;centroids[cluster].sepal_length += data[i].sepal_length;centroids[cluster].sepal_width += data[i].sepal_width;centroids[cluster].petal_length += data[i].petal_length;centroids[cluster].petal_width += data[i].petal_width;}for (int i = 0; i < k; i++) {if (cluster_counts[i] > 0) {centroids[i].sepal_length /= cluster_counts[i];centroids[i].sepal_width /= cluster_counts[i];centroids[i].petal_length /= cluster_counts[i];centroids[i].petal_width /= cluster_counts[i];}}
}void k_means(Iris *data, Iris *centroids, double *cluster_ss, int data_size, int k, int max_iterations) {Iris *old_centroids = (Iris *)malloc(k * sizeof(Iris));int *cluster_counts = (int *)malloc(k * sizeof(int));srand(time(NULL));for (int i = 0; i < k; i++) {int index = rand() % data_size;// 确保选择不同的质心while (i > 0 && calculate_distance(&centroids[i], &data[index]) == 0.0) {index = rand() % data_size;}centroids[i] = data[index];}int iteration = 0;do {memcpy(old_centroids, centroids, k * sizeof(Iris));assign_to_clusters(data, centroids, cluster_counts, cluster_ss, data_size, k);update_centroids(data, centroids, cluster_counts, data_size, k);iteration++;} while (iteration < max_iterations &&(memcmp(old_centroids, centroids, k * sizeof(Iris)) != 0));free(old_centroids);free(cluster_counts);
}Iris calculate_global_mean(Iris *data, int data_size) {Iris global_mean = {0};for (int i = 0; i < data_size; i++) {global_mean.sepal_length += data[i].sepal_length;global_mean.sepal_width += data[i].sepal_width;global_mean.petal_length += data[i].petal_length;global_mean.petal_width += data[i].petal_width;}global_mean.sepal_length /= data_size;global_mean.sepal_width /= data_size;global_mean.petal_length /= data_size;global_mean.petal_width /= data_size;return global_mean;
}void read_csv(char *filename, Iris *data, int data_size) {FILE *file = fopen(filename, "r");if (file == NULL) {fprintf(stderr, "无法打开文件 '%s'\n", filename);exit(EXIT_FAILURE);}// 声明行缓冲区char line[256];// 跳过标题行if (fgets(line, sizeof(line), file) == NULL) {fprintf(stderr, "错误：无法读取标题行。\n");fclose(file);exit(EXIT_FAILURE);}int i = 0;while (fgets(line, sizeof(line), file) != NULL && i < data_size) {if (sscanf(line, "%lf,%lf,%lf,%lf", &data[i].sepal_length, &data[i].sepal_width,&data[i].petal_length, &data[i].petal_width) == 4) {i++;} else {fprintf(stderr, "读取行时出错: %s", line);break;}}if (feof(file)) {} else {perror("读取文件时出错");}fclose(file);
}void print_cluster_means(Iris *centroids, int k) {  printf("簇均值:\n");  for (int i = 0; i < k; i++) {  printf("簇 %d: Sepal Length: %.2f, Sepal Width: %.2f, Petal Length: %.2f, Petal Width: %.2f\n",  i, centroids[i].sepal_length, centroids[i].sepal_width, centroids[i].petal_length, centroids[i].petal_width);  }  
}  double calculate_within_cluster_ss(Iris *data, Iris *centroids, int data_size, int k) {  double within_ss = 0.0;  for (int i = 0; i < data_size; i++) {  within_ss += calculate_distance(&data[i], &centroids[data[i].cluster]) * calculate_distance(&data[i], &centroids[data[i].cluster]);  }  return within_ss;  
}  double calculate_total_ss(Iris *data, Iris global_mean, int data_size) {  double total_ss = 0.0;  for (int i = 0; i < data_size; i++) {  total_ss += calculate_distance(&data[i], &global_mean) * calculate_distance(&data[i], &global_mean);  }  return total_ss;  
}  double calculate_between_cluster_ss(Iris *centroids, Iris global_mean, int k) {  double between_ss = 0.0;  for (int i = 0; i < k; i++) {  between_ss += calculate_distance(&centroids[i], &global_mean) * calculate_distance(&centroids[i], &global_mean);  }  return between_ss;  
}  int main() {int data_size = 150;Iris *data = (Iris *)malloc(data_size * sizeof(Iris));read_csv("iris_dataset.csv", data, data_size);int k = 3;int max_iterations = 100;srand(time(NULL));Iris *centroids = (Iris *)malloc(k * sizeof(Iris));double cluster_ss[k];k_means(data, centroids, cluster_ss, data_size, k, max_iterations);Iris global_mean = calculate_global_mean(data, data_size);// 输出聚类大小int *cluster_sizes = (int *)malloc(k * sizeof(int));memset(cluster_sizes, 0, k * sizeof(int));for (int i = 0; i < data_size; i++) {cluster_sizes[data[i].cluster]++;}printf("\nK-means聚类有 %d 簇:", k);for (int i = 0; i < k; i++) {printf("%d, ", cluster_sizes[i]);}printf("\b\b\n");// 输出聚类中心print_cluster_means(centroids, k);// 输出聚类向量printf("\n聚类向量:\n");for (int i = 0; i < data_size; i++) {printf(" %d", data[i].cluster);if ((i + 1) % 10 == 0) {printf("\n");}}// 输出within SS 和 between SS 比率double within_ss = calculate_within_cluster_ss(data, centroids, data_size, k);double total_ss = calculate_total_ss(data, global_mean, data_size);double between_ss = calculate_between_cluster_ss(centroids, global_mean, k);printf("\n聚类内各聚类平方和:\n");for (int i = 0; i < k; i++) {printf("[%d] %.3f\n", i + 1, cluster_ss[i]);}if (total_ss == 0.0) {printf("(between_SS / total_SS = undefined)\n");} else {printf("(between_SS / total_SS = %.1f %%)\n", (between_ss / total_ss) * 100);}free(data);free(centroids);free(cluster_sizes);return 0;
}

代码运行后输出：


K-means聚类有 3 簇:62, 38, 50, 
簇均值:
簇 0: Sepal Length: 5.90, Sepal Width: 2.75, Petal Length: 4.39, Petal Width: 1.43
簇 1: Sepal Length: 6.85, Sepal Width: 3.07, Petal Length: 5.74, Petal Width: 2.07
簇 2: Sepal Length: 5.01, Sepal Width: 3.43, Petal Length: 1.46, Petal Width: 0.25聚类向量:2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 20 0 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 01 0 1 1 1 1 0 1 1 11 1 1 0 0 1 1 1 1 01 0 1 0 1 1 0 0 1 11 1 1 0 1 1 1 1 0 11 1 0 1 1 1 0 1 1 0聚类内各聚类平方和:
[1] 39.821
[2] 23.879
[3] 15.151
(between_SS / total_SS = 2.0 %)

R语言和Python实现

相较于C语言来说，R语言实现就非常简洁，在设置好随机种子set.seed()后，直接使用内置的kmeans函数就可以轻松实现：

data(iris)
X <- iris[, 1:4]
set.seed(123)
kmeans_value <- kmeans(X, centers = 3)
print(kmeans_value)

Python实现需要提前安装好scikit-learn库和pandas库：

import pandas as pd  
from sklearn.cluster import KMeans  data = pd.read_csv('iris_dataset.csv')  
X = data.iloc[:, :-1].values  
kmeans = KMeans(n_clusters=3, random_state=0).fit(X)  
labels = kmeans.labels_  
centroids = kmeans.cluster_centers_  
print(centroids)