抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本論文では,異常値を持つ設定に対するk-平均問題に対して,いくつかの簡単で古典的サンプリングベースアルゴリズムをどのように適応するかを示した。最近,Bhaskara et al.(NeurIPS 2019)は,古典的k-平均++アルゴリズムを異常値の設定にいかに適応するかを示した。しかし,それらのアルゴリズムは,O(log(k)z)異常値を出力する必要があり,そこでは,zは真の異常値の数であり,k-平均++のO(logk)近似保証に整合する。本論文では,それらのアイデアを構築し,異常値を持つ設定にいくつかの逐次および分散k平均アルゴリズムをどのように適応するかを示し,しかし,かなり強い理論的保証:著者らのアルゴリズム出力(1+ε)z異常値を目的関数に対するO(1/ε)近似を達成している。逐次世界において,著者らは,LattanziとSohler(ICML 2019)の最近のアルゴリズムを適応することによってこれを達成した。分散設定では,Guha et al.(IEEE Trans.Know.and Data Engineering 2003)の簡単なアルゴリズム,およびBahman et al.(PVLDB 2012)のポピュラーなk-平均|を適応させた。著者らの技術の理論的な応用は,O(z)異常値を出力し,k≪z|Δnを仮定して,目的関数に対するO(1)近似を達成する実行時間O(nk ̄2/z)を有するアルゴリズムである。これは,オラクルモデルにおけるこの問題に対するΩ(nk ̄2/z)の整合下限で補完された。【JST・京大機械翻訳】
