アルゴリズム

C言語で実装するk-Meansクラスタリングの反復アルゴリズムについて解説

2025-04-15更新日: 2025-04-15

本記事ではC言語でのk-meansクラスタリング実装について解説します。

反復型アルゴリズムを用い、初期クラスタ中心の選定から各データ点を最も近い中心に割り当て、更新を繰り返す処理でグループ分けする方法を紹介します。

理解の助けとなる実装例を通して、処理の流れを確認いただけます。

目次から探す

k-Meansクラスタリングの基本
- アルゴリズムの流れ
C言語での実装準備
- 開発環境の確認
- 使用するライブラリとヘッダファイル
実装設計
デバッグとテスト
まとめ

k-Meansクラスタリングの基本

アルゴリズムの流れ

k-Meansクラスタリングは、データ点をあらかじめ設定したクラスタ数に分割する手法です。

アルゴリズムは以下の流れで進みます。

データ点の割り当て方法

各データ点は、各クラスタ中心との距離を計算し、最も近いクラスタに割り当てます。

距離の計算方法は以下のユークリッド距離の式に基づいています。

$d = \sqrt{(x - c_{x})^{2} + (y - c_{y})^{2}}$

ここで、 $(x, y)$ はデータ点の座標、 $(c_{x}, c_{y})$ はクラスタ中心の座標です。

クラスタ中心の更新手順

全てのデータ点が割り当てられた後、各クラスタ内のデータ点の平均座標を新たなクラスタ中心として更新します。

新しいクラスタ中心は、次のように計算されます。

$c_{x} = \frac{1}{N} \sum_{i = 1}^{N} x_{i}, c_{y} = \frac{1}{N} \sum_{i = 1}^{N} y_{i}$

ここで、 $N$ はクラスタに含まれるデータ点の数です。

収束条件の確認

反復処理を続け、各クラスタ中心がほとんど動かなくなった場合や、データ点の割り当てが変更されなくなった場合でアルゴリズムは終了します。

中心の移動量が $ε$ 以下の場合や、指定した反復回数に達した場合に終了条件が成立すると判断します。

C言語での実装準備

C言語でk-Meansクラスタリングを実装するために、まずは開発環境の確認と使用するライブラリ・ヘッダファイルの準備を行います。

開発環境の確認

C言語のコンパイル環境が整っていることを確認してください。

GNUコンパイラ(gcc)やClangコンパイラなどが利用可能であれば、実装を問題なく進めることができます。

エディタやIDEも使いやすいものを選んでください。

使用するライブラリとヘッダファイル

実装では、以下のヘッダファイルが必要になります。

<stdio.h> … 入出力に関する関数を利用するため
<stdlib.h> … メモリ確保や乱数生成の関数を利用するため
<math.h> … 距離計算など数学的な関数を利用するため

例えば、サンプルコードでは以下のように記述します。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

実装設計

実装設計では、データ構造の定義、各処理の実装方法について詳しく解説します。

データ構造の定義

まず、データ点とクラスタ中心を管理するための構造体を定義します。

これにより、データをわかりやすく管理できるようになります。

データ点管理用構造体

データ点を管理するための構造体は、座標情報を保持するために以下のように定義できます。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
    double x;  // x座標
    double y;  // y座標
    int cluster;  // 割り当てられたクラスタ番号
} DataPoint;

クラスタ中心管理用構造体

クラスタ中心を管理する構造体は、各クラスタの中心座標や、所属するデータ点の数を記録するために以下のように定義できます。

typedef struct {
    double x;  // クラスタ中心のx座標
    double y;  // クラスタ中心のy座標
    int count; // クラスタに属するデータ点の数
} ClusterCenter;

初期クラスタ設定の実装

初期クラスタ設定では、データ点の中からランダムにまたは最初のいくつかの点をクラスタ中心として選ぶ方法があります。

以下は、簡単なランダム初期化の例です。

#include <time.h>
// クラスタ中心をランダムに初期化するサンプル関数
void initializeClusterCenters(ClusterCenter centers[], DataPoint data[], int numClusters, int numPoints) {
    srand((unsigned)time(NULL));
    for (int i = 0; i < numClusters; i++) {
        int index = rand() % numPoints;
        centers[i].x = data[index].x;
        centers[i].y = data[index].y;
        centers[i].count = 0;
    }
}

距離計算の実装

ユークリッド距離の算出方法

ユークリッド距離は、上記でも説明した通り、2点間の直線距離を求める際に利用します。

以下はユークリッド距離を計算する関数のサンプルコードです。

// 2点間のユークリッド距離を計算する関数
double calculateEuclideanDistance(DataPoint a, ClusterCenter b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

クラスタ割り当て処理

各データ点に対して、全てのクラスタ中心までの距離を計算し、最も近いクラスタを割り当てます。

以下は、その処理の簡単な例です。

void assignClusters(DataPoint data[], ClusterCenter centers[], int numPoints, int numClusters) {
    for (int i = 0; i < numPoints; i++) {
        double minDistance = 1e9;  // 非常に大きな初期値
        int minCluster = -1;
        for (int j = 0; j < numClusters; j++) {
            double distance = calculateEuclideanDistance(data[i], centers[j]);
            if (distance < minDistance) {
                minDistance = distance;
                minCluster = j;
            }
        }
        data[i].cluster = minCluster;
    }
}

クラスタ中心更新処理

データ点の割り当て後、各クラスタ内の全データ点の平均座標を計算し、新たなクラスタ中心とします。

以下のコード例はその処理を示しています。

void updateClusterCenters(DataPoint data[], ClusterCenter centers[], int numPoints, int numClusters) {
    // 一度、全クラスタの合計とカウントをリセット
    for (int j = 0; j < numClusters; j++) {
        centers[j].x = 0;
        centers[j].y = 0;
        centers[j].count = 0;
    }
    // 各クラスタに所属するデータ点の合計を計算
    for (int i = 0; i < numPoints; i++) {
        int cluster = data[i].cluster;
        centers[cluster].x += data[i].x;
        centers[cluster].y += data[i].y;
        centers[cluster].count++;
    }
    // 各クラスタの平均を新たな中心とする
    for (int j = 0; j < numClusters; j++) {
        if (centers[j].count > 0) {
            centers[j].x /= centers[j].count;
            centers[j].y /= centers[j].count;
        }
    }
}

反復処理と収束判定

k-Meansクラスタリングは、中心が収束するまで、クラスタ割り当てと中心更新の処理を反復します。

収束判定は、各クラスタ中心の移動量が所定の閾値 $ε$ 以下であるか、もしくは反復回数が上限に達した場合に行います。

以下は、シンプルな反復処理の例です。

#define MAX_ITERATIONS 100
#define EPSILON 0.001
int main() {
    // サンプルデータの作成
    int numPoints = 6;
    int numClusters = 2;
    DataPoint data[6] = {
        {1.0, 2.0, -1},
        {1.5, 1.8, -1},
        {5.0, 8.0, -1},
        {8.0, 8.0, -1},
        {1.0, 0.6, -1},
        {9.0, 11.0, -1}
    };
    ClusterCenter centers[2];
    initializeClusterCenters(centers, data, numClusters, numPoints);
    for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
        // 古い中心を保存
        ClusterCenter oldCenters[2];
        for (int j = 0; j < numClusters; j++) {
            oldCenters[j] = centers[j];
        }
        // 各データ点にクラスタを割り当て
        assignClusters(data, centers, numPoints, numClusters);
        // クラスタ中心を更新
        updateClusterCenters(data, centers, numPoints, numClusters);
        // 収束判定
        int converged = 1;
        for (int j = 0; j < numClusters; j++) {
            double dx = centers[j].x - oldCenters[j].x;
            double dy = centers[j].y - oldCenters[j].y;
            if (sqrt(dx * dx + dy * dy) > EPSILON) {
                converged = 0;
                break;
            }
        }
        if (converged) {
            break;
        }
    }
    // 結果の表示
    printf("クラスタごとのデータ点の割り当て結果:\n");
    for (int i = 0; i < numPoints; i++) {
        printf("データ点(%f, %f) -> クラスタ%d\n", data[i].x, data[i].y, data[i].cluster);
    }
    return 0;
}

クラスタごとのデータ点の割り当て結果:
データ点(1.000000, 2.000000) -> クラスタ0
データ点(1.500000, 1.800000) -> クラスタ0
データ点(5.000000, 8.000000) -> クラスタ1
データ点(8.000000, 8.000000) -> クラスタ1
データ点(1.000000, 0.600000) -> クラスタ0
データ点(9.000000, 11.000000) -> クラスタ1