論文の概要: Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
- arxiv url: http://arxiv.org/abs/2512.01150v1
- Date: Mon, 01 Dec 2025 00:01:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-02 19:46:34.606478
- Title: Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
- Title（参考訳）: lpノルム下の説明可能なk-メディアンクラスタリングのための動的アルゴリズム
- Authors: Konstantin Makarychev, Ilias Papanikolaou, Liren Shan,
- Abstract要約: 各有限 p >= 1 に対して lp ノルムの下で説明可能な k-メディアンに対する最初のアルゴリズムを示す。
我々のアルゴリズムは任意の p >= 1 に対して最適な k-メディアンに対する O(p(log k)1 + 1/p - 1/p2) 近似を達成する。
このアルゴリズムは、挿入と削除のシーケンスの下で説明可能なクラスタリングを維持しており、償却更新時間 O(d log3 k) と O(log k) のリコースがある。
- 参考スコア（独自算出の注目度）: 11.05906005268085
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold decision tree that partitions data into k clusters while minimizing the k-medians objective. These trees are interpretable because each internal node makes a simple decision by thresholding a single feature, allowing users to trace and understand how each point is assigned to a cluster. We present the first algorithm for explainable k-medians under lp norm for every finite p >= 1. Our algorithm achieves an O(p(log k)^{1 + 1/p - 1/p^2}) approximation to the optimal k-medians cost for any p >= 1. Previously, algorithms were known only for p = 1 and p = 2. For p = 2, our algorithm improves upon the existing bound of O(log^{3/2}k), and for p = 1, it matches the tight bound of log k + O(1) up to a multiplicative O(log log k) factor. We show how to implement our algorithm in a dynamic setting. The dynamic algorithm maintains an explainable clustering under a sequence of insertions and deletions, with amortized update time O(d log^3 k) and O(log k) recourse, making it suitable for large-scale and evolving datasets.
- Abstract（参考訳）: Dasgupta, Frost, Moshkovitz, Rashtchian (2020) によって導入された説明可能なk-メディアンクラスタリングの問題について検討した。
この問題では、k-メディアンの目的を最小化しつつ、データをkクラスタに分割するしきい値決定木を構築することが目的である。
これらの木は、各内部ノードが単一の機能をしきい値にすることで簡単な決定を下すため、解釈可能であり、各ポイントがクラスタにどのように割り当てられているかをユーザが追跡して理解することができる。
各有限 p >= に対して lp ノルムの下で説明可能な k-メディアンに対する最初のアルゴリズムを示す。
1) アルゴリズムは任意の p >= に対して最適な k-メディアンに対する O(p(log k)^{1 + 1/p - 1/p^2}) 近似を達成する。
1. 以前は、p = 1 と p = 2 のみがアルゴリズムとして知られていたが、p = 2 のアルゴリズムは既存の O(log^{3/2}k) の境界を改良し、p = 1 のアルゴリズムは log k + O(1) のタイトな境界を乗法的な O(log log k) 因子に合わせる。
動的環境下でのアルゴリズムの実装方法を示す。
動的アルゴリズムは、挿入と削除のシーケンスの下で説明可能なクラスタリングを維持し、償却更新時間 O(d log^3 k) と O(log k) のリコースにより、大規模で進化したデータセットに適している。
関連論文リスト
- A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。
木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-10-19T14:02:42Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Relational Algorithms for k-means Clustering [17.552485682328772]
本稿では,関係アルゴリズムモデルにおいて効率的なk平均近似アルゴリズムを提案する。
実行時間は潜在的に$N$よりも小さくなり、リレーショナルデータベースが表すデータポイントの数はクラスタ化される。
論文 参考訳（メタデータ） (2020-08-01T23:21:40Z) - k-means++: few more steps yield constant approximation [3.7468898363447654]
Arthur and Vassilvitskii (SODA 2007) の k-means++ アルゴリズムは k-means クラスタリング問題を解くための最先端のアルゴリズムである。
最近、Lattanzi と Sohler (ICML) は k-means++ を O(k log k) 局所探索ステップで拡張し、k-means クラスタリング問題に一定の近似(期待)をもたらすことを提案した。
論文 参考訳（メタデータ） (2020-02-18T18:28:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。