「階層的クラスタリング」の「最短距離法(Single Linkage Method)」とは?初学者の方でもわかりやすいようにまとめました

アルゴリズム

前回は、クラスター分析でよく使う「類似度」を整理整頓した「距離行列」をまとめました。↓

第8回『「距離行列」とは?データ分析手法全般でよく使う「類似度」の扱いをシッカリ学びたいあなたはこちらをどうぞ

 

 

今回はクラスター分析の手順の③で、

実際にクラスタリングするところを説明したいと思います。

 

クラスター分析にはいろいろ種類があるのですが、

その中の「階層的クラスタリング」と呼ばれる、

基本的なクラスター分析のやり方をご紹介します。

 

階層的クラスタリングの中にもさまざまなアルゴリズムがあり、

今回はその中1つの

最短距離法(Single Linkage Method)

をご紹介したいと思います。

ちなみに、最短距離法のことを、別名「単結合法」とも呼びます。

 

 

本記事の概要

クラスター分析でわかること

(前回までの復習をかねているので、わかる方は読み飛ばしてください)

 

クラスター分析」というのは、バラバラでよくわからないものを、

似ているものは同じグループに、似ていないものは違うグループに分けることをいいます。

「グループ分け」することで、よくわからないものが、わりと分かりやすい感じになります。

 

たとえば、

タイトルも目次もない、順序もバラバラの本の原稿用紙を大量に受け取っても、その中身が何なのか理解するのは大変だと思います。

 

でももしも、タイトルや目次がついていたり、文章の構成が前もって分かっていれば、中身の概要はつかめるはずです。

 

この目次や文章の構成というのは、原稿用紙全体をグループ分けしているわけです。

バラバラの内容もグルーピングすることで、中身が理解しやすくなります

 

テキストマイニングでのクラスター分析も、大量の文書の内容が、おおよそどんなものかをグループ分けすることで理解したり、また、どんなグループから構成されているかなど知りたいときにも役に立ちます。

 

大量の文書をクラスター分析すると、その結果からたとえば、”政治”、”食べ物”、”コンピュータ”関係の内容の文書が含まれている、といったことがわかるかもしれません。

 

さらに、食べ物のグループ内を細かく調べたければ、食べ物関係の文書のクラスター分析結果を注目すればいいわけです。

そうすると、食べ物は食べ物でも、”パン”や”果物”についての内容が多く、ごはんや味噌・醤油に関係するものは少ない、といったように、さらに細かい内容を把握することができるわけです。

 

へぇ〜 クラスター分析ってとっても便利なんだね!

 

と思ってもらえたのではないでしょうか^^

 

 

 

 

 

 

「階層的クラスタリング」とは?

クラスター分析(クラスタリング)」には、階層的非階層的なものがありました。(今回は非階層的なものは扱わず、今後の連載でご紹介する予定です)

 

また、「階層的クラスタリング」には、以下の2つの考え方がありました。

  • 1つは、最初に全データを1つのクラスターと考えて、これを分割することでクラスターに分ける方法
  • 2つめは、各データそれぞれを1つのクラスターと最初考えて、クラスター同士をくっつけることで、大きなクラスターにまとめていくという方法

 

今回は、後者の中の方法の中の1つである「最短距離法」についてご紹介します。

クラスター分析の一番シンプルな例で、

他のクラスター分析の基礎となりますので、

その考え方もサクッと理解してもらえたら後の理解も加速するかと思います。

 

 

 

 

「クラスター分析のやり方」とは?

まず、クラスター分析の具体的なやり方についてですが、

大きく3つのステップで行われます。

 

①、データを素性ベクトルに変換する

②、素性ベクトル同士の類似度を計算する

③、類似度に基づいてクラスター分析する

 

①は、前々回までに本連載で数回にわたって詳しく説明してきました。

②は、前回の記事で、類似度と距離行列の関係や距離行列の特徴などをご紹介しました。

 

今回は、②で説明した距離行列から③のクラスター分析を行う部分をご紹介します^^

 

 

 

 

データは、どう、グループ化するの?

今回は、クラスター分析したいデータ全体をたくさんの文書の集合と考えることにします。

また、クラスター分析のスタートは、すべての各文書1つ1つを1つのクラスター(グループ)とみなすところから始めてみます。

今回のクラスター分析は、小さいクラスターをくっつけていって大きくしていくイメージになります。

 

このとき、各文書の特徴は「素性ベクトル」で記述されていて、

文書同士の類似度は、素性ベクトル同士の「類似度」で計算され、「距離行列」に保存されているとします。

 

たとえば、4つの文書のクラスター分析を考えてみましょう。

このとき距離行列Dが、

D = (

文書1文書2文書3文書4
文書1
文書23.6
文書35.78.4
文書46.57.39.1

)

のような下三角行列で表現されているとします。

 

あれ、上半分に値がないじゃない!

 

と思われた方もおられるかもしれませんが、距離行列は対称行列なので、上半分は下半分を対角項を軸に折り返した(転置した)値となっています。

もし??って方は、こちらの記事に詳しく説明があります↓

第8回『「距離行列」とは?データ分析手法全般でよく使う「類似度」の扱いをシッカリ学びたいあなたはこちらをどうぞ

 

 

距離行列中の成分3.6は、2行1列の要素で、文書2と文書1の類似度を表現しています。他の要素も同じ意味です。

 

これを踏まえて、まず最初にどの文書と文書をクラスターにしたらいいでしょうか?

実はこの考え方の違いで、階層的クラスタリングにはいくつかのアルゴリズムがあるわけなんんです。

またその方法の違いによって、そのクラスタリングに適したデータとか適してないデータがあったりします。

 

今回は、「最短距離法(Single Linkage Method)」と呼ばれる方法を、初めて聞いた方でもわかるよう、できるだけわかりやすく説明したいと思います。

 

 

この先は会員限定になります。

会員の方はログインをお願いいたします。

登録がまだの方は、会員登録をお願いします。

>>> 会員登録はこちら

 

 

クラスター分析(クラスタリング)記事一覧はこちら

 

↓こちら無料で読めます

コンテンツの残りを閲覧するにはログインが必要です。 お願い . あなたは会員ですか ? 会員について