論文の概要: Chameleon2++: An Efficient Chameleon2 Clustering with Approximate Nearest Neighbors
- arxiv url: http://arxiv.org/abs/2501.02612v1
- Date: Sun, 05 Jan 2025 17:46:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-07 17:05:45.246328
- Title: Chameleon2++: An Efficient Chameleon2 Clustering with Approximate Nearest Neighbors
- Title（参考訳）: Chameleon2++: 近似近辺をクラスタリングする効率的なChameleon2
- Authors: Priyanshu Singh, Kapil Ahuja,
- Abstract要約: 任意の形状、大きさ、密度の高品質なクラスタを識別する階層的クラスタリングアルゴリズム。
Chameleon2の複雑さは$O(n2)$であり、実際に$O(n2logn)$であることを示す。
我々は、正確な$k$-NNサーチを、およそ$k$-NNサーチに置き換える。これにより、アルゴリズムの複雑さをさらに減らし、パフォーマンスを損なうことなく$O(nlogn)$にする。
- 参考スコア（独自算出の注目度）: 0.27624021966289597
- License:
- Abstract: Clustering algorithms are fundamental tools in data analysis, with hierarchical methods being particularly valuable for their flexibility. Chameleon is a widely used hierarchical clustering algorithm that excels at identifying high-quality clusters of arbitrary shapes, sizes, and densities. Chameleon2 is the most recent variant that has demonstrated significant improvements, but suffers from critical failings and there are certain improvements that can be made. The first failure we address is that the complexity of Chameleon2 is claimed to be $O(n^2)$, while we demonstrate that it is actually $O(n^2\log{n})$, with $n$ being the number of data points. Furthermore, we suggest improvements to Chameleon2 that ensure that the complexity remains $O(n^2)$ with minimal to no loss of performance. The second failing of Chameleon2 is that it lacks transparency and it does not provide the fine-tuned algorithm parameters used to obtain the claimed results. We meticulously provide all such parameter values to enhance replicability. The improvement which we make in Chameleon2 is that we replace the exact $k$-NN search with an approximate $k$-NN search. This further reduces the algorithmic complexity down to $O(n\log{n})$ without any performance loss. Here, we primarily configure three approximate nearest neighbor search algorithms (Annoy, FLANN and NMSLIB) to align with the overarching Chameleon2 clustering framework. Experimental evaluations on standard benchmark datasets demonstrate that the proposed Chameleon2++ algorithm is more efficient, robust, and computationally optimal.
- Abstract（参考訳）: クラスタリングアルゴリズムはデータ分析の基本的なツールであり、階層的手法はその柔軟性に特に有用である。
Chameleonは、任意の形状、サイズ、密度の高品質なクラスタを特定するのに優れた階層的クラスタリングアルゴリズムである。
Chameleon2は、最も最近のバージョンで、大幅な改善を示しているが、重大な失敗に悩まされており、いくつかの改善がなされている。
最初の失敗は、Chameleon2の複雑さは$O(n^2)$であり、実際に$O(n^2\log{n})$であり、$n$はデータポイントの数であることを示すことである。
さらに、Chameleon2の改善により、パフォーマンスの損失を最小限に抑えながら、複雑さが$O(n^2)$のままであることを保証する。
Chameleon2の2つめの失敗は、透明性に欠けており、要求された結果を得るために使用される微調整されたアルゴリズムパラメータを提供していないことである。
このようなパラメータ値を慎重に提供し、複製性を高めます。
Chameleon2で実現した改善は、正確な$k$-NN検索を、およそ$k$-NN検索に置き換えることです。
これにより、アルゴリズムの複雑さは、パフォーマンス損失のない$O(n\log{n})$に削減される。
ここでは,おおよそ近接する3つの探索アルゴリズム(Annoy, FLANN, NMSLIB)を,上位のChameleon2クラスタリングフレームワークに合わせるように構成する。
標準ベンチマークデータセットに対する実験的評価は、提案したChameleon2++アルゴリズムがより効率的で、堅牢で、計算的に最適であることを示している。
関連論文リスト
- Learning Tree-Structured Composition of Data Augmentation [16.435641358351976]
そこで本研究では,$k$変換の2進木構造合成を探索するアルゴリズムを提案する。
我々のアルゴリズムはランタイムの複雑さを$O(2d k)$で達成し、$O(kd)$よりもはるかに高速である。
論文 参考訳（メタデータ） (2024-08-26T16:04:13Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
論文 参考訳（メタデータ） (2023-05-22T19:59:19Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。
OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。
OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
論文 参考訳（メタデータ） (2020-06-06T18:41:36Z) - 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) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。