This post is Private. Only a writer or those who know its URL can access this post.

Article information
Show article in Markdown
Report article
Help us understand the problem. What is going on with this article?

17章 階層的クラスタリング

17章 階層的クラスタリング

by yuji38kwmt
1 / 24

17章 概要


クラスタリング

  • フラットクラスタリング
    • 前もってクラスタ数を指定
    • 非決定的(アルゴリズム)
  • 階層的クラスタリング
    • 前もってクラス多数を決めなくてよい
    • ほとんど決定的(アルゴリズム)

分からない

決定的、非決定的とは?
なぜ、フラットクラスタリングは非決定的?


それぞれの使いどころ

  • フラットクラスタリング
    • 効率が重要なとき
  • 階層的クラスタリング
    • アプリケーションでのクラスタリング(16章)
    • フラットクラスタリングで欠点があるとき(非決定的、クラスタ数が分からない)

※「この問題について合意が取れている訳ではない」


17.1 階層的凝集クラスタリング

  • 階層的凝集クラスタリング(HAC):
    • ボトムアップ型
    • クラスタをマージ(凝集)していく
  • トップダウン型クラスタリング

系統樹(dendrogram)

HACは系統樹で表現できる

2つのクラスタの類似度(組み合わせ類似度)を示す。
※単一リンククラスタリング
image.png


HACは単調

HACの基本仮定(fundamental assumption)は、順次マージされるごとに組み合わせ類似度が減少する。

※式の意味合ってる?

階層の切断基準

  • 前もって定めた類似度
  • 類似度のギャップが最大のところ(K平均法のエルボー法 と同様)
  • モデル計算量
  • 前もって定めたクラス多数(フラットクラスタリングと同様)

HACのアルゴリズム

反復ごとに、もっとも類似されたクラスタがマージされる。

image.png


クラスタリングのアルゴリズム

  • 単一リンククラスタリング
  • 完全リンククラスタリング
  • 群平均クラスタリング(グループ平均凝集 or GAAC)
  • 重心クラスタリング

image.png

image.png

参考:http://www.kamishima.net/archive/clustering.pdf


17.2 単一リンククラスタリングと完全リンククラスタリング

  • 単一リンククラスタリング
    • 2つのクラスタ間の類似度:もっとも類似したメンバの類似度
    • マージ基準:局所的
  • 完全リンククラスタリング
    • 2つのクラスタ間の類似度:もっとも類似していないメンバの類似度
    • マージ基準:非局所的(クラスタリングの全構造に影響する)
    • もっとも小さな直径をもつようなクラスタを選んでマージすること(下図参照)
    • 外れ値に影響を受けやすい

image.png


完全リンククラスタリングの系統樹

最後のマージを切断すると、ほぼ同じサイズの2つのクラスタ。
前述の単一リンククラスタリングでは、サイズが異なった。
image.png


グラフ理論的な解釈

  • 単一リンククラスタリング
    • 連結成分
  • 完全クラスタリング
    • 極大クリーク

単一リンク、完全クラスタリングの名前の由来

※詳しい人教えて


単一リンク/完全リンククラスタリングの欠点

文書対の類似度を見ているだけで、クラスタ内の文書の分布は考慮していない。

  • 単一リンククラスタリングの欠点
    • 連鎖
  • 完全リンククラスタリングの欠点
    • 外れ値に影響を受けやすい image.png

image.png


17.3 グループ平均凝集クラスタリング

以下、GAACと呼ぶ。

すべての文書対の平均類似度(同じクラスタからの対も含める)を計算する。
ただし自分自身の類似度は含めない。

image.png


GACCの必要条件

  1. ベクトルで表現された文書
  2. 正規化されたベクトル(自己類似度が1.0)
  3. 内積(ベクトルとベクトルの和の類似度を計算する)

よく分からなかったこと

※クラスタ類似度を定数時間で計算できる?
※ベクトルの和が文書表現で使えない理由は?
※自己類似度の割合が高い地井さんクラスタに、不公平な利益を与える?もろもろ
※最善マージ持続的


17.4 重心クラスタリング

2つのクラスタの類似度が重心の類似度で定義される。
GAACと異なり、同じクラスタからの対を除外している。

image.png

概念は単純
image.png


重心クラスタリングは非単調

反転が発生する。
系統樹だと交差する。

image.png

※ -cos(π/6)×4の計算式が分からなかった
※小さなクラスタが大きなクラスタよりも一貫している?


17.2.1 時間計算量

  • 単純なHAC;Θ(N^3)
  • プライオリティキューアルゴリズム:Θ(N^2 logN)
    • HAC手法の効率的なアルゴリズム

※単一リンクで「事前マージ配列」を導入すれば、Θ(N^2)になる?


最善マージ持続

※分からなかった


17.5 階層的凝集クラスタリングの最適性

より小さな組み合わせ類似度があれば、最適と定義する。

重心クラスタリングは最適でない。


17.6 分割可能クラスタリング


17.7 クラスターラベル付け

???


17.8 実装上の注意

  • K平均法とHACを組み合わせたものがよい?
    • HACでK平均法のシードを決める
yuji38kwmt
愛知のIT企業で修行しております。2018年4月に転職しました。 基本的に自分用のメモとして、記事を書いております。 所属先の見解とは一切関係ありません。 https://qiita.com/yuji38kwmt/items/a474ad97e0d86f6081a2
kurusugawa
「いいソフトウェアを楽に作る」技術を追求する企業。今は、機械学習、画像認識中心。
http://kurusugawa.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした