問題プレビューID: 52212f74応用情報技術者試験 2021年(令和3年度)春期 午後

問 3
応用情報技術者試験 2021年(令和3年度)春期 午後

クラスタ分析に用いる k-means 法に関する次の記述を読んで,設問 1~3 に答えよ。

k-means 法によるクラスタ分析は,異なる性質のものが混ざり合った母集団から互いに似た性質をもつものを集め,クラスタと呼ばれる互いに素な部分集合に分類する手法である。新聞記事のビッグデータ検索,店舗の品ぞろえの分類,教師なし機械学習などで利用されている。ここでは,2 次元データを扱うこととする。

〔分類方法と例〕

N 個の点を K 個(N 未満)のクラスタに分類する方法を(1)~(5)に示す。

(1) N 個の点(1 から N までの番号が付いている)からランダムに K 個の点を選び(以下,初期設定という),それらの点をコアと呼ぶ。コアには 1 から K までのコア番号を付ける。なお,K 個のコアの座標は全て異なっていなければならない。

(2) N 個の点と K 個のコアとの距離をそれぞれ計算し,各点から見て,距離が最も短いコア(複数存在する場合は,番号が最も小さいコア)を選ぶ。選ばれたコアのコア番号を,各点が所属する 1 回目のクラスタ番号(1 から K)とする。ここで,二つの点を XY 座標を用いて P=(a, b)と Q=(c, d)とした場合,P と Q の距離を (a−c)2+(b−d)2\sqrt{(a - c)^2 + (b - d)^2} で計算する。

(3) K 個のクラスタのそれぞれについて,クラスタに含まれる全ての点を使って重心を求める。ここで,重心の X 座標をクラスタに含まれる点の X 座標の平均,Y 座標をクラスタに含まれる点の Y 座標の平均と定義する。ここで求めた重心の番号はクラスタの番号と同じとする。

(4) N 個の点と各クラスタの重心(G1,⋯ ,GKG_1, \cdots, G_K)との距離をそれぞれ計算し,各点から見て距離が最も短い重心(複数存在する場合は,番号が最も小さい重心)を選ぶ。選ばれた重心の番号を,各点が所属する次のクラスタ番号とする。

(5) 重心の座標が変わらなくなるまで,(3)と(4)を繰り返す。

次の座標で与えられる 7 個の点を,この分類方法に従い,二つのクラスタに分類する例を図 1 に示す。

P1=(1,0)P_1=(1, 0) P2=(2,1)P_2=(2, 1) P3=(4,1)P_3=(4, 1) P4=(1.5,2)P_4=(1.5, 2) P5=(1,3)P_5=(1, 3) P6=(2,3)P_6=(2, 3) P7=(4,3)P_7=(4, 3)

図 1 7 個の点の分類

[左:7 個の点の散布図。横軸 X(0~4),縦軸 Y(0~3)。
P1=(1,0),P2=(2,1),P3=(4,1),P4=(1.5,2),P5=(1,3),P6=(2,3),P7=(4,3)。
X=1,X=2,X=4 に縦の点線,Y=1,Y=2,Y=3 に横の点線。]
[右:手順]
(1) 初期設定はコア 1=P2,コア 2=P5 とする。
(2) 各点とコアの距離から表 1 のように所属クラスタを求める。
(3) クラスタの重心を計算し,クラスタ 1 の重心 G1 は (2.5, 1.4),
    クラスタ 2 の重心 G2 は[ア]となる。
(4) 各点と重心の距離から表 2 のように所属クラスタを見直す。
(5) (3)と(4)を繰り返し,重心の座標が変わらなくなると①分類が完了する。

表 1 コアとの距離と所属クラスタ

点コア 1 との距離コア 2 との距離所属クラスタ番号
P1P_12\sqrt{2}31
P2P_205\sqrt{5}1
P3P_3213\sqrt{13}1
P4P_45/2\sqrt{5}/25/2\sqrt{5}/21
P5P_55\sqrt{5}02
P6P_6212
P7P_7222\sqrt{2}31

表 2 重心との距離と次の所属クラスタ

点重心 G1G_1 との距離重心 G2G_2 との距離次の所属クラスタ番号
P1P_12.053.041
P2P_20.642.061
P3P_31.553.201
P4P_41.161.002
P5P_52.190.502
P6P_61.670.502
P7P_72.192.501

注記 距離は小数第 3 位以下切捨て

〔クラスタ分析のプログラム〕

この手法のプログラムを図 2 に,プログラムで使う主な変数,関数及び配列を表 3 に示す。ここで,配列の添字は全て 1 から始まり,要素の初期値は全て 0 とする。

表 3 クラスタ分析のプログラムで使う主な変数,関数及び配列

名称種類内容
core[t]配列コア番号が t である点 PmP_m の番号 m を格納する。
initial(K)関数初期設定として次の処理を行う。N 個の点 {P1,P2,⋯ ,PNP_1, P_2, \cdots, P_N} からランダムに異なる K 個を抽出し,その番号を順に配列 core に格納する。
data_dist(s, t)関数点 PsP_s とコア番号が t である点の距離を返す。
grav_dist(s, t)関数点 PsP_s と重心 GtG_t の距離を返す。
data_length[t]配列ある点から見た,コア番号が t である点との距離を格納する。
grav_length[t]配列ある点から見た,重心 GtG_t との距離を格納する。
min_index(引数は data_length 又は grav_length)関数配列の中で,最小値が格納されている添字 s を返す。最小値が二つ以上ある場合は,最も小さい添字を返す。(例 右の配列に対する戻り値は 2。添字 1 2 3 4 5/配列 5 1 4 1 3)
cluster[s]配列点 PsP_s が所属するクラスタ番号を格納する。
coordinate_x[s]配列重心 GsG_s の X 座標を格納する。
coordinate_y[s]配列重心 GsG_s の Y 座標を格納する。
gravity_x(s)関数クラスタ s の重心 GsG_s を求め,その X 座標を返す。
gravity_y(s)関数クラスタ s の重心 GsG_s を求め,その Y 座標を返す。
flag変数フラグ(値は 0 又は 1)

図 2 クラスタ分析の関数 clustering のプログラム

function clustering (N, K)              //N はデータ数,K はクラスタ数
  MaxCount ← 100                       //無限ループを防ぐため最大見直し回数を設定
  initial(K)                           //初期設定
  for( s を1からNまで1ずつ増やす )     //クラスタを決定(1 回目)
    for( t を1からKまで1ずつ増やす )
      data_length[t] ← data_dist(s, core[t])
    endfor
    cluster[s] ← min_index(data_length)
  endfor
  for( p を1からMaxCount まで1ずつ増やす )   //クラスタを見直す
    if( p が1と等しい )
      for( [イ] )                    //1 回目の重心の計算
        coordinate_x[t] ← gravity_x(t)
        coordinate_y[t] ← gravity_y(t)
      endfor
    else
      [ウ]
      for( [イ] )                    //2 回目以降の重心の計算
        if( gravity_x(t)と coordinate_x[t]が異なる   //重心を修正する
            又は gravity_y(t)と coordinate_y[t]が異なる )
          coordinate_x[t] ← gravity_x(t)
          coordinate_y[t] ← gravity_y(t)
          flag ← 1
        endif
      endfor
      if( [エ] )                     //終了して抜ける
        return
      endif
    endif
    for( s を1からNまで1ずつ増やす )   //近い重心を見つける
      for( t を1からKまで1ずつ増やす )
        grav_length[t] ← grav_dist(s, t)
      endfor
      [オ]
    endfor
  endfor
endfunction

〔初期設定の改良〕

このアルゴリズムの最終結果は初期設定に依存し,そこでのコア間の距離が短いと適切な分類結果を得にくい。そこで,関数 initial において一つ目のコアはランダムに選び,それ以降はコア間の距離が長くなる点が選ばれやすくなるアルゴリズムを検討した。検討したアルゴリズムでは,t 番目までのコアが決まった後,t+1 番目のコアを残った点から選ぶときに,それまでに決まったコアから離れた点を,より高い確率で選ぶようにする。具体的には,それまでに決まったコア(コア 1~コア t)と,残った N-t 個の点から選んだ点 PsP_s との距離の和を TsT_s とする。N-t 個の全ての点について TsT_s を求め,TsT_s が[カ]ほど高い確率で点 PsP_s が選ばれるようにする。このとき,点 PsP_s が t+1 番目のコアとして選ばれる確率として[キ]を適用する。

設問1

〔分類方法と例〕について,(1),(2)に答えよ。

(1) 図 1 中の[ア]に入れる座標を答えよ。

(2) 図 1 中の下線①のように分類が完了したときに,P1P_1 と同じクラスタに入る点を全て答えよ。

設問2

図 2 中の[イ]~[オ]に入れる適切な字句を答えよ。

設問3

〔初期設定の改良〕について,(1),(2)に答えよ。

(1) 本文中の[カ]に入れる適切な字句を解答群の中から選び,記号で答えよ。

解答群

ア 大きい  イ 小さい

(2) 本文中の[キ]に入れる適切な式を TsT_s と Sum を使って答えよ。ここで,Sum は N-t 個の全ての TsT_s の和とする。

模範解答

設問1 (1) ア (1.5, 3) (2) P2,P3,P7P_2, P_3, P_7

設問2 イ t を 1 から K まで 1 ずつ増やす ウ flag ← 0 エ flag が 0 と等しい オ cluster[s] ← min_index(grav_length)

設問3 (1) カ ア (2) キ TsT_s/Sum

解説

問 3 では,k-means 法によるクラスタ分析を題材に,アルゴリズムの理解と,その実装について問う。

設問1(1)は,クラスタ 2 に所属する P5=(1,3)P_5=(1, 3) と P6=(2,3)P_6=(2, 3) の重心であり,X 座標の平均は 1.5,Y 座標の平均は 3 となる。(2)は,分類完了時のクラスタ 1 に所属する点であり,表 2 の見直し後の所属から P1P_1 と同じクラスタ 1 は P2,P3,P7P_2, P_3, P_7 である。

設問2のイは,重心計算のループであり,t を 1 から K まで 1 ずつ増やす。ウは,重心の変化を検出するフラグの初期化(flag ← 0)であり,エは,重心が変わらなかった場合の終了条件(flag が 0 と等しい)である。オは,各点の所属クラスタの更新(cluster[s] ← min_index(grav_length))である。

設問3(1)は,コアから離れた点ほど高い確率で選ぶため,TsT_s が大きいほど高い確率となる。(2)は,TsT_s の総和 Sum に対する割合 TsT_s/Sum が選択確率となる。

関連問題

本文が同じ・似ている問題を表示しています