#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム

=====================
《ビジネス×サイエンス》
#02 位置と集団を見抜く

＜導入＞
   ■　1.　「位置と集団」のビジネスとサイエンス
＜ビジネス編＞
   ■　2.　顧客の地図を描く　～　顧客クラスタの事例と解答
   ■　3.　戦略を練るための「地図」思考　～　様々な事例と通底する理念
＜サイエンス編＞
   ■　4.　クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法　（このページ）
   ■　5.　クラスタを支える数理的概念　～　距離の定義、クラスタ数、FAQ
=====================

＜サイエンス編＞
■　4. クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法

後半では、多次元空間内で集団をあぶり出す「クラスタリング (clustering)」の技術と、それを支える「距離」の数学的な扱い方を取り上げます。

クラスタリング自体はマーケティングでは頻繁に使用されており、市場分析の専門会社と名乗っている会社に発注すると作ってくれます。ですが、実際には、低くない確率で、ほとんど「戦略の地図」として機能しない結果が出されてしまいます。残念ながらビジネスの場で筆者が目にした中では、この数理的な思考の技術がきちんと理解されて使われているケースのほうが少数です。とはいえ、以下をご覧いただければ分かる通り、小難しい言葉で覆い隠さずとも、基本的な考え方はとてもシンプルなものです。

また、ここでの解説は、「仕組み」の説明に加えて、筆者が多数の事例を扱いながら工夫を重ねてきた経験によるノウハウの塊でもあります。統計の教科書やマーケティングの教科書を読んでもどこにも書いてないことがいくつも出てきます。これらのノウハウには、ここではクラスタリングを題材としてはいますが、世の中の現象に対して数理的手法を適用する際に幅広く共通するエッセンスが詰まっているはずです。

（※　ここでは敢えて、「位置」を見抜くために広く使われているその他の手法、例えば主成分分析（Principal Component Analysis; PCA）や因子分析(Factor Analysis）、コレスポンデンス分析（Correspondence Analysis）などを総説的に解説するのではなく、クラスタリングの技術に焦点を絞ってそのノウハウを書き出します。その一つの理由は、実用上、「直感的な戦略の地図」として機能するためのシンプルさの点でこれらの統計手法の中ではクラスタリングが最も優れていると考えているからですが、もう一つの理由は、一つの手法について経験的なノウハウまで詳しく突っ込むことで、特定の分析手法に限らない、数理的手法に共通するセンスをお伝えしたいからです。）

まず、冒頭でも紹介した、クラスタリングの代表的な二つの基本的な手法、「階層的(hierarchical)クラスタリング」と「k-meansクラスタリング」の仕掛けの解説から始めましょう。うまく作られているこれらのアルゴリズムは、初めてご覧になる方にはなかなか興味深いのではないでしょうか。

■4.1 階層的クラスタリング

「階層的クラスタリング (hierarchical clustering)」は、直感的にも分かりやすい、最も基本的なクラスタリング手法です。

顧客集団をいくつかのグループに分ける手法は、「セグメンテーション」と呼ばれたり「クラスタリング」と呼ばれたりします。「セグメント(segment)」という言葉は「切る」という意味を語源に持つのに対し、「クラスタ(cluster)」という言葉は「塊、群れ」という意味を語源に持ちます。（参照：http://en.wiktionary.org/wiki/segment、http://en.wiktionary.org/wiki/cluster）　母集団を「切る」のではなく「くっつける」ことで塊を作る、というクラスタリングの発想は、この「階層的クラスタリング」で最もよく実感できるはずです。

＜手順＞

母集団（例えば日本の消費者全員）のそれぞれの構成要素（例えばひとりひとりの消費者）を、多数の軸で評価してクラスタリングを行うことを考えます。これは、多次元空間内の点を、隣接しているものをグループにしてまとめていくことを意味します。ビジネスでよく出てくる数十の軸を使う場合、数十次元の空間は図示できませんから、分かりやすく2次元空間（平面）で図示して考えましょう。

（画像が見えない場合はこちら）

この「点の分布」のなかで、近いものから順にくっつけていこう、というのが「階層的クラスタリング」の基本的な考え方です。

まず最初は、2点のペアのうち、最も近いペアをくっつけることになります。そして、それ以降もより近くにあるグループ同士をくっつける手順を順々に繰り返していきます。

近くにあるグループ同士をくっつけていくと、最終的には全体のグループ数が4つ、3つ、2つと統合されていき、ついには全体が一つのグループに統合されます。

もっと具体的にこのアルゴリズムを書き出すと、以下のステップから構成されます。

全ての「点」同士の間の「距離」を計算する　（ $N$ 個の点があると、 $N(N-1)/2$ 回の計算をすることになります）
全ての「点」同士の間の「距離」を比較し、最も「距離」が小さな「点」同士を、統合した一つの「グループ」とする
統合して新たに作った「グループ」と、その他の「点」（または他の「グループ」）との間の距離を計算する
新しい「グループ」を含め、統合されずに残っている全ての「点またはグループ」同士の距離を比較し、もっとも「距離」が小さな「点またはグループ」同士を、新たに統合する
(3.)と(4.)を繰り返す。
全ての「点」が一つのグループに統合された時点で終了する

（画像が見えない場合はこちら）

これを樹形図(dendrogram)で左から右へとグループされていく様子を書き表すと、以下のような図示が出来ます。

（画像が見えない場合はこちら）

この樹形図を使うと、例えば、「クラスタが5個」の状態、「クラスタが10個」の状態など、自由にクラスタの個数を決めて選ぶことができます。そして、「10個」版でのあるクラスタが、「5個」版ではどのクラスタにどう属しているか、という関係も一目瞭然です。この関係を見れば、「階層的(hierarchical)」という名称も分かりやすいことと思います。また、「10個」版でのクラスタのうちどれとどれが相互に近いかも、その二つのクラスタがどの段階で統合されるかを見ればおおよそ見当が付きます。

＜補足：「最も近い」の定義＞

少し技術的に難しい補足の話をすると、「より近くにあるグループ同士をくっつける」手順は、どのグループ同士が「近く」なのかの定義の方法が複数考えられ、どんな定義を選ぶかで結果が少し変わってきます。単独の点同士であれば、どの点同士が「近く」なのかは単に距離の大小を比較すればよいですが、複数の点が集まったグループ同士の場合、どれが「近く」なのかは定義によるのです。

例えば以下のような定義が考えられます。

(1) 二つのグループのうち、「最も近い点」同士の距離が最も近いグループ同士をくっつける　（”single-linkage”と呼ばれます）

(2) 二つのグループのうち、「最も遠い点」同士の距離が最も近いグループ同士をくっつける　（”complete-linkage”と呼ばれます）

(3) 二つのグループの点の全てのペアの間の距離の平均が最も短いグループ同士をくっつける　（”average-linkage”と呼ばれます）

(4) 点と点の間の「エネルギー」の総和を計算し、それが最も小さくなるようにくっつけるグループを選ぶ　（”Ward’s method”と呼ばれます）

（画像が見えない場合はこちら）

これらの方法にどのような癖があるかを考えてみると、(1)の方法は初期からより大きなクラスタが育ちやすく、クラスタの大小の差が開きやすいと考えられます。(2)の方法は逆に、どのクラスタもほぼ同じ空間的広がりになりますから、点の分布密度に大きなむらがなければ、各クラスタの大小の差は開きにくいと考えられます。(3)はその中間のバランスを取った手法ですから、(3)を標準的な手法として、その処理結果を調整したい場合に(1)や(2)を選ぶ、と考えてもよいでしょう。

(4)の方法は、一見とても複雑な数式を使用しますが、自然科学との類推を考えると、これらの手法の中でも最も納得のいくものです。それぞれのクラスタ内の「点」をばねでつなぐ時のエネルギーを考えた時に、どのグループ同士をくっつけるのが最も安定か、を表す式になっているのです。

この「階層的クラスタリング」にもいくつかの長所、短所があります。それを見る前に、比較の対象として、これとは全く逆のアプローチを取る「k-meansクラスタリング」を紹介しましょう。

■4.2 k-meansクラスタリング

「k-meansクラスタリング」は非常に効率的なアルゴリズムで、大規模集団のクラスタリングには幅広く使われてきました。今でも、多くの統計ソフトウェアで単純に「クラスタリング」のメニューを選ぶと、最もシンプルな設定での「k-meansクラスタリング」が行われるようになっています。

＜手順＞
————

まず最初に、「仮のクラスタ中心点」を、乱数を使ってランダムに振ります（最終的に作るクラスタの数だけ）。これを「種」（seeds）と考えます。
全ての「点」と、「仮のクラスタ中心点」との距離を計算します。それぞれの「点」から最も距離が近かった「仮のクラスタ中心点」に、その「点」は属する、とします。全ての「点」が、「仮のクラスタ」に属した状態です。
「仮のクラスタ」ごとに、(2.)でそれに属した「点」のそれぞれの軸の座標の平均値を計算します。平均値の座標で指定された「平均値の点」（幾何学的な「重心」）を、その「仮のクラスタ」の新たな「クラスタ中心点」とします。

（画像が見えない場合はこちら）
更新した「クラスタ中心点」に従って全ての「点」の「クラスタメンバーシップ」（どのクラスタに属するか）を更新する、更新した全ての「点」の「クラスタメンバーシップ」に従って「クラスタ中心点」を更新する、を繰り返します。
繰り返し(iteration)ごとに「クラスタ中心点」と「クラスタメンバーシップ」の変化は小さくなっていき、数十回に達するとほぼ動かなくなります。「ほぼ動かなくなった」を判定する基準値を設定しておき、繰り返しで生じた変動がその基準値を下回った時点で「収束した」と判断して繰り返しを終了します。

————

名称の「k-means」はつまり、「k個の平均」。k個の「クラスタ中心（平均）点」を作ることを意味しています（kはクラスタの個数）。

このアルゴリズムはとても高速です。最近のノートパソコンを使えば、数千個の点がある場合で数秒、数万個の点がある場合でも数分で計算が終了します。コンピュータの性能が今ほど高くなかった時代には、大量のサンプルを扱うには現実的にこの手法に限られていたと言ってもよいでしょう。

処理速度と並ぶこの手法の最大の利点は、「再利用が効く」、ということです。

確定した「クラスタ中心点」を定めるだけでクラスタを定義できることがポイントです。最初に使用したサンプルに加えて、追加でアンケート調査を行う、新規会員を加えるなどして追加のサンプルを加えることはビジネス上頻繁に生じます。その場合も、「クラスタ中心点」を固定したまま、追加サンプルがどのクラスタ中心点に近いかを計算するだけで、追加サンプルにも全く同じ定義でクラスタメンバーシップを割り当てることができるのです。

（画像が見えない場合はこちら）

また、クラスタ定義の連続性を保ったまま、クラスタ定義を改良することもできます。サンプルを追加したうえで、「クラスタ中心点」の固定を外してもう一度最適化したい場合は、もともとの「クラスタ中心点」を「種」（上記の手順では乱数で決めた代わり）として、そこから繰り返し計算をもう一度収束するまで行えば、もともとの「クラスタ中心点」から少しずれた位置に、追加サンプルの影響も算入して最適化した新しい「クラスタ中心点」が定まります。

クラスタ定義の改良として、クラスタ定義に使った軸のほうを修正したい場合は、「クラスタ中心点」の代わりに今度は「クラスタメンバーシップ」のほうを固定して、修正した軸での座標でそれぞれのクラスタメンバーの平均を取って新たに「クラスタ中心点」を計算することが出来ます。修正前との連続性を重視する場合には、この計算結果をそのまま新たな「クラスタ中心点」とすることもできますし、連続性よりも新たな定義の最適化を重視する場合は、これを「種」としてさらに繰り返し計算をもう一度収束するまで計算することもできます。

■4.3 クラスタリング手法の比較

基礎的な二つの手法のご紹介から、どのような違いに気づかれたでしょうか。

実用上まず大きな違いは、「適用できるサンプル数」。これは、「計算に要する時間」の裏返しです。

「階層的クラスタリング」では、一度の繰り返しに必要な計算量は、全サンプルのペアの間の距離の比較を計算しますから、サンプル数の二乗に比例します。その繰り返しを、（サンプル数-1）回行いますから、全体で必要な計算量は、サンプル数の三乗におおよそ比例します。つまり、サンプル数が10倍になると、計算時間は1,000倍になるわけです。最近のノートパソコンでは、数千サンプルを処理するのに数秒から数十秒かかります。そうすると、10倍の数万サンプルを扱うには、数万秒、ほぼ丸一日かかることになってしまいます。ノートパソコン1,000台分の処理能力を持つスパコンを使ったとしても、同じ時間で扱えるサンプル数は10倍しか増えません。つまり、適用可能なサンプル数はおおよそ数千個まで、頑張っても数万個までに限られます。

「k-meansクラスタリング」では、一度の繰り返しに必要な計算量は、サンプル数の一乗に比例します。また、必要な繰り返し回数は、サンプル数を増やしても大きくは増大しません。ですから、全体で必要な計算量も、おおよそサンプル数の一乗ちょっとに比例します。最近のノートパソコンでは、数千サンプルの処理に数秒ですから、たとえば1,000倍の数百万サンプルでの計算には数千秒＝約1時間。ノートパソコン1,000台分の処理能力のスパコンなら、1時間で10億サンプルの処理が可能と推定できます。計算量がサンプル数の何乗に比例するかによって、このように取り扱い可能サンプル数の差は圧倒的になるのです。

さらに、数百万サンプルを取り扱う場合、「k-means」であれば、まずは数千サンプルで繰り返し計算を行って「クラスタ中心点」を定義したうえで、「クラスタ中心点」は固定された状態で残りのサンプルはクラスタの割り当てだけを行うこともできます。数百万人～数千万人を対象としたone-to-oneマーケティングでのクラスタの適用は、「k-means」アルゴリズムの効率性がなければほとんど不可能です。

次に、先程も触れた「再利用」と「改良」です。

「k-meansクラスタリング」は、「クラスタ中心点」と「クラスタメンバーシップ」で構成されるその構造上、「再利用」と「改良」を柔軟に行えることは先に触れたとおりです。一方、「階層的クラスタリング」では、追加サンプルの配分は無理に考えられなくはないですが、基本的に想定されません。また、クラスタ定義の改良は、ゼロからもう一度クラスタの生成を行う他なく、もともとのクラスタ定義との連続性を保つのも困難です。

逆に、「階層的クラスタリング」が有意な点を挙げましょう、まずは、「一意性」。

これは、「k-meansクラスタリング」の代表的な欠点の一つです。最初に乱数を使って「種」を生成していますから、同じデータに基づいてもう一度行った場合、多くの場合には全く同じクラスタにはなりません。この欠点の解消のために、何度も乱数を振ってクラスタを何パターンも作成したうえで、クラスタのおさまりの度合いを数値化してもっとも良いパターンを選択する、という改良策を取ることもあります。一方、「階層的クラスタリング」では、同一の計算手法を採る限り、何度やっても全く同じクラスタが生成されます。

それから、「階層性」。

「k-meansクラスタリング」では、k（クラスタ数）=5でのクラスタとk=15でのクラスタを生成した時、k=15でのあるクラスタはk=5でのクラスタに属する、という関係は作られません。階層性を持ったクラスタを作成したい場合は、k=15でクラスタを生成した後、15個のクラスタから「階層的クラスタリング」の手法を使って5個まで統合するのが一つの方法です。もう一つの方法として、k=5でクラスタを生成した後、5個のクラスタそれぞれにさらに「k-meansクラスタリング」をk=3で適用して3つに分けるということも出来ます。いずれにせよ、「階層的クラスタリング」がもともと持っている階層性を持たせるには少々無理をした設計がどうしても必要になります。

このような違いがありますから、目的に応じた使い分けは比較的明確です。

数十個～数百個のSKUを分類して売り方の戦略を分けたい、という場合には、「階層性」を理解しやすく、「一意性」があるので安心も出来る「階層的クラスタリング」の手法が適しているでしょう。一方、数千人以上の顧客を分類してマーケティング戦略を立てる、という場合には、大規模集団も自由に扱え、新規顧客も後からクラスタに追加できる「k-meansクラスタリング」の手法が適しています。

なお、ここで紹介した二つのクラスタリング手法以外にも、より複雑な様々な手法が開発されています。興味をもたれた方は専門書などを当たられると、とても奥深い世界が広がっています。ただ、ビジネス戦略においては、必要以上の複雑性を持ちこむことは、たとえ数学的な精度が上がっても必ずしも良い結果をもたらすとは限らないことに注意が必要です。

次のページ：
■　5.　クラスタを支える数理的概念　～　距離の定義、クラスタ数、FAQ

=====================
《ビジネス×サイエンス》
#02 位置と集団を見抜く