Dendrogram | Tunny docs

Dendrogram ウィジェットは、階層クラスタリング（Ward 法）のマージツリーを表示します。

スライダーで任意のクラスタ数 $k$ の位置でツリーを切り、得られたグループで葉を色分けします。クラスタ数を事前に固定するのではなく、設計の入れ子構造を見てから切る水準を選べます。

概要

k-means のように事前に $k$ 個のクラスタへの単一の分割を決め打ちする代わりに、凝集型階層クラスタリングは完全な併合木（デンドログラム）を構築します。全 trial をそれぞれ独立したクラスタとして開始し、最も近い 2 つのクラスタを 1 つ残らず併合するまで繰り返し統合していきます。クラスタ数 $k$ はこの構造を_見た後で_、木を任意の高さでカットして決めます。データが実際にいくつのグループを持つのか事前に分からない場合や、自然なグルーピング自体が入れ子構造（クラスタの中にさらにクラスタ）を持つ場合に有用です。

Tunny Dashboard は Ward 法のリンケージ基準を用い、最近傍チェーンアルゴリズムによって効率的に計算します。

数式

Ward 基準は、各ステップで、併合するとクラスタ内分散の総増分が最小になるクラスタ対を選びます。これは k-means が最小化するのと同じ目的関数ですが、大域的に割り当てるのではなく逐次的に積み上げていく点が異なります。

併合のたびに分散をゼロから計算し直す代わりに、Lance-Williams の漸化式は、既存クラスタ $k$ から新しく併合されたクラスタ $i \cup j$ までの距離を、併合前の 3 つのペアワイズ距離から直接更新します:

$d^2(k,, i \cup j) = \frac{(n_i+n_k), d^2_{ik} + (n_j+n_k), d^2_{jk} - n_k, d^2_{ij}}{n_i+n_j+n_k}$ $n_i, n_j, n_k$ はクラスタサイズです。初期距離は（後述する標準化を任意で施した）trial ベクトル間のユークリッド距離の 2 乗であり、各併合で記録される値は $\sqrt{d^2}$ です。したがってデンドログラムの高さ軸はこの Ward 分散増分スケールで測られており、元データの単位そのものではありません。

最近傍チェーンアルゴリズム。 各ステップで大域的に最も近いペアを愚直に探すと、全体で $O(n^3)$ かかります。代わりに Tunny Dashboard は「互いに近づき合うクラスタの連鎖」を辿ります。チェーン末尾の現在のクラスタから最近傍を探し、その最近傍がチェーンの 1 つ前の要素でもあれば（相互最近傍対）直ちに併合します。そうでなければ、その最近傍をチェーンに追加して続行します。各クラスタが全体を通じてチェーンに出入りする回数には上限があるため、総コストは $O(n^2)$ に収まります。

チェーンは最終的な木の異なる枝の間を行き来してから併合を確定させることがあるため、$n-1$ 回の併合は必ずしも距離の昇順で生成されるわけではありません。しかし Ward 基準は単調です（親の併合距離は子のどちらの距離よりも小さくなることはありません）。そのため、最終的に距離の昇順でソートすれば必ず妥当なトポロジカル順序になります。どの子併合も親より先に現れ、描画されるデンドログラムに交差や逆転は生じません。 $k$ クラスタへの木のカットは、単に（昇順で見て）最も大きい $k-1$ 回の併合を無視し、残った部分木をそのままクラスタラベルとして読み取るだけです。ユーザが選ぶのは、距離のしきい値ではなくクラスタ数のみでかまいません。

特性・限界

Ward 基準はコンパクトでほぼ球形のクラスタを好みます。両者とも同じクラスタ内分散を最小化するため、k-means と同じバイアスを持ちます。細長い、あるいは非凸な真のクラスタは、誤って分割や統合をされることがあります。
標準化は、変数が無関係な単位やスケールを持つ場合に重要です。これは PCA Biplot や SOM Map と同様であり、標準化しなければ生のレンジが最も大きい変数がすべての距離計算を支配してしまいます。標準化は常に有効であり、ユーザが切り替えることはできません。ウィジェットは常に標準化を有効にした状態で Ward 法のリンケージを計算します。
メモリは $O(n^2)$ （全ペアワイズ距離行列）であり、数百枚を超える葉を持つデンドログラムは、いずれにせよ判読不能になります。800 行を超える場合、Tunny Dashboard はランダムではなく等間隔で決定論的にサブサンプルします。したがって同じ Study からは常に同じ縮小デンドログラムが得られ、サンプルから外れた行は単に葉として現れないだけです。
デンドログラムの高さは物理的な距離ではありません。Lance-Williams 漸化式による Ward 分散増分の累積スケールであり、同一デンドログラム内の併合同士では比較できますが、元の変数の単位や別のリンケージ法による距離と直接比較することはできません。

参考文献

Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244. https://doi.org/10.2307/2282967
Müllner, D. (2011). Modern hierarchical, agglomerative clustering algorithms. arXiv:1109.2378. https://arxiv.org/abs/1109.2378