論文の概要: 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%改善している。 これはアルゴリズムの効率性とクラスタリングの品質が大規模階層的なクラスタリングにおいて共存可能であることを示している。

関連論文リスト

• An Enhanced Model-based Approach for Short Text Clustering [58.60681789677676]
  Twitter、Google+、Facebookなどのソーシャルメディアの人気が高まり、短いテキストのクラスタリングがますます重要になっている。 既存の手法は、トピックモデルに基づくアプローチと深層表現学習に基づくアプローチの2つのパラダイムに大別することができる。 短文の空間性と高次元性を効果的に扱えるDirichlet Multinomial Mixture Model (GSDMM) のギブスサンプリングアルゴリズムを提案する。 さらなる改良を保証しているGSDMMのいくつかの側面に基づいて,さらなる性能向上を目的とした改良されたアプローチであるGSDMM+を提案する。
  論文  参考訳（メタデータ） (2025-07-18T10:07:42Z)
• 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)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• 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)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。 ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。 クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。 ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
  論文  参考訳（メタデータ） (2023-05-28T15:33:24Z)
• 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)
• Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm [3.7491936479803054]
  我々はGenieと呼ばれる新しい階層的クラスタリングリンク基準を提案する。 我々のアルゴリズムは、2つのクラスタを、選択された経済不平等尺度が与えられたしきい値を超えないようにリンクする。 このアルゴリズムのリファレンス実装は、Rのためのオープンソースの'genie'パッケージに含まれている。
  論文  参考訳（メタデータ） (2022-09-13T06:42:53Z)
• CloudAttention: Efficient Multi-Scale Attention Scheme For 3D Point Cloud Learning [81.85951026033787]
  この作業にトランスフォーマーをセットし、それらを形状分類と部分およびシーンセグメンテーションのための階層的なフレームワークに組み込む。 また、各イテレーションにおけるサンプリングとグループ化を活用して、効率的でダイナミックなグローバルなクロスアテンションを計算します。 提案した階層モデルは,最先端の形状分類を平均精度で達成し,従来のセグメンテーション法と同等の結果を得る。
  論文  参考訳（メタデータ） (2022-07-31T21:39:15Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
  エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。 階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。 提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
  論文  参考訳（メタデータ） (2021-06-10T09:29:05Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。 従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。 我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
  論文  参考訳（メタデータ） (2021-06-08T23:13:27Z)
• 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)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。 一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
  論文  参考訳（メタデータ） (2021-04-12T17:59:16Z)
• 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)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。 このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。 本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
  論文  参考訳（メタデータ） (2020-11-11T19:54:38Z)
• 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)

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

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