K 近鄰演算法 (KNN) C 語言完整實作教學

KNN 分類原理與 C 語言從零實作

K-Nearest Neighbors (KNN) 是最經典的監督式分類演算法。核心思想：「靠近朱者赤，靠近墨者黑」——在特徵空間中，若一個待分類樣本的 K 個最近鄰居多數屬於某類別，則該樣本亦屬於該類別。

演算法流程

1. 準備已標記的訓練資料集（特徵向量 + 類別標籤）
2. 輸入待分類測試樣本
3. 計算測試樣本與所有訓練樣本的歐氏距離
4. 選出距離最小的 K 個鄰居
5. 統計這 K 個鄰居的類別分布，少數服從多數，決定測試樣本類別

關鍵資料結構設計

• float **data：動態二維陣列儲存訓練資料 [N][D]
• int *in_cluster：記錄每筆資料所屬類別
• float **karray：[2][K] 暫存「距離、標籤」對，用於維護前 K 小距離

核心函數模組

// 動態配置二維陣列（連續記憶體）
float **createarray(int n, int m) {
    float **arr = malloc(n * sizeof(float *));
    arr[0] = malloc(n * m * sizeof(float));
    for (int i = 1; i < n; ++i) arr[i] = arr[i-1] + m;
    return arr;
}

// 歐氏距離
float distance(float *a, float *b, int dim) {
    float sum = 0;
    for (int i = 0; i < dim; ++i) sum += (a[i]-b[i])*(a[i]-b[i]);
    return sqrtf(sum);
}

// 維護前 K 小距離（插入排序優化）
void update_knn(float **karr, float dist, float label, int K) {
    for (int j = 0; j < K; ++j) {
        if (dist < karr[0][j]) {
            for (int k = K-1; k > j; --k) {
                karr[0][k] = karr[0][k-1];
                karr[1][k] = karr[1][k-1];
            }
            karr[0][j] = dist;
            karr[1][j] = label;
            break;
        }
    }
}

// 多數決
float majority_vote(float *labels, int K) {
    // 簡易計數：假設標籤為 0/1，可擴展為一般情況
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < K; ++i) labels[i] == 0 ? ++cnt0 : ++cnt1;
    return cnt1 > cnt0 ? 1 : 0;
}

完整主程式流程

int main() {
    int K=3, N, D;
    float **data = loadData(&K, &D, &N);  // 讀取 data.txt：首行 K=3,D=8,N=6
    float *test = malloc((D-1)*sizeof(float));
    
    while (1) {
        printf("輸入 %d 維測試資料：", D-1);
        for (int i=0;i

1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5 1
1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8 1
1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2 1
1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5 0
1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5 1
1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 0