論文の概要: Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions

• arxiv url: http://arxiv.org/abs/2603.10721v1
• Date: Wed, 11 Mar 2026 12:53:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-12 16:22:32.947344
• Title: Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
• Title（参考訳）: サンプル・アンド・サーチ:高次元での学習強化kメディアクラスタリングのための効果的なアルゴリズム
• Authors: Kangke Cheng, Shihong Song, Guanlin Mo, Hu Ding,
• Abstract要約: 本稿では,単純で効果的なサンプリング法に基づくアルゴリズムを提案する。 我々は,この手法を,最先端の学習支援手法である$k$-medianクラスタリング法と比較する実験を行った。
• 参考スコア（独自算出の注目度）: 18.61347737579578
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate the learning-augmented $k$-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate $α\in [0,1)$. This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented $k$-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.
• Abstract（参考訳）: 本稿では,従来のクラスタリングアルゴリズムの性能向上を目的とした,誤り率$α\in [0,1)$の予測器で設定した点を前処理することで,学習強化された$k$-medianクラスタリング問題について検討する。 この前処理ステップは、クラスタ化前のポイントに潜在的なラベルを割り当てる。 本稿では,既存のアルゴリズムの時間的複雑さを大幅に改善する,単純で効果的なサンプリング法に基づくこの問題に対するアルゴリズムを提案する。 さらに、ユークリッド空間の次元性に対する指数的依存を緩和する。 最後に,本手法を,最先端の学習支援手法である$k$-medianクラスタリング法と比較する実験を行った。 実験結果から,提案手法は,クラスタリングコストの低減を図りながら,実際の計算複雑性を大幅に低減できる可能性が示唆された。

関連論文リスト

• Average Sensitivity of Hierarchical $k$-Median Clustering [9.107341310040155]
  階層的およびセントロイドベースのクラスタリングを橋渡しする階層的$k$-medianクラスタリング問題に焦点を当てる。 階層的な$k$-medianクラスタリングのための効率的なアルゴリズムを提案し,その平均感度とクラスタリング品質を理論的に証明する。
  論文  参考訳（メタデータ） (2025-07-14T14:02:31Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Unsupervised Machine Learning to Classify the Confinement of Waves in Periodic Superstructures [0.0]
  我々は教師なし機械学習を用いて、最近提示した波動閉じ込め解析のスケーリング手法の精度を向上させる。 我々は、標準のk-means++アルゴリズムと、独自のモデルベースアルゴリズムを採用する。 クラスタリング手法はより物理的に意味のある結果をもたらすが、正しい閉じ込め次元の集合を特定するのに苦労する可能性がある。
  論文  参考訳（メタデータ） (2023-04-24T08:22:01Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。 このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。 このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
  論文  参考訳（メタデータ） (2022-09-27T19:04:36Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Envelope Imbalance Learning Algorithm based on Multilayer Fuzzy C-means Clustering and Minimum Interlayer discrepancy [14.339674126923903]
  本稿では,マルチ層ファジィc-means(MlFCM)と最小層間離散化機構(MIDMD)を用いたディープインスタンスエンベロープネットワークに基づく不均衡学習アルゴリズムを提案する。 このアルゴリズムは、事前の知識がなければ、ディープインスタンスエンベロープネットワークを使用して、高品質なバランスの取れたインスタンスを保証できる。
  論文  参考訳（メタデータ） (2021-11-02T04:59:57Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Fair Correlation Clustering [92.15492066925977]
  相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。 相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
  論文  参考訳（メタデータ） (2020-02-06T14:28:21Z)

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

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