クラスタリングを効率的に解くk-means法

さて、今回扱う問題は「クラスタリング」です。競技プログラミングではあまり出題されない発展的な内容ですが、ぜひ学んでみましょう。

クラスタリングとは

クラスタリングは、近いデータができるだけ同じグループになるように、データをいくつかのグループに分ける問題です。例えば、ある学校の生徒の「数学の成績」と「国語の成績」のデータが与えられたとき、学力の近い人ができるだけ同じクラスになるように3つのクラスに分ける問題は、クラスタリングの問題の1つです。

• 

クラスタリングの単純な解法

それでは、皆さんであれば、どうクラスタリング問題を解くのでしょうか。一番単純な解法は、数学の成績で分けることです。数学の成績が下位1/3の生徒は1組、中位1/3の生徒は2組、上位1/3の生徒は3組といった風に分けます。しかしこの方法では、下図のように、同じクラスでも国語の学力が大きくばらついてしまいます。

• 

また、数学の成績で機械的に分けるのではなく、手作業で良い感じになるように分けるといった方法も考えられます。もちろんこの方法を使えば、下図のように自然なクラス分けができるため、先ほどの問題点は解決できます。しかし、今度は別の問題点が発生します。これはデータ数が増えた場合に対応できないことです。例えば下図の場合、データ数が18人なので手作業でも簡単ですが、データ数が10万や100万になると、手作業では何日もかかってしまいます。そのため、何とかしてコンピュータで機械的に解くアルゴリズムを見つけなければなりません。

• 

効率的な解法：k-means 法

そこでコンピュータを用いてクラスタリングをする方法として、「k-means法」というものが知られています。k-means法は、次のようなアルゴリズムです。

• データをランダムにグループ分けする（この段階では近さなどは考えない）

• 以下の処理を何回か繰り返す

– 各グループについて、重心の位置を計算する

– 各データが属するグループを、「最も重心が近いグループ」に更新する

文章だけでは複雑だと思うので、先ほどのクラス分けの例で理解してみましょう。まず、データをランダムに3つのグループに分けると、以下のようになります。

• 

次に、1組、2組、3組の重心の位置を計算すると、下図左側のようになります。

なお、数学の成績をx、国語の成績をyとするとき、データ(x1,y1),(x2,y2),…,(xn,yn) に対する重心の位置は、((x1+x2+…+xn)/n,(y1+y2+…+yn)/n)という式で計算できます。

続いて、計算した重心を基にグループを割り振りなおすと下図右側のようになります。例えば、国語の点数が最も高いデータは、1組の重心に最も近いため、1組に割り振られます。

• 

最後に、重心の位置を計算し、それを基にグループを割り振りなおすという処理をもう一度行うと、下図のようになります。これでかなり自然なクラス分けになりました。

• 

このようにk-means法を使うと、手作業に頼らなくても、かなり最適に近いグループ分けをすることができます。ただし、k-means法には注意点があります。最初のランダムの運が悪いと上手くいかない場合もあるのです。もしそうなった場合は何回か試したり、より改良された「k-means++法」を使ったりするなどの解決策が有効です。

*　*　*

以上で、本連載で紹介するアルゴリズムは終わりとなります。お疲れさまでした。残る2回は、著者が競技プログラミングの大会に参加して得た体験や競技プログラミングの勉強方法について記しますので、ぜひこちらもご期待ください。