論文の概要: Optimal partitioning of directed acyclic graphs with dependent costs
between clusters
- arxiv url: http://arxiv.org/abs/2308.03970v1
- Date: Tue, 8 Aug 2023 01:01:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-09 14:34:56.930493
- Title: Optimal partitioning of directed acyclic graphs with dependent costs
between clusters
- Title(参考訳): クラスタ間のコストに依存する有向非巡回グラフの最適分割
- Authors: Paul Pao-Yen Wu, Fabrizio Rggeri, Kerrie Mengersen
- Abstract要約: 本稿では,依存クラスタを用いた最適なクラスタマッピングのためのDCMAPアルゴリズムを提案する。
25ノードのDBNと50ノードのDBNでは、検索スペースは、それぞれ9.91タイム109ドルと1.51タイム1021ドルであった。
計算コスト関数のDBNモデルに対して,アルゴリズムが時間効率であることがわかった。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Many statistical inference contexts, including Bayesian Networks (BNs),
Markov processes and Hidden Markov Models (HMMS) could be supported by
partitioning (i.e.~mapping) the underlying Directed Acyclic Graph (DAG) into
clusters. However, optimal partitioning is challenging, especially in
statistical inference as the cost to be optimised is dependent on both nodes
within a cluster, and the mapping of clusters connected via parent and/or child
nodes, which we call dependent clusters. We propose a novel algorithm called
DCMAP for optimal cluster mapping with dependent clusters. Given an arbitrarily
defined, positive cost function based on the DAG and cluster mappings, we show
that DCMAP converges to find all optimal clusters, and returns near-optimal
solutions along the way. Empirically, we find that the algorithm is
time-efficient for a DBN model of a seagrass complex system using a computation
cost function. For a 25 and 50-node DBN, the search space size was $9.91\times
10^9$ and $1.51\times10^{21}$ possible cluster mappings, respectively, but
near-optimal solutions with 88\% and 72\% similarity to the optimal solution
were found at iterations 170 and 865, respectively. The first optimal solution
was found at iteration 934 $(\text{95\% CI } 926,971)$, and 2256 $(2150,2271)$
with a cost that was 4\% and 0.2\% of the naive heuristic cost, respectively.
- Abstract(参考訳): ベイジアンネットワーク(bns)、マルコフ過程、隠れマルコフモデル(hmms)を含む多くの統計推論コンテキストは、基礎となる有向非巡回グラフ(dag)をクラスタに分割することでサポートされる。
しかしながら、最適化するコストはクラスタ内の両方のノードに依存し、依存するクラスタと呼ばれる親ノードと子ノードを介して接続されるクラスタのマッピングであるため、統計的推論では、最適分割は困難である。
本稿では,依存クラスタを用いた最適なクラスタマッピングのためのDCMAPアルゴリズムを提案する。
dagとクラスタマッピングに基づいて任意に定義された正のコスト関数が与えられると、dcmapは収束してすべての最適なクラスタを見つけ、途中に最適に近い解を返す。
実験により,計算コスト関数を用いた海草複合体系のDBNモデルに対して,アルゴリズムは時間効率が高いことがわかった。
25ノードdbnと50ノードdbnでは、探索空間のサイズはそれぞれ9.91\times 10^9$と1.51\times10^{21}$でクラスタマッピングが可能であるが、最適解に88\%と72\%の近似性を持つ近似最適解は170と855である。
第1の最適解は、第9434条の$(\text{95\% ci } 926,971)$、2256の$(2150,2271)$であり、それぞれ平均ヒューリスティックコストの4\%と0.2\%である。
関連論文リスト
- Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳(メタデータ) (2024-04-16T07:05:16Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - 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) - Refining a $k$-nearest neighbor graph for a computationally efficient
spectral clustering [1.5469452301122175]
近似スペクトルクラスタリング(ASC)はサンプリングまたは量子化を使用してデータ代表を選択する。
我々は、データポイントを保持し、エッジ数を積極的に削減する、$k$-nearest 隣のグラフの洗練されたバージョンを提案する。
ASC法と比較して,提案手法はエッジの大幅な削減に拘わらず一貫した性能を示した。
論文 参考訳(メタデータ) (2023-02-22T11:31:32Z) - Hybridization of K-means with improved firefly algorithm for automatic
clustering in high dimension [0.0]
最適なクラスタ数を求めるため,PCAを用いてSilhouette法とElbow法を実装した。
Fireflyアルゴリズムでは、全個体群は自動的にサブ集団に分割され、収束速度を減少させ、局所的なミニマにトラップされる。
本研究は,自動クラスタリングのためのK-meansとODFAモデルを組み合わせた改良型ホタルを提案する。
論文 参考訳(メタデータ) (2023-02-09T18:43:10Z) - Swarm Intelligence for Self-Organized Clustering [6.85316573653194]
Databionic Swarm(DBS)と呼ばれるSwarmシステムが導入された。
スウォームインテリジェンス、自己組織化、出現の相互関係を利用して、DBSはクラスタリングのタスクにおけるグローバルな目的関数の最適化に対する代替アプローチとして機能する。
論文 参考訳(メタデータ) (2021-06-10T06:21:48Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳(メタデータ) (2021-03-16T21:14:56Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。