令和3年度 春期 応用情報技術者試験 午後 問題 問3 k-means法によるクラスタ分析のアルゴリズムの理解

表1より、1回目のクラスタ分けでクラスタ2に所属する点は、$P_5$ と $P_6$ である。
問題文の「(3) クラスタの重心を計算し…」より、重心のX座標はクラスタに含まれる点のX座標の平均、Y座標はY座標の平均と定義されている。
$P_5$ の座標は $(1, 3)$、$P_6$ の座標は $(2, 3)$ である。

• X座標の平均：$(1 + 2) \div 2 = 1.5$
• Y座標の平均：$(3 + 3) \div 2 = 3$

したがって、クラスタ2の重心 $G_2$ の座標は (1.5, 3) となる。

高得点のポイント

• クラスタ2に所属する点が $P_5$ と $P_6$ であることを正確に把握できているか。
• 重心の定義に従い、X座標とY座標の平均値を正しく計算できているか。
• 座標の形式 (X, Y) に則って正しく記述できているか。

表2より、1回目の重心の見直し（手順(4)）で各点の「次の所属クラスタ番号」は以下のようになっている。

• クラスタ1：$P_1$, $P_2$, $P_3$, $P_7$
• クラスタ2：$P_4$, $P_5$, $P_6$

手順(5)に従い、再度重心を計算（手順(3)）する。

• クラスタ1の重心 $G_1$
  • X座標の平均：$(1 + 2 + 4 + 4) \div 4 = 11 \div 4 = 2.75$
  • Y座標の平均：$(0 + 1 + 1 + 3) \div 4 = 5 \div 4 = 1.25$
  • よって $G_1 = (2.75, 1.25)$
• クラスタ2の重心 $G_2$
  • X座標の平均：$(1.5 + 1 + 2) \div 3 = 4.5 \div 3 = 1.5$
  • Y座標の平均：$(2 + 3 + 3) \div 3 = 8 \div 3 = 2.66...$（約2.67）
  • よって $G_2 = (1.5, 2.67)$

次に、各点と新しい重心との距離を比較（手順(4)）する。

• $P_1(1, 0)$：$G_1$との距離の2乗 $= (1-2.75)^2+(0-1.25)^2 = 3.0625 + 1.5625 = 4.625$。$G_2$との距離の2乗 $= (1-1.5)^2+(0-2.67)^2 \approx 0.25 + 7.13 = 7.38$。よって $G_1$ が近いのでクラスタ1。
• $P_2(2, 1)$：$G_1$との距離の2乗 $= (2-2.75)^2+(1-1.25)^2 = 0.5625 + 0.0625 = 0.625$。$G_2$との距離の2乗 $= (2-1.5)^2+(1-2.67)^2 \approx 0.25 + 2.79 = 3.04$。よって $G_1$ が近いのでクラスタ1。
• $P_3(4, 1)$：$G_1$との距離の2乗 $= (4-2.75)^2+(1-1.25)^2 = 1.5625 + 0.0625 = 1.625$。$G_2$との距離の2乗 $= (4-1.5)^2+(1-2.67)^2 \approx 6.25 + 2.79 = 9.04$。よって $G_1$ が近いのでクラスタ1。
• $P_4(1.5, 2)$：$G_1$との距離の2乗 $= (1.5-2.75)^2+(2-1.25)^2 = 1.5625 + 0.5625 = 2.125$。$G_2$との距離の2乗 $= (1.5-1.5)^2+(2-2.67)^2 \approx 0 + 0.45 = 0.45$。よって $G_2$ が近いのでクラスタ2。
• $P_5(1, 3)$：$G_2$のX座標は $P_5$ に近く、Y座標も $G_1$ より明らかに近いためクラスタ2。
• $P_6(2, 3)$：$G_2$のX座標は $P_6$ に近く、Y座標も $G_1$ より明らかに近いためクラスタ2。
• $P_7(4, 3)$：$G_1$との距離の2乗 $= (4-2.75)^2+(3-1.25)^2 = 1.5625 + 3.0625 = 4.625$。$G_2$との距離の2乗 $= (4-1.5)^2+(3-2.67)^2 \approx 6.25 + 0.11 = 6.36$。よって $G_1$ が近いのでクラスタ1。

各点の所属クラスタが前回と変わらないため、重心の座標も変わらなくなり、分類が完了する。
最終的に $P_1$ と同じクラスタ1に入るのは、$P_2$、$P_3$、$P_7$ である。

高得点のポイント

• 2回目の重心座標を正しく計算できているか。
• 計算した重心との距離を比較し、各点の新しい所属クラスタを正しく判定できているか。
• 所属クラスタが変わらないことを確認し、最終的なクラスタ1の要素を漏れなく解答できているか。

図2のプログラム関数 clustering の中盤にある、「1回目の重心の計算」と「2回目以降の重心の計算」のループ条件（イ）について考える。

表3より、関数 gravity_x(s) は「クラスタsの重心$G_s$を求め，そのX座標を返す」関数であり、gravity_y(s) は同様にY座標を返す関数である。
プログラム内では coordinate_x[t] ← gravity_x(t) のように呼び出されており、変数 t はクラスタの番号を表している。
問題の分類方法(3)に「$K$ 個のクラスタのそれぞれについて…」とある通り、重心の計算はすべてのクラスタ（1 から $K$ まで）に対して行う必要がある。

プログラム内の他の for ループ（例：for( t を 1 から K まで 1 ずつ増やす )）の記述構文に倣うと、イには t を 1 から K まで 1 ずつ増やす が入る。

高得点のポイント

• 重心計算の対象が全クラスタ（1から $K$）であることを理解できているか。
• プログラム中の他のループ処理の構文（「〜を〜から〜まで1ずつ増やす」）に合わせて正確に記述できているか。

図2のプログラムにおいて、変数 flag は「重心を修正する」処理の中で、座標が変化した場合に 1 が代入されている。
これは、重心の座標が変わったかどうかを判定するためのフラグである。

ウは、「2回目以降の重心の計算」を行う for ループの直前に位置している。
ここでは、各クラスタの重心計算と変更判定（gravity_x(t) と coordinate_x[t] の比較）を行う前に、事前にフラグをリセットしておく必要がある。
もし座標の変化が一つもなければ flag は初期化された値のままとなり、その後のエの判定で「終了して抜ける」処理へ進むことができる。

したがって、変化があった場合に 1 となる flag は、ループに入る前のウで 0 に初期化（代入）しなければならない。
解答は flag ← 0 となる。

高得点のポイント

• 変数 flag が重心変化の有無を記録するフラグであることを理解できているか。
• ループ開始前にフラグを初期化する代入文 flag ← 0 を正しく記述できているか。

図2のプログラム中のエは、「終了して抜ける」ための条件を判定する if 文の条件式である。

問題文の分類方法(5)に「重心の座標が変わらなくなるまで、(3)と(4)を繰り返す」とある。
ウの直後のループ処理内で、重心の座標が前回と異なる（修正された）場合には flag ← 1 が実行される。
逆に、すべてのクラスタで重心の座標が変わらなかった場合、flag はウで初期化された 0 のままとなる。

したがって、アルゴリズムが終了する条件は「重心の座標が変わらなかった場合」、つまり flag が 0 であることとなる。
よって、エには flagが0と等しい が入る。

高得点のポイント

• k-means法の終了条件が「重心の座標が変わらないこと」であることを理解できているか。
• フラグ変数 flag の値を用いて、終了判定の条件式（「〜が〜と等しい」）を適切に記述できているか。

図2のプログラム中のオは、「近い重心を見つける」処理の内部で、点 $P_s$ が次に所属するクラスタ番号を決定する処理である。

直前の for ループ内で、点 $P_s$ と各クラスタの重心 $G_t$ との距離が grav_dist(s, t) で計算され、配列 grav_length[t] に格納されている。
分類方法(4)に「各点から見て距離が最も短い重心（複数存在する場合は、番号が最も小さい重心）を選ぶ。選ばれた重心の番号を、各点が所属する次のクラスタ番号とする」とある。

表3の関数 min_index() は「配列の中で，最小値が格納されている添字sを返す」ものであり、これを活用する。
1回目のクラスタ決定の処理（cluster[s] ← min_index(data_length)）と同様に、重心との距離が格納された grav_length を min_index() の引数として渡し、その結果（最短距離となるクラスタ番号）を cluster[s] に格納すればよい。

したがって、オには cluster[s] ← min_index(grav_length) が入る。

高得点のポイント

• 各点から最も近い重心のクラスタ番号を取得する関数 min_index の使い方を理解できているか。
• 引数として適切な配列 grav_length を指定し、結果を cluster[s] に代入する式を正しく構成できているか。

問題文の〔初期設定の改良〕において、「それまでに決まったコアから離れた点を、より高い確率で選ぶ」アルゴリズムの検討が行われている。

「それまでに決まったコア（コア 1〜コア $t$）と，残った $N－t$ 個の点から選んだ点 $P_s$ との距離の和を $T_s$ とする」と定義されているため、$T_s$ が大きいほど、その点 $P_s$ は既存のコアから離れていることになる。
目的は「離れた点を、より高い確率で選ぶ」ことであるため、$T_s$ の値が「大きい」ほど高い確率で選ばれるように設定すればよい。

したがって、カには「大きい」が入る。正解は ア である。

各選択肢の解説

• ア (大きい): 正解。距離の和 $T_s$ が大きいほど既存のコアから離れているため、改良の目的に合致する。
• イ (小さい): 距離の和 $T_s$ が小さい点は既存のコアに近い点である。これを選びやすくすると「コア間の距離が短いと適切な分類結果を得にくい」という課題を解決できず、誤りである。

問題文より、点 $P_s$ が選ばれる確率は、距離の和 $T_s$ が大きいほど高くなるように設定する。
具体的には、$T_s$ に比例する確率分布を考える。

確率の基本性質として、すべての選択肢（残った $N-t$ 個のすべての点）が選ばれる確率の合計は 1（100%）にならなければならない。
各点の $T_s$ の値に比例し、かつ総和が 1 になるような確率を求めるには、各点の $T_s$ を「すべての $T_s$ の総和」で割ればよい。

問題文では、$N-t$ 個の全ての $T_s$ の和を $Sum$ と定義している。
したがって、点 $P_s$ が選ばれる確率は、$T_s$ を $Sum$ で割った $T_s / Sum$（または $T_s \div Sum$）という式になる。

高得点のポイント

• 確率の総和が 1 になるという基本的な性質を理解できているか。
• 距離の和 $T_s$ に比例する確率を、全体の和 $Sum$ を用いた比（割り算）として正しく数式化できているか。