Fugu-MT 論文翻訳(概要): Linear time small coresets for k-mean clustering of segments with applications

論文の概要: Linear time small coresets for k-mean clustering of segments with applications

arxiv url: http://arxiv.org/abs/2511.12564v1
Date: Sun, 16 Nov 2025 11:48:55 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-18 14:36:24.378339
Title: Linear time small coresets for k-mean clustering of segments with applications
Title（参考訳）: セグメントのk平均クラスタリングのための線形時間小コアセットとその応用
Authors: David Denisov, Shlomi Dolev, Dan Felmdan, Michael Segal,
Abstract要約: 集合 $mathcalS subseteq mathbbRd$ of $n$ segments に対して $k$-means 問題を研究する。任意の $varepsilon > 0$ に対して、$varepsilon$-coreset は $C の部分集合 $C の部分集合 mathbbRd$ であり、$D(mathcalS,X)$ を任意の $k$ に対して 1 pm varepsilon$ で近似する。
参考スコア（独自算出の注目度）: 4.759823735082844
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: We study the $k$-means problem for a set $\mathcal{S} \subseteq \mathbb{R}^d$ of $n$ segments, aiming to find $k$ centers $X \subseteq \mathbb{R}^d$ that minimize $D(\mathcal{S},X) := \sum_{S \in \mathcal{S}} \min_{x \in X} D(S,x)$, where $D(S,x) := \int_{p \in S} |p - x| dp$ measures the total distance from each point along a segment to a center. Variants of this problem include handling outliers, employing alternative distance functions such as M-estimators, weighting distances to achieve balanced clustering, or enforcing unique cluster assignments. For any $\varepsilon > 0$, an $\varepsilon$-coreset is a weighted subset $C \subseteq \mathbb{R}^d$ that approximates $D(\mathcal{S},X)$ within a factor of $1 \pm \varepsilon$ for any set of $k$ centers, enabling efficient streaming, distributed, or parallel computation. We propose the first coreset construction that provably handles arbitrary input segments. For constant $k$ and $\varepsilon$, it produces a coreset of size $O(\log^2 n)$ computable in $O(nd)$ time. Experiments, including a real-time video tracking application, demonstrate substantial speedups with minimal loss in clustering accuracy, confirming both the practical efficiency and theoretical guarantees of our method.
Abstract（参考訳）: 集合 $\mathcal{S} \subseteq \mathbb{R}^d$ of $n$ segments の $k$ center $X \subseteq \mathbb{R}^d$ を最小化する $D(\mathcal{S},X) := \sum_{S \in \mathcal{S}} \min_{x \in X} D(S,x)$ に対して $D(S,x) := \int_{p \in S} |p - x| dp$ を求める。この問題の変数には、異常値の処理、M推定器のような代替距離関数の使用、バランスの取れたクラスタリングを達成するための距離の重み付け、独自のクラスタ割り当ての実施が含まれる。任意の$\varepsilon > 0$に対して、$\varepsilon$-coresetは重み付き部分集合である$C \subseteq \mathbb{R}^d$で、$D(\mathcal{S},X)$を$1 \pm \varepsilon$の係数で近似する。任意の入力セグメントを確実に処理する最初のコアセット構成を提案する。定数$k$と$\varepsilon$の場合、$O(\log^2 n)$のコアセットを$O(nd)$時間で計算可能である。リアルタイムビデオ追跡アプリケーションを含む実験では,クラスタリング精度の低下が最小限に抑えられ,本手法の実用的効率と理論的保証が検証された。

関連論文リスト

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文参考訳（メタデータ） (2025-10-12T15:42:44Z)
Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文参考訳（メタデータ） (2025-04-29T15:56:48Z)
Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。 We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
論文参考訳（メタデータ） (2025-03-26T03:36:36Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。 j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文参考訳（メタデータ） (2023-10-13T14:15:54Z)
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文参考訳（メタデータ） (2023-05-12T08:43:28Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
論文参考訳（メタデータ） (2022-02-25T16:13:28Z)
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)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文参考訳（メタデータ） (2020-03-09T13:30:30Z)

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

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