クラスタ分析に用いる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の距離をで計算する。
（3）K個のクラスタのそれぞれについて，クラスタに含まれる全ての点を使って重心を求める。ここで，重心のX座標をクラスタに含まれる点のX座標の平均，Y座標をクラスタに含まれる点のY座標の平均と定義する。ここで求めた重心の番号はクラスタの番号と同じとする。
（4）N個の点と各クラスタの重心(G1, …, GK)との距離をそれぞれ計算し，各点から見て距離が最も短い重心（複数存在する場合は，番号が最も小さい重心）を選ぶ。選ばれた重心の番号を，各点が所属する次のクラスタ番号とする。
（5）重心の座標が変わらなくなるまで，（3）と（4）を繰り返す。
次の座標で与えられる7個の点を，この分類方法に従い，二つのクラスタに分類する例を図1に示す。
P1=(1, 0) P2=(2, 1) P3=(4, 1) P4=(1.5, 2) P5=(1, 3) P6=(2, 3) P7=(4, 3)
図1 7個の点の分類
表1 コアとの距離と所属クラスタ
| 点 | コア1と の距離 |
コア2と の距離 |
所属クラ スタ番号 |
| P1 | √2 | 3 | 1 |
| P2 | 0 | √5 | 1 |
| P3 | 2 | √13 | 1 |
| P4 | √5/2 | √5/2 | 1 |
| P5 | √5 | 0 | 2 |
| P6 | 2 | 1 | 2 |
| P7 | 2√2 | 3 | 1 |
表2 重心との距離と次の所属クラスタ
| 点 | 重心G1 との距離 |
重心G1 との距離 |
次の所属 クラスタ番号 |
| P1 | 2.05 | 3.04 | 1 |
| P2 | 0.64 | 2.06 | 1 |
| P3 | 1.55 | 3.20 | 1 |
| P4 | 1.16 | 1.00 | 2 |
| P5 | 2.19 | 0.50 | 2 |
| P6 | 1.67 | 0.50 | 2 |
| P7 | 2.19 | 2.50 | 1 |
〔クラスタ分析のプログラム〕
この手法のプログラムを図2に，プログラムで使う主な変数，関数及び配列を表3に示す。ここで，配列の添字は全て1から始まり，要素の初期値は全て0とする。
表3 クラスタ分析のプログラムで使う主な変数，関数及び配列
| 名称 | 種類 | 内容 |
| core[t] | 配列 | コア番号がtである点Pmの番号mを格納する。 |
| initial(K) | 関数 | 初期設定として次の処理を行う。N個の点{P1, P2, …, PN}からランダムに異なるK個を抽出し，その番号を順に配列coreに格納する。 |
| datadist(s, t) | 関数 | 点Psとコア番号がtである点の距離を返す。 |
| grav_dist(s, t) | 関数 | 点Psと重心Gtの距離を返す。 |
| data_length[t] | 配列 | ある点から見た，コア番号がtである点との距離を格納する。 |
| grav_length[t] | 配列 | ある点から見た，重心Gtとの距離を格納する。 |
| minindex() 引数は data_length 又は grav_length |
関数 | 配列の中で，最小値が格納されている添字sを返す。最小値が二つ以上ある場合は，最も小さい添字を返す。 例 右の配列に対する戻り値は2  |
| cluster[s] | 配列 | 点Psが所属するクラスタ番号を格納する。 |
| coordinatex[s] | 配列 | 重心GsのX座標を格納する。 |
| coordinate_y[s] | 配列 | 重心GsのY座標を格納する。 |
| gravity_x(s) | 関数 | クラスタsの重心Gsを求め，そのX座標を返す。 |
| gravity_y(s) | 関数 | クラスタsの重心Gsを求め，そのY座標を返す。 |
| flag | 変数 | フラグ（値は0又は1） |
図2 クラスタ分析の関数clusteringのプログラム
〔初期設定の改良〕
このアルゴリズムの最終結果は初期設定に依存し，そこでのコア間の距離が短いと適切な分類結果を得にくい。そこで，関数initialにおいて一つ目のコアはランダムに選び，それ以降はコア間の距離が長くなる点が選ばれやすくなるアルゴリズムを検討した。検討したアルゴリズムでは，t番目までのコアが決まった後，t+1番目のコアを残った点から選ぶときに，それまでに決まったコアから離れた点を，より高い確率で選ぶようにする。具体的には，それまでに決まったコア（コア1〜コアt）と，残ったN−t個の点から選んだ点Ps，との距離の和をTsとする。N−t個の全ての点についてTsを求め，Tsが カ ほど高い確率で点Psが選ばれるようにする。このとき，点Psがt+1番目のコアとして選ばれる確率として， キ を適用する。
出典：令和3年度春期 問3
設問1 〔分類方法と例〕について，（1），（2）に答えよ。
（1）図1中の ア に入れる座標を答えよ。
解答・解説
解答例
(1.5, 3)
解説
（2）図1中の下線①のように分類が完了したときに，P1と同じクラスタに入る点を全て答えよ。
解答・解説
解答例
P₂，P₃，P₇
解説
設問2 図2中の イ 〜 オ に入れる適切な字句を答えよ。
解答・解説
解答例
イ：tを1からKまで1ずつ増やす
ウ：flag ← 0
エ：flagが0と等しい
オ：cluster[s] ← min_index(grav_length)
解説
設問3 〔初期設定の改良〕について，（1），（2）に答えよ。
（1）本文中の カ に入れる適切な字句を解答群の中から選び，記号で答えよ。
解答群
- 大きい
- 小さい
解答・解説
解答例
ア
解説
（2）本文中の キ に入れる適切な式をTsとSumを使って答えよ。ここで，SumはN−t個の全てのTsの和とする。
解答・解説
解答例
Ts / Sum
解説
IPA公開情報
出題趣旨
近年，機械学習を利用したデータ分析が多く利用されている。
本問では，データの分類に利用されるクラスタリングを行う手法の一つである k-means 法を題材として，クラスタリングのアルゴリズムの理解と，そのアルゴリズムの実装について問う。
採点講評
問 3 では，クラスタリングを行う手法の一つである k-means 法を題材に，クラスタリングのアルゴリズムに関する理解と実装について出題した。全体として正答率は高かった。
設問 1(2)は，正答率がやや低かった。表 2 の結果を使い，重心とクラスタの見直しを繰り返し，座標が変わらなくなるまで，落ち着いて計算して正答を導き出してほしい。
設問 3 は，正答率がやや高かった。問題文から，各点と既存コアの距離をベースにした確率分布を用いていることが分かるので，確率を TS／Sum とすればよい。これによって，総和が 1 になるなどの確率の基本性質に合致することを理解してほしい。
