論文の概要: Improved Learning-augmented Algorithms for k-means and k-medians
Clustering
- arxiv url: http://arxiv.org/abs/2210.17028v1
- Date: Mon, 31 Oct 2022 03:00:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 18:21:28.766720
- Title: Improved Learning-augmented Algorithms for k-means and k-medians
Clustering
- Title（参考訳）: k-meansとk-mediansクラスタリングのための学習提示アルゴリズムの改善
- Authors: Thy Nguyen, Anamay Chaturvedi, Huy L\^e Nguyen
- Abstract要約: 学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
- 参考スコア（独自算出の注目度）: 8.04779839951237
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of clustering in the learning-augmented setting,
where we are given a data set in $d$-dimensional Euclidean space, and a label
for each data point given by an oracle indicating what subsets of points should
be clustered together. This setting captures situations where we have access to
some auxiliary information about the data set relevant for our clustering
objective, for instance the labels output by a neural network. Following prior
work, we assume that there are at most an $\alpha \in (0,c)$ for some $c<1$
fraction of false positives and false negatives in each predicted cluster, in
the absence of which the labels would attain the optimal clustering cost
$\mathrm{OPT}$.
For a dataset of size $m$, we propose a deterministic $k$-means algorithm
that produces centers with improved bound on clustering cost compared to the
previous randomized algorithm while preserving the $O( d m \log m)$ runtime.
Furthermore, our algorithm works even when the predictions are not very
accurate, i.e. our bound holds for $\alpha$ up to $1/2$, an improvement over
$\alpha$ being at most $1/7$ in the previous work. For the $k$-medians problem
we improve upon prior work by achieving a biquadratic improvement in the
dependence of the approximation factor on the accuracy parameter $\alpha$ to
get a cost of $(1+O(\alpha))\mathrm{OPT}$, while requiring essentially just
$O(md \log^3 m/\alpha)$ runtime.
- Abstract（参考訳）: 学習強化環境でのクラスタリングの問題は、$d$次元ユークリッド空間のデータセットと、どの点のサブセットをクラスタ化すべきかを示すオラクルによって与えられる各データポイントのラベルが与えられることである。
この設定は、例えばニューラルネットワークによって出力されるラベルなど、クラスタリングの対象に関連のあるデータセットに関する補助的な情報にアクセス可能な状況をキャプチャする。
先行研究の後、予測されたクラスタごとに少なくとも$c<1$の偽陽性と偽陰性の比率に対して$\alpha \in (0,c)$があると仮定し、ラベルが最適なクラスタリングコストである$\mathrm{opt}$を得ることができないと仮定する。
サイズが$m$のデータセットでは、$O(d m \log m)$ランタイムを保ちながら、以前のランダム化アルゴリズムと比較してクラスタリングコストが改善されたセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
さらに、予測があまり正確でない場合でも、アルゴリズムは動作します。すなわち、我々のバウンドは、$\alpha$が$/2$で、$\alpha$が以前の作業で最大$/7$で改善されます。
k$-medians問題では、精度パラメータの近似係数の依存度が2次的に改善され、$(1+o(\alpha))\mathrm{opt}$となるが、基本的には$o(md \log^3 m/\alpha)$ランタイムが必要となる。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳（メタデータ） (2023-06-20T06:13:56Z) - 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) - Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。
我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文 参考訳（メタデータ） (2022-02-16T16:24:31Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。