論文の概要: Individual Preference Stability for Clustering
- arxiv url: http://arxiv.org/abs/2207.03600v1
- Date: Thu, 7 Jul 2022 22:01:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-11 14:02:24.446138
- Title: Individual Preference Stability for Clustering
- Title（参考訳）: クラスタ化のための個人選好安定性
- Authors: Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matth\"aus Kleindessner,
Jamie Morgenstern, Pattara Sukprasert, Ali Vakilian
- Abstract要約: 本稿では,クラスタリングにおける個別選好(IP)安定性の自然な概念を提案する。
我々の概念は、平均してすべてのデータポイントが、他のどのクラスタのポイントよりも、自身のクラスタのポイントに近いことを要求します。
- 参考スコア（独自算出の注目度）: 24.301650646957246
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a natural notion of individual preference (IP)
stability for clustering, which asks that every data point, on average, is
closer to the points in its own cluster than to the points in any other
cluster. Our notion can be motivated from several perspectives, including game
theory and algorithmic fairness. We study several questions related to our
proposed notion. We first show that deciding whether a given data set allows
for an IP-stable clustering in general is NP-hard. As a result, we explore the
design of efficient algorithms for finding IP-stable clusterings in some
restricted metric spaces. We present a polytime algorithm to find a clustering
satisfying exact IP-stability on the real line, and an efficient algorithm to
find an IP-stable 2-clustering for a tree metric. We also consider relaxing the
stability constraint, i.e., every data point should not be too far from its own
cluster compared to any other cluster. For this case, we provide polytime
algorithms with different guarantees. We evaluate some of our algorithms and
several standard clustering approaches on real data sets.
- Abstract（参考訳）: 本稿では,クラスタリングにおける個人選好(IP)安定性の自然な概念を提案し,各データポイントが,他のクラスタのポイントよりも,クラスタ内のポイントに近いことを問う。
我々の概念は、ゲーム理論やアルゴリズム的公正性など、いくつかの観点から動機付けられる。
我々は提案する概念に関するいくつかの質問を考察する。
まず、あるデータセットがip-stableクラスタリングを一般に許すかどうかを決定することはnp-hardであることを示す。
その結果,いくつかの制限付き距離空間におけるIP安定クラスタリングの効率的なアルゴリズムの設計について検討した。
本稿では,実線上の正確なIP安定度を満たすクラスタリングを求めるポリ時間アルゴリズムと,木メータに対するIP安定2クラスタリングを求める効率的なアルゴリズムを提案する。
また、安定性の制約を緩和すること、すなわち、すべてのデータポイントが、他のクラスタと比べて、自身のクラスタから遠ざかるべきではない、とも考えています。
この場合、異なる保証を持つポリタイムアルゴリズムを提供する。
実データに対して,アルゴリズムのいくつかと標準的なクラスタリング手法を評価した。
関連論文リスト
- Gödel Number based Clustering Algorithm with Decimal First Degree Cellular Automata [0.0]
本稿では,FDCAに基づくクラスタリングアルゴリズムを提案する。
データオブジェクトは、G"odel番号ベースのエンコーディングを使用して十進文字列にエンコードされる。
既存のクラスタリングアルゴリズムと比較して,提案アルゴリズムは性能が向上する。
論文 参考訳（メタデータ） (2024-05-08T08:30:34Z) - Scalable Algorithms for Individual Preference Stable Clustering [8.01184332330228]
本稿では,IP安定クラスタリングのための自然局所探索アルゴリズムについて検討する。
このアルゴリズムでは,$O(log n)$-IP安定性が保証され,$n$は入力の点数を表す。
論文 参考訳（メタデータ） (2024-03-15T14:58:27Z) - Constant Approximation for Individual Preference Stable Clustering [26.716316367717585]
個人の嗜好(IP)安定性は、安定性と公正性の制約に触発された自然なクラスタリングの目的である。
o(n)$-IPの安定クラスタリングが常にエフェキシストであるかどうかは不明であり、それまでの最先端技術では$O(n)$-IPの安定クラスタリングしか保証されていなかった。
O(1)$-IPの安定クラスタリングは常に一般的なメトリクスに対して存在し、そのようなクラスタリングを出力する効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-09-28T20:42:46Z) - Privacy-preserving Continual Federated Clustering via Adaptive Resonance
Theory [11.190614418770558]
クラスタリング領域では、フェデレーション学習フレームワーク(フェデレーションクラスタリング)を用いた様々なアルゴリズムが活発に研究されている。
本稿では,プライバシ保護型継続フェデレーションクラスタリングアルゴリズムを提案する。
合成および実世界のデータセットによる実験結果から,提案アルゴリズムはクラスタリング性能が優れていることが示された。
論文 参考訳（メタデータ） (2023-09-07T05:45:47Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Determinantal consensus clustering [77.34726150561087]
本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。
DPPは部分集合内の中心点の多様性を好んでいる。
DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
論文 参考訳（メタデータ） (2021-02-07T23:48:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。