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') の計算は不要．
リンク†
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
