論文の概要: Scalable and Distributed Silhouette Approximation
- arxiv url: http://arxiv.org/abs/2607.01993v1
- Date: Thu, 02 Jul 2026 10:27:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-03 19:45:08.789595
- Title: Scalable and Distributed Silhouette Approximation
- Title（参考訳）: スケーラブルで分散シルエット近似
- Abstract要約: シルエットは、$n$要素のデータセットの$k$クラスタリングの品質を評価するために最も広く使用される尺度の1つである。
これまでの$O(n2)$ 距離計算を用いた近似手法では、結果の品質に対する制御可能な保証は提供されていない。
i)データセットの各要素の(局所的な)シルエット、(ii)任意の計量$k$-クラスタリングの(グローバルな)シルエット。
- 参考スコア（独自算出の注目度）: 4.628299420104186
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The silhouette is one of the most widely used measures to assess the quality of a $k$-clustering of a dataset of $n$ elements. Its evaluation requires no information beyond the clustering assignment. In addition, the silhouette is extremely easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. The exact computation of the: (i) silhouette of each element of a dataset; and (ii) the global silhouette of the clustering; require $Θ(n^2)$ distance calculations, under general metrics. The quadratic complexity $Θ(n^2)$ is extremely prohibitive, especially on massive modern datasets. Surprisingly, existing approximate methods using $O(n^2)$ distance calculations are heuristics not offering provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate: (i) the (local) silhouette of each element of a dataset; and (ii) the (global) silhouette; of any metric $k$-clustering. Our methods, based on sampling, perform $O(nk\varepsilon^{-2}\ln (nk/δ))$ distance computations, and provide estimates with additive error $O(\varepsilon)$ with probability at least $1-δ$. That is, parameters $\varepsilon$ and $δ$ in $(0,1)$ control the trade-off between accuracy and efficiency. We also introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Finally, we perform extensive experiments against state-of-the-art approaches. The results show that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation. In addition, our methods scale efficiently to massive datasets for which an exact computation of the silhouette is not practical.
- Abstract（参考訳）: シルエットは、$n$要素のデータセットの$k$クラスタリングの品質を評価するために最も広く使用される尺度の1つである。
その評価はクラスタリングの代入以上の情報を必要としない。
さらに、シルエットの解釈は非常に簡単で、クラスタリングの質を全体または各要素で測定するためのスコアを提供する。
正確な計算は以下の通り。
一 データセットの各要素のシルエット及び
(ii) クラスタリングの大域的シルエット; 一般的な測度の下では、$(n^2)$ 距離計算を必要とする。
二次複雑性$(n^2)$は、特に大規模な現代のデータセットでは、非常に禁じられている。
驚くべきことに、$O(n^2)$距離計算を用いた既存の近似手法は、証明可能で制御可能な結果の品質保証を提供していないヒューリスティックである。
最初の厳密で効率的なアルゴリズムを紹介します。
一 データセットの各要素の(地方)シルエット及び
(ii) (グローバル)シルエット、任意の計量$k$-クラスタリング。
本手法はサンプリングに基づいて,$O(nk\varepsilon^{-2}\ln (nk/δ))$距離計算を行い,少なくとも1-δ$の確率で付加誤差$O(\varepsilon)$を推定する。
つまり、パラメータ $\varepsilon$ と $δ$ in $(0,1)$ は精度と効率のトレードオフを制御する。
また、MapReduceおよびMassively Parallel Computing(MPC)フレームワークのための、我々のメソッドのスケーラブルで分散設計も導入しています。
我々の分散アルゴリズムは、一定数のラウンドとサブ線形ローカルメモリを使用する。
最後に、最先端のアプローチに対する広範な実験を行う。
その結果,本手法は局所およびグローバルなシルエット推定において,精度と効率の最良のトレードオフをもたらすことがわかった。
さらに,本手法は,シルエットの正確な計算が現実的でない大規模データセットに効率よくスケールする。
関連論文リスト
- Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
低ランク近似と残差に基づくサンプリングに基づく新しいデータ選択フレームワークを提案する。
平均損失がデータセット全体の平均損失を近似した$tildeOleft(k + frac1varepsilon2right)$データポイントの重み付きサブセットを選択することができることを示す。
論文 参考訳（メタデータ） (2026-06-14T22:29:59Z) - Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。
本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。
実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
論文 参考訳（メタデータ） (2026-06-04T16:04:31Z) - Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
教師なしの地上距離学習アプローチが導入されました
一つの有望な選択肢はワッサーシュタイン特異ベクトル(WSV)であり、特徴量とサンプルの間の最適な輸送距離を同時に計算する際に現れる。
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
論文 参考訳（メタデータ） (2024-11-11T23:21:01Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Scalable Distributed Approximation of Internal Measures for Clustering
Evaluation [5.144809478361603]
クラスタリング評価のための内部測度はシルエット係数であり、計算には2つの距離計算が必要である。
本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。
また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
論文 参考訳（メタデータ） (2020-03-03T10:28:14Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。