論文の概要: Chameleon2++: An Efficient and Scalable Variant Of Chameleon Clustering

• arxiv url: http://arxiv.org/abs/2501.02612v2
• Date: Sun, 05 Oct 2025 15:42:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 14:28:09.257514
• Title: Chameleon2++: An Efficient and Scalable Variant Of Chameleon Clustering
• Title（参考訳）: Chameleon2++ - Chameleonクラスタリングの効率的でスケーラブルなバリアント
• Authors: Priyanshu Singh, Kapil Ahuja,
• Abstract要約: 階層的クラスタリングは、データマイニングにおける根本的な課題である。 最近のアルゴリズム - Chameleon2, M-Chameleon, INNGS-Chameleon は高度な戦略を提案しているが、それでも計算複雑性は$O(nlog n)$である。 Chameleon2をベースアルゴリズムとして、この課題に対処するChameleon2++を紹介します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical clustering remains a fundamental challenge in data mining, particularly when dealing with large-scale datasets where traditional approaches fail to scale effectively. Recent Chameleon-based algorithms - Chameleon2, M-Chameleon, and INNGS-Chameleon have proposed advanced strategies but they still suffer from $O(n^2)$ computational complexity, especially for large datasets. With Chameleon2 as the base algorithm, we introduce Chameleon2++ that addresses this challenge. Our algorithm has three parts. First, Graph Generation - we propose an approximate $k$-NN search instead of an exact one, specifically we integrate with the Annoy algorithm. This results in fast approximate nearest neighbor computation, significantly reducing the graph generation time. Second, Graph Partitioning - we propose use of a multi-level partitioning algorithm instead of a recursive bisection one. Specifically we adapt the hMETIS algorithm instead of the FM. This is because multi-level algorithms are robust to approximation introduced in the graph generation phase yielding higher-quality partitions, and that too with minimum configuration requirements. Third, Merging - we retain the flood fill heuristic that ensures connected balanced components in the partitions as well as efficient partition merging criteria leading to the final clusters. These enhancements reduce the overall time complexity to $O(n\log n)$, achieving scalability. On real-world benchmark datasets used in prior Chameleon works, Chameleon2++ delivers an average of 4% improvement in clustering quality. This demonstrates that algorithmic efficiency and clustering quality can co-exist in large-scale hierarchical clustering.
• Abstract（参考訳）: 階層的クラスタリングは、特に従来のアプローチが効果的にスケールできない大規模データセットを扱う場合、データマイニングにおいて依然として根本的な課題である。 最近のChameleonベースのアルゴリズム - Chameleon2、M-Chameleon、INNGS-Chameleonは高度な戦略を提案しているが、大きなデータセットではO(n^2)$計算の複雑さに悩まされている。 Chameleon2をベースアルゴリズムとして、この課題に対処するChameleon2++を紹介します。 私たちのアルゴリズムには3つの部分があります。 まず、グラフ生成 - 正確な検索ではなく、およそ$k$-NNの検索を提案します。 これにより、高速に近似した近接計算が可能となり、グラフ生成時間が大幅に短縮される。 第2に、グラフ分割 - 再帰的二項分割ではなく、多値分割アルゴリズムを提案する。 具体的には、FMの代わりにhMETISアルゴリズムを適用する。 これは、マルチレベルアルゴリズムがグラフ生成フェーズで導入された近似に頑健であり、高品質なパーティションが得られ、最小構成要件も伴うためである。 第3に、マージ – パーティション内のバランスの取れたコンポーネントと、最終クラスタにつながる効率的なパーティションマージ基準を確実にする、フラッドフィルヒューリスティックを維持します。 これらの拡張により、全体的な時間の複雑さは、スケーラビリティを達成するために$O(n\log n)$に削減される。 Chameleonの以前の作業で使用されている実世界のベンチマークデータセットでは、Chameleon2++はクラスタリングの品質を平均4%改善している。 これはアルゴリズムの効率性とクラスタリングの品質が大規模階層的なクラスタリングにおいて共存可能であることを示している。

関連論文リスト

• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• 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)
• 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)
• Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
  我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。 我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。 これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
  論文  参考訳（メタデータ） (2021-02-16T18:15:51Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• 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)

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

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