論文の概要: Explainable Clustering via Exemplars: Complexity and Efficient
Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2209.09670v1
- Date: Tue, 20 Sep 2022 12:09:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-21 17:42:25.982680
- Title: Explainable Clustering via Exemplars: Complexity and Efficient
Approximation Algorithms
- Title(参考訳): Exemplarsによる説明可能なクラスタリング:複雑さと効率的な近似アルゴリズム
- Authors: Ian Davidson, Michael Livanos, Antoine Gourru, Peter Walker, Julien
Velcin and S. S. Ravi
- Abstract要約: 本稿では,各クラスタを説明するためのクラスタや例を見出すための,説明可能なクラスタリング手法を提案する。
理解のための模範的概念の使用は、心理学における模範的概念定義の流派によって支持されている。
一つのクラスタでも説明できるような,小さな例の集合を見つけることは,計算的に難解であることを示す。
- 参考スコア(独自算出の注目度): 30.369731369945296
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Explainable AI (XAI) is an important developing area but remains relatively
understudied for clustering. We propose an explainable-by-design clustering
approach that not only finds clusters but also exemplars to explain each
cluster. The use of exemplars for understanding is supported by the
exemplar-based school of concept definition in psychology. We show that finding
a small set of exemplars to explain even a single cluster is computationally
intractable; hence, the overall problem is challenging. We develop an
approximation algorithm that provides provable performance guarantees with
respect to clustering quality as well as the number of exemplars used. This
basic algorithm explains all the instances in every cluster whilst another
approximation algorithm uses a bounded number of exemplars to allow simpler
explanations and provably covers a large fraction of all the instances.
Experimental results show that our work is useful in domains involving
difficult to understand deep embeddings of images and text.
- Abstract(参考訳): 説明可能なAI(XAI)は重要な開発領域であるが、クラスタリングの分野ではまだ比較的過小評価されている。
本稿では,クラスタを探索するだけでなく,各クラスタを説明する実例を探索する手法を提案する。
理解のための例題の使用は、心理学における例題ベースの概念定義学派によって支持されている。
1つのクラスタでさえも説明できるような小さな例を見つけることは計算に難解であることを示し、全体的な問題は困難である。
本稿では,クラスタリングの品質および使用例数に関して,証明可能な性能保証を提供する近似アルゴリズムを開発した。
この基本的なアルゴリズムは、各クラスタのすべてのインスタンスを解析する一方、別の近似アルゴリズムは、より単純な説明を可能にするために、境界付けられた多数の例を使って、すべてのインスタンスの大部分を確実にカバーする。
画像やテキストの深い埋め込みを理解するのが難しい領域では,本研究が有用であることを示す。
関連論文リスト
- Stable Cluster Discrimination for Deep Clustering [7.175082696240088]
ディープクラスタリングは、インスタンスの表現(つまり、表現学習)を最適化し、固有のデータ分散を探索することができる。
結合された目的は、すべてのインスタンスが一様機能に崩壊する、自明な解決策を意味する。
本研究では,1段階クラスタリングにおいて,教師あり学習における一般的な識別タスクが不安定であることを示す。
新規な安定クラスタ識別(SeCu)タスクを提案し、それに応じて新しいハードネス対応クラスタリング基準を得ることができる。
論文 参考訳(メタデータ) (2023-11-24T06:43:26Z) - 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) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳(メタデータ) (2021-12-29T08:13:56Z) - KnAC: an approach for enhancing cluster analysis with background
knowledge and explanations [0.20999222360659603]
我々はKnAC(Knowledge Augmented Clustering)を紹介します。
KnACは任意のクラスタリングアルゴリズムの拡張として機能し、アプローチを堅牢でモデルに依存しないものにすることができる。
論文 参考訳(メタデータ) (2021-12-16T10:13:47Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Weighted Sparse Subspace Representation: A Unified Framework for
Subspace Clustering, Constrained Clustering, and Active Learning [0.3553493344868413]
まず,近距離点の疎凸結合として各点を表現しようとするスペクトルに基づく新しい部分空間クラスタリングアルゴリズムを提案する。
次に、アルゴリズムを制約付きクラスタリングとアクティブな学習設定に拡張します。
このようなフレームワークを開発する動機は、通常、少量のラベル付きデータが事前に利用可能であるという事実や、いくつかのポイントをコストでラベル付けできるという事実に起因しています。
論文 参考訳(メタデータ) (2021-06-08T13:39:43Z) - Graph Contrastive Clustering [131.67881457114316]
本稿では,クラスタリングタスクに適用可能な新しいグラフコントラスト学習フレームワークを提案し,gcc(graph constrastive clustering)法を考案した。
特に、グラフラプラシアンに基づくコントラスト損失は、より識別的かつクラスタリングフレンドリーな特徴を学ぶために提案されている。
一方で、よりコンパクトなクラスタリング割り当てを学ぶために、グラフベースのコントラスト学習戦略が提案されている。
論文 参考訳(メタデータ) (2021-04-03T15:32:49Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z) - Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。
本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
論文 参考訳(メタデータ) (2020-02-20T02:41:02Z) - Efficient Algorithms for Generating Provably Near-Optimal Cluster
Descriptors for Explainability [36.11663695534294]
本稿では,クラスタに対する簡潔な表現を構築するための最近のアプローチを拡張して,クラスタをより解釈しやすくする問題について検討する。
我々は,その問題に対する性能保証を証明可能な近似アルゴリズムを開発した。
また、異なる脅威レベルを表すゲノム配列のクラスタを含むデータセットからのクラスタを説明するアプリケーションを示す。
論文 参考訳(メタデータ) (2020-02-06T19:49:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。