linkage

凝集型の階層クラスター ツリー

構文

Z = linkage(X)

Z = linkage(X,method)

Z = linkage(X,method,metric)

Z = linkage(X,method,metric,'savememory',value)

Z = linkage(X,method,pdist_inputs)

Z = linkage(y)

Z = linkage(y,method)

説明

Z = linkage(X) は、入力データ行列 X の行の階層クラスターが含まれているツリーをエンコードする行列 Z を返します。

Z = linkage(X,method) は、指定された method (クラスター間の距離を測定する方法を記述します) を使用してツリーを作成します。詳細は、リンケージを参照してください。

Z = linkage(X,method,metric) は、X の行の間の距離を計算する関数 pdist に metric を渡すことによりクラスタリングを実行します。

Z = linkage(X,method,metric,'savememory',value) は、value が 'on' である場合はメモリ節約アルゴリズムを、value が 'off' である場合は標準アルゴリズムを使用します。

Z = linkage(X,method,pdist_inputs) は、X の行の間の距離を計算する関数 pdist に pdist_inputs を渡します。引数 pdist_inputs は、'seuclidean'、'minkowski'、'mahalanobis' のいずれかの尺度と追加の距離計量オプションから構成されます。

Z = linkage(y) は、距離行列のベクトル表現 y を使用します。y は、pdist によって計算されるか、pdist の出力形式に従うより一般的な非類似度行列になります。

Z = linkage(y,method) は、指定された method (クラスター間の距離を測定する方法を記述します) を使用してツリーを作成します。

例

データのクラスター化と結果のプロット

20,000 件の観測値をもつ標本データを無作為に生成します。

rng(0,"twister") % For reproducibility
X = rand(20000,3);

ward 連結法を使用して階層クラスター ツリーを作成します。このケースでは、既定によりclusterdata関数の SaveMemory オプションが "on" に設定されます。通常は、X の次元数と使用可能メモリに基づいて SaveMemory に最適な値を指定します。

Z = linkage(X,"ward");

データを最大 4 つのグループにクラスター化し、結果をプロットします。

c = cluster(Z,MaxClust=4);
scatter3(X(:,1),X(:,2),X(:,3),10,c)

cluster は、データ内のグループを 4 つ識別します。

クラスターの割り当てとクラスの比較

fisheriris データ セットで最大 3 つのクラスターを求め、花のクラスター割り当てを既知の分類と比較します。

標本データを読み込みます。

load fisheriris

"average" 法と "chebychev" 尺度を使用して階層クラスター ツリーを作成します。

Z = linkage(meas,"average","chebychev");

データ内のクラスターを最大 3 つ求めます。

T = cluster(Z,MaxClust=3);

Z のデンドログラム プロットを作成します。3 つのクラスターを表示するため、3 番目から最後までのリンクと 2 番目から最後までのリンクの中間点にカットオフを設定して ColorThreshold を使用します。

cutoff = median([Z(end-2,3) Z(end-1,3)]);
dendrogram(Z,ColorThreshold=cutoff,ShowCut=true)

3 つのクラスターがどのようにして 1 つに結合されるかを調べるため、Z の最後の 2 行を表示します。linkage は、293 番目のクラスター (オレンジ) を 297 番目のクラスター (青) と結合し、1.7583 というリンクで 298 番目のクラスターを形成します。そして、linkage は 296 番目のクラスター (赤) を 298 番目のクラスターと結合します。

lastTwo = Z(end-1:end,:)

lastTwo = 2×3

  293.0000  297.0000    1.7583
  296.0000  298.0000    3.4445

クラスターの割り当てが 3 つの種類に対応しています。たとえば、クラスターの 1 つには、2 番目の種類の花が 50 本、3 番目の種類の花が 40 本含まれています。

crosstab(T,species)

ans = 3×3

     0     0    10
     0    50    40
    50     0     0

階層ツリーにおけるクラスタリング手順の観察

examgrades データ セットを読み込みます。

load examgrades

linkage を使用して階層ツリーを作成します。'single' 法と指数が 3 のミンコフスキー計量を使用します。

Z = linkage(grades,'single',{'minkowski',3});

25 番目のクラスタリング手順を観察します。

Z(25,:)

ans = 1×3

   86.0000  137.0000    4.5307

linkage は、86 番目の観測値と 137 番目のクラスターを結合して、インデックス $120+25=145$ のクラスターを形成します。120 は grades 内の観測値の総数、25 は Z の行番号です。86 番目の観測値と 137 番目のクラスター内の任意の点の間の最小距離は 4.5307 です。

非類似度行列の使用によるデータのクラスタリング

非類似度行列を使用して凝集型階層クラスター ツリーを作成します。

非類似度行列として X を使用します。squareform を使用して、linkage が受け入れるベクトル形式にこの行列を変換します。

X = [0 1 2 3; 1 0 4 5; 2 4 0 6; 3 5 6 0];
y = squareform(X);

linkage を使用してクラスター ツリーを作成します。'complete' 法でクラスター間の距離を計算します。Z の最初の 2 列は、linkage がどのようにクラスターを結合したかを示します。Z の 3 列目は、クラスター間の距離を与えます。

Z = linkage(y,'complete')

Z = 3×3

     1     2     1
     3     5     4
     4     6     6

Z のデンドログラム プロットを作成します。x 軸はツリーの葉ノードに、y 軸はクラスター間のリンク距離に対応します。

dendrogram(Z)

入力引数

X — 入力データ

数値行列

入力データ。2 行以上の数値行列を指定します。行は観測値を、列はカテゴリまたは次元を表します。

データ型: single | double

method — クラスター間の距離を計算するアルゴリズム

'single' (既定値) | 'average' | 'centroid' | 'complete' | ...

クラスター間の距離を計算するアルゴリズム。次の表のいずれかの値を指定します。

メソッド	説明
'average'	重みのない平均距離 (UPGMA)
'centroid'	重心までの距離 (UPGMC)。ユークリッド距離にのみ適しています。
'complete'	最大距離
'median'	重みのある重心までの距離 (WPGMC)。ユークリッド距離にのみ適しています。
'single'	最短距離
'ward'	内部平方距離 (最小分散アルゴリズム)。ユークリッド距離にのみ適しています。
'weighted'	重みのある平均距離 (WPGMA)

これらの方法の詳細については、リンケージを参照してください。

metric — 距離計量

'euclidean' (既定値) | 'squaredeuclidean' | 'seuclidean' | 'mahalanobis' | 関数ハンドル | ...

距離計量。関数 pdist が受け入れる尺度を指定します。これらの尺度について、次の表で説明します。

値	説明
'euclidean'	ユークリッド距離 (既定)
'squaredeuclidean'	2 乗ユークリッド距離(効率向上のみを目的に提供されているオプション。三角不等式は満たさない)。
'seuclidean'	標準化されたユークリッド距離。観測値間の各座標差は、標準偏差 S = std(X,'omitnan') の対応する要素で除算することによりスケーリングされます。S について別の値を指定するには、DistParameter を使用します。
'fasteuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されるユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'fastsquaredeuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される 2 乗ユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'fastseuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される標準化されたユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'mahalanobis'	X の標本共分散を使用して C = cov(X,'omitrows') として計算されるマハラノビス距離。C について別の値を指定するには、DistParameter を使用します。ここで、行列 C は対称な正定値です。
'cityblock'	市街地距離
'minkowski'	ミンコフスキー距離。既定の指数は 2 です。異なる指数 P を指定するには、DistParameter を使用します。P は指数を表す正のスカラー値です。
'chebychev'	チェビシェフ距離 (最大座標差)
'cosine'	1 から、ベクトルとして扱われる点の間の夾角の余弦を引いた値
'correlation'	1 から、値の系列として扱われる点の間の標本相関を引いた値
'hamming'	ハミング距離 (異なる座標の比率)
'jaccard'	1 からジャカード係数 (異なる非ゼロ座標の比率) を減算
'spearman'	1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理)
@distfun	カスタム距離関数のハンドル。距離関数の形式は次のようになります。 function D2 = distfun(ZI,ZJ) % calculation of distance ... ここで ZI は、単一の観測値が含まれている 1 行 n 列のベクトルです。 ZJ は、複数の観測値が含まれている m2 行 n 列の行列です。distfun は、任意の個数の観測値が含まれている行列 ZJ を受け入れなければなりません。 D2 は m2 行 1 列の距離のベクトルであり、D2(k) は観測値 ZI と ZJ(k,:) の間の距離です。 データがスパースでない場合、通常は関数ハンドルではなく組み込みの距離計量を使用する方が高速に距離を計算できます。

詳細は、距離計量を参照してください。

'seuclidean'、'minkowski'、'mahalanobis' の場合に pdist の追加入力引数 DistParameter を指定するには、metric ではなく pdist_inputs を使用します。

データ型: char | string | function_handle

pdist_inputs — 距離計量と距離計量オプション

cell 配列

距離計量およびそのオプション。関数 pdist の 2 つの入力引数 Distance および DistParameter から構成されるコンマ区切りのペアによる cell 配列を指定します。この引数は、'seuclidean'、'minkowski' または 'mahalanobis' を指定する場合のみ有効です。

例: {'minkowski',5}

データ型: cell

value — 'savememory' オプションのフラグ

'on' | 'off'

'savememory' オプションのフラグ。'on' または 'off' のいずれかを指定します。'on' に設定すると、linkage は距離行列を計算せずにクラスターを作成します。method が 'centroid'、'median' または 'ward' であり、metric が 'euclidean' である場合のみ、'on' に設定できます。

value が 'on' である場合、linkage の実行時間は次元数 (X の列数) に比例します。value が 'off' である場合、linkage で必要となるメモリ量は N² に比例します。N は観測値の個数です。value について使用する最適な (最短時間になる) 設定は、問題の次元数、観測値の個数および利用可能なメモリ量に依存します。既定の value の設定は、最適な設定のラフな近似です。

X の列数が 20 以下である場合、または距離行列を格納するための十分なメモリがない場合、既定値は 'on' です。それ以外の場合は、既定値は 'off' です。

例: 'savememory','on'

y — 距離

数値ベクトル

距離。関数 pdist の出力と同じ形式の数値ベクトルを指定します。

• m 行の行列内の観測値のペアに対応する、長さ m(m – 1)/2 の行ベクトル

• (2,1), (3,1), ..., (m,1), (3,2), ..., (m,2), ..., (m,m – 1)) という順序で並んでいる距離

y は、関数 pdist の出力形式に従うことで、より一般的な非類似度行列になります。

データ型: single | double

出力引数

Z — 凝集型の階層クラスター ツリー

数値行列

凝集型の階層クラスター ツリー。数値行列として返されます。Z は (m – 1) 行 3 列の行列です。m は元のデータの観測値の個数です。Z の 1 列目と 2 列目は、二分木の作成のペアにリンクされるクラスターのインデックスを含んでいます。葉ノードには 1 から m までの番号が付けられます。葉ノードは、シングルトンのクラスターで、それより高いすべてのクラスターを含んでいます。行 Z(I,:) に対応する、新しく形成される各クラスターには、インデックス m + I が割り当てられます。エントリ Z(I,1) および Z(I,2) には、クラスター m + I を形成する 2 つの成分クラスターのインデックスが格納されます。m – 1 個の上位クラスターは、クラスタリング ツリーの内部ノードに対応します。Z(I,3) には、行 Z(I,:) でマージされた 2 つのクラスターの間のリンク距離が格納されます。

たとえば、30 個の初期ノードがあるツリーの作成について考えます。クラスター 5 とクラスター 7 がステップ 12 で結合され、このステップではこれらの間の距離が 1.5 であるとします。この場合、Z(12,:) は [5 7 1.5] になります。新しく形成されるクラスターのインデックスは 12 + 30 = 42 になります。以後の行でクラスター 42 が現れた場合、ステップ 12 で作成されたクラスターはより大きいクラスターに結合されます。

データ型: single | double

詳細

リンケージ

"リンケージ" は 2 つのクラスターの間の距離です。

以下の表記は、さまざまな方法で使用されるリンケージを記述します。

• クラスター r は、クラスター p および q から作成されます。

• n_r は、クラスター r のオブジェクトの数になります。

• x_ri は、クラスター r の i 番目のオブジェクトになります。

• "単連結法" は "最近傍" とも呼ばれ、2 つのクラスターのオブジェクト間の最小距離を使用します。

  $$d(r,s)=\min (dist(x_{ri},x_{sj})),i\in (i,\mathrm{...},n_r),j\in (1,\mathrm{...},n_s)$$

• "完全連結法" は "最遠隣" とも呼ばれ、2 つのクラスターのオブジェクト間の最大距離を使用します。

  $$d(r,s)=\max (dist(x_{ri},x_{sj})),i\in (1,\mathrm{...},n_r),j\in (1,\mathrm{...},n_s)$$

• "平均連結法" では、2 つのクラスターにおけるオブジェクトのペアすべての間の距離の平均を使用します。

  $$d(r,s)=\frac{1}{n_r{n}_s}{\displaystyle \sum _{i=1}^{n_r}{\displaystyle \sum _{j=1}^{n_s}dist(x_{ri},x_{sj})}}$$

• "重心連結法" では、2 つのクラスターの重心間のユークリッド距離を使用します。

  $$d(r,s)={\Vert {\overline{x}}_r-{\overline{x}}_s\Vert }_2,$$

  ここで

  $${\overline{x}}_r=\frac{1}{n_r}{\displaystyle \sum _{i=1}^{n_r}{x}_{ri}}$$

• "メディアン連結法" では、2 つのクラスターの加重重心間のユークリッド距離を使用します。

  $$d(r,s)={\Vert {\tilde{x}}_r-{\tilde{x}}_s\Vert }_2,$$

  ここで、$${\tilde{x}}_r$$ および $${\tilde{x}}_s$$ はクラスター r および s の加重重心です。クラスター p および q を結合することによってクラスター r が作成された場合、$${\tilde{x}}_r$$ は次のように再帰的に定義されます。

  $${\tilde{x}}_r=\frac{1}{2}({\tilde{x}}_p+{\tilde{x}}_q)$$

• "ウォードの連結" では、二乗和の増分、つまり 2 つのクラスターを結合したことによるクラスター内二乗和の増加を使用します。クラスター内二乗和は、クラスター内のすべてのオブジェクトと重心間の距離の二乗和として定義されます。二乗和尺度は次の距離計量 d(r,s) に等しくなります。これは linkage が使用する式です。

  $$d(r,s)=\sqrt{\frac{2n_r{n}_s}{(n_r+n_s)}}{\Vert {\overline{x}}_r-{\overline{x}}_s\Vert }_2,$$

  ここで

  • $${\Vert \Vert }_2$$ はユークリッド距離です。

  • $${\overline{x}}_r$$ および $${\overline{x}}_s$$ はクラスター r および s の重心です。

  • n_r および n_s はクラスター r および s の要素数です。

  一部の参考文献では、2 と n_rn_s を乗算した係数をウォードの連結で使用していません。関数 linkage はこの係数を使用するので、2 つのシングルトン クラスターの間の距離はユークリッド距離に等しくなります。

• "加重平均連結法" では、2 つのクラスターの間で距離を計算するために再帰的定義を使用します。クラスター p および q を結合することによってクラスター r が作成された場合、r と別のクラスター s の間の距離は、p と s の間の距離および q と s の間の距離の平均として定義されます。

  $$d\left(r,s\right)=\frac{\left(d\left(p,s\right)+d\left(q,s\right)\right)}{2}$$

ヒント

• linkage(y) が距離行列のベクトル表現である場合、y の計算速度が低下する可能性があります。'centroid'、'median'、および 'ward' メソッドの場合、linkage は y がユークリッド距離かどうかを確認します。時間のかかるチェックを回避するには、y ではなく X を渡してください。

• 'centroid' および 'median' メソッドは、単調ではないクラスター ツリーを作成できます。このようになるのは、2 つのクラスター r および s の結合から 3 番目のクラスターまでの距離が r と s の間の距離より小さい場合です。この場合、既定の方向に描画したデンドログラムでは、葉からルート ノードへのパスは下向きになります。これを回避するには、別の方法を使用してください。次の図に非単調のクラスター ツリーを示します。

  

  この場合、クラスター 1 とクラスター 3 が結合され新しいクラスターになっていて、この新しいクラスターとクラスター 2 の間の距離はクラスター 1 とクラスター 3 の間の距離よりも短くなっています。これは、非単調なツリーになります。

• ツリーを表示する関数 dendrogram、クラスターに点を割り当てる関数 cluster、不整合の程度を計算する関数 inconsistent およびコーフェン相関係数を計算する関数 cophenet などを含む、その他の関数に出力 Z を提供することができます。

バージョン履歴

R2006a より前に導入

参考

cluster | clusterdata | cophenet | dendrogram | inconsistent | kmeans | pdist | silhouette | squareform

トピック

• 階層クラスタリング