応用情報技術者 2021年 春期 午後 問03

解答の論理構成

1. 【問題文】の手順(3)には
   「クラスタの重心を求める。ここで、重心の X 座標をクラスタに含まれる点の X 座標の平均、Y 座標をクラスタに含まれる点の Y 座標の平均と定義する。」
   とあります。したがって重心Ｇ₂はクラスタ2に入った点の平均座標で決まります。
2. クラスタ番号は手順(2)によって決まり、その結果が【表1】です。表1で「所属クラスタ番号」が"2"になっているのは
   ・$P_5$＝(1, 3)
   ・$P_6$＝(2, 3)
   の2点だけです。
3. そこで平均を取ります。
   X 座標：$(1＋2)/2=1.5$
   Y 座標：$(3＋3)/2=3$
   よって重心Ｇ₂＝(1.5, 3)。
4. 図1中のアはＧ₂の座標を示す欄なので、解答は(1.5, 3)となります。

誤りやすいポイント

• 【表1】を読み違え、$P_7$をクラスタ2に含めてしまうと平均値がずれます。クラスタ2に属するのは「所属クラスタ番号」が"2"の行のみです。
• 手順(3)の「平均」は各座標軸ごとに求める点が重要です。X と Y を合算して2で割るなどの操作は誤りです。
• 重心が一意に決まるのは手順(2)を正しく実施したときだけです。初期設定のコア座標を使って平均を取ってしまうミスが散見されます。

FAQ

解答の論理構成

• 【問題文】の手順(1)により初期設定は「コア1＝$P_2$、コア2＝$P_5$」です。
• 手順(2)で全点とコアの距離を計算した結果が【表1】です。ここで「所属クラスタ番号」が
  ・クラスタ1：$P_1$、$P_2$、$P_3$、$P_4$、$P_7$
  ・クラスタ2：$P_5$、$P_6$
  となります。
• 手順(3)で各クラスタの重心を求めます。クラスタ1の重心は【問題文】にあるとおり
  「クラスタ1の重心 $G_1$ は (2.5, 1.4)」です。
  クラスタ2は $P_5(1,3)$ と $P_6(2,3)$ だけなので $$G_2=\left(\frac{1+2}{2},\frac{3+3}{2}\right)=(1.5,3)$$
• 手順(4)で各点と $G_1$, $G_2$ の距離を比較した結果が【表2】です。ここで「次の所属クラスタ番号」は
  ・クラスタ1：$P_1$、$P_2$、$P_3$、$P_7$
  ・クラスタ2：$P_4$、$P_5$、$P_6$
  となり、$P_1$ と同じクラスタに残ったのは $P_2$, $P_3$, $P_7$ です。
• 手順(5)で重心を再計算しても座標が変化しないため【問題文】の「①分類が完了する」状態に到達します。
• 以上より、求める解答は【模範解答】のとおり
  $P_2$, $P_3$, $P_7$ となります。

誤りやすいポイント

• 【表1】と【表2】の「距離」を眺めただけで判断し、クラスタ番号を写し間違える。距離が小さい方に対応する番号を再確認しましょう。
• $P_4$ が最後にクラスタ2へ移動する点を見落とし、$P_4$ まで解答に含めてしまう。
• 最終重心を再計算せず「1 回目の結果＝最終結果」と思い込む。k-means 法は“重心が変わらなくなるまで”が条件です。

FAQ

解答の論理構成

1. 【問題文】図2には
   for( イ ) //1 回目の重心の計算
   とあり、直前の行で if( p が 1 と等しい ) と分岐しています。重心はクラスタごとに 1 つなので、ここでループ変数はコアや重心に対応する t でなければなりません。さらに他のループ宣言は
   for( t を 1 から K まで 1 ずつ増やす )
   という書式で統一されています。したがってイは
   tを1からKまで1ずつ増やす
   となります。
2. 2 回目以降の見直しでは、重心を修正したかどうかを判定するフラグが必要です。図2には
   flag <- 1
   とセットする処理が示されており、その前で必ず 0 に初期化する必要があります。従って ウ は
   flag ← 0
   です。
3. フラグが更新されなければ収束したと判断して終了します。図2のコメント
   //終了して抜ける
   に対応する条件は「flag が 0 と等しい」となります。よって エ は
   flagが0と等しい
   です。
4. 各データ点が最も近い重心に属するようクラスタ番号を付け替える処理が
   for( s を 1 から N まで 1 ずつ増やす ) //近い重心を見つける
   の後に置かれています。距離を格納した grav_length 配列から最小値の添字を取り、その添字をクラスタ番号とするのは 1 回目の割当てと同じパターンです。図2の 1 回目では
   cluster[s] <- min_index(data_length)
   を使っているため、オ は同じ書式で
   cluster[s] ← min_index(grav_length)
   となります。

誤りやすいポイント

• イを s を 1 から N まで と誤ってデータ数で回してしまうと、重心計算が「クラスタ×データ点」の二重ループになり計算量が激増します。
• ウの初期化を忘れると、前回のループで立てた flag が残り続け、実際は重心が動いているのに即終了するバグが発生します。
• エの判定を flag が 1 と等しい と逆に書くと、重心が動いたときに終了してしまい、正しい収束判定ができません。
• オを min_value といった距離の最小値に置き換えてしまうと、「どのクラスタに属するか」という“添字”情報が失われます。

FAQ

解答の論理構成

1. 問題文は初期設定の改良意図を次のように述べています。
   「それまでに決まったコアから離れた点を、より高い確率で選ぶようにする。」
   ここで“離れた”とは距離の総和 $T_s$ が大きい点を指します。
2. 続いて
   「$T_s$がカほど高い確率で点$P_s$が選ばれるようにする。」
   という一文があり、“離れた点ほど”に対応して カ には「大きい」が入るのが自然です。
3. 以上より、カ＝「大きい」と判断できます。

誤りやすいポイント

• 「離れた点を高確率で選ぶ」の逆に解釈し、“距離が小さい点”を優先すると勘違いしやすいです。
• $T_s$ は“距離の和”なので、距離が大きいほど $T_s$ も大きくなることを見落とすと判断を誤ります。
• k-means 全体の手順と“初期コア選択”の目的を混同し、後半の重心計算ロジックと同じ最小距離基準で考えてしまう失敗がよく見られます。

FAQ

解答の論理構成

1. 問題文は「それまでに決まったコア（コア 1～コア t）と、残った N−t 個の点から選んだ点 $P_s$ との距離の和を $T_s$ とする。N−t 個の全ての点について $T_s$ を求め、$T_s$ がカほど高い確率で点 $P_s$ が選ばれるようにする。」と述べています。
2. つまり「$T_s$ が大きい点ほど選ばれやすい＝確率は $T_s$ に比例」させたい、という要求です。
3. 確率の総和は 1 でなければなりません。よって、$T_s$ をそのまま使うのではなく正規化します。
4. 正規化の最も標準的な方法は「個々の $T_s$ を全体の和で割る」ことです。問題文でも「N−t 個の全ての $T_s$ の和」を Sum と定義しています。
5. したがって、点 $P_s$ が t+1 番目のコアとして選ばれる確率は
   $\frac{T_s}{\text{Sum}}$
   となり、これが解答欄 キ に入る式です。

誤りやすいポイント

• 「大きい $T_s$ ほど高い確率」と読んで、単に $T_s$ を確率として採用してしまう。確率は 0〜1 に収まり、合計が 1 になる必要がある点を失念しがちです。
• $\text{Sum}$ を「最大値」や「平均値」と勘違いしてしまう。問題文は「N−t 個の全ての $T_s$ の和」と明記しているので注意しましょう。
• $T_s/\text{Sum}$ ではなく $\text{Sum}/T_s$ と逆に書いてしまうミス。比例・反比例の違いを図で確認すると防げます。

FAQ