問題
k-means はラベルのないデータからグループを見つけます。与えられた重心から始めて、iterations 回繰り返します。
- 割り当て：各点を、最も近い重心（ユークリッド距離）のクラスタに入れます。2つの重心が同じ距離なら、インデックスが小さい方を選びます。
- 更新：各重心を、割り当てられた点の平均に移動します。点が1つもない重心はそのままです。
k_means(points, centroids, iterations) を実装してください。
入力
points: データ点。各点は座標のリストです。
centroids: k 個の初期重心。座標の数は点と同じです。
iterations: 割り当てと更新を何回行うか。
出力
最終的な重心を元の順序で返してください。
制約
1 ≤ 点の数 ≤ 1,000、1 ≤ k ≤ 20、1 ≤ 次元数 ≤ 10
0 ≤ iterations ≤ 100
-1,000 ≤ 各座標 ≤ 1,000
例
例 1
入力：
points = [
[1.0, 1.0],
[1.5, 2.0],
[8.0, 8.0],
[9.0, 8.5]
]
centroids = [
[0.0, 0.0],
[10.0, 10.0]
]
iterations = 1
期待される出力：
expected = [
[1.25, 1.5],
[8.5, 8.25]
]入力：
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{1.5, 2.0},
{8.0, 8.0},
{9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
{0.0, 0.0},
{10.0, 10.0}
};
long long iterations = 1;
期待される出力：
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};入力：
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {1.5, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
new double[] {0.0, 0.0},
new double[] {10.0, 10.0}
};
long iterations = 1;
期待される出力：
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};解説
最初の2点は (0, 0) に近く、最後の2点は (10, 10) に近いです。新しい重心はそれぞれの平均で、((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) と ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25) です。
例 2
入力：
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
期待される出力：
expected = [
[3.666667],
[100.0]
]入力：
std::vector<std::vector<double>> points = {
{0.0},
{1.0},
{10.0}
};
std::vector<std::vector<double>> centroids = {
{0.0},
{100.0}
};
long long iterations = 2;
期待される出力：
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};入力：
double[][] points = new double[][] {
new double[] {0.0},
new double[] {1.0},
new double[] {10.0}
};
double[][] centroids = new double[][] {
new double[] {0.0},
new double[] {100.0}
};
long iterations = 2;
期待される出力：
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};解説
1回目：(100) はどの点からも遠いので、3点すべてが重心1に入り、重心1は (0 + 1 + 10) / 3 ≈ 3.666667 に移動します。重心2には点がないので 100 のままです。2回目も同じ割り当てになるので、結果は [[3.666667], [100]] です。
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。