論文の概要: k-Center Clustering with Outliers in Sliding Windows

• arxiv url: http://arxiv.org/abs/2201.02448v1
• Date: Fri, 7 Jan 2022 13:34:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-10 17:22:31.987374
• Title: k-Center Clustering with Outliers in Sliding Windows
• Title（参考訳）: Windows のスライディングにおけるoutlier による k-Center クラスタリング
• Authors: Paolo Pellizzoni, Andrea Pietracaprina, Geppino Pucci
• Abstract要約: Metric $k$-centerクラスタリングは、基本的な教師なし学習プリミティブである。 我々は,スライディングウインドウ設定下でのストリーミングモデルにおいて,この重要な変種に対する効率的なアルゴリズムを提供する。 我々のアルゴリズムは$O(1)$近似を達成し、驚くほど、$k+z$の動作メモリと$|W|$の対数しか必要としない。
• 参考スコア（独自算出の注目度）: 0.6875312133832077
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Metric $k$-center clustering is a fundamental unsupervised learning primitive. Although widely used, this primitive is heavily affected by noise in the data, so that a more sensible variant seeks for the best solution that disregards a given number $z$ of points of the dataset, called outliers. We provide efficient algorithms for this important variant in the streaming model under the sliding window setting, where, at each time step, the dataset to be clustered is the window $W$ of the most recent data items. Our algorithms achieve $O(1)$ approximation and, remarkably, require a working memory linear in $k+z$ and only logarithmic in $|W|$. As a by-product, we show how to estimate the effective diameter of the window $W$, which is a measure of the spread of the window points, disregarding a given fraction of noisy distances. We also provide experimental evidence of the practical viability of our theoretical results.
• Abstract（参考訳）: メトリック $k$-center クラスタリングは基本的な教師なし学習プリミティブである。 広く使われているが、このプリミティブはデータのノイズに大きく影響を受けるため、より合理的な変種は、与えられたデータセットの点数$z$を無視する最良の解を求め、outliersと呼ばれる。 我々は、スライディングウィンドウ設定の下で、このストリーミングモデルにおいて、この重要な変種に対する効率的なアルゴリズムを提供し、各ステップでクラスタ化すべきデータセットは、最新のデータ項目のウィンドウ$W$である。 我々のアルゴリズムは$O(1)$近似を達成し、驚くほど、$k+z$の動作メモリと$|W|$の対数しか必要としない。 副生成物として、窓の有効径を$W$と見積もる方法を示す。 また,理論結果の実用性を示す実験的な証拠も提供する。

関連論文リスト

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
  我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。 既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。 本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
  論文  参考訳（メタデータ） (2024-04-20T15:01:35Z)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
  学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。 本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。 我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
  論文  参考訳（メタデータ） (2022-10-31T03:00:11Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
  一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
  論文  参考訳（メタデータ） (2022-02-16T16:24:31Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。