Fugu-MT 論文翻訳(概要): Scalable Algorithms for Individual Preference Stable Clustering

論文の概要: Scalable Algorithms for Individual Preference Stable Clustering

arxiv url: http://arxiv.org/abs/2403.10365v1
Date: Fri, 15 Mar 2024 14:58:27 GMT
ステータス: 処理完了
システム内更新日: 2024-03-18 16:41:56.946418
Title: Scalable Algorithms for Individual Preference Stable Clustering
Title（参考訳）: 個人選好安定クラスタリングのためのスケーラブルアルゴリズム
Authors: Ron Mosenzon, Ali Vakilian,
Abstract要約: 本稿では,IP安定クラスタリングのための自然局所探索アルゴリズムについて検討する。このアルゴリズムでは,$O(log n)$-IP安定性が保証され,$n$は入力の点数を表す。
参考スコア（独自算出の注目度）: 8.01184332330228
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is $\alpha$-IP stable when each data point's average distance to its cluster is no more than $\alpha$ times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(\log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, $\tilde{O}(nk)$.
Abstract（参考訳）: 本稿では、クラスタリングにおける個人の公正性と安定性を捉える概念である、個人の嗜好(IP)安定性について検討する。この設定内で、クラスタリングは、各データポイントのクラスタへの平均距離が他のクラスタへの平均距離の$\alpha$-IP 倍以下である場合、$\alpha$-IP 安定である。本稿では,IP安定クラスタリングのための自然局所探索アルゴリズムについて検討する。このアルゴリズムでは,$O(\log n)$-IP安定性が保証され,$n$は入力の点数を表す。さらに、局所的な探索手法を洗練することにより、ほぼ線形時間で、$\tilde{O}(nk)$で実行されることを示す。

関連論文リスト

A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Constant Approximation for Individual Preference Stable Clustering [26.716316367717585]
個人の嗜好(IP)安定性は、安定性と公正性の制約に触発された自然なクラスタリングの目的である。 o(n)$-IPの安定クラスタリングが常にエフェキシストであるかどうかは不明であり、それまでの最先端技術では$O(n)$-IPの安定クラスタリングしか保証されていなかった。 O(1)$-IPの安定クラスタリングは常に一般的なメトリクスに対して存在し、そのようなクラスタリングを出力する効率的なアルゴリズムを提供する。
論文参考訳（メタデータ） (2023-09-28T20:42:46Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
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)
Approximate spectral clustering with eigenvector selection and self-tuned $k$ [1.827510863075184]
最近出現したスペクトルクラスタリングは、凸性仮定なしで任意の形状のクラスターを検出することによって、従来のクラスタリング法を超越している。実際には、$k$のマニュアル設定は主観的あるいは時間を要する可能性がある。提案アルゴリズムは、ASCの2つの重要なステップにおいて、$k$を推定する2つの関連指標を持つ。実験では、提案アルゴリズムの効率と、$k$を手動で設定する類似の手法と競合する能力を示す。
論文参考訳（メタデータ） (2023-02-22T11:32:24Z)
Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文参考訳（メタデータ） (2022-10-31T03:00:11Z)
Individual Preference Stability for Clustering [24.301650646957246]
本稿では,クラスタリングにおける個別選好(IP)安定性の自然な概念を提案する。我々の概念は、平均してすべてのデータポイントが、他のどのクラスタのポイントよりも、自身のクラスタのポイントに近いことを要求します。
論文参考訳（メタデータ） (2022-07-07T22:01:01Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
Stable and consistent density-based clustering via multiparameter persistence [77.34726150561087]
トポロジカルデータ解析による次数-リップス構成について考察する。我々は,入力データの摂動に対する安定性を,通信間距離を用いて解析する。私たちはこれらのメソッドを、Persistableと呼ばれる密度ベースのクラスタリングのためのパイプラインに統合します。
論文参考訳（メタデータ） (2020-05-18T19:45:04Z)

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