論文の概要: Distributed k-Means with Outliers in General Metrics

• arxiv url: http://arxiv.org/abs/2202.08173v2
• Date: Fri, 18 Feb 2022 16:56:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-21 12:43:16.856972
• Title: Distributed k-Means with Outliers in General Metrics
• Title（参考訳）: 一般メトリクスに異常値を持つ分散k平均
• Authors: Enrico Dandolo, Andrea Pietracaprina, Geppino Pucci
• Abstract要約: 一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
• 参考スコア（独自算出の注目度）: 0.6117371161379208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Center-based clustering is a pivotal primitive for unsupervised learning and data analysis. A popular variant is undoubtedly the k-means problem, which, given a set $P$ of points from a metric space and a parameter $k<|P|$, requires to determine a subset $S$ of $k$ centers minimizing the sum of all squared distances of points in $P$ from their closest center. A more general formulation, known as k-means with $z$ outliers, introduced to deal with noisy datasets, features a further parameter $z$ and allows up to $z$ points of $P$ (outliers) to be disregarded when computing the aforementioned sum. We present a distributed coreset-based 3-round approximation algorithm for k-means with $z$ outliers for general metric spaces, using MapReduce as a computational model. Our distributed algorithm requires sublinear local memory per reducer, and yields a solution whose approximation ratio is an additive term $O(\gamma)$ away from the one achievable by the best known sequential (possibly bicriteria) algorithm, where $\gamma$ can be made arbitrarily small. An important feature of our algorithm is that it obliviously adapts to the intrinsic complexity of the dataset, captured by the doubling dimension $D$ of the metric space. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance tradeoffs for general metrics.
• Abstract（参考訳）: センターベースのクラスタリングは教師なし学習とデータ分析のための重要なプリミティブである。 k-平均問題(k-means problem)は、計量空間からの点のセットが p$ であり、パラメータが $k<|p|$ であるような場合、最も近い中心からの点のすべての二乗距離の和を最小化する部分集合 $s$ of $k$ を決定する必要がある。 ノイズの多いデータセットを扱うために導入された k-means with $z$ outliers と呼ばれるより一般的な定式化では、さらにパラメータ $z$ があり、上記の和を計算するとき、最大 $z$ の $p$ (outliers) が無視される。 本稿では, MapReduce を計算モデルとして, 一般的な距離空間に対する k-means に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々の分散アルゴリズムは、還元器あたりのサブ線形ローカルメモリを必要としており、近似比が$O(\gamma)$であるような解は、最もよく知られた逐次的(おそらくはビクリテリア)アルゴリズムによって達成可能なものから離れたもので、$\gamma$を任意に小さくすることができる。 我々のアルゴリズムの重要な特徴は、距離空間の倍の次元$D$で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。 私たちの知る限りでは、従来の分散アプローチでは、一般的なメトリクスに対して同様の品質とパフォーマンスのトレードオフを達成できなかったのです。

関連論文リスト

• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• Private Geometric Median [10.359525525715421]
  データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。 我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
  論文  参考訳（メタデータ） (2024-06-11T16:13:09Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Parameterized Approximation Schemes for Clustering with General Norm Objectives [0.6956677722498498]
  本稿では、$(k,epsilon)$-approximationアルゴリズムを$k$-clustering問題に対して設計する、よく研究されている方式について考察する。 私たちの主な貢献は、クリーンでシンプルなEPASで、10以上のクラスタリング問題を解決しています。
  論文  参考訳（メタデータ） (2023-04-06T15:31:37Z)
• Global $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm [0.20305676256390928]
  k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。 本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-22T13:42:53Z)
• 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)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。 $cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。 $mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
  論文  参考訳（メタデータ） (2021-10-19T17:43:50Z)
• 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)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。 仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
  論文  参考訳（メタデータ） (2020-06-18T17:47:37Z)

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

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