論文の概要: Differentially-Private Clustering of Easy Instances

• arxiv url: http://arxiv.org/abs/2112.14445v1
• Date: Wed, 29 Dec 2021 08:13:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-30 16:35:05.589350
• Title: Differentially-Private Clustering of Easy Instances
• Title（参考訳）: 簡易インスタンスの差分生成クラスタリング
• Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, Eliad Tsfadia
• Abstract要約: 異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 67.04951703461657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentially private clustering algorithms that provide utility when the data is "easy," e.g., when there exists a significant separation between the clusters. We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and $k$-means. We complement our theoretical analysis with an empirical evaluation on synthetic data.
• Abstract（参考訳）: データ分析におけるクラスタリングは根本的な問題である。 異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 重大な研究の進展にもかかわらず、この問題は実際的な解決策に抵抗していた。 本研究では,クラスタ間の分離が著しい場合など,データの“容易”な場合に有用性を提供する,簡易な実装可能な差分プライベートクラスタリングアルゴリズムを提供することを目標としている。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに結合するフレームワークを提案する。 ガウス混合と$k$-meansのいくつかの場合において、サンプルの複雑さ境界を改善することができる。 我々は合成データに関する経験的評価で理論解析を補完する。

関連論文リスト

• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。 オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。 本稿では,データ拡張を必要としない手法を提案する。
  論文  参考訳（メタデータ） (2023-03-29T08:23:26Z)
• Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
  センターベースのクラスタリングと線形サブスペースクラスタリングは、現実世界のデータを小さなクラスタに分割する一般的なテクニックである。 異なる敏感なグループに対する1点当たりのクラスタリングコストは、公平性に関連する害をもたらす可能性がある。 本稿では,社会的に公平なセンタベースのクラスタリングと線形サブスペースクラスタリングを解決するための統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-08-22T07:10:17Z)
• Robust Trimmed k-means [70.88503833248159]
  本稿では,外乱点とクラスタポイントを同時に識別するRobust Trimmed k-means (RTKM)を提案する。 RTKMは他の方法と競合することを示す。
  論文  参考訳（メタデータ） (2021-08-16T15:49:40Z)
• Differentially Private Algorithms for Clustering with Stability Assumptions [0.76146285961466]
  安定な入力をクラスタリングするためのより単純なアルゴリズムを提案する。 我々はWasserstein距離とk-meansコストの両方でその実用性を分析する。 我々のアルゴリズムは、k-medianインスタンスの「ニッチ」と微分プライバシの局所モデルのためのストレートフォワードアナログを持つ。
  論文  参考訳（メタデータ） (2021-06-11T00:45:39Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Heterogeneity for the Win: One-Shot Federated Clustering [8.64969514480008]
  我々は、広く使われている$k$-meansクラスタリング法に基づいて、1ショットのフェデレーションクラスタリングスキームである$k$-FEDを開発し、分析する。 フェデレーションネットワークにおける統計的不均一性の問題は,実際に解析に有用であることを示す。
  論文  参考訳（メタデータ） (2021-03-01T02:17:33Z)
• Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
  本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。 私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。 本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
  論文  参考訳（メタデータ） (2020-09-10T05:21:20Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
  直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。 本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
  論文  参考訳（メタデータ） (2020-02-20T02:41:02Z)

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

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