論文の概要: Coresets for Clustering Under Stochastic Noise

• arxiv url: http://arxiv.org/abs/2510.23438v1
• Date: Mon, 27 Oct 2025 15:41:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:15.594603
• Title: Coresets for Clustering Under Stochastic Noise
• Title（参考訳）: 確率雑音下でのクラスタリングのためのコアセット
• Authors: Lingxiao Huang, Zhize Li, Nisheeth K. Vishnoi, Runkai Yang, Haoyu Zhao,
• Abstract要約: 本稿では,入力データセットがノイズによって破損した場合に,$(k, z)$-clusteringに対してコアセットを構築するという問題について検討する。 私たちは、真のクラスタリングコストと確実に関連付けられた、トラクタブルなサロゲートエラーメトリクスを使用します。 コアセットのサイズは最大$mathrmpoly(k)$で改善できるが、$n$はデータセットのサイズである。
• 参考スコア（独自算出の注目度）: 33.12252505929148
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independently of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an $\varepsilon$-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to $\mathrm{poly}(k)$, where $n$ is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.
• Abstract（参考訳）: 本稿では,入力データセットが既知の分布から引き出された確率的雑音によって劣化した場合に,$(k, z)$-clusteringに対してコアセットを構築するという問題について検討する。 この設定では、コアセットの品質を評価することは本質的に難しい。 そこで,本研究では,真のクラスタリングコストと高い相関性を有するサロゲート誤差測定値を用いてコアセット構築について検討する。 従来のメトリクスを以前の作業から分析し、真のコストとより密に一致した新しいエラーメトリックを導入します。 我々の測定基準はノイズ分布とは独立に定義されているが、騒音レベルのスケールを近似保証することができる。 この測定値に基づいてコアセット構築アルゴリズムを設計し、データとノイズの軽度な仮定の下で、我々の測定値の下に$\varepsilon$-boundを強制すると、より小さなコアセットが得られ、古典的な測定値よりも真のクラスタリングコストが保証されることを示す。 特に、コアセットのサイズが最大$\mathrm{poly}(k)$で改善できることを証明する。 実世界のデータセットの実験は、我々の理論的な発見を支援し、我々のアプローチの実践的な利点を実証する。

関連論文リスト

• DAG DECORation: Continuous Optimization for Structure Learning under Hidden Confounding [0.0]
  本研究では, 線形ガウスSEMの構造学習について検討した。 我々は,DAGと相関雑音モデルとを共同で学習する単一の可能性に基づく推定器であるtextscDECORを提案する。
  論文  参考訳（メタデータ） (2025-10-02T15:23:30Z)
• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  最適分解点1/2のロバストな推定器であるGeometric Medianを利用する新しいk-subset選択法を提案する。 提案手法は, k-subset を反復的に選択し,部分集合の平均が(潜在的に)ノイズデータセットの GM に近似し,任意の汚損の下でもロバスト性を確保する。
  論文  参考訳（メタデータ） (2025-04-01T09:22:05Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。 多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
  論文  参考訳（メタデータ） (2024-09-08T13:08:45Z)
• TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization [2.4783546111391215]
  密度に基づくモード探索法は,低密度点から高密度近傍への遠心依存性を生成する。 両言語の観点から, 局所的に定義された依存関係を探索することにより, 固有性という新しい概念を導入する。 我々は,グローバルビューの典型性を利用して,モードを効果的かつ効率的に識別するアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-08-19T15:26:25Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Revisiting Rotation Averaging: Uncertainties and Robust Losses [51.64986160468128]
  現在の手法の主な問題は、推定エピポーラを通して入力データと弱い結合しか持たない最小コスト関数である。 本稿では,点対応から回転平均化への不確実性を直接伝播させることにより,基礎となる雑音分布をモデル化することを提案する。
  論文  参考訳（メタデータ） (2023-03-09T11:51:20Z)
• Coresets for Time Series Clustering [33.801060211529354]
  本稿では,時系列データを用いたクラスタリング問題に対するコアセット構築の問題について検討する。 我々の主な貢献は混合モデルのためのコアセットを構築するアルゴリズムである。 合成データを用いて,コアセットの性能を実証的に評価した。
  論文  参考訳（メタデータ） (2021-10-28T16:21:13Z)
• Noise-robust Clustering [2.0199917525888895]
  本稿では,教師なし機械学習におけるノイズロバストクラスタリング手法を提案する。 ノイズ、一貫性、その他の曖昧性に関する不確実性は、データ分析において深刻な障害となる可能性がある。
  論文  参考訳（メタデータ） (2021-10-17T17:15:13Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。 アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
  論文  参考訳（メタデータ） (2021-06-04T16:37:19Z)

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

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