論文の概要: How to Find a Good Explanation for Clustering?
- arxiv url: http://arxiv.org/abs/2112.06580v2
- Date: Thu, 16 Dec 2021 15:16:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-17 13:40:29.441048
- Title: How to Find a Good Explanation for Clustering?
- Title（参考訳）: クラスタリングのよい説明を見つけるには?
- Authors: Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, William Lochet,
Nidhi Purohit, Kirill Simonov
- Abstract要約: Moshkovitz氏、Dasgupta氏、Rashtchian氏、Frost氏(ICML 2020)は、説明可能な$k$-meansと$k$-medianクラスタリングのエレガントなモデルを提案した。
説明可能なクラスタリングに関する2つの自然なアルゴリズム的問題について検討する。
厳密なアルゴリズム分析では、入力サイズ、データの寸法、外乱数、クラスタ数、近似比といったパラメータが、説明可能なクラスタリングの計算複雑性に与える影響について光を当てています。
- 参考スコア（独自算出の注目度）: 7.951746797489421
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: $k$-means and $k$-median clustering are powerful unsupervised machine
learning techniques. However, due to complicated dependences on all the
features, it is challenging to interpret the resulting cluster assignments.
Moshkovitz, Dasgupta, Rashtchian, and Frost [ICML 2020] proposed an elegant
model of explainable $k$-means and $k$-median clustering. In this model, a
decision tree with $k$ leaves provides a straightforward characterization of
the data set into clusters.
We study two natural algorithmic questions about explainable clustering. (1)
For a given clustering, how to find the "best explanation" by using a decision
tree with $k$ leaves? (2) For a given set of points, how to find a decision
tree with $k$ leaves minimizing the $k$-means/median objective of the resulting
explainable clustering? To address the first question, we introduce a new model
of explainable clustering. Our model, inspired by the notion of outliers in
robust statistics, is the following. We are seeking a small number of points
(outliers) whose removal makes the existing clustering well-explainable. For
addressing the second question, we initiate the study of the model of
Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous
algorithmic analysis sheds some light on the influence of parameters like the
input size, dimension of the data, the number of outliers, the number of
clusters, and the approximation ratio, on the computational complexity of
explainable clustering.
- Abstract（参考訳）: k$-meansと$k$-medianクラスタリングは、教師なしの強力な機械学習技術である。
しかしながら、すべての機能に複雑な依存があるため、結果のクラスタ割り当てを解釈することは困難である。
Moshkovitz氏、Dasgupta氏、Rashtchian氏、Frost氏(ICML 2020)は、説明可能な$k$-meansと$k$-medianクラスタリングのエレガントなモデルを提案した。
このモデルでは、$k$の葉を持つ決定木は、クラスタにセットされたデータの簡単なキャラクタリゼーションを提供する。
説明可能なクラスタリングに関する2つの自然アルゴリズム質問について検討した。
1) 所定のクラスタリングについて、$k$の葉を持つ決定木を用いて「最良の説明」を見つけるには、どうすればよいか?
(2) 与えられた点集合に対して、説明可能なクラスタリングの目標である$k$-means/medianを最小化する、$k$の葉を持つ決定木をどうやって見つけるか?
最初の問題に対処するために、説明可能なクラスタリングの新しいモデルを導入する。
我々のモデルは、ロバスト統計における外れ値の概念に着想を得たものである。
私たちは、既存のクラスタリングをうまく説明できる少数のポイント(外れ値)を求めています。
2つ目の疑問に対処するために、多変量複雑性の観点から、モシュコヴィッツらのモデルの研究を開始する。
厳密なアルゴリズム分析では、入力サイズ、データの寸法、外乱数、クラスタ数、近似比といったパラメータが、説明可能なクラスタリングの計算複雑性に与える影響について光を当てています。
関連論文リスト
- ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
それは実用性を目指しており、アイテムはアプリケーション固有の重要な値を持つことができ、クラスタリングがどちらが優れているかを判断するときに人間の判断を使うのは粗悪であり、アイテムの任意のスライスのためのメトリクスを報告できる。
クラスタリング品質の差分を測定するアプローチは、高価な地平を前もって構築し、それに関して各クラスタリングを評価する代わりに、ABCDEはクラスタリング間の実際の差分に基づいて、判定のための質問をサンプリングする。
論文 参考訳（メタデータ） (2024-07-31T08:29:35Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - 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 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。
我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
論文 参考訳（メタデータ） (2020-06-08T15:27:58Z) - ExKMC: Expanding Explainable $k$-Means Clustering [19.702066333512548]
説明可能性と精度のトレードオフに着目し,$k$-meansクラスタリングのアルゴリズムについて検討した。
我々は、新しい説明可能な$k$-meansクラスタリングアルゴリズム、ExKMCを開発し、$k' geq k$を加算し、$k'$の葉を持つ決定木を出力する。
ExKMCは、標準的な決定木法と説明可能なクラスタリングのための他のアルゴリズムの両方を上回る、低コストのクラスタリングを生成する。
論文 参考訳（メタデータ） (2020-06-03T17:14:55Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。