17章 概要
クラスタリング
- フラットクラスタリング
- 前もってクラスタ数を指定
- 非決定的（アルゴリズム）
- 階層的クラスタリング
- 前もってクラス多数を決めなくてよい
- ほとんど決定的（アルゴリズム）
分からない
決定的、非決定的とは？
なぜ、フラットクラスタリングは非決定的？
それぞれの使いどころ
- フラットクラスタリング
- 効率が重要なとき
- 階層的クラスタリング
- アプリケーションでのクラスタリング（16章）
- フラットクラスタリングで欠点があるとき（非決定的、クラスタ数が分からない）
※「この問題について合意が取れている訳ではない」
17.1 階層的凝集クラスタリング
- 階層的凝集クラスタリング(HAC)：
- ボトムアップ型
- クラスタをマージ（凝集）していく
- トップダウン型クラスタリング
系統樹（dendrogram）
HACは系統樹で表現できる
2つのクラスタの類似度（組み合わせ類似度）を示す。
※単一リンククラスタリング
HACは単調
HACの基本仮定（fundamental assumption）は、順次マージされるごとに組み合わせ類似度が減少する。
※式の意味合ってる？
階層の切断基準
- 前もって定めた類似度
- 類似度のギャップが最大のところ（K平均法のエルボー法 と同様）
- モデル計算量
- 前もって定めたクラス多数（フラットクラスタリングと同様）
HACのアルゴリズム
反復ごとに、もっとも類似されたクラスタがマージされる。
クラスタリングのアルゴリズム
- 単一リンククラスタリング
- 完全リンククラスタリング
- 群平均クラスタリング（グループ平均凝集 or GAAC）
- 重心クラスタリング
参考：http://www.kamishima.net/archive/clustering.pdf
17.2 単一リンククラスタリングと完全リンククラスタリング
- 単一リンククラスタリング
- 2つのクラスタ間の類似度：もっとも類似したメンバの類似度
- マージ基準：局所的
- 完全リンククラスタリング
- 2つのクラスタ間の類似度：もっとも類似していないメンバの類似度
- マージ基準：非局所的（クラスタリングの全構造に影響する）
- もっとも小さな直径をもつようなクラスタを選んでマージすること（下図参照）
- 外れ値に影響を受けやすい
完全リンククラスタリングの系統樹
最後のマージを切断すると、ほぼ同じサイズの2つのクラスタ。
前述の単一リンククラスタリングでは、サイズが異なった。
グラフ理論的な解釈
- 単一リンククラスタリング
- 連結成分
- 完全クラスタリング
- 極大クリーク
単一リンク、完全クラスタリングの名前の由来
※詳しい人教えて
単一リンク/完全リンククラスタリングの欠点
文書対の類似度を見ているだけで、クラスタ内の文書の分布は考慮していない。
- 単一リンククラスタリングの欠点
- 連鎖
- 完全リンククラスタリングの欠点
- 外れ値に影響を受けやすい
- 外れ値に影響を受けやすい
17.3 グループ平均凝集クラスタリング
以下、GAACと呼ぶ。
すべての文書対の平均類似度（同じクラスタからの対も含める）を計算する。
ただし自分自身の類似度は含めない。
GACCの必要条件
- ベクトルで表現された文書
- 正規化されたベクトル（自己類似度が1.0）
- 内積（ベクトルとベクトルの和の類似度を計算する）
よく分からなかったこと
※クラスタ類似度を定数時間で計算できる？
※ベクトルの和が文書表現で使えない理由は？
※自己類似度の割合が高い地井さんクラスタに、不公平な利益を与える？もろもろ
※最善マージ持続的
17.4 重心クラスタリング
2つのクラスタの類似度が重心の類似度で定義される。
GAACと異なり、同じクラスタからの対を除外している。
概念は単純
重心クラスタリングは非単調
反転が発生する。
系統樹だと交差する。
※ -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平均法のシードを決める