C语言如何实现KNN算法？-C语言-盈思创科技

KNN 算法核心思想

KNN 的核心思想可以概括为 “物以类聚，人以群分”。

对于一个待分类的未知数据点,KNN 算法会：

计算距离：计算这个未知点与训练数据集中所有已知点的距离。
寻找邻居：根据距离，找出距离最近的 K 个已知数据点，这 K 个点被称为“邻居”。
投票分类：查看这 K 个邻居的类别，哪个类别占多数，就把未知点归为哪个类别。

关键概念：

K (k)：一个整数，代表要考虑的邻居数量，K 的选择对结果影响很大。
距离度量：通常使用 欧氏距离，对于两个 n 维点 (x1, y1, ..., zn) 和 (a1, b1, ..., an)，它们的欧氏距离为： Distance = sqrt((x1-a1)² + (y1-b1)² + ... + (zn-an)²)

C 语言实现步骤

在 C 语言中实现 KNN，我们需要以下几个步骤：

定义数据结构：
- 创建一个结构体 DataPoint 来表示一个数据点，它需要包含一个特征数组（features[]）和一个类别标签（label）。
- 创建一个结构体 Neighbor 来存储一个邻居点及其与未知点的距离，方便后续排序。
计算距离函数：
- 编写一个函数 calculate_distance，它接收两个 DataPoint 结构体作为参数，并返回它们之间的欧氏距离。
KNN 核心逻辑函数：
- 编写主函数 knn_predict。
- 输入：训练数据集、未知数据点、K 值。
- 过程： a. 为每个训练点计算与未知点的距离，并将点和距离存入一个 Neighbor 结构体数组。 b. 对这个 Neighbor 数组按照距离进行升序排序（从近到远）。 c. 取出前 K 个邻居。 d. 统计这 K 个邻居中各个类别的数量。 e. 找出数量最多的类别，作为预测结果。
- 输出：预测的类别标签。
主函数 main：
- 创建一个小的训练数据集（硬编码）。
- 定义一个或多个未知数据点。
- 调用 knn_predict 函数进行预测。
- 打印预测结果。

完整 C 语言代码示例

这是一个完整的、可运行的 C 语言 KNN 实现，我们用一个简单的二维例子来演示：根据一个人的身高和体重来判断其体型类别（"瘦", "正常", "胖"）。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
// 定义数据点的结构体
typedef struct {
    double features[2]; // 特征，[身高, 体重]
    char label[20];     // 类别标签，"瘦", "正常", "胖"
} DataPoint;
// 定义邻居的结构体，用于存储数据点和其距离
typedef struct {
    DataPoint point;
    double distance;
} Neighbor;
// 函数声明
double calculate_distance(DataPoint a, DataPoint b);
void sort_neighbors(Neighbor neighbors[], int size);
const char* knn_predict(DataPoint training_data[], int training_size, DataPoint unknown_point, int k);
int main() {
    // 1. 创建训练数据集
    // 格式: {身高, 体重}, "类别"
    DataPoint training_data[] = {
        {160.0, 50.0, "瘦"},
        {165.0, 55.0, "瘦"},
        {170.0, 65.0, "正常"},
        {175.0, 70.0, "正常"},
        {180.0, 85.0, "胖"},
        {185.0, 90.0, "胖"},
        {168.0, 58.0, "瘦"},
        {172.0, 68.0, "正常"},
        {178.0, 78.0, "正常"},
        {182.0, 88.0, "胖"}
    };
    int training_size = sizeof(training_data) / sizeof(training_data[0]);
    // 2. 定义未知数据点
    DataPoint unknown_person1 = {172.0, 60.0}; // 一个待分类的人
    DataPoint unknown_person2 = {178.0, 95.0}; // 另一个待分类的人
    // 3. 设置 K 值
    int k = 3;
    // 4. 进行预测并打印结果
    printf("--- KNN 分类器演示 (K=%d) ---\n\n", k);
    const char* prediction1 = knn_predict(training_data, training_size, unknown_person1, k);
    printf("未知人员1 (身高: %.1f, 体重: %.1f) 的预测类别是: %s\n", 
           unknown_person1.features[0], unknown_person1.features[1], prediction1);
    const char* prediction2 = knn_predict(training_data, training_size, unknown_person2, k);
    printf("未知人员2 (身高: %.1f, 体重: %.1f) 的预测类别是: %s\n", 
           unknown_person2.features[0], unknown_person2.features[1], prediction2);
    return 0;
}
/**
 * @brief 计算两个数据点之间的欧氏距离
 */
double calculate_distance(DataPoint a, DataPoint b) {
    double sum = 0.0;
    for (int i = 0; i < 2; i++) { // 假设特征维度是2
        sum += pow(a.features[i] - b.features[i], 2);
    }
    return sqrt(sum);
}
/**
 * @brief 对邻居数组进行排序（使用简单的冒泡排序）
 * 排序依据是 distance，从小到大
 */
void sort_neighbors(Neighbor neighbors[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (neighbors[j].distance > neighbors[j+1].distance) {
                // 交换
                Neighbor temp = neighbors[j];
                neighbors[j] = neighbors[j+1];
                neighbors[j+1] = temp;
            }
        }
    }
}
/**
 * @brief KNN 预测函数
 * @param training_data 训练数据集
 * @param training_size 训练数据集大小
 * @param unknown_point 未知数据点
 * @param k K 值
 * @return 预测的类别标签字符串
 */
const char* knn_predict(DataPoint training_data[], int training_size, DataPoint unknown_point, int k) {
    // 1. 为所有训练点计算距离并存储
    Neighbor neighbors[training_size];
    for (int i = 0; i < training_size; i++) {
        neighbors[i].point = training_data[i];
        neighbors[i].distance = calculate_distance(training_data[i], unknown_point);
    }
    // 2. 按距离对邻居进行排序
    sort_neighbors(neighbors, training_size);
    // 3. 统计前 K 个邻居的类别
    int label_counts[3] = {0}; // 假设我们有3个类别：瘦, 正常, 胖
    const char* labels[] = {"瘦", "正常", "胖"};
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 3; j++) {
            if (strcmp(neighbors[i].point.label, labels[j]) == 0) {
                label_counts[j]++;
                break;
            }
        }
    }
    // 4. 找出数量最多的类别
    int max_count = label_counts[0];
    int predicted_label_index = 0;
    for (int i = 1; i < 3; i++) {
        if (label_counts[i] > max_count) {
            max_count = label_counts[i];
            predicted_label_index = i;
        }
    }
    return labels[predicted_label_index];
}

代码详解

DataPoint 和 Neighbor 结构体：
- DataPoint 存储了机器学习中一个样本的核心信息：特征和标签。
- Neighbor 是一个辅助结构体，它将 DataPoint 和计算出的 distance 绑定在一起，这使得在排序后，我们既能知道距离，又能知道对应的是哪个数据点。
calculate_distance 函数：
- 这是一个纯数学函数,根据欧氏距离公式计算两点间距离。pow() 函数用于计算平方，sqrt() 用于开方，它们都来自 <math.h> 库。
sort_neighbors 函数：
- KNN 的关键一步是找到最近的 K 个点，这需要对距离进行排序。
- 为了简单,这里使用了冒泡排序，对于小型数据集，它足够用，如果训练数据集非常大，应该使用更高效的排序算法，如快速排序或 C 标准库中的 qsort。
- 排序的依据是 Neighbor 结构体中的 distance 成员变量。
knn_predict 函数：
- 这是整个算法的核心。
- 第一步：计算距离，遍历整个训练集，为每个点计算与未知点的距离，并存入 neighbors 数组。
- 第二步：排序，调用 sort_neighbors 对邻居数组进行排序。
- 第三步：投票，取排序后数组的前 k 个元素（即最近的 K 个邻居），遍历这 K 个邻居，统计它们各自类别出现的次数，这里我们用一个 label_counts 数组来计数。
- 第四步：决策，在 label_counts 数组中找到值最大的那个索引，然后用这个索引从 labels 数组中取出对应的类别名称作为最终预测结果。
main 函数：
- 作为程序的入口,它负责准备数据（创建训练集和未知点），设置参数（K 值），然后调用 knn_predict 函数并打印结果。

如何编译和运行

因为代码中使用了 <math.h> 库（sqrt, pow），所以在编译时需要链接数学库。

将代码保存为文件,knn_example.c。
打开终端或命令提示符。
使用 GCC 进行编译，并加上 -lm 选项：
```
gcc knn_example.c -o knn_example -lm
```
- gcc knn_example.c：编译 C 文件。
- -o knn_example：指定输出的可执行文件名为 knn_example。
- -lm：链接数学库。
运行生成的可执行文件：
```
./knn_example
```

预期输出：

--- KNN 分类器演示 (K=3) ---
未知人员1 (身高: 172.0, 体重: 60.0) 的预测类别是: 瘦
未知人员2 (身高: 178.0, 体重: 95.0) 的预测类别是: 胖

(注意：根据 K 值和数据的随机性，结果可能会有微小差异，但大体趋势是一致的)

优缺点与改进方向

优点：

简单易懂：算法逻辑直观，实现相对容易。
无需训练：KNN 是一个“懒惰学习器”（Lazy Learner），它没有明确的训练阶段，只是在需要预测时才进行计算。
适应性强：可以用于分类和回归问题。

缺点：

计算成本高：每次预测都需要计算与所有训练点的距离，如果训练集很大，预测会非常慢。
内存消耗大：需要存储整个训练数据集。
对 K 值和距离敏感：K 的选择以及距离度量方式（如曼哈顿距离）对结果影响很大。
特征尺度敏感：如果特征的尺度差异很大（身高单位是米，体重单位是公斤），那么尺度大的特征会主导距离计算，通常需要对数据进行归一化或标准化处理。

改进方向：

数据预处理：在计算距离前，对所有特征进行归一化（将所有值缩放到 [0, 1] 区间）。
使用更高效的排序：用 qsort 替换冒泡排序。
使用 KD-Tree 或 Ball-Tree：对于高维和大规模数据集，可以使用这些空间索引数据结构来加速“寻找最近邻”的过程，而无需计算所有点的距离。
交叉验证选择 K：通过实验来找到一个最优的 K 值，而不是凭空设定。

C语言如何实现KNN算法？

目录