論文の概要: Constant Approximation for Individual Preference Stable Clustering
- arxiv url: http://arxiv.org/abs/2309.16840v1
- Date: Thu, 28 Sep 2023 20:42:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-02 16:27:44.474949
- Title: Constant Approximation for Individual Preference Stable Clustering
- Title（参考訳）: 個人選好安定クラスタリングのための定数近似
- Authors: Anders Aamand, Justin Y. Chen, Allen Liu, Sandeep Silwal, Pattara
Sukprasert, Ali Vakilian, Fred Zhang
- Abstract要約: 個人の嗜好(IP)安定性は、安定性と公正性の制約に触発された自然なクラスタリングの目的である。
o(n)$-IPの安定クラスタリングが常にエフェキシストであるかどうかは不明であり、それまでの最先端技術では$O(n)$-IPの安定クラスタリングしか保証されていなかった。
O(1)$-IPの安定クラスタリングは常に一般的なメトリクスに対して存在し、そのようなクラスタリングを出力する効率的なアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 26.716316367717585
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Individual preference (IP) stability, introduced by Ahmadi et al. (ICML
2022), is a natural clustering objective inspired by stability and fairness
constraints. A clustering is $\alpha$-IP stable if the average distance of
every data point to its own cluster is at most $\alpha$ times the average
distance to any other cluster. Unfortunately, determining if a dataset admits a
$1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown
if an $o(n)$-IP stable clustering always \emph{exists}, as the prior state of
the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in
understanding and show that an $O(1)$-IP stable clustering always exists for
general metrics, and we give an efficient algorithm which outputs such a
clustering. We also introduce generalizations of IP stability beyond average
distance and give efficient, near-optimal algorithms in the cases where we
consider the maximum and minimum distances within and between clusters.
- Abstract（参考訳）: Ahmadi et al. (ICML 2022)によって導入されたIPの安定性は、安定性と公正性の制約に触発された自然なクラスタリングの目的である。
クラスタリングが$\alpha$-IP である場合、各データポイントから自身のクラスタへの平均距離が、他のクラスタへの平均距離の少なくとも$\alpha$-IP 倍である。
残念ながら、データセットが$$$-ipの安定したクラスタリングを認めているかどうかを決定するのはnp-hardである。
さらに、この研究以前には、$o(n)$-ip 安定クラスタリングが常に \emph{exists} であるかどうかは分かっておらず、以前の状態は$o(n)$-ip安定クラスタリングしか保証されていなかった。
このギャップを解消し、一般的なメトリクスに対して常に$o(1)$-ip安定クラスタリングが存在することを示し、そのようなクラスタリングを出力する効率的なアルゴリズムを与える。
また、平均距離を超えるIP安定性の一般化を導入し、クラスタ内およびクラスタ間の最大および最小距離を考慮した場合、効率よく、ほぼ最適アルゴリズムを提供する。
関連論文リスト
- Scalable Algorithms for Individual Preference Stable Clustering [8.01184332330228]
本稿では,IP安定クラスタリングのための自然局所探索アルゴリズムについて検討する。
このアルゴリズムでは,$O(log n)$-IP安定性が保証され,$n$は入力の点数を表す。
論文 参考訳（メタデータ） (2024-03-15T14:58:27Z) - Dependent Cluster Mapping (DCMAP): Optimal clustering of directed
acyclic graphs for statistical inference [0.0]
Directed Acyclic Graph(DAG)は、推論をサポートするために、クラスタに分割あるいはマッピングすることができる。
本稿では,依存クラスタを用いた最適なクラスタマッピングのためのDCMAPアルゴリズムを提案する。
25ノードのDBNと50ノードのDBNでは、検索スペースは9.91タイム109ドルと1.51タイム1021ドルであり、最初の最適解は934ドル(text95% CI 926,971)であった。
論文 参考訳（メタデータ） (2023-08-08T01:01:37Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Individual Preference Stability for Clustering [24.301650646957246]
本稿では,クラスタリングにおける個別選好(IP)安定性の自然な概念を提案する。
我々の概念は、平均してすべてのデータポイントが、他のどのクラスタのポイントよりも、自身のクラスタのポイントに近いことを要求します。
論文 参考訳（メタデータ） (2022-07-07T22:01:01Z) - 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) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳（メタデータ） (2021-03-16T21:14:56Z) - Stable and consistent density-based clustering via multiparameter
persistence [77.34726150561087]
トポロジカルデータ解析による次数-リップス構成について考察する。
我々は,入力データの摂動に対する安定性を,通信間距離を用いて解析する。
私たちはこれらのメソッドを、Persistableと呼ばれる密度ベースのクラスタリングのためのパイプラインに統合します。
論文 参考訳（メタデータ） (2020-05-18T19:45:04Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。