論文の概要: Clustering with Tangles: Algorithmic Framework and Theoretical
Guarantees
- arxiv url: http://arxiv.org/abs/2006.14444v3
- Date: Sun, 6 Nov 2022 22:11:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 03:12:06.869457
- Title: Clustering with Tangles: Algorithmic Framework and Theoretical
Guarantees
- Title（参考訳）: Tanglesによるクラスタリング - アルゴリズムフレームワークと理論的保証
- Authors: Solveig Klepper, Christian Elbracht, Diego Fioravanti, Jakob Kneip,
Luca Rendsburg, Maximilian Teegen, Ulrike von Luxburg
- Abstract要約: 本稿では,機械学習応用におけるトライアングルの実用可能性を示す。
任意のデータセットのカットの集合が与えられたとき、トライアングルはこれらのカットを密集構造の方向を指し示すために集約する。
タングルを用いたクラスタリングのためのアルゴリズムフレームワークを構築し、様々な設定で理論的保証を証明し、広範囲なシミュレーションとユースケースを提供する。
- 参考スコア（独自算出の注目度）: 10.992467680364962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Originally, tangles were invented as an abstract tool in mathematical graph
theory to prove the famous graph minor theorem. In this paper, we showcase the
practical potential of tangles in machine learning applications. Given a
collection of cuts of any dataset, tangles aggregate these cuts to point in the
direction of a dense structure. As a result, a cluster is softly characterized
by a set of consistent pointers. This highly flexible approach can solve
clustering problems in various setups, ranging from questionnaires over
community detection in graphs to clustering points in metric spaces. The output
of our proposed framework is hierarchical and induces the notion of a soft
dendrogram, which can help explore the cluster structure of a dataset. The
computational complexity of aggregating the cuts is linear in the number of
data points. Thus the bottleneck of the tangle approach is to generate the
cuts, for which simple and fast algorithms form a sufficient basis. In our
paper we construct the algorithmic framework for clustering with tangles, prove
theoretical guarantees in various settings, and provide extensive simulations
and use cases. Python code is available on github.
- Abstract（参考訳）: もともと、トライアングルは有名なグラフマイナー定理を証明するために数学グラフ理論の抽象的な道具として発明された。
本稿では,機械学習応用におけるタングルの実用的可能性について述べる。
データセットのカットの集合が与えられると、タングルはこれらのカットを集約して密度の高い構造の方向に向ける。
その結果、クラスタは、一貫したポインタの集合によってソフトに特徴づけられる。
この高度に柔軟なアプローチは、グラフのコミュニティ検出よりもアンケートからメトリクス空間のクラスタリングポイントまで、さまざまなセットアップでのクラスタリング問題を解決することができる。
提案するフレームワークの出力は階層的であり,データセットのクラスタ構造を探索するためのソフトなデンドログラムの概念を誘導する。
カットを集約する計算の複雑さはデータポイントの数で線形である。
したがって、タングルアプローチのボトルネックは、単純で高速なアルゴリズムが十分な基礎を形成するカットを生成することである。
本稿では,タングルを用いたクラスタリングのためのアルゴリズムフレームワークを構築し,様々な設定で理論的保証を証明し,広範なシミュレーションとユースケースを提供する。
Pythonコードはgithubで入手できる。
関連論文リスト
- Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。
我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
論文 参考訳（メタデータ） (2023-01-28T11:10:50Z) - flow-based clustering and spectral clustering: a comparison [0.688204255655161]
本研究では,本質的なネットワーク構造を持つデータに対する新しいグラフクラスタリング手法を提案する。
我々は、ユークリッド特徴ベクトルを構築するために、データ固有のネットワーク構造を利用する。
以上の結果から,クラスタリング手法が特定のグラフ構造に対処できることが示唆された。
論文 参考訳（メタデータ） (2022-06-20T21:49:52Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
カーネル重み付けの観点からノード集約を再解釈する。
本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。
特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
論文 参考訳（メタデータ） (2020-05-16T04:44:29Z) - Clustering by Constructing Hyper-Planes [0.0]
データポイントを識別するハイパープレーンを探索し,クラスタリングアルゴリズムを提案する。
中心とクラスターの数を決定するために点間の限界空間に依存する。
このアルゴリズムは線形構造に基づいており、データセットの分布を正確にかつ柔軟に近似することができる。
論文 参考訳（メタデータ） (2020-04-25T08:52:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。