論文の概要: EPTAS for $k$-means Clustering of Affine Subspaces
- arxiv url: http://arxiv.org/abs/2010.09580v1
- Date: Mon, 19 Oct 2020 15:04:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 23:26:56.496117
- Title: EPTAS for $k$-means Clustering of Affine Subspaces
- Title（参考訳）: Affine 部分空間の $k$-means クラスタリングのための EPTAS
- Authors: Eduard Eiben, Fedor V. Fomin, Petr A. Golovach, William Lochet, Fahad
Panolan and Kirill Simonov
- Abstract要約: 不完全または破損したエントリを持つデータに対する基本的な$k$-meansクラスタリングの一般化を検討する。
最大$Delta$未特定成分を持つ不完全データポイントは、少なくとも$Delta$-pointと呼ばれる次元の軸平行アフィン部分空間に対応する。
- 参考スコア（独自算出の注目度）: 23.307003144376626
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a generalization of the fundamental $k$-means clustering for data
with incomplete or corrupted entries. When data objects are represented by
points in $\mathbb{R}^d$, a data point is said to be incomplete when some of
its entries are missing or unspecified. An incomplete data point with at most
$\Delta$ unspecified entries corresponds to an axis-parallel affine subspace of
dimension at most $\Delta$, called a $\Delta$-point. Thus we seek a partition
of $n$ input $\Delta$-points into $k$ clusters minimizing the $k$-means
objective. For $\Delta=0$, when all coordinates of each point are specified,
this is the usual $k$-means clustering. We give an algorithm that finds an $(1+
\epsilon)$-approximate solution in time $f(k,\epsilon, \Delta) \cdot n^2 \cdot
d$ for some function $f$ of $k,\epsilon$, and $\Delta$ only.
- Abstract（参考訳）: 不完全または破損したエントリを持つデータに対する基本的な$k$-meansクラスタリングの一般化を検討する。
データオブジェクトが$\mathbb{r}^d$のポイントで表現されるとき、データポイントは、そのエントリのいくつかが欠落しているか未定であるときに不完全であると言われる。
最大$\Delta$未特定成分を持つ不完全データポイントは、少なくとも$\Delta$-pointと呼ばれる次元の軸平行アフィン部分空間に対応する。
したがって、$n$ input $\Delta$-pointsを$k$クラスタに分割し、$k$-meansの目的を最小化する。
$\Delta=0$の場合、各点の座標が指定されると、これは通常の$k$-meansクラスタリングである。
f(k,\epsilon, \delta) \cdot n^2 \cdot d$ ある関数に対して、$k,\epsilon$,$\delta$ only で$(1+ \epsilon)$-approximate 解を求めるアルゴリズムを与える。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文 参考訳（メタデータ） (2023-10-13T14:15:54Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Approximation Algorithms for Fair Range Clustering [14.380145034918158]
本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。
目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。
特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
論文 参考訳（メタデータ） (2023-06-11T21:18:40Z) - 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) - 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) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。
クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。
我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
論文 参考訳（メタデータ） (2021-08-11T12:31:48Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Deep Learning Meets Projective Clustering [66.726500395069]
NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。
計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
論文 参考訳（メタデータ） (2020-10-08T22:47:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。