Java|k-means法を作成する【応用情報令和3年春期午後】

今回は応用情報令和3年春期の午後試験の問3（プログラム）で出題された、k-means法（k平均法）について、Javaプログラミングで同じ処理を行うコードを作成してみます。

k-means法について

k-means法はクラスタリングのアルゴリズムの1つです。

与えられたデータからクラスタを適当に選び、クラスタの平均（この問題では重心との距離）からデータを分割するクラスタを調整していく方法です。

k-means法のプログラムの作成

応用情報の問題文と同じ処理をするプログラムを作成しました。実際の問題がこちらになります。

『応用情報技術者過去問題 令和3年春期 午後問3』

サンプルコードでは要素の個数と座標が同じものを2つのクラスタに分けてみます。試験問題では最終的にクラスタは「P₁,P₂ ,P₃,P₇」と「P₄,P₅ ,P₆」に分割されました。

サンプルコードでも同じ結果になるか検証してみましょう。

サンプルコード

サンプルコードを以下に示します。

import java.util.Arrays;

public class K_means {

	static int n = 7, k = 2;
	static double[][] p = { { 1, 0 }, { 2, 1 }, { 4, 1 }, { 1.5, 2 }, { 1, 3 }, { 2, 3 }, { 4, 3 } };
	static int core[] = { 2, 5 };

	public static void main(String[] args) {
		double data_length[] = new double[k];
		double grav_length[] = new double[k];
		int cluster[] = new int[n];
		double[] coordinate_x = new double[k];
		double[] coordinate_y = new double[k];

		for (int s = 0; s < n; s++) {
			for (int t = 0; t < k; t++) {
				data_length[t] = data_dist(s, core[t]);
			}
			cluster[s] = min_index(data_length);
		}

		for (int i = 1; i <= 100; i++) {
			if (i == 1) {
				for (int t = 0; t < k; t++) {
					coordinate_x[t] = gravity_x(t, cluster);
					coordinate_y[t] = gravity_y(t, cluster);
				}
			} else {
				int flag = 0;
				for (int t = 0; t < k; t++) {
					if (coordinate_x[t] != gravity_x(t, cluster) || coordinate_y[t] != gravity_y(t, cluster)) {
						coordinate_x[t] = gravity_x(t, cluster);
						coordinate_y[t] = gravity_y(t, cluster);
						flag++;
					}
				}
				if (flag == 1) {
					break;
				}
			}
		}

		for (int s = 0; s < n; s++) {
			for (int t = 0; t < k; t++) {
				grav_length[t] = grav_dist(s, coordinate_x[t], coordinate_y[t]);

			}
			cluster[s] = min_index(grav_length);
		}

		System.out.println("最終的なクラスタ");
		System.out.println(Arrays.toString(cluster));
	}

	public static double data_dist(int s, int core) {
		double d = Math.pow(p[s][0] - p[core - 1][0], 2) + Math.pow(p[s][1] - p[core - 1][1], 2);
		return Math.sqrt(d);
	}

	public static int min_index(double length[]) {
		double[] scores = length;
		int index = 0;
		double min = scores[0];
		for (int i = 1; i < scores.length; i++) {
			if (scores[i] < min) {
				min = scores[i];
				index = i;
			}
		}
		return index;
	}

	public static double gravity_x(int t, int cluster[]) {
		double sum = 0;
		int x = 0;
		for (int i = 0; i < n; i++) {
			if (cluster[i] == t) {
				sum += p[i][0];
				x++;
			}
		}
		return sum / x;
	}

	public static double gravity_y(int t, int cluster[]) {
		double sum = 0;
		int x = 0;
		for (int i = 0; i < n; i++) {
			if (cluster[i] == t) {
				sum += p[i][1];
				x++;
			}
		}
		return sum / x;
	}

	public static double grav_dist(int s, double coordinate_x, double coordinate_y) {
		double d = Math.pow(p[s][0] - coordinate_x, 2) + Math.pow(p[s][1] - coordinate_y, 2);
		return Math.sqrt(d);
	}
}

出力結果

サンプルコードの出力結果を以下に示します。

最終的なクラスタ
[0, 0, 0, 1, 1, 1, 0]

出力結果ではコアを0と1に分類した配列が出力されています。実際の問題と同じ分割がなされています。

最初に与える値を変えることで、色々な要素で処理できるようになっています。

まとめ

今回はJavaでk-means法を行うコードを記述してみました。