論文の概要: Scalable Distributed Approximation of Internal Measures for Clustering
Evaluation
- arxiv url: http://arxiv.org/abs/2003.01430v3
- Date: Wed, 20 Jan 2021 09:34:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 23:27:55.558082
- Title: Scalable Distributed Approximation of Internal Measures for Clustering
Evaluation
- Title（参考訳）: クラスタリング評価のための内部対策のスケーラブル分散近似
- Authors: Federico Altieri, Andrea Pietracaprina, Geppino Pucci, Fabio Vandin
- Abstract要約: クラスタリング評価のための内部測度はシルエット係数であり、計算には2つの距離計算が必要である。
本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。
また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
- 参考スコア（独自算出の注目度）: 5.144809478361603
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The most widely used internal measure for clustering evaluation is the
silhouette coefficient, whose naive computation requires a quadratic number of
distance calculations, which is clearly unfeasible for massive datasets.
Surprisingly, there are no known general methods to efficiently approximate the
silhouette coefficient of a clustering with rigorously provable high accuracy.
In this paper, we present the first scalable algorithm to compute such a
rigorous approximation for the evaluation of clusterings based on any metric
distances. Our algorithm hinges on a Probability Proportional to Size (PPS)
sampling scheme, and, for any fixed $\varepsilon, \delta \in (0,1)$, it
approximates the silhouette coefficient within a mere additive error
$O(\varepsilon)$ with probability $1-\delta$, using a very small number of
distance calculations. We also prove that the algorithm can be adapted to
obtain rigorous approximations of other internal measures of clustering
quality, such as cohesion and separation. Importantly, we provide a distributed
implementation of the algorithm using the MapReduce model, which runs in
constant rounds and requires only sublinear local space at each worker, which
makes our estimation approach applicable to big data scenarios. We perform an
extensive experimental evaluation of our silhouette approximation algorithm,
comparing its performance to a number of baseline heuristics on real and
synthetic datasets. The experiments provide evidence that, unlike other
heuristics, our estimation strategy not only provides tight theoretical
guarantees but is also able to return highly accurate estimations while running
in a fraction of the time required by the exact computation, and that its
distributed implementation is highly scalable, thus enabling the computation of
internal measures for very large datasets for which the exact computation is
prohibitive.
- Abstract（参考訳）: クラスタリング評価において最も広く用いられる内部測度はシルエット係数であり、その計算には2次的な距離計算が必要であり、大規模なデータセットでは明らかに不可能である。
驚くべきことに、クラスタリングのシルエット係数を厳密に証明可能な高精度で効率的に近似する方法は知られていない。
本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。
我々のアルゴリズムは、PPSサンプリングスキームに基づいており、固定された$\varepsilon, \delta \in (0,1)$に対して、単純な加算誤差$O(\varepsilon)$内のシルエット係数を、非常に少数の距離計算を用いて、確率1-\delta$で近似する。
また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
重要なことに、我々はMapReduceモデルを用いてアルゴリズムの分散実装を提供し、これは一定のラウンドで実行され、各ワーカにサブ線形局所空間しか必要としないため、私たちの推定アプローチはビッグデータのシナリオに適用できる。
我々は,シルエット近似アルゴリズムの実験的評価を行い,その性能を実データおよび合成データセット上での多くのベースラインヒューリスティックと比較した。
他のヒューリスティックと異なり、我々の推定戦略は厳密な理論的保証を提供するだけでなく、正確な計算に必要な時間の一部で実行しながら高い精度の見積もりを返すことができ、その分散実装は高度にスケーラブルであるため、正確な計算が禁じられている非常に大きなデータセットに対する内部測度を計算できるという証拠を提供する。
関連論文リスト
- Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。
本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。
大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
論文 参考訳（メタデータ） (2023-09-01T18:02:04Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Statistical, Robustness, and Computational Guarantees for Sliced
Wasserstein Distances [18.9717974398864]
スライスされたワッサーシュタイン距離は古典的なワッサーシュタイン距離の性質を保ちながら、高次元での計算と推定によりスケーラブルである。
このスケーラビリティを, (i) 経験的収束率, (ii) データの汚染に対する堅牢性, (iii) 効率的な計算方法という3つの重要な側面から定量化する。
論文 参考訳（メタデータ） (2022-10-17T15:04:51Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-03T13:45:36Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Manifold learning with approximate nearest neighbors [1.8477401359673706]
多様体学習アルゴリズムでは近距離近傍の近似アルゴリズムを多用し,その埋め込み精度への影響を評価した。
ベンチマークmnistデータセットに基づく徹底的な実証調査により,近似近辺の計算時間が大幅に改善されることが示されている。
本アプリケーションは,提案手法を用いて異常を可視化し,同定し,高次元データ中の基盤構造を明らかにする方法を示す。
論文 参考訳（メタデータ） (2021-02-22T12:04:23Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。
本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文 参考訳（メタデータ） (2020-06-13T06:09:27Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators
with Massive Data [20.79270369203348]
既存の手法は主に高い計算効率のために置換されたサブサンプリングに焦点を当てている。
まず,準類似度推定の文脈で最適なサブサンプリング確率を導出する。
我々は,分散サブサンプリングフレームワークを開発し,全データの小さなパーティションで統計を同時に計算する。
論文 参考訳（メタデータ） (2020-05-21T02:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。