論文の概要: Is Simple Uniform Sampling Efficient for Center-Based Clustering With
Outliers: When and Why?
- arxiv url: http://arxiv.org/abs/2103.00558v1
- Date: Sun, 28 Feb 2021 16:43:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-03 15:45:40.689839
- Title: Is Simple Uniform Sampling Efficient for Center-Based Clustering With
Outliers: When and Why?
- Title（参考訳）: 単体サンプリングはアウトレーヤ付きセンターベースのクラスタリングに有効か:いつとなぜか?
- Authors: Hu Ding and Jiawei Huang
- Abstract要約: 本稿では,3つの中心型クラスタリングをアウトレーヤ問題で解くためのフレームワークを提案する。
実際にフレームワークは非常にシンプルで、入力から小さな一様サンプルを取り出して、既存の近似アルゴリズムをサンプル上で実行する必要があります。
- 参考スコア（独自算出の注目度）: 29.833389636978936
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering has many important applications in computer science, but
real-world datasets often contain outliers. The presence of outliers can make
the clustering problems to be much more challenging. In this paper, we propose
a framework for solving three representative center-based clustering with
outliers problems: $k$-center/median/means clustering with outliers. The
framework actually is very simple, where we just need to take a small uniform
sample from the input and run an existing approximation algorithm on the
sample. However, 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 "significance" criterion 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
sufficiently "significant", which is in fact a fairly appropriate assumption in
practice. Due to its simplicity, the uniform sampling approach also enjoys
several significant advantages over the non-uniform sampling approaches. The
experiments suggest that our framework can achieve comparable clustering
results with existing methods, but is much easier to implement and can greatly
reduce the running times. 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。