論文の概要: Nearly-Tight and Oblivious Algorithms for Explainable Clustering
- arxiv url: http://arxiv.org/abs/2106.16147v1
- Date: Wed, 30 Jun 2021 15:49:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-01 15:18:17.551526
- Title: Nearly-Tight and Oblivious Algorithms for Explainable Clustering
- Title（参考訳）: 説明可能なクラスタリングのための近似的・難解なアルゴリズム
- Authors: Buddhima Gamlath, Xinrui Jia, Adam Polak, Ola Svensson
- Abstract要約: Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 8.071379672971542
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of explainable clustering in the setting first
formalized by Moshkovitz, Dasgupta, Rashtchian, and Frost (ICML 2020). A
$k$-clustering is said to be explainable if it is given by a decision tree
where each internal node splits data points with a threshold cut in a single
dimension (feature), and each of the $k$ leaves corresponds to a cluster. We
give an algorithm that outputs an explainable clustering that loses at most a
factor of $O(\log^2 k)$ compared to an optimal (not necessarily explainable)
clustering for the $k$-medians objective, and a factor of $O(k \log^2 k)$ for
the $k$-means objective. This improves over the previous best upper bounds of
$O(k)$ and $O(k^2)$, respectively, and nearly matches the previous $\Omega(\log
k)$ lower bound for $k$-medians and our new $\Omega(k)$ lower bound for
$k$-means. The algorithm is remarkably simple. In particular, given an initial
not necessarily explainable clustering in $\mathbb{R}^d$, it is oblivious to
the data points and runs in time $O(dk \log^2 k)$, independent of the number of
data points $n$. Our upper and lower bounds also generalize to objectives given
by higher $\ell_p$-norms.
- Abstract（参考訳）: まず,Moshkovitz,Dasgupta,Rashtchian,Frost(ICML 2020)によって定式化された設定における説明可能なクラスタリングの問題を検討した。
k$-クラスタ化は、各内部ノードが1つの次元でカットされたしきい値でデータポイントを分割し、各$k$の葉がクラスタに対応する決定木によって与えられる場合に説明できると言われている。
k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、最大で$o(\log^2 k)$を失う説明可能なクラスタリングを出力するアルゴリズムと、$k$-meansの目的に対して$o(k \log^2 k)$という係数を与える。
これは、以前の$O(k)$と$O(k^2)$よりも改善され、以前の$\Omega(\log k)$lowbound for $k$-mediansと、新しい$\Omega(k)$ lower bound for $k$-meansとほぼ一致する。
アルゴリズムは非常にシンプルです。
特に、$\mathbb{R}^d$ で必ずしも説明できない初期クラスタリングを考えると、データポイントに不利であり、時間$O(dk \log^2 k)$ で実行され、データポイントの数$n$ とは独立である。
我々の上界と下界は、より高い$\ell_p$-normsによって与えられる目的にも一般化される。
関連論文リスト
- 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) - Explainable k-means. Don't be greedy, plant bigger trees! [12.68470213641421]
説明可能な$k$-meansクラスタリングのために,新しいbi-criteria $tildeO(log2 k)$の競合アルゴリズムを提供する。
説明可能な$k$-meansは、最近Dasgupta、Frost、Moshkovitz、Rashtchian(ICML 2020)によって導入された。
論文 参考訳（メタデータ） (2021-11-04T23:15:17Z) - Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。
私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
論文 参考訳（メタデータ） (2021-07-02T02:07:12Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。