論文の概要: Shallow decision trees for explainable $k$-means clustering
- arxiv url: http://arxiv.org/abs/2112.14718v1
- Date: Wed, 29 Dec 2021 18:22:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-30 15:43:39.945391
- Title: Shallow decision trees for explainable $k$-means clustering
- Title（参考訳）: 説明可能な$k$-meansクラスタリングのための浅い決定木
- Authors: Eduardo Laber, Lucas Murtinho, Felipe Oliveira
- Abstract要約: 決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。
16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
- 参考スコア（独自算出の注目度）: 1.2891210250935146
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: A number of recent works have employed decision trees for the construction of
explainable partitions that aim to minimize the $k$-means cost function. These
works, however, largely ignore metrics related to the depths of the leaves in
the resulting tree, which is perhaps surprising considering how the
explainability of a decision tree depends on these depths. To fill this gap in
the literature, we propose an efficient algorithm that takes into account these
metrics. In experiments on 16 datasets, our algorithm yields better results
than decision-tree clustering algorithms such as the ones presented in
\cite{dasgupta2020explainable}, \cite{frost2020exkmc}, \cite{laber2021price}
and \cite{DBLP:conf/icml/MakarychevS21}, typically achieving lower or
equivalent costs with considerably shallower trees. We also show, through a
simple adaptation of existing techniques, that the problem of building
explainable partitions induced by binary trees for the $k$-means cost function
does not admit an $(1+\epsilon)$-approximation in polynomial time unless
$P=NP$, which justifies the quest for approximation algorithms and/or
heuristics.
- Abstract（参考訳）: 最近の多くの研究は、k$-meansコスト関数を最小化することを目的とした説明可能なパーティションを構築するために決定木を採用した。
しかし、これらの研究は結果の木の葉の深さに関する指標をほとんど無視しており、決定木の説明可能性がどのようにこれらの深さに依存するかを考えると、おそらく驚くべきことである。
文献のこのギャップを埋めるために,これらの指標を考慮に入れた効率的なアルゴリズムを提案する。
16のデータセットに対する実験では,提案アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。例えば \cite{dasgupta2020explainable}, \cite{frost 2020exkmc}, \cite{laber2021price} や \cite{DBLP:conf/icml/MakarychevS21} では,比較的浅い木で低コストあるいは同等のコストを得られる。
また, 既存手法の簡単な適応により, $k$-meansコスト関数に対して二分木によって引き起こされる説明可能な分割を構築できる問題は, 近似アルゴリズムやヒューリスティックの探求を正当化する $p=np$ がない限り多項式時間で 1+\epsilon)$-approximation を認めないことを示した。
関連論文リスト
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳（メタデータ） (2022-05-25T09:57:28Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。
ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
論文 参考訳（メタデータ） (2021-06-01T20:23:41Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳（メタデータ） (2021-01-22T01:57:35Z) - On the price of explainability for some clustering problems [1.52292571922932]
我々は,決定木を用いて説明可能性を実現する自然モデルに対して,上下境界を提供する。
k$-means と $k$-medians の問題に対して、上限は [moshkovitz et.] によって得られる問題を改善する。
低次元のための al, ICML 20]。
もう1つの貢献は、$k$-means問題に対する説明可能なクラスタリングを構築するための単純で効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-05T15:08:25Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳（メタデータ） (2020-08-20T03:42:40Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。