論文の概要: Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?

• arxiv url: http://arxiv.org/abs/2103.00558v5
• Date: Tue, 3 Oct 2023 14:59:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 11:32:55.532815
• Title: Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?
• Title（参考訳）: 単体サンプリングはアウトレーヤ付きセンターベースのクラスタリングに有効か:いつ,なぜか?
• Authors: Jiawei Huang, Wenjie Liu and Hu Ding
• Abstract要約: 本稿では,3つの中心型クラスタリングを外乱問題で解くための簡易な一様サンプリングフレームワークを提案する。 我々の分析は、以前の(一様で非一様)サンプリングに基づく考え方と根本的に異なる。
• 参考スコア（独自算出の注目度）: 14.757827466271209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Real-world datasets often contain outliers, and the presence of outliers can make the clustering problems to be much more challenging. In this paper, we propose a simple uniform sampling framework for solving three representative center-based clustering with outliers problems: $k$-center/median/means clustering with outliers. Our analysis is fundamentally different from the previous (uniform and non-uniform) sampling based ideas. To explain the effectiveness of uniform sampling in theory, we introduce a measure of "significance" and prove that the performance of our framework depends on the significance degree of the given instance. In particular, the sample size can be independent of the input data size $n$ and the dimensionality $d$, if we assume the given instance is "significant", which is in fact a fairly reasonable assumption in practice. Due to its simplicity, the uniform sampling approach also enjoys several significant advantages over the non-uniform sampling approaches in practice. To the best of our knowledge, this is the first work that systematically studies the effectiveness of uniform sampling from both theoretical and experimental aspects.
• Abstract（参考訳）: 現実世界のデータセットには、しばしば外れ値が含まれており、外れ値が存在することで、クラスタリングの問題はより困難になる可能性がある。 本稿では,異常値を持つ3つの代表的センターベースクラスタリングを解決するための,簡易な一様サンプリングフレームワークを提案する。 我々の分析は、以前の(一様で非一様)サンプリングに基づく考え方と根本的に異なる。 統一サンプリングの有効性を理論的に説明するために,「意味度」の尺度を導入し,提案手法の性能が与えられたインスタンスの重要度に依存することを証明した。 特に、サンプルサイズは入力データサイズ $n$ と次元 $d$ とは独立であり、与えられたインスタンスが "重要" であると仮定すれば、実際にはかなり合理的な仮定である。 その単純さから、一様サンプリングアプローチは非一様サンプリングアプローチよりもいくつかの大きな利点を享受している。 我々の知る限りでは、これは理論と実験の両方の観点から一様サンプリングの有効性を体系的に研究する最初の作品である。

関連論文リスト

• Mini-batch Submodular Maximization [5.439020425819001]
  単調デコンポーザブルな部分モジュラ関数,$F=sum_i=1N fi$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。 我々は、一様と重み付けの2つのサンプリング手法を検討する。 意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。
  論文  参考訳（メタデータ） (2024-01-23T04:16:58Z)
• Sample Complexity of Robust Learning against Evasion Attacks [3.8888996044605855]
  本研究では, 学習理論の観点から, サンプルの複雑さを考慮し, 逆向きの頑健な学習の実現可能性について検討する。 均一分布下では, 連接関係をしっかり学習する相手の予算への指数的依存は避けられないままである。 問合せ半径が敵の予算に等しければ、分布自由な環境で堅牢な経験的リスクアルゴリズムを開発できることを示す。
  論文  参考訳（メタデータ） (2023-08-23T10:51:33Z)
• Hard Sample Aware Network for Contrastive Deep Graph Clustering [38.44763843990694]
  我々は,Hard Sample Aware Network (HSAN) と呼ばれる,新しい対照的な深層グラフクラスタリング手法を提案する。 本アルゴリズムでは, 属性埋め込みと構造埋め込みの両方を考慮し, サンプル間の類似性を計算した。 得られた高信頼度クラスタリング情報のガイダンスに基づき,提案した重み調整関数は,まず正および負のサンプルを認識する。
  論文  参考訳（メタデータ） (2022-12-16T16:57:37Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  コラボレーティブ・メトリック・ラーニング(CML)パラダイムはレコメンデーション・システム(RS)分野に広く関心を集めている。 負のサンプリングが一般化誤差のバイアス付き推定に繋がることがわかった。 そこで我々は,SFCML (textitSampling-Free Collaborative Metric Learning) という名前のCMLに対して,負のサンプリングを伴わない効率的な手法を提案する。
  論文  参考訳（メタデータ） (2022-06-23T08:50:22Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。 ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。 本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
  論文  参考訳（メタデータ） (2021-05-11T03:38:16Z)
• Optimal Importance Sampling for Federated Learning [57.14673504239551]
  フェデレートラーニングには、集中型と分散化された処理タスクが混在する。 エージェントとデータのサンプリングは概して一様であるが、本研究では一様でないサンプリングについて考察する。 エージェント選択とデータ選択の両方に最適な重要サンプリング戦略を導出し、置換のない一様サンプリングが元のFedAvgアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2020-10-26T14:15:33Z)
• Understanding Negative Sampling in Graph Representation Learning [87.35038268508414]
  最適化目標と結果のばらつきを決定するためには, 正のサンプリングと同様に負のサンプリングが重要であることを示す。 我々は,自己コントラスト近似による正の分布を近似し,メトロポリス・ハスティングスによる負のサンプリングを高速化するメトロポリス・ハスティングス(MCNS)を提案する。 提案手法は,リンク予測,ノード分類,パーソナライズドレコメンデーションを含む,下流グラフ学習タスクをカバーする5つのデータセットに対して評価する。
  論文  参考訳（メタデータ） (2020-05-20T06:25:21Z)
• Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
  判別分析フレームワーク内での大きなサンプルサイズに起因する計算問題を考察する。 線形および二次判別分析のためのトレーニングサンプル数を削減するための新しい圧縮手法を提案する。
  論文  参考訳（メタデータ） (2020-05-08T05:09:08Z)

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

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