論文の概要: Universal Weak Coreset
- arxiv url: http://arxiv.org/abs/2305.16890v1
- Date: Fri, 26 May 2023 12:51:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 15:04:48.197230
- Title: Universal Weak Coreset
- Title（参考訳）: Universal Weak Coreset
- Authors: Ragesh Jaiswal and Amit Kumar
- Abstract要約: 弱コアセットは点の部分集合の対$(J,S)$であり、そこでは点集合の要約として$S$が作用し、ポテンシャル中心の集合として$J$が作用する。
我々は、制約付きクラスタリング設定のために、ユニバーサル弱コアセットと呼ばれるこのフレームワークを開発した。
- 参考スコア（独自算出の注目度）: 3.1509756165776635
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Coresets for $k$-means and $k$-median problems yield a small summary of the
data, which preserve the clustering cost with respect to any set of $k$
centers. Recently coresets have also been constructed for constrained $k$-means
and $k$-median problems. However, the notion of coresets has the drawback that
(i) they can only be applied in settings where the input points are allowed to
have weights, and (ii) in general metric spaces, the size of the coresets can
depend logarithmically on the number of points. The notion of weak coresets,
which have less stringent requirements than coresets, has been studied in the
context of classical $k$-means and $k$-median problems. A weak coreset is a
pair $(J,S)$ of subsets of points, where $S$ acts as a summary of the point set
and $J$ as a set of potential centers. This pair satisfies the properties that
(i) $S$ is a good summary of the data as long as the $k$ centers are chosen
from $J$ only, and (ii) there is a good choice of $k$ centers in $J$ with cost
close to the optimal cost. We develop this framework, which we call universal
weak coresets, for constrained clustering settings. In conjunction with recent
coreset constructions for constrained settings, our designs give greater data
compression, are conceptually simpler, and apply to a wide range of constrained
$k$-median and $k$-means problems.
- Abstract（参考訳）: coresets for $k$-means and $k$-median problems(英語版)ではデータの小さな要約が行われ、任意の$k$センターに対するクラスタリングコストが保たれる。
最近、制約付き$k$-meansと$k$-median問題のためにcoresetも構築されている。
しかし、コアセットの概念には欠点がある。
(i)入力点の重み付けが許される設定でのみ適用可能であり、
(ii) 一般計量空間において、コアセットのサイズは点の数に対数的に依存することができる。
弱コアセットの概念は、コアセットよりも厳密な要求が少なく、古典的な$k$-平均問題や$k$-中間問題の文脈で研究されている。
弱コアセットは点の部分集合のペア$(j,s)$であり、ここでは$s$は点集合の要約として、$j$はポテンシャル中心のセットとして振る舞う。
このペアは、その特性を満たす。
(i)$S$は、$k$センターが$J$のみから選ばれている限り、データの良い要約です。
(ii) 最適なコストに近いコストで、$j$で$k$センターを選択するのがよい。
制約のあるクラスタリング設定のために、ユニバーサル弱いコアセットと呼ばれるこのフレームワークを開発します。
最近の制約付き設定のためのcoreset構成と連動して、我々の設計はより大きなデータ圧縮を提供し、概念的にシンプルであり、制約付き$k$medianおよび$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) - Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。
中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。
目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
論文 参考訳（メタデータ） (2024-10-31T16:33:40Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - New Coresets for Projective Clustering and Applications [34.82221047030618]
点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。
我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
論文 参考訳（メタデータ） (2022-03-08T19:50:27Z) - Improved Search of Relevant Points for Nearest-Neighbor Classification [91.3755431537592]
トレーニングセットから除外された場合、トレーニングポイントが$mathbbRd$のクエリポイントの誤分類を引き起こす可能性がある場合、トレーニングポイントは関連していると言います。
出力に敏感なアルゴリズムが提案され、境界点の集合が$P$ in $O(n2 + nk2 )$ time, ここで$k$はそのような集合のサイズである。
本稿では,このアルゴリズムを,O(nk2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(n2)であることを示す。
論文 参考訳（メタデータ） (2022-03-07T18:10:27Z) - Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。
我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
論文 参考訳（メタデータ） (2022-02-25T16:13:28Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z) - Coresets for the Nearest-Neighbor Rule [78.15296214629433]
最も近い隣の凝縮は、サブセット$R の部分集合 P$ を見つけることである。
本稿では,最寄りの分類のためのコアセットの概念を紹介する。
そこで我々は,選択した部分集合のサイズを上界として証明可能な2次時間近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-16T19:00:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。