論文の概要: Enabling DBSCAN for Very Large-Scale High-Dimensional Spaces
- arxiv url: http://arxiv.org/abs/2411.11421v2
- Date: Fri, 29 Nov 2024 08:02:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-02 15:16:12.120581
- Title: Enabling DBSCAN for Very Large-Scale High-Dimensional Spaces
- Title(参考訳): 超大規模高次元空間のためのDBSCANの開発
- Authors: Yongyu Wang,
- Abstract要約: DBSCANは、非パラメトリックな教師なしデータ分析ツールの中で最も重要なものの一つである。
DBSCANアルゴリズムの時間複雑性は$O(n2 beta)$であり、$n$はデータ点の数、$beta = O(D)$はデータ空間の次元を表す$D$である。
スペクトルデータ圧縮に基づくDBSCAN法を提案し、大量のデータポイントと高次元のデータセットを効率的に処理する。
- 参考スコア(独自算出の注目度): 2.1937382384136637
- License:
- Abstract: DBSCAN is one of the most important non-parametric unsupervised data analysis tools. By applying DBSCAN to a dataset, two key analytical results can be obtained: (1) clustering data points based on density distribution and (2) identifying outliers in the dataset. However, the time complexity of the DBSCAN algorithm is $O(n^2 \beta)$, where $n$ is the number of data points and $\beta = O(D)$, with $D$ representing the dimensionality of the data space. As a result, DBSCAN becomes computationally infeasible when both $n$ and $D$ are large. In this paper, we propose a DBSCAN method based on spectral data compression, capable of efficiently processing datasets with a large number of data points ($n$) and high dimensionality ($D$). By preserving only the most critical structural information during the compression process, our method effectively removes substantial redundancy and noise. Consequently, the solution quality of DBSCAN is significantly improved, enabling more accurate and reliable results.
- Abstract(参考訳): DBSCANは、非パラメトリックな教師なしデータ分析ツールの中で最も重要なものの一つである。
データセットにDBSCANを適用することで、(1)密度分布に基づくデータポイントのクラスタリングと(2)データセットの外れ値の識別という、2つの重要な分析結果が得られる。
しかし、DBSCANアルゴリズムの時間複雑性は$O(n^2 \beta)$であり、$n$はデータ点の数、$\beta = O(D)$はデータ空間の次元を表す$D$である。
その結果、$n$と$D$の両方が大きければ、DBSCANは計算不能になる。
本稿では,大量のデータポイント(n$)と高次元性(D$)のデータセットを効率的に処理できるスペクトルデータ圧縮に基づくDBSCAN法を提案する。
圧縮過程においてもっとも重要な構造情報のみを保存することにより,かなりの冗長性とノイズを効果的に除去する。
これにより、DBSCANの溶液品質が大幅に向上し、より正確で信頼性の高い結果が得られる。
関連論文リスト
- Scalable Density-based Clustering with Random Projections [9.028773906859541]
本稿では,コサイン距離の高い高次元密度クラスタリングアルゴリズムであるsDBSCANを提案する。
実証的には、sDBSCANは、現実世界の百万点データセット上の他の多くのクラスタリングアルゴリズムよりもはるかに高速で精度が高い。
論文 参考訳(メタデータ) (2024-02-24T01:45:51Z) - Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。
また、Acharyaなどのアルゴリズムの改良版も提供します。
論文 参考訳(メタデータ) (2023-06-20T06:13:56Z) - Lossy Compression of Large-Scale Radio Interferometric Data [0.0]
本研究は,ベースライン依存型損失圧縮技術を用いて,可視データ量を削減することを提案する。
MeerKAT と European Very Long Baseline Interferometry Network を基準望遠鏡として,提案手法の性能評価・比較を行っている。
論文 参考訳(メタデータ) (2023-04-14T10:50:24Z) - Learned Accelerator Framework for Angular-Distance-Based
High-Dimensional DBSCAN [7.949962335466427]
DBSCANのような従来の密度ベースのクラスタリング技術は、高次元データ上での劣化性能を持つ。
本稿では,従来のDBSCANとサンプリングに基づくDBSCANの変種を高速化する汎用的な学習アクセラレータフレームワークであるLAFを提案する。
評価の結果, LAF強化DBSCAN法は, 効率と品質の両面で, 最先端のDBSCAN法よりも優れていた。
論文 参考訳(メタデータ) (2023-02-06T21:49:03Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳(メタデータ) (2022-08-29T18:01:42Z) - Automating DBSCAN via Deep Reinforcement Learning [73.82740568765279]
本稿では,DBSCANの自動パラメータ検索フレームワークであるDRL-DBSCANを提案する。
このフレームワークは、クラスタリング環境をマルコフ決定プロセスとして知覚することで、パラメータ探索方向を調整する過程をモデル化する。
このフレームワークはDBSCANクラスタリングの精度を最大で26%、25%改善している。
論文 参考訳(メタデータ) (2022-08-09T04:40:11Z) - High Performance Out-of-sample Embedding Techniques for Multidimensional
Scaling [0.5156484100374058]
我々は,大規模なデータに対するMDSアルゴリズムを拡張するために,サンプル外埋め込み(OSE)ソリューションを提案する。
我々は2つのOSE技術を提案する。1つは最適化アプローチに基づくもので、もう1つはニューラルネットワークモデルに基づくものである。
論文 参考訳(メタデータ) (2021-11-07T12:36:33Z) - Visual Cluster Separation Using High-Dimensional Sharpened
Dimensionality Reduction [65.80631307271705]
高次元シャープ化DR(HD-SDR)は、合成データセットと実世界のデータセットの両方で試験される。
提案手法は,高品質(品質指標による測定)を達成し,大規模高次元データを用いて計算的に精度よくスケールする。
具体的な応用を説明するため,近年の天文カタログにHD-SDRを適用した。
論文 参考訳(メタデータ) (2021-10-01T11:13:51Z) - How to distribute data across tasks for meta-learning? [59.608652082495624]
タスクごとのデータポイントの最適な数は予算に依存しますが、それは大きな予算のためのユニークな一定の値に収束します。
この結果から,データ収集の簡便かつ効率的な手順が示唆された。
論文 参考訳(メタデータ) (2021-03-15T15:38:47Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳(メタデータ) (2020-12-29T04:08:38Z) - Faster DBSCAN via subsampled similarity queries [42.93847281082316]
DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。
本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
論文 参考訳(メタデータ) (2020-06-11T18:57:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。