論文の概要: Near-optimal Algorithms for Explainable k-Medians and k-Means
- arxiv url: http://arxiv.org/abs/2107.00798v1
- Date: Fri, 2 Jul 2021 02:07:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-06 02:48:07.107976
- Title: Near-optimal Algorithms for Explainable k-Medians and k-Means
- Title（参考訳）: 説明可能なk-mediansとk-meansの近似最適アルゴリズム
- Authors: Konstantin Makarychev, Liren Shan
- Abstract要約: Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。
私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
- 参考スコア（独自算出の注目度）: 12.68470213641421
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of explainable $k$-medians and $k$-means introduced
by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem,
our goal is to find a \emph{threshold decision tree} that partitions data into
$k$ clusters and minimizes the $k$-medians or $k$-means objective. The obtained
clustering is easy to interpret because every decision node of a threshold tree
splits data based on a single feature into two groups. We propose a new
algorithm for this problem which is $\tilde O(\log k)$ competitive with
$k$-medians with $\ell_1$ norm and $\tilde O(k)$ competitive with $k$-means.
This is an improvement over the previous guarantees of $O(k)$ and $O(k^2)$ by
Dasgupta et al (2020). We also provide a new algorithm which is $O(\log^{3/2}
k)$ competitive for $k$-medians with $\ell_2$ norm. Our first algorithm is
near-optimal: Dasgupta et al (2020) showed a lower bound of $\Omega(\log k)$
for $k$-medians; in this work, we prove a lower bound of $\tilde\Omega(k)$ for
$k$-means. We also provide a lower bound of $\Omega(\log k)$ for $k$-medians
with $\ell_2$ norm.
- Abstract（参考訳）: 我々は,dasgupta,frost,moshkovitz,rashtchian~(icml 2020)が導入した説明可能な$k$-mediansと$k$-meansの問題を考える。
この問題では、データを$k$クラスタに分割し、$k$-mediansや$k$-meansの目的を最小化する、‘emph{threshold decision tree’を見つけることが目的です。
閾値木のすべての決定ノードは、1つの特徴に基づいてデータを2つのグループに分割するため、得られたクラスタリングは容易に解釈できる。
我々は、$\tilde o(\log k)$が$k$-medians、$\ell_1$ norm、$\tilde o(k)$が$k$-meansと競合する問題に対する新しいアルゴリズムを提案する。
これは Dasgupta et al (2020) による$O(k)$ と $O(k^2)$ の以前の保証よりも改善されている。
また、$O(\log^{3/2} k)$$k$-medians with $\ell_2$ normに対して競合する新しいアルゴリズムも提供する。
dasgupta et al (2020) は$k$-medians に対して$\omega(\log k)$という下限を示し、本研究では$k$-means に対して$\tilde\omega(k)$という下限を証明した。
また、$\ell_2$ normを持つ$k$-mediansに対して$\Omega(\log k)$の低い境界も提供する。
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A Nearly Tight Analysis of Greedy k-means++ [1.452875650827562]
k$-means++アルゴリズムは期待して$Theta(log k)$近似解を返すことが知られている。
我々は、greedy $k$-means++アルゴリズムに対して、ほぼ一致する下界と上界を示す。
論文 参考訳（メタデータ） (2022-07-16T13:49:07Z) - Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。
これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
論文 参考訳（メタデータ） (2021-11-08T20:18:10Z) - Almost Tight Approximation Algorithms for Explainable Clustering [16.22135057266913]
本稿では,Dasguptaらによって提案された最近の説明可能なクラスタリングの枠組みについて考察する。
具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
論文 参考訳（メタデータ） (2021-07-01T23:49:23Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Adapting $k$-means algorithms for outliers [1.9290392443571387]
我々は、$k$-means問題に対して、複数の単純なサンプリングベースのアルゴリズムを、外れ値を持つ設定に適応する方法を示す。
我々のアルゴリズムは、目的関数に対して$O(varepsilon)$-approximationを行いながら、$(varepsilon)z$outliersを出力する。
論文 参考訳（メタデータ） (2020-07-02T14:14:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。