論文の概要: On the price of explainability for some clustering problems
- arxiv url: http://arxiv.org/abs/2101.01576v2
- Date: Sat, 13 Feb 2021 14:39:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-11 15:23:22.826152
- Title: On the price of explainability for some clustering problems
- Title（参考訳）: クラスタリング問題に対する説明可能性の価格について
- Authors: Eduardo Laber, Lucas Murtinho
- Abstract要約: 我々は,決定木を用いて説明可能性を実現する自然モデルに対して,上下境界を提供する。
k$-means と $k$-medians の問題に対して、上限は [moshkovitz et.] によって得られる問題を改善する。
低次元のための al, ICML 20]。
もう1つの貢献は、$k$-means問題に対する説明可能なクラスタリングを構築するための単純で効率的なアルゴリズムである。
- 参考スコア（独自算出の注目度）: 1.52292571922932
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The price of explainability for a clustering task can be defined as the
unavoidable loss,in terms of the objective function, if we force the final
partition to be explainable.
Here, we study this price for the following clustering problems: $k$-means,
$k$-medians, $k$-centers and maximum-spacing. We provide upper and lower bounds
for a natural model where explainability is achieved via decision trees. For
the $k$-means and $k$-medians problems our upper bounds improve those obtained
by [Moshkovitz et. al, ICML 20] for low dimensions.
Another contribution is a simple and efficient algorithm for building
explainable clusterings for the $k$-means problem. We provide empirical
evidence that its performance is better than the current state of the art for
decision-tree based explainable clustering.
- Abstract（参考訳）: クラスタリングタスクの説明可能性の価格は、目的関数の観点から、最終的な分割を説明可能に強制した場合、避けられない損失と定義できる。
ここでは、k$-means、k$-medians、k$-centers、maximum-spacingといったクラスタ問題に対するこの価格を調査します。
我々は,決定木を用いて説明可能性を実現する自然モデルに対して,上下境界を提供する。
k$-means と $k$-medians の問題に対して、上限は [moshkovitz et.] によって得られる問題を改善する。
al, icml 20]低次元の場合。
もう1つの貢献は、$k$-means問題に対する説明可能なクラスタリングを構築するための単純で効率的なアルゴリズムである。
我々は,その性能が決定木に基づく説明可能なクラスタリング技術の現状よりも優れているという実証的な証拠を提供する。
関連論文リスト
- Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳（メタデータ） (2024-09-24T08:59:51Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - 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) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - 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) - 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) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。