k-means--: A unified approach to clustering and outlier detection

k-means--: A unified approach to clustering and outlier detection

  • Sanjay Chawla, Aristides Gionis
  • SDM 2013

概要

  • l点除いてかつk-meansも最小
    • 除いたLが外れ値

問題定義

  • D(X\L, C)を最小化するC (of size k) とL (of size l) を求めたい
    • Dは最小二乗距離和
  • k=1ならn^d^3で解けるけど基本NP-hard

提案手法

  • k-meansの変形に相当
  1. 各点についてクラスタまでの距離計算
  2. 距離でソートして大きいl点をLにつっこむ
  3. Lを無視してクラスタ更新
  • これを収束するまで
  • 定理: Bregman divergenceなら収束する

実験

  • 手法の効率よりは,外れ値が検出できているかの方が大事そう
  • ground truth の outliersとのJaccard係数とか出している
  • というか計算時間は無し

SDM k-means 外れ値検出

2014-09-07 03:40:57 (Sun)

最終更新:2014年09月07日 03:40