論文の概要: Cluster-and-Conquer: When Randomness Meets Graph Locality

• arxiv url: http://arxiv.org/abs/2010.11497v1
• Date: Thu, 22 Oct 2020 07:31:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 08:27:40.740695
• Title: Cluster-and-Conquer: When Randomness Meets Graph Locality
• Title（参考訳）: Cluster-and-Conquer:Randomnessがグラフの局所性に出会ったとき
• Authors: George Giakkoupis (WIDE), Anne-Marie Kermarrec (EPFL), Olivier Ruas (SPIRALS), Fran\c{c}ois Ta\"iani (WIDE, IRISA)
• Abstract要約: 最も効率的なKNNグラフアルゴリズムのいくつかはインクリメンタルで局所的なものである。 Cluster-and-Conquerは、greedyアルゴリズムの開始構成を強化します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by traversing neighbors-of-neighbors links. Paradoxically, this random start is also one of the key weaknesses of these algorithms: nodes are initially connected to dissimilar neighbors, that lie far away according to the similarity metric. As a result, incremental algorithms must first laboriously explore spurious potential neighbors before they can identify similar nodes, and start converging. In this paper, we remove this drawback with Cluster-and-Conquer (C 2 for short). Cluster-and-Conquer boosts the starting configuration of greedy algorithms thanks to a novel lightweight clustering mechanism, dubbed FastRandomHash. FastRandomHash leverages random-ness and recursion to pre-cluster similar nodes at a very low cost. Our extensive evaluation on real datasets shows that Cluster-and-Conquer significantly outperforms existing approaches, including LSH, yielding speed-ups of up to x4.42 while incurring only a negligible loss in terms of KNN quality.
• Abstract（参考訳）: k-nearest-neighbors(knn)グラフは多くのエンブレマデータマイニングと機械学習アプリケーションの中心である。 最も効率的なknグラフアルゴリズムのいくつかは漸進的かつ局所的であり、ランダムグラフから始まり、近隣のneighborsリンクを横切ることで漸進的に改善される。 反対に、このランダムスタートはこれらのアルゴリズムの重要な弱点の1つでもある:ノードは最初、類似度メートル法により遠く離れた異種近傍に接続される。 結果として、インクリメンタルなアルゴリズムは、最初に、類似のノードを識別し、収束を始める前に、スプリアスな潜在的な隣人を精力的に探さなければならない。 本稿では,Cluster-and-Conquer(略してC2)によるこの欠点を除去する。 fastrandomhashと呼ばれる新しい軽量クラスタリングメカニズムにより、クラスタ・アンド・コンクェリはgreedyアルゴリズムの開始設定を促進する。 FastRandomHashはランダムネスと再帰を利用して、クラスタ前の類似ノードを極めて低コストで処理する。 我々の実際のデータセットに対する広範な評価は、クラスタ・アンド・コンカマーがLSHを含む既存のアプローチを著しく上回り、最大でx4.42のスピードアップとなり、KNNの品質の面では無視できない損失しか生じないことを示している。

関連論文リスト

• Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
  表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。 木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-10-19T14:02:42Z)
• DenMune: Density peak based clustering using mutual nearest neighbors [0.0]
  多くのクラスタリングアルゴリズムは、クラスタが任意の形状、様々な密度、あるいはデータクラスが互いに不均衡で近接している場合に失敗する。 この課題を満たすために、新しいクラスタリングアルゴリズムであるDenMuneが提示されている。 これは、Kがユーザから要求される唯一のパラメータである大きさKの互いに近い近傍を用いて、密集領域を特定することに基づいている。
  論文  参考訳（メタデータ） (2023-09-23T16:18:00Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• 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)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。 本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。 実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
  論文  参考訳（メタデータ） (2022-07-05T05:00:38Z)
• A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
  この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。 分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
  論文  参考訳（メタデータ） (2022-03-02T09:29:40Z)
• Learning Hierarchical Graph Neural Networks for Image Clustering [81.5841862489509]
  本稿では,画像の集合を未知の個数にクラスタリングする方法を学ぶ階層型グラフニューラルネットワーク(GNN)モデルを提案する。 我々の階層的なGNNは、階層の各レベルで予測される連結コンポーネントをマージして、次のレベルで新しいグラフを形成するために、新しいアプローチを用いています。
  論文  参考訳（メタデータ） (2021-07-03T01:28:42Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。 一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
  論文  参考訳（メタデータ） (2021-04-12T17:59:16Z)
• Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural Networks [24.017988997693262]
  ノードとノードのクラスタメンバーシップ間の接続が時間とともに変化する可能性がある動的グラフにおけるノードのクラスタリングの問題を検討する。 まず,ノード間の重み付き接続に基づいてノードをクラスタ化し,その重みが時間とともに一定速度で減少する,簡易な崩壊ベースのクラスタリングアルゴリズムを提案する。 本稿では,各クラスタの最適減衰率を特徴付け,真のクラスタのほぼ完全回復を実現するクラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2020-12-16T04:31:19Z)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。 このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。 本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
  論文  参考訳（メタデータ） (2020-11-11T19:54:38Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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