Using the Triangle Inequality to Accelerate k-Means

@InProceedings{icml:03:05,
 author =       "C. Elkan",
 title =        "Using the Triangle Inequality to Accelerate {\textit{k}}-Means",
 booktitle =    "Proc. of The 20th Int'l Conf. on Machine Learning",
 year =         2003,
 pages =     "147-153"
}

キーワード

k-means法, スケーラビリティ, 三角不等式

メモ

距離の三角不等式と距離の上限・下限を管理することで,距離の評価回数を n k e から n に近づける高速化. (n:データ数,k:クラスタ数,e:反復数)

  • x をデータ点で,現在,中心 c に属しているとする.c' は別の中心.(1/2)d(c,c')≧d(x,c) なら,d(x,c')≧d(x,c) である.このとき,d(x,c')の計算は省略できる.
  • d(x,c)の正確な値は未知だが,その上限 u は既知とする. もし u≦(1/2) min d(c,c') (全てのc'≠c についての最小) なら,x は必ず c に割り当てられ,x についての距離計算は省略できる.
  • データ点 x は中心 b に所属.b' は b の前回の反復での中心.前回の反復での下限 d(x,b')≧l' が既知とする.このとき,今回の反復の下限は次式で推定可能 \[d(x,b)\ge \max\{ 0, d(x,b') - d(b,b') \} \ge \max\{0, l' - d(b,b')\} = l\]
  • 点 x と,この点が属する中心 c についての上限を u(x)≧d(x,c),x と他の中心 c' の距離の下限を l(x,c')≦d(x,c') とする.もし,u(x) ≦ l(x,c') なら d(x,c)≦u(x)≦l(x,c')≦d(x,c') なので,d(x,c) と d(x,c') の計算は不要.

リンク


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:15 (2488d)