論文の概要: A Greedy Strategy for Graph Cut

• arxiv url: http://arxiv.org/abs/2412.20035v1
• Date: Sat, 28 Dec 2024 05:49:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:05:33.018286
• Title: A Greedy Strategy for Graph Cut
• Title（参考訳）: グラフカットのグレディ戦略
• Authors: Feiping Nie, Shenfei Pei, Zengwei Zheng, Rong Wang, Xuelong Li,
• Abstract要約: GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
• 参考スコア（独自算出の注目度）: 95.2841574410968
• License:
• Abstract: We propose a Greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters which reduces the value of the global objective function the most until the required number of clusters is obtained, and the monotonicity of the sequence of objective function values is proved. To reduce the computational complexity of GGC, only mergers between clusters and their neighbors are considered. Therefore, GGC has a nearly linear computational complexity with respect to the number of samples. Also, unlike other algorithms, due to the greedy strategy, the solution of the proposed algorithm is unique. In other words, its performance is not affected by randomness. We apply the proposed method to solve the problem of normalized cut which is a widely concerned graph cut problem. Extensive experiments show that better solutions can often be achieved compared to the traditional two-stage optimization algorithm (eigendecomposition + k-means), on the normalized cut problem. In addition, the performance of GGC also has advantages compared to several state-of-the-art clustering algorithms.
• Abstract（参考訳）: GGCと呼ばれるグラフカットの問題を解決するためのグリーディ戦略を提案する。 これは、各データサンプルをクラスタと見なす状態から始まり、大域的目的関数の値を最も少なくする2つのクラスタを動的にマージする。 GGCの計算複雑性を低減するために、クラスタと隣人の合併のみを考慮する。 したがって、GCはサンプル数に関してほぼ線形な計算複雑性を持つ。 また、他のアルゴリズムとは異なり、欲求戦略のため、提案アルゴリズムの解は独特である。 言い換えれば、その性能はランダム性に影響されない。 本稿では,グラフ切断問題である正規化カットの問題を解くために提案手法を適用した。 拡張実験により、正規化されたカット問題において、従来の2段階最適化アルゴリズム(固有分解+k平均)と比較して、より良い解がしばしば達成できることが示されている。 さらに、GCの性能は、最先端のクラスタリングアルゴリズムと比較しても利点がある。

関連論文リスト

• A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering [0.30693357740321775]
  最小2乗クラスタリング問題(MSSC)は、$n$のデータポイントを$k$クラスタに分割する問題を指す。 カラム生成(CG)と動的制約集約(DCA)を組み合わせた大規模MSSCインスタンスの効率的な解法を提案する。
  論文  参考訳（メタデータ） (2024-10-08T16:51:28Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
  グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。 既存のGCメソッドは、複雑な最適化プロセス、過剰なコンピューティングリソースとトレーニング時間を必要とする。 我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。 CGCはOgbn-productsグラフを30秒以内に凝縮し、102$Xから104$Xまでのスピードアップを実現し、精度は4.2%まで向上した。
  論文  参考訳（メタデータ） (2024-05-22T14:57:09Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
  任意のサイズ制約下でグラフを分割するグラフカットアルゴリズムを提案する。 我々は,大域収束を臨界点に保証する高速化された近位GDアルゴリズムを用いてこの問題を解決する。
  論文  参考訳（メタデータ） (2024-02-07T10:33:09Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。 一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。 これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
  論文  参考訳（メタデータ） (2023-02-05T18:22:29Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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