optimalleaforder

階層クラスタリングの最適な葉ノードの順序

構文

leafOrder = optimalleaforder(tree,D)

leafOrder = optimalleaforder(tree,D,Name,Value)

説明

leafOrder = optimalleaforder(tree,D) は、距離 D を使用して、階層バイナリ クラスター ツリー tree の最適な葉ノードの順序を返します。二分木に最適な葉ノードの順序を使用すると、クラスターを分割せずにツリーの分岐を反転させて、隣接している葉の間で合計された類似度を最大化できます。

leafOrder = optimalleaforder(tree,D,Name,Value) は、1 つ以上の名前と値の引数ペアを使用して最適な葉ノードの順序を返します。

例

最適な葉の順序を使用したデンドログラムのプロット

linkage を使用して、階層バイナリ クラスター ツリーを作成します。次に、既定の順序を使用したデンドログラムと、最適な葉ノードの順序を使用したデンドログラムを比較します。

標本データを生成します。

rng(0,"twister") % For reproducibility
X = rand(10,2);

距離ベクトルと階層バイナリ クラスタリング ツリーを作成します。距離とクラスタリング ツリーを使用して、最適な葉ノードの順序を判断します。

D = pdist(X);
tree = linkage(D,"average");
leafOrder = optimalleaforder(tree,D);

既定の順序を使用したデンドログラムと、最適な葉ノードの順序を使用したデンドログラムをプロットします。

figure()
subplot(2,1,1)
dendrogram(tree)
title("Default Leaf Order")

subplot(2,1,2)
dendrogram(tree,reorder=leafOrder)
title("Optimal Leaf Order")

下の図における葉の順序は、leafOrder の要素に対応しています。最適な葉の順序では、隣接する葉の間で類似度の合計が最大になるようにツリーの枝が反転しています。

leafOrder

leafOrder = 1×10

     1     4     9    10     2     5     8     3     7     6

標本データの散布図を作成し、点にラベルを付けます。

figure()
plot(X(:,1),X(:,2),".")
text(X(:,1),X(:,2),num2str((1:size(X,1))'))

既定の葉の順序では、点 1 と 4 は点 3 と 8 の隣にあります。最適な葉の順序では、点 1 と 4 は点 9 の隣にあり、それらの相対的な位置が散布図に反映されています。

逆の距離相似変換を使用した最適な葉ノードの順序

標本データを生成します。

rng('default') % For reproducibility
X = rand(10,2);

距離ベクトルと階層バイナリ クラスタリング ツリーを作成します。

D = pdist(X);
tree = linkage(D,'average');

逆の距離相似変換を使用して、最適な葉ノードの順序を判断します。

leafOrder = optimalleaforder(tree,D,'Transformation','inverse')

leafOrder = 1×10

     1     4     9    10     2     5     8     3     7     6

入力引数

tree — 階層バイナリ クラスター ツリー

linkage で返される行列

(M - 1) 行 3 列の行列として指定される、階層バイナリ クラスター ツリー。M は葉の数であり、この行列は linkage によって生成されます。

D — 距離

行列 | ベクトル

葉の間の類似度を判定するための距離。距離の行列またはベクトルとして指定します。たとえば、pdist を使用して距離を求めることができます。

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで、Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後に指定しなければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、名前と値をそれぞれコンマを使って区切り、Name を引用符で囲みます。

例: 'Criteria','group','Transformation','inverse' は、逆の相似変換を使用して、それぞれの葉と、隣接するクラスター内における他のすべての葉との類似度を合計して最大化するように指定します。

Criteria — 最適化条件

'adjacent' (既定値) | 'group'

最適な葉ノードの順序を決定するための最適化の条件。'criteria' と次のいずれかの値から構成されるコンマ区切りのペアとして指定します。

'adjacent'	隣接する葉との類似度の合計を最大化します。
'group'	デンドログラムの同じレベルにおいて、それぞれの葉と、隣接するクラスター内において他のすべての葉との類似度を合計して最大化します。

例: 'Criteria','group'

Transformation — 距離を類似度に変換する方法

'linear' (既定値) | 'inverse' | 関数ハンドル

距離を類似度に変換する方法。'Transformation' と、コンマ区切りのペアとして指定し、'linear'、'inverse' または関数ハンドルのいずれかで構成されます。

d_i,j と Sim_i,j は、葉 i と葉 j の間の距離と類似度を示しています。以下の相似変換が用意されています。

'linear'	Simi,j = maxi,j (di,j ) – di,j
'inverse'	Simi,j = 1/di,j

カスタムの変換関数を使用するには、距離の行列 D を受け入れ、類似度の行列 S を返す関数へのハンドルを指定します。この関数は、距離の値の範囲で単調減少でなければなりません。S のサイズは D と同じでなければなりません。S(i,j) は D(i,j) に基づいて計算された類似度となります。

例: 'Transformation',@myTransform

出力引数

leafOrder — 最適な葉ノードの順序

ベクトル

長さが M のベクトルとして返される、最適な葉ノードの順序。M は葉の数です。leafOrder は、指定された距離と相似変換に基づき最適な葉ノードの順序を指定する、ベクトル 1:M の順列です。

参照

[1] Bar-Joseph, Z., Gifford, D.K., and Jaakkola, T.S. (2001). "Fast optimal leaf ordering for hierarchical clustering." Bioinformatics Vol. 17, Suppl 1:S22–9. PMID: 11472989.

バージョン履歴

R2012b で導入

参考

dendrogram | linkage | pdist