論文の概要: Impossibility of Depth Reduction in Explainable Clustering
- arxiv url: http://arxiv.org/abs/2305.02850v1
- Date: Thu, 4 May 2023 14:11:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 15:24:17.779039
- Title: Impossibility of Depth Reduction in Explainable Clustering
- Title（参考訳）: 説明可能なクラスタリングにおける深さ低減の可能性
- Authors: Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, and
Adarsh Srinivasan
- Abstract要約: 入力点がユークリッド平面にある場合でも、説明の深さの減少はk平均とk中間のコストの非有界損失をもたらすことを示す。
我々は、より弱い保証にもかかわらず、結果をk中心の目的にも拡張する。
- 参考スコア（独自算出の注目度）: 2.2835610890984164
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Over the last few years Explainable Clustering has gathered a lot of
attention. Dasgupta et al. [ICML'20] initiated the study of explainable k-means
and k-median clustering problems where the explanation is captured by a
threshold decision tree which partitions the space at each node using axis
parallel hyperplanes. Recently, Laber et al. [Pattern Recognition'23] made a
case to consider the depth of the decision tree as an additional complexity
measure of interest.
In this work, we prove that even when the input points are in the Euclidean
plane, then any depth reduction in the explanation incurs unbounded loss in the
k-means and k-median cost. Formally, we show that there exists a data set X in
the Euclidean plane, for which there is a decision tree of depth k-1 whose
k-means/k-median cost matches the optimal clustering cost of X, but every
decision tree of depth less than k-1 has unbounded cost w.r.t. the optimal cost
of clustering. We extend our results to the k-center objective as well, albeit
with weaker guarantees.
- Abstract（参考訳）: ここ数年間、Explainable Clusteringは多くの注目を集めてきた。
Dasguptaなど。
ICML'20は、各ノードの空間を軸平行超平面を用いて分割する閾値決定木により説明可能なk平均およびk中間クラスタリング問題の研究を開始した。
最近ではlaberらも参加している。
[パターン認識’23]は、決定木の深さを追加の複雑度尺度として検討した。
本研究では,入力点がユークリッド平面にある場合でも,説明の深さの減少がk平均およびk中間コストの非有界損失を引き起こすことを証明した。
形式的には、ユークリッド平面にデータセット x が存在し、k-means/k-medianコストが x の最適クラスタリングコストに一致する深さ k-1 の決定木が存在するが、深さが k-1 未満のすべての決定木は無界コスト w.r.t を持つ。
我々は、より弱い保証とともに、結果をk中心の目的にも拡張する。
関連論文リスト
- Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。
木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-10-19T14:02:42Z) - Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳（メタデータ） (2024-09-24T08:59:51Z) - Explaining Kernel Clustering via Decision Trees [10.504801686625129]
解釈可能なカーネルクラスタリングについて検討し、カーネルk-meansによって誘導されるパーティションを近似するために決定木を構築するアルゴリズムを提案する。
本稿は,k-meansに関する従来の研究に基づいて,解釈可能なモデルの近似保証を犠牲にすることなく,適切な特徴の選択が解釈可能性の維持を可能にすることを実証する。
論文 参考訳（メタデータ） (2024-02-15T11:08:23Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。
分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
論文 参考訳（メタデータ） (2022-03-02T09:29:40Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - 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) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。