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

本連載ではこれまで20近くのアルゴリズムを紹介してきましたが、今回はいよいよ最後のアルゴリズムの紹介となります。難しい内容もあったと思いますが、ここまで読まれたというのは本当に素晴らしいことです。学んだアルゴリズムをさまざまな場面で活用していただければと思います。

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

クラスタリングとは

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