Fugu-MT 論文翻訳(概要): Provable Imbalanced Point Clustering

論文の概要: Provable Imbalanced Point Clustering

arxiv url: http://arxiv.org/abs/2408.14225v1
Date: Mon, 26 Aug 2024 12:41:41 GMT
ステータス: 処理完了
システム内更新日: 2024-08-27 14:01:29.236162
Title: Provable Imbalanced Point Clustering
Title（参考訳）: 確率的不均衡点クラスタリング
Authors: David Denisov, Dan Feldman, Shlomi Dolev, Michael Segal,
Abstract要約: 不均衡点クラスタリングの近似を計算するための効率的かつ証明可能な手法を提案する。提案手法の実証的寄与を実画像(ノイズと参照)、合成データ、実世界のデータに示す実験を行った。
参考スコア（独自算出の注目度）: 19.74926864871558
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We suggest efficient and provable methods to compute an approximation for imbalanced point clustering, that is, fitting $k$-centers to a set of points in $\mathbb{R}^d$, for any $d,k\geq 1$. To this end, we utilize \emph{coresets}, which, in the context of the paper, are essentially weighted sets of points in $\mathbb{R}^d$ that approximate the fitting loss for every model in a given set, up to a multiplicative factor of $1\pm\varepsilon$. We provide [Section 3 and Section E in the appendix] experiments that show the empirical contribution of our suggested methods for real images (novel and reference), synthetic data, and real-world data. We also propose choice clustering, which by combining clustering algorithms yields better performance than each one separately.
Abstract（参考訳）: すなわち、$k$-centers を任意の$d,k\geq 1$に対して $\mathbb{R}^d$ の点集合に適合させる。この目的のために \emph{coresets} を用いるが、これは本質的には、与えられた集合のすべてのモデルの適合損失を近似する$\mathbb{R}^d$の重み付き点集合であり、乗算係数は $1\pm\varepsilon$ である。提案手法は, 実画像, 合成データ, 実世界のデータに対して, 提案手法の実証的寄与を示す実験である。また、選択クラスタリングを提案し、クラスタリングアルゴリズムを組み合わせることで、各クラスタよりもパフォーマンスが向上する。

関連論文リスト

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文参考訳（メタデータ） (2024-11-02T02:50:12Z)
A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文参考訳（メタデータ） (2024-02-02T10:44:42Z)
Diversity-aware clustering: Computational Complexity and Approximation Algorithms [19.67390261007849]
本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-01-10T19:01:05Z)
Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文参考訳（メタデータ） (2023-05-12T03:01:41Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文参考訳（メタデータ） (2022-02-16T16:24:31Z)
Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文参考訳（メタデータ） (2021-06-04T16:37:19Z)
Determinantal consensus clustering [77.34726150561087]
本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。 DPPは部分集合内の中心点の多様性を好んでいる。 DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
論文参考訳（メタデータ） (2021-02-07T23:48:24Z)
Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文参考訳（メタデータ） (2020-05-21T17:51:30Z)
$p$-Norm Flow Diffusion for Local Graph Clustering [18.90840167452118]
我々は、p-ノルムネットワークフローとの拡散を$pin (1,infty)$とする凸最適化定式化の族を示す。局所クラスタリングでは,入力種子の周囲の低コンダクタンスカットの発見に有用であることを示す。提案手法は,pge 2$の強い局所実行時間で解き,合成グラフと実世界のグラフの両方で実験的な評価を行い,既存の手法とよく比較できることを示す。
論文参考訳（メタデータ） (2020-05-20T01:08:17Z)

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