* Using the Triangle Inequality to Accelerate k-Means [#l0714820]

//ここには文献のリファレンスを書いてください.bibtex形式で書くことを推奨します.
 @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"
 }

*キーワード [#n0aae159]

//ここにはキーワードを列挙してください.
k-means法, スケーラビリティ, 三角不等式

*メモ [#o617cbeb]

//内容とかを簡単に書いてください

距離の三角不等式と距離の上限・下限を管理することで,距離の評価回数を 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') の計算は不要.

*リンク [#w705e877]

//関連リンクを書いてください.
-[[ICML>Meeting#ICML]]
-[[GoogleScholarAll:Using the Triangle Inequality to Accelerate k-Means]]

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS