○原聡(大阪大学) ○竹内孝(京都大学) ○吉田悠一(国立情報学研究所)
背景
データ間の類似関係を階層構造で表現する階層クラスタリングには「安定性」という問題があって、例えばデータが1点削除されただけでもう階層構造が変わったりする。なのである程度データの削除や追加にロバストなクラスタリングが欲しい。
問題設定
まず不安定性を定量的に表現する。まず1点を選ぶ。全データを用いてクラスタリングを行った場合と、その点を削除してクラスタリングを行った場合の階層構造の違い(より正確には、分岐の違い 削除した点による差異は考慮しない)によって距離を測定する。すべての点に対して距離を測定し、その平均として平均感度を定義する。この平均感度をなるべく小さくするアルゴリズムを設定する。なお、平均感度だけ最小にしようとすると同じ結果を返す分類が最適になってしまうため、Dasgupta Scoreを導入してクラスタ構造の質を評価する
既存のトップダウン型(データ全体を分割していく方式の)クラスタリングが不安定である理由は、スパーシティを最小にするものを選んでいるからで、一回でも前と違う分割を取ると結果が不安定になる。
なので、最小にはしないものに対しても、確率によって選ぶようなアルゴリズムを提案する。つまり、指数を用いた確率によって分割を選択することである程度のロバスト性を確保する。
結果
平均感度とDasgupta Scoreがトレードオフの関係になっているのは変わらないが、やはり安定性が高まっているらしい、さもありなん。
感想
データセットから取り除く点が1点のみなのが気になった。複数点の場合は変数の条件が変わるらしいが理論上は特に問題ないらしい。でもシンプルで良いと思った。例えば一部のデータ点だけで階層構造を決定して、複数のサブセットによってできた複数の階層構造の案を統合するとかも考えられるがどうなんでしょうか。
