前回は、クラスター分析でよく使う「類似度」を整理整頓した「距離行列」をまとめました。↓
第８回『「距離行列」とは？データ分析手法全般でよく使う「類似度」の扱いをシッカリ学びたいあなたはこちらをどうぞ』
今回はクラスター分析の手順の③で、
実際にクラスタリングするところを説明したいと思います。
クラスター分析にはいろいろ種類があるのですが、
その中の「階層的クラスタリング」と呼ばれる、
基本的なクラスター分析のやり方をご紹介します。
階層的クラスタリングの中にもさまざまなアルゴリズムがあり、
今回はその中１つの
「最短距離法（Single Linkage Method）」
をご紹介したいと思います。
ちなみに、最短距離法のことを、別名「単結合法」とも呼びます。
本記事の概要
クラスター分析でわかること
（前回までの復習をかねているので、わかる方は読み飛ばしてください）
「クラスター分析」というのは、バラバラでよくわからないものを、
似ているものは同じグループに、似ていないものは違うグループに分けることをいいます。
「グループ分け」することで、よくわからないものが、わりと分かりやすい感じになります。
たとえば、
タイトルも目次もない、順序もバラバラの本の原稿用紙を大量に受け取っても、その中身が何なのか理解するのは大変だと思います。
でももしも、タイトルや目次がついていたり、文章の構成が前もって分かっていれば、中身の概要はつかめるはずです。
この目次や文章の構成というのは、原稿用紙全体をグループ分けしているわけです。
バラバラの内容もグルーピングすることで、中身が理解しやすくなります。
テキストマイニングでのクラスター分析も、大量の文書の内容が、おおよそどんなものかをグループ分けすることで理解したり、また、どんなグループから構成されているかなど知りたいときにも役に立ちます。
大量の文書をクラスター分析すると、その結果からたとえば、”政治”、”食べ物”、”コンピュータ”関係の内容の文書が含まれている、といったことがわかるかもしれません。
さらに、食べ物のグループ内を細かく調べたければ、食べ物関係の文書のクラスター分析結果を注目すればいいわけです。
そうすると、食べ物は食べ物でも、”パン”や”果物”についての内容が多く、ごはんや味噌・醤油に関係するものは少ない、といったように、さらに細かい内容を把握することができるわけです。
へぇ〜 クラスター分析ってとっても便利なんだね！
と思ってもらえたのではないでしょうか＾＾
「階層的クラスタリング」とは？
「クラスター分析（クラスタリング）」には、階層的・非階層的なものがありました。（今回は非階層的なものは扱わず、今後の連載でご紹介する予定です）
また、「階層的クラスタリング」には、以下の２つの考え方がありました。
- １つは、最初に全データを１つのクラスターと考えて、これを分割することでクラスターに分ける方法
- ２つめは、各データそれぞれを１つのクラスターと最初考えて、クラスター同士をくっつけることで、大きなクラスターにまとめていくという方法
今回は、後者の中の方法の中の１つである「最短距離法」についてご紹介します。
クラスター分析の一番シンプルな例で、
他のクラスター分析の基礎となりますので、
その考え方もサクッと理解してもらえたら後の理解も加速するかと思います。
「クラスター分析のやり方」とは？
まず、クラスター分析の具体的なやり方についてですが、
大きく３つのステップで行われます。
①、データを素性ベクトルに変換する
②、素性ベクトル同士の類似度を計算する
③、類似度に基づいてクラスター分析する
①は、前々回までに本連載で数回にわたって詳しく説明してきました。
②は、前回の記事で、類似度と距離行列の関係や距離行列の特徴などをご紹介しました。
今回は、②で説明した距離行列から③のクラスター分析を行う部分をご紹介します＾＾
データは、どう、グループ化するの？
今回は、クラスター分析したいデータ全体をたくさんの文書の集合と考えることにします。
また、クラスター分析のスタートは、すべての各文書１つ１つを１つのクラスター（グループ）とみなすところから始めてみます。
今回のクラスター分析は、小さいクラスターをくっつけていって大きくしていくイメージになります。
このとき、各文書の特徴は「素性ベクトル」で記述されていて、
文書同士の類似度は、素性ベクトル同士の「類似度」で計算され、「距離行列」に保存されているとします。
たとえば、４つの文書のクラスター分析を考えてみましょう。
このとき距離行列Dが、
D = (
| 文書１ | 文書２ | 文書３ | 文書４ | |
| 文書１ | ０ | |||
| 文書２ | 3.6 | ０ | ||
| 文書３ | 5.7 | 8.4 | ０ | |
| 文書４ | 6.5 | 7.3 | 9.1 | ０ |
)
のような下三角行列で表現されているとします。
あれ、上半分に値がないじゃない！
と思われた方もおられるかもしれませんが、距離行列は対称行列なので、上半分は下半分を対角項を軸に折り返した（転置した）値となっています。
もし？？って方は、こちらの記事に詳しく説明があります↓
第８回『「距離行列」とは？データ分析手法全般でよく使う「類似度」の扱いをシッカリ学びたいあなたはこちらをどうぞ』
距離行列中の成分3.6は、２行１列の要素で、文書２と文書１の類似度を表現しています。他の要素も同じ意味です。
これを踏まえて、まず最初にどの文書と文書をクラスターにしたらいいでしょうか？
実はこの考え方の違いで、階層的クラスタリングにはいくつかのアルゴリズムがあるわけなんんです。
またその方法の違いによって、そのクラスタリングに適したデータとか適してないデータがあったりします。
今回は、「最短距離法（Single Linkage Method）」と呼ばれる方法を、初めて聞いた方でもわかるよう、できるだけわかりやすく説明したいと思います。
最短距離法のアルゴリズムは、以下の感じです。
①、距離行列の最小要素を探す
②、最小要素をもとに、距離行列を更新する
③、新しい距離行列で①、②を繰り返す
④、すべての要素がどれかのグループに属したら終了
といった感じでクラスタリングします。
え？なにこれ！？
と思われたかもしれませんが、１つずつ説明しますので下を読んでみてください＾＾
①、距離行列の最小要素をもとにグループ化する
距離行列が以下のものだとします。
D = (
| 文書１ | 文書２ | 文書３ | 文書４ | |
| 文書１ | ０ | |||
| 文書２ | 3.6 | ０ | ||
| 文書３ | 5.7 | 8.4 | ０ | |
| 文書４ | 6.5 | 7.3 | 9.1 | ０ |
)
最小要素は3.6で、これは２行１列の要素なので、文書２と文書１の類似度だとわかります。
②、最小要素をもとに、距離行列を更新する
最小要素が文書２と文書１の類似度なので、文書２と文書１を１つのクラスターにします。
すると、この新しく作ったクラスターと、それ以外の文書（文書３と文書４）の距離がそれぞれ必要になります。
このとき、新しいクラスター（”文書２１”と呼ぶことにします）と文書３との距離は、
- 文書２と文書３の距離
- 文書１と文書３の距離
の小さいほうを採用します。
上の距離行列をみると、それぞれ
- 文書２と文書３の距離 ＝ 8.4
- 文書１と文書３の距離 ＝ 5.7
なので、小さい5.7を採用するわけです。
同様に、新しいクラスターと文書４の距離は
- 文書２と文書４の距離 ＝ 7.3
- 文書１と文書４の距離 ＝ 6.5
なので、6.5となります。
これらの情報を使って、新しいクラスター文書２１を含んだ距離行列D’に更新します。
D’＝（
| 文書２１ | 文書３ | 文書４ | |
| 文書２１ | ０ | ||
| 文書３ | 5.7 | ０ | |
| 文書４ | 6.5 | 9.1 | ０ |
）
文書３と文書４の距離は変わらず9.1となっています。
③、新しい距離行列で①、②を繰り返す
①、②を繰り返します。
新しい距離行列 D’ で最小の要素は5.7で、それは文書２１と文書３の類似度になっています。
これを新しいクラスター（文書２１３）と考えると、これと文書４との距離が必要になります。
文書２１と文書４の距離は6.5、文書３と文書４の距離は9.1なので、
小さい6.5が採用されます。
すると新しい距離行列 D” ＝ (
| 文書２１３ | 文書４ | |
| 文書２１３ | ０ | |
| 文書４ | 6.5 | ０ |
)
と更新できます。
④、すべての要素がどれかのグループに属したら終了
これ以上グループ化すると、全文書集合になるのでここで終了です。
というわけで、グループ化ができました。
文書１、２、３、４は、
- 文書２と１が似ているグループ１
- 次に、文書２１と３が似ているグループ２
- 文書４が１番似ていない
のように分けることができました。
めでたしです＾＾
このように、類似度の小さい（最短距離）をどんどんくっつけていくので、「最短距離法」と呼ばれているわけです。
ちなみに、この最短距離法を使うときには、データの分布をみてみることが大事です。
最短距離法では、
- メリットとして、よくあるデータの分布が楕円形のような場合だけでなく、例えばバナナのような分布でもクラスタリングできる
- デメリットとしては、データの塊同士が近い場合には、それらを別のクラスターと識別しにくかったり、クラスターが長い鎖のような形をとることがあり、この場合、同じクラスターでも、端と端のデータは性質が大きく違う場合があるので注意が必要
といった特徴があることを知っておくと、実データの分析の際には役に立つかもしれません＾＾
というわけで、今回は階層的クラスタリングの最短距離法について説明しました。
１つ１つ見ていくと、コンピュータでも処理ができる手順の繰り返しなので、大量のデータでもクラスター分析ができることが分かるかと思います。
次回は、その他の階層的クラスタリング手法についてご紹介しようと思います↓
第１０回『「階層的クラスタリング」の「完全連結法（Complete Linkage Method）」とは？初学者の方でも、わかりやすいようにまとめました』
過去記事はこちらです↓
第８回『「距離行列」とは？データ分析手法全般でよく使う「類似度」の扱いをシッカリ学びたいあなたはこちらをどうぞ』
第７回『「クラスター分析」ってどうやるの？クラスター分析のやり方、具体的な３つのステップはこちらです』
第６回『テキストマイニングの「クラスター分析」などで使われる、知らないと恥ずかしい「素性ベクトル作成の定番的方法」とは？』
第５回『テキストマイニングなどの「クラスター分析」で必要な「素性ベクトル」を洗練する２つのテクニックとは？』
第４回『テキストマイニングなどのクラスター分析で必要な「素性ベクトル」をつくりたいあなたが知らないと損をする必須のテクニックとは？』
第３回『テキストマイニングなどのクラスター分析でも重要な「素性ベクトル」を作るための３つのステップとは？』
第２回『テキストマイニングの「クラスター分析」でも必要な「素性ベクトル」とは？なぜ必要なの？』
第１回『「クラスター分析」とは？膨大な情報の内容を、ラク〜にサクッと理解したいあなたはこちらをどうぞ』
こちらの記事もございます
『「機械学習」に入門したいあなたにチェックしてほしい良書、１０冊はこちらです』
『「データマイニング」を勉強したいあなたにチェックしてほしい良書、１０冊はこちらです』
『「エクセル」で「データ分析」できるようになりたいあなたにチェックしてほしい良書１０冊はこちらです』
『「データ分析」を活用したい！けど分からないことだらけの方、その悩みを解決する良書１０冊はこちらです』
『「アンケート調査」をしたいあなたにチェックしてほしい良書、８冊はこちらです』
本連載では、クラスター分析について定期的に更新しています。
Twitterなどフォローしてもらえると、更新情報が届くので便利です！
