論文の概要: Privacy-Preserving Vertical K-Means Clustering

• arxiv url: http://arxiv.org/abs/2504.07578v1
• Date: Thu, 10 Apr 2025 09:20:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-11 12:21:29.339022
• Title: Privacy-Preserving Vertical K-Means Clustering
• Title（参考訳）: プライバシー保護型垂直K平均クラスタリング
• Authors: Federico Mazzone, Trevor Brown, Florian Kerschbaum, Kevin H. Wilson, Maarten Everts, Florian Hahn, Andreas Peter,
• Abstract要約: クラスタリングは、1つ以上の機能に基づいたレコードのグループ化に使用される基本的なデータ処理タスクである。 我々は、O(n+kt)への通信複雑性を低減し、同相暗号とDPに基づく新しい解を提案する。 我々のソリューションは、73MBの通信で10万の2次元点を5つのクラスタにクラスタリングし、既存の作業では101GB、100Mbpsのネットワークでは3分弱で完了した。
• 参考スコア（独自算出の注目度）: 24.55805676985619
• License:
• Abstract: Clustering is a fundamental data processing task used for grouping records based on one or more features. In the vertically partitioned setting, data is distributed among entities, with each holding only a subset of those features. A key challenge in this scenario is that computing distances between records requires access to all distributed features, which may be privacy-sensitive and cannot be directly shared with other parties. The goal is to compute the joint clusters while preserving the privacy of each entity's dataset. Existing solutions using secret sharing or garbled circuits implement privacy-preserving variants of Lloyd's algorithm but incur high communication costs, scaling as O(nkt), where n is the number of data points, k the number of clusters, and t the number of rounds. These methods become impractical for large datasets or several parties, limiting their use to LAN settings only. On the other hand, a different line of solutions rely on differential privacy (DP) to outsource the local features of the parties to a central server. However, they often significantly degrade the utility of the clustering outcome due to excessive noise. In this work, we propose a novel solution based on homomorphic encryption and DP, reducing communication complexity to O(n+kt). In our method, parties securely outsource their features once, allowing a computing party to perform clustering operations under encryption. DP is applied only to the clusters' centroids, ensuring privacy with minimal impact on utility. Our solution clusters 100,000 two-dimensional points into five clusters using only 73MB of communication, compared to 101GB for existing works, and completes in just under 3 minutes on a 100Mbps network, whereas existing works take over 1 day. This makes our solution practical even for WAN deployments, all while maintaining accuracy comparable to plaintext k-means algorithms.
• Abstract（参考訳）: クラスタリングは、1つ以上の機能に基づいたレコードのグループ化に使用される基本的なデータ処理タスクである。 垂直に分割された設定では、データはエンティティ間で分散され、それぞれがそれらの機能のサブセットのみを保持する。 このシナリオにおける重要な課題は、レコード間の距離を計算するには、プライバシに敏感で、他のパーティと直接共有できない、すべての分散機能へのアクセスが必要であることだ。 目標は、各エンティティのデータセットのプライバシを保持しながら、ジョイントクラスタを計算することだ。 シークレット共有やガブルド回路を使った既存のソリューションでは、ロイドのアルゴリズムのプライバシ保護の亜種が実装されているが、通信コストが高く、nはデータポイントの数、kはクラスタ数、tはラウンド数である。 これらのメソッドは大規模なデータセットやいくつかのパーティでは実用的ではなく、LAN設定のみに制限される。 一方、異なるソリューションのラインは、パーティのローカル機能を中央サーバにアウトソースするために、差分プライバシ(DP)に依存しています。 しかし、過度なノイズによるクラスタリング結果の有用性は著しく低下することが多い。 本研究では,O(n+kt)への通信複雑性を低減し,同相暗号とDPに基づく新しい解を提案する。 提案手法では,セキュアに機能をアウトソースすることで,暗号化下でのクラスタリング操作を行うことが可能になる。 DPはクラスタのセントロイドにのみ適用され、ユーティリティに最小限の影響でプライバシーを確保する。 既存の作業は101GBで,100Mbpsのネットワークでは3分弱で完了するのに対して,既存の作業は1日以上かかる。 これにより、WANデプロイメントにおいても、平文k-meansアルゴリズムに匹敵する精度を維持しながら、ソリューションを実用的なものにすることができます。

関連論文リスト

• Sparse Decentralized Federated Learning [35.32297764027417]
  分散フェデレートラーニング(DFL)は、中央サーバーなしで協調的なモデルトレーニングを可能にするが、効率、安定性、信頼性の課題に直面している。 Sparse DFL (SDFL) に繋がる共有モデルに空間制約を導入し,新しいアルゴリズムCEPSを提案する。 数値実験により,高い信頼性を維持しつつ,コミュニケーションと効率を向上させるための提案アルゴリズムの有効性が検証された。
  論文  参考訳（メタデータ） (2023-08-31T12:22:40Z)
• DMS: Differentiable Mean Shift for Dataset Agnostic Task Specific Clustering Using Side Information [0.0]
  我々は、サイド情報から直接データをクラスタリングすることを学ぶ新しいアプローチを提案する。 クラスタの数、その中心、あるいは類似性に関するあらゆる種類の距離メートル法を知る必要はありません。 本手法は,特定のタスクのニーズに応じて,同じデータポイントを様々な方法で分割することができる。
  論文  参考訳（メタデータ） (2023-05-29T13:45:49Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。 オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。 本稿では,データ拡張を必要としない手法を提案する。
  論文  参考訳（メタデータ） (2023-03-29T08:23:26Z)
• Efficient Distribution Similarity Identification in Clustered Federated Learning via Principal Angles Between Client Data Subspaces [59.33965805898736]
  クラスタ学習は、クライアントをクラスタにグループ化することで、有望な結果をもたらすことが示されている。 既存のFLアルゴリズムは基本的に、クライアントを同様のディストリビューションでグループ化しようとしている。 以前のFLアルゴリズムは、訓練中に間接的に類似性を試みていた。
  論文  参考訳（メタデータ） (2022-09-21T17:37:54Z)
• Differentially Private Vertical Federated Clustering [13.27934054846057]
  多くのアプリケーションでは、複数のパーティが同じユーザのセットに関するプライベートデータを持っているが、非結合な属性のセットについてである。 データ対象者のプライバシーを保護しながらモデル学習を可能にするためには、垂直連合学習(VFL)技術が必要である。 本論文で提案するアルゴリズムは, 個人用垂直結合型K平均クラスタリングのための最初の実用的な解法である。
  論文  参考訳（メタデータ） (2022-08-02T19:23:48Z)
• Unsupervised Space Partitioning for Nearest Neighbor Search [6.516813715425121]
  本稿では,個別の損失関数を用いて分割処理と学習段階を結合するエンドツーエンド学習フレームワークを提案する。 提案したソリューションの重要な利点は、データセットの高価な事前処理を必要としないことです。 提案手法は,最先端空間分割法とユビキタスK平均クラスタリング法に勝ることを示す。
  論文  参考訳（メタデータ） (2022-06-16T11:17:03Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Very Compact Clusters with Structural Regularization via Similarity and Connectivity [3.779514860341336]
  本稿では,汎用データセットのためのエンドツーエンドのディープクラスタリングアルゴリズムであるVery Compact Clusters (VCC)を提案する。 提案手法は,最先端のクラスタリング手法よりも優れたクラスタリング性能を実現する。
  論文  参考訳（メタデータ） (2021-06-09T23:22:03Z)
• Overcomplete Deep Subspace Clustering Networks [80.16644725886968]
  4つのベンチマークデータセットの実験結果から,クラスタリング誤差の観点から,DSCや他のクラスタリング手法に対する提案手法の有効性が示された。 また,本手法は,最高の性能を得るために事前学習を中止する点にDSCほど依存せず,騒音にも頑健である。
  論文  参考訳（メタデータ） (2020-11-16T22:07:18Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Probabilistic Partitive Partitioning (PPP) [0.0]
  クラスタリングアルゴリズムは一般に2つの一般的な問題に直面している。 彼らは異なる初期条件で異なる設定に収束する。 クラスタの数は、事前に任意に決めなければならない。
  論文  参考訳（メタデータ） (2020-03-09T19:18:35Z)

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

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