論文の概要: Faster DBSCAN via subsampled similarity queries

• arxiv url: http://arxiv.org/abs/2006.06743v2
• Date: Thu, 22 Oct 2020 01:19:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 12:39:19.090879
• Title: Faster DBSCAN via subsampled similarity queries
• Title（参考訳）: サブサンプル類似性クエリによるDBSCANの高速化
• Authors: Heinrich Jiang, Jennifer Jang, Jakub {\L}\k{a}cki
• Abstract要約: DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。 本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
• 参考スコア（独自算出の注目度）: 42.93847281082316
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: DBSCAN is a popular density-based clustering algorithm. It computes the $\epsilon$-neighborhood graph of a dataset and uses the connected components of the high-degree nodes to decide the clusters. However, the full neighborhood graph may be too costly to compute with a worst-case complexity of $O(n^2)$. In this paper, we propose a simple variant called SNG-DBSCAN, which clusters based on a subsampled $\epsilon$-neighborhood graph, only requires access to similarity queries for pairs of points and in particular avoids any complex data structures which need the embeddings of the data points themselves. The runtime of the procedure is $O(sn^2)$, where $s$ is the sampling rate. We show under some natural theoretical assumptions that $s \approx \log n/n$ is sufficient for statistical cluster recovery guarantees leading to an $O(n\log n)$ complexity. We provide an extensive experimental analysis showing that on large datasets, one can subsample as little as $0.1\%$ of the neighborhood graph, leading to as much as over 200x speedup and 250x reduction in RAM consumption compared to scikit-learn's implementation of DBSCAN, while still maintaining competitive clustering performance.
• Abstract（参考訳）: DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。 データセットの$\epsilon$-neighborhoodグラフを計算し、高次ノードの接続されたコンポーネントを使用してクラスタを決定する。 しかし、全近傍グラフは、O(n^2)$の最悪の複雑性で計算するには高すぎるかもしれない。 本稿では,サブサンプルである$\epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化する,SNG-DBSCANという単純な変種を提案する。 手順のランタイムは$o(sn^2)$であり、$s$はサンプリングレートである。 いくつかの自然理論的な仮定の下で、$s \approx \log n/n$ は統計的クラスタ回復を保証するのに十分であることを示す。 大規模なデータセットでは、近隣グラフの0.1\%程度のサブサンプリングが可能で、Scikit-LernのDBSCANの実装と比較して200倍以上のスピードアップと250倍のRAM消費が削減され、競争力のあるクラスタリング性能を維持している。

関連論文リスト

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• 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)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Systematically improving existing k-means initialization algorithms at nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
  PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。 与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
  論文  参考訳（メタデータ） (2022-02-08T15:56:30Z)
• Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
  k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。 改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T16:59:03Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)
• Query-Efficient Correlation Clustering [13.085439249887713]
  相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。 相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。 我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-02-26T15:18:20Z)

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

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