AI資格ドリル
資格を選ぶ

用語比較

最短距離法(単連結)とWard法の違い|階層的クラスタリングの併合基準(G検定)

最短距離法(単連結)とWard法は、凝集型の階層的クラスタリングで次に併合するクラスタを決める併合基準です。最短距離法は最も近い観測のペアの距離で測り、Ward法は併合後の二乗差の合計が最も小さい組を選びます。

最も近い観測どうしの距離なら最短距離法、分散を最小にするならWard法と区別します。

この記事の根拠と出典

各セクションの見出しの下に、公式資料で確認した内容か編集部の整理かをラベルで示しています。 試験日・料金・申込条件・試験方式は変わることがあるため、申込前に公式サイトで確認してください。

最短距離法(single linkage)とWard法の要点

最短距離法(single linkage)

2つのクラスタに属する観測のペアのうち、最も近い距離を併合の基準にする。ノイズには頑健でないが、非常に効率よく計算でき、球状でないデータでもうまくいくことがある。

Ward法

併合したあとのすべてのクラスタ内の二乗差の合計を最小にする分散最小化の方式。k-meansの目的関数に似ており、クラスタの大きさが最も規則的になりやすい。

違いを表で確認

比較軸最短距離法(single linkage)Ward法
併合の基準2つのクラスタの観測のペアのうち、最も近い距離併合したあとのクラスタ内の二乗差の合計が最も小さくなる組
クラスタの大きさ不ぞろいになりやすく、併合基準の中で最も偏りやすい併合基準の中で最も規則的な大きさになりやすい
強み非常に効率よく計算でき、大きなデータにも向く。球状でないデータでもうまくいくことがあるクラスタの大きさが最も規則的になりやすい。分散を最小にする点でk-meansに近い考え方
弱みノイズに頑健でない距離を変えられない。ユークリッド以外の距離では平均連結が代替になる
選択肢で探すキーワード最も近い、最短距離、単連結、single linkage分散最小化、二乗差の合計、k-meansに似る、Ward

どこで迷っているかを切り分ける

01

併合基準という言葉の意味から分からない人

凝集型は、最初は各観測が自分だけのクラスタで、似たクラスタを順に併合していきます。併合基準は、どのクラスタ同士が「似ている」かを数える物差しのことで、最短距離法とWard法は、その物差しの別々の選び方です。

02

最短距離法の「最短」が何の最短か迷う人

2つのクラスタの観測を総当たりで組にし、そのうち一番近い1組の距離を、クラスタ同士の距離とみなします。クラスタ全体の中心どうしの距離ではありません。

03

Ward法をk-meansと同じものと考える人

Ward法はクラスタ内の二乗差の合計を最小にする点がk-meansの目的関数に似ていますが、併合を1回ずつ重ねる凝集型で解く方法です。クラスタ数を先に決めて重心を更新するのはk-meansです。

具体例で使い分ける

例 1

説明に「最も近い観測どうしの距離」「大きさが不ぞろい」とある場合

階層的クラスタリングの併合基準について、2つのクラスタの観測のペアのうち最も近い距離を基準にし、クラスタの大きさが不ぞろいになりやすいと書かれています。

  • scikit-learn公式ドキュメントは、single linkageを、2つのクラスタの観測のペアの最も近い距離を最小にする基準と説明しています。
  • 同じ文書は、クラスタの大きさが不ぞろいになる傾向について、single linkageが最悪の基準だと述べています。
  • 分散や二乗差の合計は出てこないので、Ward法ではありません。

結論: 最も近い観測どうしの距離が基準なら、最短距離法(単連結)を選びます。

例 2

説明に「クラスタ内の二乗差の合計を最小にする」とある場合

併合基準の説明に、すべてのクラスタ内の二乗差の合計を最小にする分散最小化の方式で、k-meansの目的関数に似ていると書かれています。

  • 公式ドキュメントは、Wardをこの説明のとおりの方式としています。
  • 併合を重ねる凝集型で解く点で、重心を更新するk-meansとは手順が違います。
  • 併合基準の話なので、k-meansそのものを選ぶ設問ではありません。

結論: 二乗差の合計を最小にするなら、Ward法を選びます。

例 3

距離をユークリッド距離以外にしたい場合

ユークリッド距離ではない距離でクラスタリングしたいとき、どの併合基準なら使えるかを問われています。

  • 公式ドキュメントは、Wardでは距離を変えられないので、ユークリッド以外の距離では平均連結が代替になると述べています。
  • つまり、距離を自由に変えたい場面で、Ward法は選択肢から外れます。

結論: ユークリッド以外の距離を使うなら、Ward法ではなく平均連結を検討します。

問題文から答えを選ぶ手順

  1. 1

    階層的クラスタリングの話かを確かめる

    デンドログラムや併合の語があれば階層的クラスタリングです。重心とクラスタ数kが中心ならk-meansなので、この記事の対象ではありません。

  2. 2

    距離の測り方を探す

    最も近い観測どうしの距離という説明なら最短距離法です。

  3. 3

    分散・二乗差の語を探す

    クラスタ内の二乗差の合計を最小にするという説明ならWard法です。

  4. 4

    大きさの偏りやノイズの語で最終確認する

    クラスタの大きさが不ぞろいになりやすく、ノイズに頑健でないのは最短距離法の特徴です。

試験での見分け方

  • 1最短距離法(single linkage)は、2つのクラスタの観測のペアのうち最も近い距離で併合を決める。
  • 2Ward法は、すべてのクラスタ内の二乗差の合計を最小にする分散最小化の方式で、k-meansの目的関数に似る。
  • 3クラスタの大きさが不ぞろいになりやすい度合いは、single linkageが最悪、Wardが最も規則的とされる。
  • 4最短距離法はノイズに頑健でないが、非常に効率よく計算でき、球状でないデータでもうまくいくことがある。
  • 5Ward法は距離を変えられず、ユークリッド以外の距離では平均連結が代替になる。

誤答しやすい選択肢

最短距離法の「最短」を、クラスタの中心どうしの距離と考える

修正: 2つのクラスタの観測のペアのうち、最も近い1組の距離です。中心どうしの距離を基準にする方式ではありません。

Ward法を、クラスタ数を先に決めるk-meansと同じと考える

修正: Ward法は併合を重ねる凝集型で、木を作ったあとにクラスタ数や距離のしきい値で切ります。クラスタ数を先に指定するのはk-meansです。

最短距離法はクラスタを偏りなく作ると考える

修正: 公式ドキュメントは、クラスタの大きさが不ぞろいになる点で最短距離法が最悪の基準だと述べています。最も規則的な大きさを与えるのはWardです。

どの併合基準でも、距離を自由に選べると考える

修正: Wardは距離を変えられません。ユークリッド以外の距離を使うなら、平均連結などを検討します。

確認問題

Q12つのクラスタの観測のペアのうち、最も近い距離を併合の基準にする方式はどちらですか?

答え: 最短距離法(single linkage)

公式ドキュメントは、single linkageを、クラスタ同士の最も近い観測の距離を最小にする基準と説明しています。

Q2すべてのクラスタ内の二乗差の合計を最小にし、k-meansの目的関数に似た併合基準はどちらですか?

答え: Ward法

公式ドキュメントは、Wardを分散最小化の方式で、k-meansの目的関数に似るが凝集型の方法で解くものと説明しています。

Q3クラスタの大きさが最も規則的になりやすい併合基準はどちらですか?

答え: Ward法

公式ドキュメントは、クラスタの大きさが不ぞろいになる傾向についてsingle linkageが最悪、Wardが最も規則的な大きさを与えると述べています。

到達チェック

  • 最短距離法が、最も近い観測のペアの距離を基準にすると言える
  • Ward法が、クラスタ内の二乗差の合計を最小にする方式だと言える
  • クラスタの大きさの偏りが大きいのは最短距離法、規則的なのはWard法だと説明できる
  • Ward法では距離を変えられないことを言える
  • k-meansとWard法の手順の違い(重心の更新と併合)を説明できる

同じ資格で次に知りたいこと

  • 固定の学習率と学習率の減衰の違い(G検定)

    固定の学習率と学習率の減衰の違いを、確率的勾配降下法でノイズが消えない理由、線形に減らす式、手計算の例、G検定での見分け方と確認問題で整理します。

  • STRIPSとSHRDLUの違い(G検定)

    STRIPSとSHRDLUの違いを、行動の手順を自動で組み立てる計画と、積み木の世界で英語の指示を解釈する対話という役割、開発者と年代、G検定での見分け方と確認問題で整理します。

  • 意味ネットワークとオントロジーの違い(G検定)

    意味ネットワークとオントロジーの違いを、概念をつなぐ表し方と分野の概念を定義する考え方という役割、is-a関係・part-of関係、Cycプロジェクトとの位置づけで整理。G検定の確認問題つき。

よくある質問

Q最短距離法とWard法の一番大きな違いは何ですか?

A

クラスタ同士の距離の測り方です。最短距離法は最も近い観測のペアの距離、Ward法は併合後のクラスタ内の二乗差の合計を最小にする基準です。

Qクラスタの大きさが最も規則的になるのはどちらですか?

A

scikit-learn公式ドキュメントは、Wardが最も規則的な大きさを与え、single linkageが最も不ぞろいになりやすいと述べています。

Q最短距離法は、どんなときに役立ちますか?

A

公式ドキュメントは、ノイズに頑健でないものの非常に効率よく計算でき、大きなデータの階層的クラスタリングに役立つと述べています。球状でないデータでもうまくいくことがあります。

QWard法とk-meansは同じですか?

A

同じではありません。目的関数は似ていますが、Ward法は併合を重ねる凝集型の方法で解きます。

次に見る比較

執筆: AI資格ドリル編集部(運営者情報を見る)