論文の概要: Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space

• arxiv url: http://arxiv.org/abs/2106.07319v1
• Date: Mon, 14 Jun 2021 11:45:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-15 15:33:27.946538
• Title: Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space
• Title（参考訳）: 低次元ユークリッド空間における制約付きk中間およびk平均クラスタリングのコアセット
• Authors: Melanie Schmidt and Julian Wargalla
• Abstract要約: ストリーミングモデルに制約のある$k$-medianと$k$-meansを研究します。 2019年に提案された、特定の制約付きストリーミングの問題(すなわち、$k$-meansクラスタリング)を解決するためのテクニックは、実際には、これらの制約すべてに対してストリーミングアルゴリズムを暗示している。
• 参考スコア（独自算出の注目度）: 1.218340575383456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study (Euclidean) $k$-median and $k$-means with constraints in the streaming model. There have been recent efforts to design unified algorithms to solve constrained $k$-means problems without using knowledge of the specific constraint at hand aside from mild assumptions like the polynomial computability of feasibility under the constraint (compute if a clustering satisfies the constraint) or the presence of an efficient assignment oracle (given a set of centers, produce an optimal assignment of points to the centers which satisfies the constraint). These algorithms have a running time exponential in $k$, but can be applied to a wide range of constraints. We demonstrate that a technique proposed in 2019 for solving a specific constrained streaming $k$-means problem, namely fair $k$-means clustering, actually implies streaming algorithms for all these constraints. These work for low dimensional Euclidean space. [Note that there are more algorithms for streaming fair $k$-means today, in particular they exist for high dimensional spaces now as well.]
• Abstract（参考訳）: 私たちはストリーミングモデルに制約付きで、k$medianとk$-means(euclidean)を調べました。 制約の下で実現可能性の多項式計算可能性(もしクラスタリングが制約を満たすなら計算する)や効率的な割当オラクルの存在(センターの集合を配置し、制約を満たすセンターへの最適なポイントの割り当てを生成する)といった穏やかな仮定を除いて、手元に特定の制約の知識を用いることなく、制約付き$k$-means問題を解くための統一アルゴリズムの設計が近年行われている。 これらのアルゴリズムは、実行時間は$k$で指数関数的であるが、幅広い制約に適用できる。 2019年に提案された制限付きストリーミング$k$-means問題の解法、すなわちフェア$k$-meansクラスタリングは、実際にこれらの制約すべてに対してストリーミングアルゴリズムを暗示している。 これらは低次元ユークリッド空間に作用する。 [なお、現在、k$-meansをストリーミングするためのアルゴリズムが増えていることに注意してください。特に、高次元空間にも存在します。]

関連論文リスト

• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
  複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。 我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。 PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
  論文  参考訳（メタデータ） (2024-11-02T02:50:12Z)
• 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)
• Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
  本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。 高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。 ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
  論文  参考訳（メタデータ） (2023-10-29T16:46:26Z)
• A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.9047096855236125]
  不等式制約を伴う非滑らかな複合最適化は、統計学習とデータ科学において重要である。 textbfOBCDは、これらの課題に対処するための、実現可能な小さな計算フットプリント手法である。 我々はtextbfOBCD がブロック$k$定常点に収束することを証明する。
  論文  参考訳（メタデータ） (2023-04-07T13:44:59Z)
• Global $k$-means$++$: an effective relaxation of the global $k$-means clustering algorithm [0.20305676256390928]
  k$-meansアルゴリズムは、その単純さ、有効性、スピードから、一般的なクラスタリング手法である。 本稿では,高品質クラスタリングソリューションを効果的に取得する手段として,emphglobal $k$-meanstexttt++クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-22T13:42:53Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Structures of Spurious Local Minima in $k$-means [20.155509538529568]
  我々は、$k$-means問題に対する急激な局所解の構造について検討する。 分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
  論文  参考訳（メタデータ） (2020-02-16T22:15:03Z)

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

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