階層クラスタリング

階層クラスタリングの紹介

階層的なクラスタリンググループは、クラスターツリーまたは "系統樹" を作成することによって、さまざまなスケールで、データをグループ化します。このツリーは、1 つのクラスターの集合ではなく、あるレベルのクラスターが次のレベルでクラスターとして加わる多重レベルの階層です。これにより、アプリケーションに最適なクラスタリングのレベルまたはスケールを決定することが可能になります。関数 clusterdata は、凝集型クラスタリングをサポートし、必要なすべての手順を実行します。関数 pdist、linkage、cluster が組み込まれ、これらの関数はさらに詳細な分析で別々に使用することもできます。関数 dendrogram は、クラスターツリーをプロットします。

アルゴリズムの説明

Statistics and Machine Learning Toolbox™ の関数を使用してデータセットの凝集型の階層クラスター分析を実行するには、次の手順に従います。

データセット内のオブジェクトの各ペア間の類似度または非類似度を求めます。この手順では、関数 pdist を使って、オブジェクト間の "距離" を計算します。関数 pdist は、この測定を計算するさまざまな多くの方法をサポートします。詳細は、類似度の測定を参照してください。
オブジェクトを、2 値の階層クラスターツリーにグループ化します。この手順では、関数 linkage を使って、近接するオブジェクトのペアをリンクします。関数 linkage は、ステップ 1 で生成された距離の情報を使用して、オブジェクトの互いの近接度を決めます。オブジェクトは 2 つのクラスターでペアになっているので、新規に作成されたクラスターは、階層ツリーが形成されるまで大きいクラスター内にグループ化されています。詳細は、リンケージを参照してください。
階層ツリーを切り取る位置を決め、クラス木にします。この手順では、関数 cluster を使用して、階層ツリーの下部から分岐を枝刈りし、それぞれ切り取った分岐の下のすべてのオブジェクトを 1 つのクラスターに割り当てます。これは、データの分割を作成します。関数 cluster は、階層ツリーで自然のグループ化を検出したり、または任意の点で階層ツリーをカットオフすることによって、これらのクラスターを作成できます。

以下の節では、これらのステップに関する情報を詳しく説明します。

メモ:

関数 clusterdata は、必要なすべての手順を実行します。関数 pdist、linkage、または cluster を別々に実行する必要はありません。

類似度の測定

関数 pdist を使用して、データセットのオブジェクトのペア間の距離を計算します。m 個のオブジェクトで構成されているデータセットの場合、m*(m – 1)/2 対のペアがデータセット内にあります。この計算の結果は、距離行列または非類似度行列として一般に知られています。

この距離情報を計算する方法はたくさんあります。既定の設定では、関数 pdist は、オブジェクト間のユークリッド距離を計算します。しかし、その他のオプションのいずれかを指定できます。詳細は、pdist を参照してください。

メモ:

距離の情報を計算する前に、データセットの値をオプションによって正規化できます。実世界のデータセットでは、変数は異なるスケールに対して測定される場合があります。たとえば、ある変数が Intelligence Quotient (IQ) テストスコアを測定し、別の変数が頭部の円周を測定することがあります。これらのばらつきは、近接度の計算を歪めることがあります。関数 zscore を使うと、データセットのすべての値を変換し、同じ比率のスケールを使用できます。詳細は、zscore を参照してください。

たとえば、各オブジェクトが x,y 座標のセットである 5 つのオブジェクトで構成されている、データセット X を考えます。

オブジェクト 1: 1, 2
オブジェクト 2: 2.5, 4.5
オブジェクト 3: 2, 2
オブジェクト 4: 4, 1.5
オブジェクト 5: 4, 2.5

このデータセットを行列として定義し、

rng("default") % For reproducibility
X = [1 2; 2.5 4.5; 2 2; 4 1.5; ...
    4 2.5];

を pdist に渡すことができます。関数 pdist は、オブジェクト 1 とオブジェクト 2、オブジェクト 1 とオブジェクト 3 などのペアの距離を、すべてのペアの間の距離が算出されるまで計算します。次の図は、グラフにこれらのオブジェクトをプロットしています。オブジェクト 2 とオブジェクト 3 の間のユークリッド距離は、距離の 1 つの解釈を説明するために示されます。

Diagram showing the Euclidean distance between two objects

距離情報

関数 pdist は、この距離情報をベクトル Y で返します。各要素には、オブジェクトのペア間の距離が含まれています。

Y = pdist(X)

Y =

  Columns 1 through 6

    2.9155    1.0000    3.0414    3.0414    2.5495    3.3541

  Columns 7 through 10

    2.5000    2.0616    2.0616    1.0000

pdist とオリジナルのデータセットのオブジェクトにより生成される距離情報の関係を確認しやすくするため、関数 squareform を使用して、距離ベクトルを行列に作り変えることができます。この行列では、要素 i,j は、元のデータセットのオブジェクト i とオブジェクト j の距離に相当します。次の例で、要素 1,1 は、オブジェクト 1 とオブジェクト 1 の距離 (ゼロ) を表します。要素 1,2 は、オブジェクト 1 とオブジェクト 2 の距離を表し、以降同様です。

squareform(Y)

ans =

         0    2.9155    1.0000    3.0414    3.0414
    2.9155         0    2.5495    3.3541    2.5000
    1.0000    2.5495         0    2.0616    2.0616
    3.0414    3.3541    2.0616         0    1.0000
    3.0414    2.5000    2.0616    1.0000         0

リンケージ

データセット内のオブジェクト間の近接度を計算すると、関数 linkage を使用して、データセット内のどのオブジェクトがクラスターにグループ化されるべきかを決定することができます。関数 linkage は、pdist により作成された距離情報を受け取り、近接したオブジェクトのペアをバイナリクラスター (2 つのオブジェクトから構成されるクラスター) にリンクします。すると、関数 linkage は、これらの新しく形成されたクラスターを互いにリンクしたり、他のオブジェクトにリンクして、クラスターツリーとして、オリジナルデータセットのすべてのオブジェクトにリンクされるまで、より大きなクラスターを生成していきます。

たとえば、x 座標と y 座標の標本データセットから pdist により生成された距離ベクトル Y が与えられると、関数 linkage は、階層クラスターツリーを作成して行列 Z にリンケージ情報を返します。

Z = linkage(Y)

Z =

    4.0000    5.0000    1.0000
    1.0000    3.0000    1.0000
    6.0000    7.0000    2.0616
    2.0000    8.0000    2.5000

この出力において、各行はオブジェクトまたはクラスター間のリンクを識別します。最初の 2 列は、リンクされたオブジェクトを識別します。3 列目は、これらのオブジェクト間の距離を含みます。x 座標と y 座標の標本データセットに対して、関数 linkage ははじめにオブジェクト 4 と 5 をグループ化します。これらは最近接 (距離の値 = 1.0000) になります。関数 linkage は、次にオブジェクト 1 と 3 をグループ化します。これも距離の値は 1.0000 です。

3 行目は、関数 linkage がオブジェクト 6 および 7 をグループ化したことを表しています。元の標本データセットに 5 つのオブジェクトのみが含まれていたとすると、オブジェクト 6 および 7 は何でしょうか。オブジェクト 6 は、オブジェクト 4 および 5 のグループ化によって新しく形成されたバイナリクラスターです。関数 linkage で 2 つのオブジェクトをグループ化して新しいクラスターを作成する場合、値 m + 1 から始まる一意なインデックス値をクラスターに割り当てなければなりません。ここで、m は元のデータセットに含まれているオブジェクトの個数です (値 1 ～ m は、元のデータセットによって既に使用されています)。同様に、オブジェクト 7 は、オブジェクト 1 と 3 をグループ化することによって形成されるクラスターです。

linkage は、距離を使ってオブジェクトをクラスターする順序を決定します。距離ベクトル Y には、元のオブジェクト 1 から 5 の間の距離が含まれています。しかし、linkage では、作成したクラスター (オブジェクト 6 や 7 など) に関する距離も決定できなければなりません。既定の設定の linkage では、単連結法と呼ばれる方法を使用します。しかし、利用できる方法はまだ他にもあります。詳細は、linkage のリファレンスページを参照してください。

最後のクラスターとして、関数 linkage は、元のデータセットからのオブジェクト 2 と共に、オブジェクト 6 と 7 から構成される新しく形成されたクラスターであるオブジェクト 8 をグループ化しました。次の図は、linkage がオブジェクトをクラスター階層にグループ化する方法をグラフィカルに説明します。

Diagram of a hierarchy of clusters

系統樹

関数 linkage によって作成された階層的なバイナリクラスターツリーは、グラフィカルに表示されると最も容易に理解できます。関数 dendrogram は、次のようにツリーをプロットします。

dendrogram(Z)

Plot of a hierarchical, binary cluster tree

図の横軸に表示された数値は、オリジナルデータセットのオブジェクトのインデックスを表します。オブジェクト間のリンクは、逆 U 字形の線として表されます。U の高さは、オブジェクト間の距離を示します。たとえば、オブジェクト 1 および 3 が含まれているクラスターを表すリンクの高さは 1 です。オブジェクト 2 を、オブジェクト 1、3、4、5 (既にオブジェクト 8 としてクラスター化されている) と共にグループ化するクラスターを表すリンクの高さは 2.5 です。この高さは、linkage で計算したオブジェクト 2 および 8 の間の距離を表します。系統樹図の作成の詳細については、dendrogram のリファレンスページを参照してください。

クラスターツリーの確認

データセットのオブジェクトを階層クラスターツリーにリンクした後、ツリーにおける距離 (すなわち、高さ) がオリジナルの距離を正確に反映することを確認したい場合もあります。さらに、オブジェクト間のリンクの間に存在する自然な分割について調べることもできます。以下のセクションで説明するように、Statistics and Machine Learning Toolbox の関数はこれらのタスクの両方に使用できます。

非類似度の検証
一致の確認

非類似度の検証

階層クラスターツリーにおいて、オリジナルデータセットの任意の 2 つのオブジェクトは最終的に、あるレベルでリンクされます。リンクの高さは、それら 2 つのオブジェクトを含む 2 つのクラスター間の距離を表します。この高さは、2 つのオブジェクト間の "コーフェン距離" として知られます。関数 linkage によって作成されたクラスターツリーが適切にデータを反映しているかどうかを測定する 1 つの方法は、コーフェン距離を、関数 pdist によって作成されたオリジナルの距離データと比較することです。クラスタリングが有効である場合は、クラスターツリー内のオブジェクトのリンクは、距離ベクトル内のオブジェクト間の距離と強い相関があります。関数 cophenet は、これら 2 つの値の集合を比較し、それらの相関を計算し、"コーフェン相関係数" と呼ばれる値を出力します。コーフェン相関係数の値が 1 に近づくにつれて、クラスタリングの解は、より正確にデータを反映します。

コーフェン相関係数を使って、異なる距離計算法またはクラスタリングアルゴリズムを使った同じデータセットのクラスタリングの結果を比較することができます。たとえば、関数 cophenet を使用して、標本データセットに対して作成されたクラスターを評価できます。

c = cophenet(Z,Y)

c =

    0.8615

Z は関数 linkage による行列の出力であり、Y は関数 pdist による距離ベクトルの出力です。

今回は City Block metric を指定して同じデータセットに対して再び pdist を実行します。平均リンケージの方法を使用して、この新しい pdist の出力に関数 linkage を実行後、cophenet を呼び出して、クラスタリングの解を評価します。

Y = pdist(X,"cityblock");
Z = linkage(Y,"average");
c = cophenet(Z,Y)

c =

    0.9047

コーフェン相関係数は、異なる距離とリンケージの方法を使うと、オリジナルの距離をわずかにより適切に表す平方 2 乗を作成することを示します。

一致の確認

データセット内での自然なクラスターの分割を決定する方法の 1 つは、クラスターツリーの各リンクの高さを、そのツリーより下のリンクの高さと比較することです。

リンクの高さがその下のリンクの高さとほぼ同じである場合、階層のそのレベルで結合するオブジェクト間にはっきりと区別できる分割が存在しないことを示します。これらのリンクは、高レベルの一致を示すと言われます。なぜなら、結合されているオブジェクト間の距離は、それらが含むオブジェクト間の距離とほぼ同じであるためです。

一方、リンクの高さがその下のリンクの高さと著しく異なる場合、クラスターツリーのこのレベルで結合したオブジェクトは、それらの成分が結合した時点よりも相互に離れているということを示します。このリンクは、その下のリンクと不整合であると言われます。

クラスター分析において、不整合リンクは、データセット内の自然な分割の境界を示します。関数 cluster は、不整合の量的な尺度を使用して、データセットをクラスターに分割する位置を決定します。

次の系統樹は、不整合リンクを説明します。系統樹のオブジェクトが、ツリーのかなり高いレベルで、リンクによって結合している 2 つのグループに分類される様子に注意してください。これらのリンクは、階層でそれらの下のリンクと比較されるとき不整合です。

Hierarchical cluster tree displaying the difference between links that show consistency and links that show inconsistency

階層クラスターツリーも各リンクの相対的な整合性は、不整合係数として定量化され表されます。この値は、クラスター階層のリンクの高さとその下のリンクの平均の高さを比較します。異なるクラスターに結合するリンクは、高い不整合係数をもちます。indistinct クラスターに結合するリンクは、低い不整合係数をもちます。

クラスターツリーの各リンクに対する不整合係数のリストを作成するには、関数 inconsistent を使用します。既定の設定では、関数 inconsistent は、クラスター階層の各リンクを、クラスター階層内のそれより 2 レベル内にある下の近隣のリンクと比較します。これは、比較の "深さ" と呼ばれます。他の深さを指定することもできます。葉ノードと呼ばれる、下層にオブジェクトをもたないクラスターツリーの一番下のオブジェクトは、不整合係数が 0 です。2 つの葉に結合するクラスターは、ゼロの不整合係数ももちます。

たとえば、関数 inconsistent を使用して、リンケージで関数 linkage によって作成したリンクに対する不整合値を計算できます。

最初に既定の設定を使用して距離とリンク値を再計算します。

Y = pdist(X);
Z = linkage(Y);

次に inconsistent を使用して不整合値を計算します。

I = inconsistent(Z)

I =

    1.0000         0    1.0000         0
    1.0000         0    1.0000         0
    1.3539    0.6129    3.0000    1.1547
    2.2808    0.3100    2.0000    0.7071

関数 inconsistent は、(m-1) 行 4 列の行列のリンクについてのデータを出力します。次の表は、この行列の列を示しています。

列	説明
1	計算に含まれるすべてのリンクの高さの平均
2	計算に含まれるすべてのリンクの標準偏差
3	計算に含まれるリンクの数
4	不整合係数

サンプル出力において、1 行目はオブジェクト 4 と 5 の間のリンクを表します。このクラスターには、関数 linkage によってインデックス 6 が割り当てられています。4 と 5 は葉ノードであるため、クラスターに対する不整合係数は 0 です。2 行目はオブジェクト 1 と 3 (これらも葉ノード) の間のリンクを表します。このクラスターは、関数 linkage によってインデックス 7 を割り当てられます。

3 行目では、オブジェクト 6 および 7 という 2 つのクラスターを接続するリンクを評価しています (この新しいクラスターには、linkage の出力でインデックス 8 が割り当てられています)。3 列目は、3 つのリンクが計算で考えられることを示します: リンク自身と階層内でその直接の下の 2 つのリンク。1 列目は、これらのリンクの高さの平均を表します。関数 inconsistent は、平均を計算するために関数 linkage により出力される高さの情報を使用します。2 列目は、リンク間の標準偏差を表します。最後の列は、これらのリンクに対する不整合値 1.1547 を含みます。これは、現在のリンクの高さと平均の差を、標準偏差によって正規化したものです。

(2.0616 - 1.3539) / 0.6129

ans =

    1.1547

次の図は、この計算に含まれるリンクと高さを説明します。

Hierarchical cluster tree showing the three links used to compute the third inconsistency coefficient

メモ:

前の図において、y 軸の下限は、リンクの高さを示すために、0 に設定されます。下限を 0 に設定するには、[編集] メニューから [Axes プロパティ] を選択し、[Y 軸] タブをクリックして、[Y 範囲] の右隣のフィールドに 0 を入力します。

出力行列の 4 行目には、オブジェクト 8 とオブジェクト 2 の間のリンクが記述されています。3 列目は、この計算に 2 つのリンク (リンク自体と階層内でそのリンクの直下にあるリンク) が含まれていることを示します。このリンクに対する不整合係数は、0.7071 です。

次の図は、この計算に含まれるリンクと高さを説明します。

Hierarchical cluster tree showing the two links used to compute the fourth inconsistency coefficient

クラスターの作成

バイナリクラスターの階層ツリーを作成後、関数 cluster を使用してツリーを枝刈りして、データをクラスターに分割することができます。関数 cluster は、以下の節で説明するように、クラスを 2 とおりの方法で作成します。

データの自然な分割の検出
任意のクラスターの指定

データの自然な分割の検出

階層的なクラスターツリーは、データをはっきりと区別できる、十分に分離したクラスターに自然に分割できます。データから作成された系統樹図において、特に明らかであるかもしれません。ここでは、オブジェクトのグループは、ある領域には密に詰められ、他においてはそうでありません。クラスターツリーのリンクの不整合係数は、オブジェクト間の類似性が急に変化する、これらの分割を識別できます。(不整合係数の詳細は、クラスターツリーの確認を参照してください)。この値を使って、関数 cluster がクラスターの境界を作成する位置を決めることができます。

たとえば、関数 cluster を使用して、cutoff 引数の値として、不整合係数のしきい値 1.2 を指定し、標本データをクラスターにグループ化する場合、関数 cluster は、標本データセットのすべてのオブジェクトを 1 つのクラスターにグループ化します。この例では、不整合係数が 1.2 より大きいリンクがクラスター階層内にありませんでした。

T = cluster(Z,"cutoff",1.2)

関数 cluster は、元のデータセットと同じサイズであるベクトル T を出力します。このベクトルの各要素は、オリジナルのデータセットの対応するオブジェクトが置かれたクラスターの数を含みます。

不整合係数のしきい値を 0.8 まで下げた場合、関数 cluster は標本データセットを 3 つの別々のクラスターに分割します。

T = cluster(Z,"cutoff",0.8)

この出力は、オブジェクト 1 および 3 が 1 つのクラスターに、オブジェクト 4 および 5 が別のクラスターに、オブジェクト 2 は独自のクラスターに含まれていることを示します。

このようにクラスターが形成されると、カットオフの値が不整合係数に適用されます。これらのクラスターは、必ずというわけではありませんが、ある高さで系統樹を横切る水平なスライスに相当します。系統樹の水平スライスに対応するクラスターを得たい場合、criterion オプションを使用して、カットオフが、不整合ではなく距離に基づくべきであるということを指定するか、あるいは以下の節で説明するように、クラスターの数を直接指定できます。

任意のクラスターの指定

関数 cluster で、データセット内の自然の分割で決定するクラスターを作成するのではなく、作成するクラスターの数を指定できます。

たとえば、標本データセットを 2 つのクラスターに分割するために、関数 cluster にさせたいことを指定できます。この場合、関数 cluster は、オブジェクト 1、3、4、および 5 が含まれているクラスターとオブジェクト 2 が含まれている別のクラスターを作成します。

T = cluster(Z,"maxclust",2)

次の図は、階層的なクラスターツリーの系統樹を示し、関数 cluster がこれらのクラスターを決める様子の可視化に役立ちます。水平の破線は樹形図の 2 つのラインと交わります。これは maxclust を 2 に設定することに対応します。左側のラインの下のオブジェクト、すなわち 1、3、4、5 は 1 つのクラスターに属します。一方、右側のラインの下のオブジェクト、すなわち 2 は他のクラスターに属します。

Hierarchical cluster tree showing a cutoff value for creating two clusters