A Three-Level Optimization Model for Nonlinearly Separable Clustering
A Three-Level Optimization Model for Nonlinearly Separable Clustering(AAAI2020 Accepted paper)を読んでまとめました。
解釈間違い等ある時がありますので、その場合指摘いただけると助かります。
目次
背景と概要
- 複雑な構造をもつ実世界のデータでは、nonlinearly separable clusteringがクラスタリング問題として研究されているものの一つとなっている。
- nonlinearly separable clusteringとして現在以下のようなものがある
- kernel k-means clustering
- spectral clustering
- density clustering
- ただ、効率とクラスタリングの有効性(精度？)のバランスを取るのが難しい
- 本論文では、3段階のclusteringを提案
- linearly separable clustering
- nonlinearly separable clustering
- ensemble clustering
- 上記clusteringの最適化問題を解くために、NKM-NSC algorithmという問題を3つのパートに分けて計算する手法を提案
The three-level optimization model
- 仮定:nonlinearly separable clusterは、いくつかの小さなlinearly separable clusterから成る。
- 下記が今回のモデルの概要図となる。
モデルの流れ
X:n×mのデータ行列
n:オブジェクト数
m:feature数
- Xにlinear clusteringを実行する事でn×pの分割した行列Wを得る
- p:Wのcluster数であり、実際のcluster数kより小さい必要がある
- linear clusteringのタスク:同一clusterのものを、幾何空間上で見た時に似ているものをクラスタリングする。
- 行列Wのそれぞれのclusterに対してnonlinear clusteringを実行してk個のnonlinear clusterにする。
- その結果できる行列:H(p×k)
- そして行列U(n×k)が得たい行列となる。
- やりたいこと:WとHを統合してUに近いものを作る(
)。
- この近似精度はWとHのクオリティに依存する。
- Uへの統合の推定量としてT(>1)を導入。
最適化問題
Linearly separable clusteringにおける最適化
- 与えられたデータXに対するt回目のlinear clustering(1 ≦ t ≦T)
- classicalなk-means
Nonlinearly separable clusteringにおける最適化
- Linearly separable clusteringの結果に対するt回目のnonlinear clustering
- kernel k-means
Ensemble clusteringにおける最適化
最適化問題の最終系
- 最終的に以下の最適化問題となる
制約条件
最適化問題のsolution(NKM-NSC algorithm)
- 最適化問題を以下の3つの問題に分割。
- 全体の流れは下図のようになる。
Problem P1
- H,U,Gが与えられている状態で以下を最小化
- k-meansとして解く
Problem P2
- W,V,U,Gが与えられている状態で以下を最小化
- spactral methodで解く
Problem P3
- W,V,Hが与えられている状態で以下を最小化
実験解析
8つの人工データと7つのリアルデータで実験をしている。
アルゴリズムの計算時間
- アルゴリズム・データ毎の検証
