多変量解析

k-means法とは?メリットデメリットとRでの実装!

こんにちは!デジタルマーケターのウマたんです!

大学院時代は、クラスター分析を用いて回帰分析の精度を高める手法の研究などを行っていました。

クラスター分析は非常に便利な手法でビジネスの場でもよく使われます。

そんなクラスター分析には実は階層的クラスター分析と非階層的クラスター分析があるということをご存知でしょうか?

階層的クラスター分析は分かりやすく、結果が出た後に分類の様子からクラスタ数を決めることが可能です。ただデータ量が多くなると計算に時間がかかるというデメリットがあります。

一方非階層的クラスター分析は、クラスタ数をあらかじめ決めておかなくてはいけませんが膨大なデータでも比較的計算が早く終わるというメリットがあります。

どちらの手法も一長一短ですが、一般的にビジネスの場では膨大なデータを扱うことが多いため非階層的クラスター分析が良く用いられます。

この記事では、そんな非階層的クラスター分析の中で最もよく用いられるk-means法についてまとめていきます。

k-means法を進化させたx-means法についても紹介していきますので是非参考に!

ウマたん
ウマたん
k-means法についてどこよりも詳しくまとめていくよ!

ちなみにクラスター分析に関してもっと詳しく知りたい方は以下の記事を参考にしてみてください。

クラスター分析 こんにちは!デジタルマーケターのウマたんです! 大量のデータセットをいくつかのグループ・セグメントに分けたい! そん...

k-means法とは

まず、初めにk-means法とは何か見ていきましょう!

1.代表点を適当に決める
2.ユークリッド距離をもとにデータを代表点を持つクラスタに割り当て
3.クラスタの重心点を代表点とする
4.代表点が変わらなければ終了。変われば2へ

具体的にどういうことか図で見ていきます。

まず代表点を適当に決めます。

この際にクラスタが3つなら3つの代表点が選ばれます。

続いてStep2、ユークリッド距離を計算して各データはどの代表点に近いかでグループ分けします。

最初の適当な点が今回は比較的良かったので綺麗に分かれていますが、毎回そうとは限りません。

続いてStep3、各クラスタの重心点を計算します。

このクラスタの重心点が次の代表点になります。

そしてまたStep2に戻って・・・を繰り返して最終的に代表点が動かなくなったら終了!

今回は緑の〇が一つピンクになりました。

※イメージしやすいように手で作っているので少し違和感あるかも

非常に単純なアルゴリズムなんです。

k-means法のメリット

そんなk-means法ですが、どんなメリットがあるのでしょうか?

アルゴリズムが単純で分かりやすい

k-means法のアルゴリズムは図で考えると非常に単純で分かりやすいんです。

アルゴリズムを覚える必要はありませんが、ある程度説明できるのと説明できないのとでは説得力が違います。

計算負荷が少ない

アルゴリズムが単純であることと関連するのですが、その分計算負荷が少ないので膨大なデータに対しても素早く計算することが可能です。

そのため、大量のデータを扱うことの多いビジネスの場ではk-means法が好んで使用されます。

k-means法のデメリット

ただ、一方でk-means法のデメリットも存在します。

クラスタ数をあらかじめ決めなくてはいけない

先ほども書きましたが、k-means法はクラスタ数をあらかじめ決めなくてはいけません。

クラスタ数をいくつか動かしてみて最も最適なクラスタ数を探すと良いでしょう。クラスタに意味を与えるのがマーケターの仕事なのです。

ちなみに自動で最適なクラスタ数を算出してくれる「x-means法」という手法もありますので後で見ていきましょう!

局所最適解になってしまう

代表点を決めてそこから逐次的に最適解を探していくため、局所最適になってしまい、大局的最適解であるとは限りません。

そのため代表点の選び方によって結果が変わることがあります。

k-means法のデメリットを解消した最強の手法「x-means法」

実はk-means法のデメリットを解消した「x-means法」という手法があるんです。

「x-means法」を使えば、最適なクラスタ数を自動で決めてくれるます。

「x-means法」はPelleg and Moore(2000)によって名づけられたもので,始めに十分に小さなクラスタ分割から始めて、各クラスタについて2分割が適当であると判断される限り分割を繰り返すものです。

アルゴリズムは以下のよう。

1.クラスタ数をnとしk-means法を行う。⇛C1,C2,…Cn
2.Ci(i=1,2,…,n)にクラスタ数を2としk-means法を行う。
3.分割前のBIC (ベイズ情報量基準)と分割後のBICを比較し大きくなるならその分割をし,そうでないなら分割しない。
4.2,3を分割できるクラスタがなくなるまで繰り返す。

BICはある種の回帰分析の変数選択の場面で用いられることがある、サンプル数をペナルティ項として課した指標です。

AIC(赤池情報量基準)などと仲間です。

この時、BICの式を簡単に書くと以下のようになります。

BIC=ー(尤度)+k×(サンプル数)

サンプル数が大きければ大きいほどBICは大きくなり、尤度が小さければ小さいほどBICが大きくなります。今回のケースでは、クラスタ内多変量正規分布のばらつきが小さいほど尤度は小さくなります。

そのため、サンプルが多くてかつばらつきが少ないクラスターができるとBICが大きくなるというイメージ。

そのロジックを使って、BICが大きくなるのであれば分割するというようなアルゴリズムになっているのがこのx-means法なのです。

これだけ聞くとx-means法の方が良さそうですが、k-means法は元々局所最適解に陥りやすいのにもかかわらずx-means法はさらに局所最適解に陥りやすくなっています。

簡易的に計算する分にはx-means法を使ってもよいかもしれませんが、最適なクラスタ数を精緻に探す場合はk-means法のほうが良いかもしれません。

詳しくは以下の論文(石岡[2000])を読んでいただくと良いと思います。

k-means法とx-means法をRで実装してみよう!

それでは、最後にk-means法とx-means法をそれぞれRで実装していきましょう!

Rのパッケージ内に入っているk-means法と先ほどの石岡[2000]の論文中のx-means法を使って比較してみます。

(x-means法はパッケージがないので別途実装が必要ですが、ネットにソースが落ちています)

データは、irisというめちゃんこ有名なR内のデータセット(150サンプル5変数で花びらの特徴を表したデータセット)を使います。

3つの花のタイプに分かれているので、そのラベルがk-means法とx-means法で上手く分類できるかどうか見ていきます。

実際に行ってみた結果がこちら

■k-means法

1 2 3
setosa 0 50 0
versicolor 48 0 2
virginica 14 0 36

■x-means法

1 2 3 4 5 6 7 8
setosa 28 22 0 0 0 0 0 0
versicolor 0 0 18 4 6 20 0 2
virginica 0 0 1 13 0 0 12 24

k-means法は明示的にクラスタ数を3と指定しているのでそれなりに綺麗にクラスタが分かれていますが、x-mean法ではクラスタ数が8つに分かれてしまっています・・・

x-means法は非常に便利な手法ですが、気を付けて使わないといけないですね。

ウマたん
ウマたん
やっぱりビジネスシーンではk-means法が無難だね!

k-means法 まとめ

k-mean法について見てきました。

最後にk-means法についてまとめておきましょう!

■k-means法のメリット
・計算負荷が少ない
・アルゴリズムが単純で説明しやすい

■k-means法のデメリット
・クラスタ数をあらかじめ決めなくてはいけない
・局所最適解に陥りやすい

k-mean法はとても優秀で汎用性の高い手法であり、様々なビジネスシーンで使われます。

是非使ってみてください!