論文の概要: 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$と見積もる方法を示す。
また,理論結果の実用性を示す実験的な証拠も提供する。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - 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) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。