論文の概要: Sets Clustering
- arxiv url: http://arxiv.org/abs/2003.04135v1
- Date: Mon, 9 Mar 2020 13:30:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-25 08:07:20.352874
- Title: Sets Clustering
- Title(参考訳): setクラスタリング
- Authors: Ibrahim Jubran and Murad Tukan and Alaa Maalouf and Dan Feldman
- Abstract要約: 我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
- 参考スコア(独自算出の注目度): 25.358415142404752
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The input to the \emph{sets-$k$-means} problem is an integer $k\geq 1$ and a
set $\mathcal{P}=\{P_1,\cdots,P_n\}$ of sets in $\mathbb{R}^d$. The goal is to
compute a set $C$ of $k$ centers (points) in $\mathbb{R}^d$ that minimizes the
sum $\sum_{P\in \mathcal{P}} \min_{p\in P, c\in C}\left\| p-c \right\|^2$ of
squared distances to these sets. An \emph{$\varepsilon$-core-set} for this
problem is a weighted subset of $\mathcal{P}$ that approximates this sum up to
$1\pm\varepsilon$ factor, for \emph{every} set $C$ of $k$ centers in
$\mathbb{R}^d$. We prove that such a core-set of $O(\log^2{n})$ sets always
exists, and can be computed in $O(n\log{n})$ time, for every input
$\mathcal{P}$ and every fixed $d,k\geq 1$ and $\varepsilon \in (0,1)$. The
result easily generalized for any metric space, distances to the power of
$z>0$, and M-estimators that handle outliers. Applying an inefficient but
optimal algorithm on this coreset allows us to obtain the first PTAS
($1+\varepsilon$ approximation) for the sets-$k$-means problem that takes time
near linear in $n$. This is the first result even for sets-mean on the plane
($k=1$, $d=2$). Open source code and experimental results for document
classification and facility locations are also provided.
- Abstract(参考訳): emph{sets-$k$-means}問題への入力は整数 $k\geq 1$ であり、$\mathcal{p}=\{p_1,\cdots,p_n\}$ of set in $\mathbb{r}^d$ である。
目標は、$\sum_{p\in \mathcal{p}} \min_{p\in p, c\in c}\left\| p-c \right\|^2$ of squared distances to these set である。
この問題に対する \emph{$\varepsilon$-core-set} は$\mathcal{P}$ の重み付き部分集合であり、$\mathbb{R}^d$ における$k$の集合に対して$1\pm\varepsilon$ factor に近似する。
このような $o(\log^2{n})$ のコア集合は常に存在し、すべての入力 $\mathcal{p}$ と固定 $d,k\geq 1$ と $\varepsilon \in (0,1)$ に対して $o(n\log{n})$ time で計算できる。
結果は、任意の距離空間、$z>0$ のパワーへの距離、および外れ値を扱う M-推定器に対して容易に一般化される。
このコアセットに非効率だが最適なアルゴリズムを適用することで、n$で線形に近い時間を要する集合-k$-平均問題に対する最初のptas ($1+\varepsilon$ approximation) が得られる。
これは平面上の集合平均 (k=1$, $d=2$) に対しても最初の結果である。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
関連論文リスト
- Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Bicriteria Approximation Algorithms for Priority Matroid Median [1.7188280334580193]
我々は、プライオリティを$k$-Median問題に一般化する、プライオリティ・マトロイド・メディア問題を考える。
目標は、mathcalF ff_iの$sum_iを最小化するために、サブセット$S subseteq MathcalF$を選択することである。
論文 参考訳(メタデータ) (2022-10-04T20:19:55Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。
我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文 参考訳(メタデータ) (2022-02-03T03:45:45Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳(メタデータ) (2021-06-25T19:14:45Z) - FPT Approximation for Socially Fair Clustering [0.38073142980733]
距離関数 $d(.,.)$ を持つ距離空間 $mathcalX$ において点の集合 $P$ が与えられる。
社会的に公正な$k$-median問題の目標は、すべてのグループに対する最大平均コストを最小限に抑える、セットの$CサブセットF$ of $k$センターを見つけることである。
本研究では、社会的に公正な$k$-medianと$k$-meansに対する$(5+varepsilon)$と$(33+varepsilon)$近似アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-06-12T11:53:18Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳(メタデータ) (2020-07-15T22:58:50Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳(メタデータ) (2020-02-12T03:40:52Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。