論文の概要: $k$-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy

• arxiv url: http://arxiv.org/abs/2206.12895v1
• Date: Sun, 26 Jun 2022 14:58:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-29 07:59:48.355085
• Title: $k$-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy
• Title（参考訳）: Metric Embeddingによる$k$-Medianクラスタリング - 差別化プライバシによるイニシャライゼーション向上を目指す
• Authors: Chenglin Fan, Ping Li, Xiaoyun Li
• Abstract要約: 一般計量空間における$k$-median問題に対する新しいHSTスキームを開発する。 そこで本研究では,新しい探索アルゴリズムを提案する。 私たちのアプローチは、$k$-means問題にも拡張できます。
• 参考スコア（独自算出の注目度）: 31.963659189956367
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When designing clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. In this paper, we develop a new initialization scheme, called HST initialization, for the $k$-median problem in the general metric space (e.g., discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. From the tree, we propose a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. Our proposed HST initialization can produce initial centers achieving lower errors than those from another popular initialization method, $k$-median++, with comparable efficiency. The HST initialization can also be extended to the setting of differential privacy (DP) to generate private initial centers. We show that the error from applying DP local search followed by our private HST initialization improves previous results on the approximation error, and approaches the lower bound within a small factor. Experiments justify the theory and demonstrate the effectiveness of our proposed method. Our approach can also be extended to the $k$-means problem.
• Abstract（参考訳）: クラスタリングアルゴリズムを設計する場合、学習したクラスタの品質には初期センタの選択が不可欠である。 本稿では,一般距離空間(グラフによって引き起こされる離散空間など)における$k$-median問題に対するhst初期化と呼ばれる新しい初期化スキームを,データの計量埋め込み木構造の構築に基づいて開発する。 この木から,局所探索アルゴリズムに使用可能な,優れた初期中心のための,新規で効率的な探索アルゴリズムを提案する。 提案したHSTイニシャライゼーションは,他の一般的な初期化メソッドである$k$-median++よりも低いエラーを発生させる。 HSTの初期化は、ディファレンシャルプライバシ(DP)の設定にまで拡張して、プライベートイニシャルセンターを生成することもできる。 DP局所探索とHSTの初期化による誤差が近似誤差の先行結果を改善することを示し, 最小限の係数で下界に接近することを示した。 実験は理論を正当化し,提案手法の有効性を示す。 私たちのアプローチは、$k$-means問題にも拡張できます。

関連論文リスト

• Unsupervised Learning of Initialization in Deep Neural Networks via Maximum Mean Discrepancy [74.34895342081407]
  本稿では,入力データに対する優れた初期化を求めるための教師なしアルゴリズムを提案する。 まず、パラメータ空間における各パラメータ構成が、d-way分類の特定の下流タスクに対応することに気付く。 次に、学習の成功は、初期パラメータの近傍で下流タスクがいかに多様であるかに直接関連していると推測する。
  論文  参考訳（メタデータ） (2023-02-08T23:23:28Z)
• Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing [10.751269349279912]
  ラベルなしセンシング問題は、変分線形測定から未知の信号を復元することである。 広範に検討されているk-スパース置換モデルに対して,初期化に適した交互最小化アルゴリズムを提案する。 我々のアルゴリズムは計算にスケーラブルであり、ベースライン法と比較すると、実データや合成データに対して優れた性能が得られる。
  論文  参考訳（メタデータ） (2022-11-14T18:44:55Z)
• An enhanced method of initial cluster center selection for K-means algorithm [0.0]
  K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。 Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。 We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
  論文  参考訳（メタデータ） (2022-10-18T00:58:50Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Scalable Initialization Methods for Large-Scale Clustering [0.0]
  K平均クラスタリングのための2つの新しい手法を提案する。 提案手法はスケーラブルであり、並列で実行できる。 実験の結果,提案手法は最先端技術と良好に比較できることがわかった。
  論文  参考訳（メタデータ） (2020-07-23T11:29:53Z)
• Learnable Subspace Clustering [76.2352740039615]
  本研究では,大規模サブスペースクラスタリング問題を効率的に解くために,学習可能なサブスペースクラスタリングパラダイムを開発する。 鍵となる考え方は、高次元部分空間を下層の低次元部分空間に分割するパラメトリック関数を学ぶことである。 我々の知る限り、本論文は、サブスペースクラスタリング手法の中で、数百万のデータポイントを効率的にクラスタ化する最初の試みである。
  論文  参考訳（メタデータ） (2020-04-09T12:53:28Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• A novel initialisation based on hospital-resident assignment for the k-modes algorithm [0.0]
  本稿では,k-modesアルゴリズムの初期解を選択する新しい方法を提案する。 これは、数学的公正性の概念と、文献から共通の初期化ができないデータの活用を可能にする。
  論文  参考訳（メタデータ） (2020-02-07T10:20:49Z)
• MSE-Optimal Neural Network Initialization via Layer Fusion [68.72356718879428]
  ディープニューラルネットワークは、さまざまな分類と推論タスクに対して最先端のパフォーマンスを達成する。 グラデーションと非進化性の組み合わせは、学習を新しい問題の影響を受けやすいものにする。 確率変数を用いて学習した深層ネットワークの近傍層を融合する手法を提案する。
  論文  参考訳（メタデータ） (2020-01-28T18:25:15Z)

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

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