論文の概要: The Core in Max-Loss Non-Centroid Clustering Can Be Empty

• arxiv url: http://arxiv.org/abs/2511.19107v1
• Date: Mon, 24 Nov 2025 13:42:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:25.220155
• Title: The Core in Max-Loss Non-Centroid Clustering Can Be Empty
• Title（参考訳）: Max-Lossの非Centroidクラスタリングのコアはエキサイティング
• Authors: Robert Bredereck, Eva Deltl, Leon Kellerhals, Jannik Peters,
• Abstract要約: 我々は,各エージェントの損失がクラスタの他のメンバとの最大距離である最大余剰目標の下で,非セントロイドクラスタリングのコア安定性について検討した。 これは、我々の知る限りでは、コアが最大ロスの目的の下で非セントロイドクラスタリングにおいて空であることを示す最初の不可能な結果である。
• 参考スコア（独自算出の注目度）: 17.80792387357159
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study core stability in non-centroid clustering under the max-loss objective, where each agent's loss is the maximum distance to other members of their cluster. We prove that for all $k\geq 3$ there exist metric instances with $n\ge 9$ agents, with $n$ divisible by $k$, for which no clustering lies in the $α$-core for any $α<2^{\frac{1}{5}}\sim 1.148$. The bound is tight for our construction. Using a computer-aided proof, we also identify a two-dimensional Euclidean point set whose associated lower bound is slightly smaller than that of our general construction. This is, to our knowledge, the first impossibility result showing that the core can be empty in non-centroid clustering under the max-loss objective.
• Abstract（参考訳）: 我々は,各エージェントの損失がクラスタの他のメンバとの最大距離である最大余剰目標の下で,非セントロイドクラスタリングのコア安定性について検討した。 すべての$k\geq 3$に対して、$n\ge 9$エージェントを持つ計量インスタンスが存在し、$n$が$k$で割り切れると、任意の$α<2^{\frac{1}{5}}\sim 1.148$に対して$α$-coreにクラスタリングが存在しないことが証明されている。 私たちの建設には限界がある。 コンピュータ支援による証明を用いて、関連する下界が一般構成よりもわずかに小さい2次元ユークリッド点集合も同定する。 これは、我々の知る限りでは、コアが最大ロスの目的の下で非セントロイドクラスタリングにおいて空であることを示す最初の不可能な結果である。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
  論文  参考訳（メタデータ） (2025-06-01T09:34:52Z)
• Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
  与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。 中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
  論文  参考訳（メタデータ） (2024-10-31T16:33:40Z)
• A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
  我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。 私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。 ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
  論文  参考訳（メタデータ） (2024-02-02T10:44:42Z)
• Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
  Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。 k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。 我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-30T15:49:41Z)
• 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)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。 我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
  論文  参考訳（メタデータ） (2021-04-28T13:35:17Z)
• Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries [22.672233769934845]
  オラクルクエリを用いたクラスタ依存の正確な問題について検討する。 任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
  論文  参考訳（メタデータ） (2021-01-31T18:00:29Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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