k-means（高校生向け）

正解のないデータを分ける #

線形回帰 では「気温→売上」のように正解（答え）つきのデータから予測の直線を作りました。今回はちがいます。たとえば学年全員の「1 日の勉強時間」と「睡眠時間」を散布図にしたとき、誰がどのタイプかという答えはどこにも書いてありません。

それでも点の集まりを見れば、「よく勉強してよく寝る人たち」「夜ふかし組」のように、いくつかのかたまりが見えてきます。このかたまりを自動で見つけるのがクラスタリングで、k-means はその代表です。

仕組み：重心を置いて、動かす #

k-means は、グループの数 \(k\) を先に決めてから動きます。まず重心を \(k\) 個、適当な場所に置きます（最初はランダムでかまいません）。次に、各点をいちばん近い重心のグループに入れます。そして各グループの重心を、そのグループに入った点の平均の位置に動かします。この「入れる」と「動かす」を、重心が動かなくなるまで繰り返せば完成です。上の図の赤い × 印 3 つが、動き終わった重心です。

動かして見てみよう #

下の図で「再生」を押すと、説明した手順が 1 つずつ進みます。手順ごとの説明は図の下に出ます。

「良い分け方」をどう決める？ #

正解がないので、k-means は自分で基準を持っています。

各点と、自分が入っているグループの重心との距離の 2 乗を全部足した値（まとまりの悪さ）が小さいほど良い。

上の手順の「入れる」と「動かす」は、どちらもこの値を減らす方向にしか動きません。だから繰り返すうちに必ず止まります。ただし「いちばん良い分け方」にたどり着く保証はなく、最初に置いた重心によって結果が変わることがあります。実際のソフト（scikit-learn など）は、最初の置き方を工夫したり、10 回やり直して一番良い結果を選んだりしています。

k はどう決める？ #

\(k\) は人が決めます。目安としてよく使うのがエルボー法です。\(k\) を 1, 2, 3, … と増やしながら「まとまりの悪さ」をグラフにすると、最初は急に下がり、途中からあまり下がらなくなります。その「ひじ（elbow）」のように折れる場所の \(k\) を選びます。

苦手なデータ #

k-means は「重心からの距離」でグループを決めるので、丸いかたまりを見つけるのは得意です。苦手なのは 3 種類あります。1 つ目は三日月形や輪っか状につながったグループで、重心からの距離では月の中央で縦に割れてしまいます。2 つ目は大小のグループが混ざったデータです。k-means では大きい方の端の点が、小さい方の重心に取られてしまいます。3 つ目はひとつだけ極端に離れた点（外れ値）があるデータで、外れ値は重心を自分の方へ引っぱってしまいます。こうしたデータには、密度でつながりを見る DBSCAN など別の方法があります。

やってみよう #

最初の課題は、紙に点を 12 個ほどばらばらに描き、重心を 2 つ置いて、「入れる」と「動かす」を手で 3 回繰り返すことです。重心がどう動くか観察しましょう。二つ目は、「正解ラベルがないのに分けたいデータ」を身の回りで 2 つ考えることです（例：クラスの遊び方のタイプ、好きな音楽の傾向）。三つ目は、三日月形に並んだ点を k = 2 で分けたら、どう分かれてしまうか予想することです。

つぎに読む #

数式（目的関数）と Python での実装、エルボー法のコードは 標準版の k-means にあります。最初の重心の置き方を工夫する方法は k-means++ で扱います。かたまりの形が丸くないデータには DBSCAN、グループの階層が知りたいときは 階層的クラスタリング へ進んでください。