論文の概要: Fast Approximation of Similarity Graphs with Kernel Density Estimation
- arxiv url: http://arxiv.org/abs/2310.13870v1
- Date: Sat, 21 Oct 2023 00:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 04:49:02.269476
- Title: Fast Approximation of Similarity Graphs with Kernel Density Estimation
- Title（参考訳）: 核密度推定による類似度グラフの高速近似
- Authors: Peter Macgregor and He Sun
- Abstract要約: 我々は,データポイントのセットである$X$から類似性グラフを構築するための新しいアルゴリズムをmathbbRd$に提示する。
提案アルゴリズムはカーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
- 参考スコア（独自算出の注目度）: 12.321755440062732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constructing a similarity graph from a set $X$ of data points in
$\mathbb{R}^d$ is the first step of many modern clustering algorithms. However,
typical constructions of a similarity graph have high time complexity, and a
quadratic space dependency with respect to $|X|$. We address this limitation
and present a new algorithmic framework that constructs a sparse approximation
of the fully connected similarity graph while preserving its cluster structure.
Our presented algorithm is based on the kernel density estimation problem, and
is applicable for arbitrary kernel functions. We compare our designed algorithm
with the well-known implementations from the scikit-learn library and the FAISS
library, and find that our method significantly outperforms the implementation
from both libraries on a variety of datasets.
- Abstract（参考訳）: 類似性グラフを$X$のデータポイントから$\mathbb{R}^d$で構築することは、多くの現代的なクラスタリングアルゴリズムの最初のステップである。
しかし、類似性グラフの典型的な構成は、高時間複雑性を持ち、$|X|$ に対する二次空間依存性を持つ。
この制限に対処し、クラスタ構造を維持しつつ、完全連結な類似性グラフのスパース近似を構成する新しいアルゴリズムフレームワークを提案する。
提案アルゴリズムは,カーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
設計したアルゴリズムと,Scikit-LernライブラリとFAISSライブラリのよく知られた実装を比較し,本手法が各種データセット上で両ライブラリの実装を著しく上回っていることを確認する。
関連論文リスト
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs [7.616556723260849]
本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリング(HC)アルゴリズムを提案する。
明確なクラスタ構造を持つ任意の入力グラフ$G$に対して、我々の設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に実行される。
設計したアルゴリズムは、より少ない実行時間で、より優れたHCツリーを生成する。
論文 参考訳（メタデータ） (2023-06-16T16:31:46Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳（メタデータ） (2023-05-07T19:28:23Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T04:57:37Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。
本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文 参考訳（メタデータ） (2021-12-16T17:52:04Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
カーネル重み付けの観点からノード集約を再解釈する。
本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。
特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
論文 参考訳（メタデータ） (2020-05-16T04:44:29Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳（メタデータ） (2020-02-26T17:43:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。