論文の概要: Metric $k$-clustering using only Weak Comparison Oracles
- arxiv url: http://arxiv.org/abs/2601.19333v1
- Date: Tue, 27 Jan 2026 08:17:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-28 15:26:51.24331
- Title: Metric $k$-clustering using only Weak Comparison Oracles
- Title（参考訳）: 弱比較Oracleのみを使用したメトリック$k$-clustering
- Authors: Rahul Raychaudhury, Aryan Esmailpour, Sainyam Galhotra, Stavros Sintos,
- Abstract要約: 本研究では,相対距離比較のみを提供するEmphRank-model (R-model) のクラスタリングについて検討した。
我々のフレームワークは,スケーラブルなクラスタリングアルゴリズムに,いかにノイズの多い低コストのオラクルを体系的に組み込むことができるかを示す。
- 参考スコア（独自算出の注目度）: 10.889763398951262
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Clustering is a fundamental primitive in unsupervised learning. However, classical algorithms for $k$-clustering (such as $k$-median and $k$-means) assume access to exact pairwise distances -- an unrealistic requirement in many modern applications. We study clustering in the \emph{Rank-model (R-model)}, where access to distances is entirely replaced by a \emph{quadruplet oracle} that provides only relative distance comparisons. In practice, such an oracle can represent learned models or human feedback, and is expected to be noisy and entail an access cost. Given a metric space with $n$ input items, we design randomized algorithms that, using only a noisy quadruplet oracle, compute a set of $O(k \cdot \mathsf{polylog}(n))$ centers along with a mapping from the input items to the centers such that the clustering cost of the mapping is at most constant times the optimum $k$-clustering cost. Our method achieves a query complexity of $O(n\cdot k \cdot \mathsf{polylog}(n))$ for arbitrary metric spaces and improves to $O((n+k^2) \cdot \mathsf{polylog}(n))$ when the underlying metric has bounded doubling dimension. When the metric has bounded doubling dimension we can further improve the approximation from constant to $1+\varepsilon$, for any arbitrarily small constant $\varepsilon\in(0,1)$, while preserving the same asymptotic query complexity. Our framework demonstrates how noisy, low-cost oracles, such as those derived from large language models, can be systematically integrated into scalable clustering algorithms.
- Abstract（参考訳）: クラスタリングは教師なし学習における基本的なプリミティブである。
しかし、$k$-clustering($k$-medianや$k$-meansなど)の古典的なアルゴリズムは、多くの現代のアプリケーションでは非現実的な要件である正確なペアワイズ距離へのアクセスを前提としている。
距離へのアクセスは相対距離比較のみを提供する \emph{quadruplet oracle} に完全に置き換えられる。
実際には、そのようなオラクルは学習したモデルや人間のフィードバックを表現することができ、ノイズがあり、アクセスコストがかかることが期待されている。
入力項目が$n$の計量空間を与えられた場合、ノイズの多い四重極オラクルのみを用いて、入力項目から中心へのマッピングとともに$O(k \cdot \mathsf{polylog}(n))$中心の集合を計算し、マッピングのクラスタリングコストが最適な$k$クラスタリングコストのほぼ一定倍となるようにランダム化アルゴリズムを設計する。
この方法は任意の距離空間に対して$O(n\cdot k \cdot \mathsf{polylog}(n))$のクエリ複雑性を達成し、基礎となる計量が有界な倍次元を持つ場合には$O((n+k^2) \cdot \mathsf{polylog}(n))$に改善する。
計量が有界な倍次元を持つとき、同じ漸近的なクエリの複雑さを保ちながら、任意の任意の任意の小さな定数$\varepsilon(0,1)$に対して、定数から1+\varepsilon$への近似をさらに改善することができる。
我々のフレームワークは,大規模言語モデルから派生したような,ノイズの多い低コストのオラクルを,スケーラブルなクラスタリングアルゴリズムに体系的に組み込むことができることを示す。
関連論文リスト
- 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) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。
当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - 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) - Systematically improving existing k-means initialization algorithms at
nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。
与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
論文 参考訳（メタデータ） (2022-02-08T15:56:30Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。