倍加計量における完全動的k中心クラスタリング【JST・京大機械翻訳】

Goranci Gramoz; Henzinger Monika; Leniowski Dariusz; Schulz Christian; Svozil Alexander

プレプリント

J-GLOBAL ID：202202220455708570 整理番号：22P0072030

倍加計量における完全動的k中心クラスタリング【JST・京大機械翻訳】

Fully Dynamic k-Center Clustering in Doubling Metrics

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2019年08月11日プレプリントサーバーでの情報更新日： 2020年02月09日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

クラスタリングは,多数のアプリケーションによる教師なし学習における最も基本的な問題の1つである。しかしながら,古典的クラスタリングアルゴリズムは,データが静的であり,従って,データが絶えず変化し,進化している多くの実世界アプリケーションを捉えることができないと仮定する。これにより,完全動的設定におけるメトリックk中心クラスタリング問題を研究し,そこでは,目標がクラスタリングを効率的に維持し,一方,点の挿入と欠失の相互混合配列をサポートする。また,本モデルは,与えられた点が中心であるかどうか,または(2)クラスタを割当てるかどうかの質問をサポートする。ポリ対数更新とクエリ時間における(2+ε)近似を証明できるk中心クラスタリング問題のための決定論的動的アルゴリズムを提示し,もし基礎となる計量が有界倍加次元を持つならば,そのアスペクト比は多項式によって有界であり,εは一定である。著者らのアルゴリズムの重要な特徴は,更新とクエリ時間がkに依存しないことである。理論によって示唆されたkとεの値に対して,著者らのアルゴリズム構築が,解品質と実行時間に関して最先端のアルゴリズムより優れていることを,広範囲な実験研究を通して,この特徴の実際的関連性を確認した。【JST・京大機械翻訳】

, , , , , , ,
, , , , , , , 【Automatic Indexing@JST】

人工知能

前のページに戻る