論文の概要: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

• arxiv url: http://arxiv.org/abs/2107.01804v1
• Date: Mon, 5 Jul 2021 05:55:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-06 14:40:10.189605
• Title: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
• Title（参考訳）: 施設配置のランダム化次元化と単一リンククラスタリング
• Authors: Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir
• Abstract要約: ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。 本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
• 参考スコア（独自算出の注目度）: 13.208510864854894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.
• Abstract（参考訳）: ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。 本研究では,施設配置問題と,最小スパンディングツリーの計算に等価な単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。 入力点集合 $x$ をランダムな $d = o(d_x)$-次元部分空間(ここで$d_x$ は2倍の次元である)に投影すると、射影空間における最適な施設配置コストは、元のコストを定数に近似する。 最小のスパンディングツリーに対する類似のステートメントを示すが、次元 $d$ は追加の $\log \log n$ 項を持ち、近似係数は任意に 1$ に近い。 さらに、これらの結果をコストだけでなく、ソリューションの近似に拡張する。 最後に,ソリューションの品質と次元減少によるスピードアップを検証するための実験結果を提供する。 このアプローチを$k$-means や $k$-medians の文脈で研究する以前の論文とは異なり、我々の次元境界はクラスタの数に依存するのではなく、本質的な次元の$X$にのみ依存する。

関連論文リスト

• 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)
• Debiasing and a local analysis for population clustering using semidefinite programming [1.9761774213809036]
  サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。 この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• 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)
• New Coresets for Projective Clustering and Applications [34.82221047030618]
  点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。 我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
  論文  参考訳（メタデータ） (2022-03-08T19:50:27Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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