論文の概要: ExKMC: Expanding Explainable $k$-Means Clustering

• arxiv url: http://arxiv.org/abs/2006.02399v2
• Date: Thu, 2 Jul 2020 01:24:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-25 17:46:50.824619
• Title: ExKMC: Expanding Explainable $k$-Means Clustering
• Title（参考訳）: ExKMC: 説明可能な$k$-Meansクラスタの拡張
• Authors: Nave Frost, Michal Moshkovitz, Cyrus Rashtchian
• Abstract要約: 説明可能性と精度のトレードオフに着目し,$k$-meansクラスタリングのアルゴリズムについて検討した。 我々は、新しい説明可能な$k$-meansクラスタリングアルゴリズム、ExKMCを開発し、$k' geq k$を加算し、$k'$の葉を持つ決定木を出力する。 ExKMCは、標準的な決定木法と説明可能なクラスタリングのための他のアルゴリズムの両方を上回る、低コストのクラスタリングを生成する。
• 参考スコア（独自算出の注目度）: 19.702066333512548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the popularity of explainable AI, there is limited work on effective methods for unsupervised learning. We study algorithms for $k$-means clustering, focusing on a trade-off between explainability and accuracy. Following prior work, we use a small decision tree to partition a dataset into $k$ clusters. This enables us to explain each cluster assignment by a short sequence of single-feature thresholds. While larger trees produce more accurate clusterings, they also require more complex explanations. To allow flexibility, we develop a new explainable $k$-means clustering algorithm, ExKMC, that takes an additional parameter $k' \geq k$ and outputs a decision tree with $k'$ leaves. We use a new surrogate cost to efficiently expand the tree and to label the leaves with one of $k$ clusters. We prove that as $k'$ increases, the surrogate cost is non-increasing, and hence, we trade explainability for accuracy. Empirically, we validate that ExKMC produces a low cost clustering, outperforming both standard decision tree methods and other algorithms for explainable clustering. Implementation of ExKMC available at https://github.com/navefr/ExKMC.
• Abstract（参考訳）: 説明可能なAIの人気にもかかわらず、教師なし学習の効果的な方法には限界がある。 説明可能性と精度のトレードオフに着目し,$k$-meansクラスタリングのアルゴリズムについて検討した。 以前の作業の後、データセットを$k$クラスタに分割するために、小さな決定ツリーを使用します。 これにより、各クラスタ割り当てを、単一機能しきい値の短いシーケンスで説明できる。 大きな木はより正確なクラスタリングを生成するが、さらに複雑な説明を必要とする。 フレキシビリティを実現するために、新しい説明可能な$k$-meansクラスタリングアルゴリズムであるExKMCを開発し、$k' \geq k$を加算し、$k'$の葉を持つ決定木を出力する。 木を効率的に拡張し、葉に$k$クラスタの1つをラベル付けするために、新しいサロゲートコストを使用します。 k'$が増加するにつれて、サロゲートコストは増加せず、したがって説明可能性と精度を交換する。 実験により,ExKMCが低コストのクラスタリングを実現し,標準的な決定木法と説明可能なクラスタリングのためのアルゴリズムの両方に優れることを確認した。 ExKMCの実装はhttps://github.com/navefr/ExKMCで公開されている。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• GBMST: An Efficient Minimum Spanning Tree Clustering Based on Granular-Ball Computing [78.92205914422925]
  多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。 粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。 いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
  論文  参考訳（メタデータ） (2023-03-02T09:04:35Z)
• How to Find a Good Explanation for Clustering? [7.951746797489421]
  Moshkovitz氏、Dasgupta氏、Rashtchian氏、Frost氏(ICML 2020)は、説明可能な$k$-meansと$k$-medianクラスタリングのエレガントなモデルを提案した。 説明可能なクラスタリングに関する2つの自然なアルゴリズム的問題について検討する。 厳密なアルゴリズム分析では、入力サイズ、データの寸法、外乱数、クラスタ数、近似比といったパラメータが、説明可能なクラスタリングの計算複雑性に与える影響について光を当てています。
  論文  参考訳（メタデータ） (2021-12-13T11:48:38Z)
• 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)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。