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!
スポンサーリンク

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

スポンサーリンク
ウォード法 Ward method クラスタリング クラスター分析 わかりやすい 解説 アルゴリズム クラスタリング
ウォード法 Ward method クラスタリング クラスター分析 わかりやすい 解説 アルゴリズム
スポンサーリンク
スポンサーリンク

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

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

 

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

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

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

 

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

今回はその中1つの

ウォード法(Ward Method)

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

 

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

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

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

 

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

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

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

 

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

(過去記事は、本記事の下にリンクがあります)

 

今回は、②、③のクラスター分析を行う部分をご紹介します

 

 

 

 

 

 

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

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

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

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

 

具体的には、以下のデータを考えてみます。

変数1 変数2
文書A
文書B
文書C
文書D

各文書A〜Dの特徴が、「素性ベクトル」として各行に書かれています。

各列には文書の特徴を表現した変数がまとめられます。たとえば単語の頻度などがあります。

 

今回はこれらの文書 A〜Dを「ウォード法(Ward法)」によって、クラスター分析してみます。

 

ウォード法のクラスタリング・アルゴリズムとは?

ウォード法では、偏差平方和(へんさへいほうわ)に基づいてクラスタリングしていきます。

偏差とは、平均値との差のことです。

ウォード法のアルゴリズムは、以下のステップで進みます。

 

①、各クラスターの偏差平方和を考える

今回は上で紹介した以下のデータをウォード法によりクラスタリングしたいと思います。

変数1 変数2
文書A
文書B
文書C
文書D

最初は、各文書1つ1つが1つのクラスターと考えます。

このとき例えば、文書Aクラスターの偏差平方和はゼロになります。

他のすべての文書B, C, Dもすべて偏差平方和はゼロです。

 

②、最小の偏差平方和となるように、2つのクラスターを1つにする

次に、4つの文書から2つを選んで1つのクラスターにすることを考えます。

どの2つにするかは、組み合わせとして 4C=6通り(AB, AC, AD, BC, BD, CD)があります。

この組み合わせのそれぞれで偏差平方和を計算して、最小のものを採用します。

ここがウォード法のキモとなっています

 

偏差平方和の計算のしかたは以下の通りです。

★例として、文書Aと文書Bを1つのクラスターにするときの、偏差平方和を計算してみます

まずは偏差を計算するのに必要な(各変数ごとの)平均を求めます。

変数1の文書A, Bの平均 = (4 + 2 ) / 2 = 3

変数2の文書A, Bの平均 = (6 + 7) / 2 = 13 / 2

 

次に、クラスター内の偏差平方和を求めます。

ABクラスターの偏差平方和は、文書Aと文書Bそれぞれの平方和の和から求めることができます。

文書Aの平方和 = (4 – 3)^2 + (6 – 13/2)^2 = 5/4

文書Bの平方和 = (2 – 3)^2 + (7 – 13/2)^2 = 5/4

文書AとBのクラスター内偏差平方和 = 5/4 + 5/4 = 2.5

 

最後にその他のクラスターの偏差平方和も一緒に考えます。

他のクラスター文書C、文書Dの偏差平方和はどちらも0なので、

3つのクラスター{ (AB), C, D }の偏差平方和は、

2.5 + 0 + 0 = 2.5・・・①

と計算できます。

 

同様に、AC, AD, BC, BD, CDをクラスターにした場合の偏差平方和をそれぞれ計算します。

{ (AC), B, D } の偏差平方和 = 10・・・②

{ (AD), B, C } の偏差平方和 = 12.5・・・③

{ (BC), A, D } の偏差平方和 = 22.5・・・④

{ (BD), A, C } の偏差平方和 = 20・・・⑤

{ (CD), A, B } の偏差平方和 = 22.5・・・⑥

 

偏差平方和が最小の組み合わせを、1つのクラスターにします。

ウォード法では、①〜⑥の中で、偏差平方和が最小になるものをクラスターにします。

この例では、①が最小なので、文書Aと文書Bを1つのクラスターにすることになります。

 

③、新しくできたクラスター群で、②を繰り返す

②によって、3つのクラスター { (AB), C, D } になりました。

次は、この3つのクラスターの中から2つ選んで、新しいクラスターにします。

手順は②と同じなのですが、もう一度詳しくまとめてみますね。

 

可能な組み合わせは、{ (ABC), D }, { (ABD), C }, { (AB), (AC) } の3通りあります。

 

★{ (ABC), D }とした場合の偏差平方和の計算をしてみます。

変数1の平均 = (4+2+8)/3 = 14/3

変数2の平均 = (6+7+4)/3 = 17/3

 

(ABC)内の偏差平方和を計算してみます。

文書Aの偏差平方和 = (4 – 14/3)^2 + (6 – 17/3)^2 = 5/9

文書Bの偏差平方和 = (2 – 14/3)^2 + (7 – 17/3)^2 = 80/9

文書Cの偏差平方和 = (8 – 14/3)^2 + (4 – 17/3)^2 = 125/9

(ABC)内の偏差平方和= 5/9 + 80/9 + 125/9 = 70/3

D の偏差平方和 = 0

{ (ABC), D }の偏差平方和 = 70/3 + 0 = 70/3 ・・・⑦

 

同様に、 { (ABD), C }, { (AB), (AC) } の偏差平方和は、

{ (ABD), C }の偏差平方和 =22 ・・・⑧

{ (AB), (AC) }の偏差平方和 = 15 ・・・⑨

 

⑦、⑧、⑨より、⑨が最小となり { (AB), (AC) } としてクラスタリングします。

 

④、すべてのクラスターが1つのクラスターになったら終了

{ (AB), (AC) } をさらにクラスタリングすると1つのクラスターになるので、ここで終了です。

 

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

文書1、2、3、4は、

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

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

 

めでたしです^^

 

このように、『ウォード法(Ward法)』では、

クラスターの偏差平方和が最小になるようにクラスタリングしている

ことがわかりました。

 

 

というわけで、今回は階層的クラスタリングの「ウォード法(Ward法)」について説明しました。

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

 

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

 

 

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

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

 

 

過去記事はこちらです↓

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

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

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

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

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

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

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

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

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

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

 

 

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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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