論文の概要: Clustering to Minimize Cluster-Aware Norm Objectives

• arxiv url: http://arxiv.org/abs/2410.24104v1
• Date: Thu, 31 Oct 2024 16:33:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:44.019397
• Title: Clustering to Minimize Cluster-Aware Norm Objectives
• Title（参考訳）: クラスタ対応ノームオブジェクトの最小化のためのクラスタリング
• Authors: Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase,
• Abstract要約: 与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。 中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
• 参考スコア（独自算出の注目度）: 0.3481985817302898
• License:
• Abstract: We initiate the study of the following general clustering problem. We seek to partition a given set $P$ of data points into $k$ clusters by finding a set $X$ of $k$ centers and assigning each data point to one of the centers. The cost of a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$ (inner norm) of the vector of distances of points assigned to $x$. The goal is to minimize a norm $g$ (outer norm) of the vector of cluster costs. This problem, which we call $(f,g)$-Clustering, generalizes many fundamental clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy [STOC'19]) studies norm objectives that are oblivious to the cluster structure such as $k$-Median and $k$-Center. In contrast, our problem models cluster-aware objectives including Min-Sum of Radii and Min-Load $k$-Clustering. Our main results are as follows. First, we design a constant-factor approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest distances. Second, we design a constant-factor approximation\ for $(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex combination of $\textsf{top}_\ell$ norms (ordered weighted norm).
• Abstract（参考訳）: 以下の一般的なクラスタリング問題の研究に着手する。 私たちは、与えられたデータセットの$P$を$k$クラスタに分割し、セットの$X$ of $k$ Centerを見つけ、各データポイントをセンターの1つに割り当てることを模索しています。 中心の$x\in X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。 この問題は$(f,g)$-Clusteringと呼ばれ、$k$-Center, $k$-Median , Min-Sum of Radii, Min-Load $k$-Clustering といった多くの基本的なクラスタリング問題を一般化する。 最近の研究の行(Chakrabarty, Swamy (STOC'19))は、$k$-Medianや$k$-Centerのようなクラスタ構造に不利な規範的目的について研究している。 対照的に、我々の問題は、Radi の Min-Sum や Min-Load $k$-Clustering など、クラスタ対応の目標をモデル化する。 主な成果は以下の通りである。 まず、$(\textsf{top}_\ell,\mathcal{L}_1)$-Clusteringに対して、内部ノルム(\textsf{top}_\ell$)が$$\ell$最大の距離の和となるような定数係数近似アルゴリズムを設計する。 次に、定数係数近似\ for $(\mathcal{L}_\infty,\textsf{Ord})$-Clustering ここで、外ノルムは$\textsf{top}_\ell$ノルム(順序付き重み付きノルム)の凸結合である。

関連論文リスト

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
  我々は,ユーザのネットワーク上で動作する分散クラスタリングアルゴリズムのファミリーを開発する。 DGC-$mathcalF_rho$は、K$-meansやHuber Losといった一般的なクラスタリング損失に特化している。 DGC-$mathcalF_rho$のコンセンサス固定点は、全データ上の勾配クラスタリングの固定点と等価であることを示す。
  論文  参考訳（メタデータ） (2024-02-02T10:44:42Z)
• On Generalization Bounds for Projective Clustering [3.4490841399255823]
  ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。 中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。 j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
  論文  参考訳（メタデータ） (2023-10-13T14:15:54Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Approximation Algorithms for Fair Range Clustering [14.380145034918158]
  本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。 目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。 特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
  論文  参考訳（メタデータ） (2023-06-11T21:18:40Z)
• Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
  ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。 これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
  論文  参考訳（メタデータ） (2021-11-08T20:18:10Z)
• 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)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。 我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
  論文  参考訳（メタデータ） (2021-04-28T13:35:17Z)
• K-expectiles clustering [0.0]
  本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。 固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
  論文  参考訳（メタデータ） (2021-03-16T21:14:56Z)

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

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