Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!
スポンサーリンク

「階層的クラスタリング」の「完全連結法(Complete Linkage Method)」とは?初学者の方でも、わかりやすいようにまとめました

スポンサーリンク
完全連結法 クラスター分析 クラスタリング complete linkage method 階層的クラスタリング アルゴリズム アルゴリズム
完全連結法 クラスター分析 クラスタリング complete linkage method 階層的クラスタリング アルゴリズム
スポンサーリンク
スポンサーリンク

前回は、クラスター分析でよく使う「最短距離法」という階層的クラスタリングの手法についてまとめました↓

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

 

 

今回はその続きで、「階層的クラスタリング」の第2弾となります。

 

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

今回はその中1つの

完全連結法(Complete Linkage Method)

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

 

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

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

 

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

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

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

 

たとえば、

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

 

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

 

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

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

 

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

 

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

 

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

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

 

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

 

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

 

 

 

 

 

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

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

 

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

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

 

今回は、後者の1つである「完全連結法」についてご紹介します。

クラスター分析の単結合法と同様に、シンプルで、他のクラスター分析の基礎となります。

クラスタリングの考え方をサクッと理解してもらえたら後の理解も加速するかと思います。

 

 

 

 

 

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

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

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

 

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

このとき距離行列 D が、

D = (

文書1 文書2 文書3 文書4
文書1
文書2 3.6
文書3 5.7 8.4
文書4 6.5 7.3 9.1

)

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

 

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

 

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

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

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

 

 

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

 

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

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

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

 

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

 

完全連結法のアルゴリズムは、以下の感じです。

①、距離行列の最小要素を探す

②、その要素をもとに、距離行列を更新する

③、新し距離行列で①、②を繰り返す

④、すべての要素がどれかのグループに属したら終了

といった感じでクラスタリングします。

 

え?意味がわからない!?

 

と思われたかもしれませんが、1つずつ説明しますので下を読んでみてください^^

 

 

 

 

 

①、距離行列の要素をもとにグループ化する

距離行列が以下のものだとします。

D = (

文書1 文書2 文書3 文書4
文書1
文書2 3.6
文書3 5.7 8.4
文書4 6.5 7.3 9.1

)

最小要素は3.6で、これは2行1列の要素なので、文書2と文書1の類似度だとわかります。

 

②、最小要素をもとに、距離行列を更新する

最小要素が文書2と文書1の類似度なので、文書2と文書1を1つのクラスターにします。

 

すると、この新しく作ったクラスターと、それ以外の文書(文書3と文書4)の距離がそれぞれ必要になります。

 

このとき、新しいクラスター(”文書21”と呼ぶことにします)と文書3との距離は、

  • 文書2と文書3の距離
  • 文書1と文書3の距離

大きい方を採用します

(↑  「完全連結法」では、大きい方を採用します。ちなみに「最短距離法」では、小さい方を採用しました(今回のポイントはここです))

上の距離行列をみると、それぞれ

  • 文書2と文書3の距離 = 8.4
  • 文書1と文書3の距離 = 5.7

なので、大きい方の8.4を採用するわけです。

 

同様に、新しいクラスターと文書4の距離は

  • 文書2と文書4の距離 = 7.3
  • 文書1と文書4の距離 = 6.5

なので、大きい方の7.3を採用します。

 

これらの情報を使って、新しいクラスター文書21を含んだ距離行列 D’ に更新します。

D’=(

文書21 文書3 文書4
文書21
文書3 8.4
文書4 7.3 9.1

文書3と文書4の距離は変わらず9.1となっています。

③、新しい距離行列で①、②を繰り返す

①、②を繰り返します。

新しい距離行列 D’ で最小の要素は7.3で、それは文書21と文書4の類似度になっています。

これを新しいクラスター(文書214)と考えると、これと文書3との距離が必要になります。

文書21と文書3の距離は8.4、文書4と文書3の距離は9.1なので、

大きい方の 9.1 が採用されます。

すると新しい距離行列 D” = (

文書214 文書3
文書214
文書3 9.1

)

と更新できます。

④、すべての要素がどれかのグループに属したら終了

これ以上グループ化すると、全文書集合になるのでここで終了です。

 

というわけで、グループ化ができました。

文書1、2、3、4は、

  • 文書2と1が似ているグループ1
  • 次に、文書21と4が似ているグループ2
  • 文書3が1番似ていない

のように分けることができました。

 

めでたしです^^

 

このようなクラスタリングアルゴリズムを「完全連結法」と呼んでいます。

 

 

 

 

 

 

というわけで、今回は階層的クラスタリングの完全連結法について説明しました。

1つ1つ見ていくと、コンピュータでも処理ができる手順の繰り返しなので、大量のデータでもクラスター分析ができることが分かるかと思います。

 

次回は、その他の階層的クラスタリング手法についてご紹介しようと思います↓

第11回『階層的クラスター分析の「ウォード法(Ward法)」とは?そのクラスタリング・アルゴリズムなど分かりやすくまとめました

 

 

 

過去記事はこちらです↓

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

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

第7回『「クラスター分析」ってどうやるの?クラスター分析のやり方、具体的な3つのステップはこちらです

第6回『テキストマイニングの「クラスター分析」などで使われる、知らないと恥ずかしい「素性ベクトル作成の定番的方法」とは?

第5回『テキストマイニングなどの「クラスター分析」で必要な「素性ベクトル」を洗練する2つのテクニックとは?

第4回『テキストマイニングなどのクラスター分析で必要な「素性ベクトル」をつくりたいあなたが知らないと損をする必須のテクニックとは?

第3回『テキストマイニングなどのクラスター分析でも重要な「素性ベクトル」を作るための3つのステップとは?

第2回『テキストマイニングの「クラスター分析」でも必要な「素性ベクトル」とは?なぜ必要なの?

第1回『「クラスター分析」とは?膨大な情報の内容を、ラク〜にサクッと理解したいあなたはこちらをどうぞ

 

 

 

こちらの記事もございます

『「テキストマイニング」の記事まとめはこちらです

 

「多変量解析」の記事まとめはこちらです

 

「機械学習」に入門したいあなたにチェックしてほしい良書、10冊はこちらです

 

『「データマイニング」を勉強したいあなたにチェックしてほしい良書、10冊はこちらです』

 

「エクセル」で「データ分析」できるようになりたいあなたにチェックしてほしい良書10冊はこちらです

 

「データ分析」を活用したい!けど分からないことだらけの方、その悩みを解決する良書10冊はこちらです

 

「アンケート調査」をしたいあなたにチェックしてほしい良書、8冊はこちらです

 

 

本連載では、クラスター分析について定期的に更新しています。

Twitterなどフォローしてもらえると、更新情報が届くので便利です!

タイトルとURLをコピーしました