論文の概要: Hierarchical Clustering via Local Search

• arxiv url: http://arxiv.org/abs/2405.15983v1
• Date: Fri, 24 May 2024 23:46:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 01:49:07.199533
• Title: Hierarchical Clustering via Local Search
• Title（参考訳）: 局所探索による階層クラスタリング
• Authors: Hossein Jowhari,
• Abstract要約: 階層クラスタリングのための局所探索アルゴリズムを提案する。 任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we introduce a local search algorithm for hierarchical clustering. For the local step, we consider a tree re-arrangement operation, known as the {\em interchange}, which involves swapping two closely positioned sub-trees within a tree hierarchy. The interchange operation has been previously used in the context of phylogenetic trees. As the objective function for evaluating the resulting hierarchies, we utilize the revenue function proposed by Moseley and Wang (NIPS 2017.) In our main result, we show that any locally optimal tree guarantees a revenue of at least $\frac{n-2}{3}\sum_{i < j}w(i,j)$ where is $n$ the number of objects and $w: [n] \times [n] \rightarrow \mathbb{R}^+$ is the associated similarity function. This finding echoes the previously established bound for the average link algorithm as analyzed by Moseley and Wang. We demonstrate that this alignment is not coincidental, as the average link trees enjoy the property of being locally optimal with respect to the interchange operation. Consequently, our study provides an alternative insight into the average link algorithm and reveals the existence of a broader range of hierarchies with relatively high revenue achievable through a straightforward local search algorithm. Furthermore, we present an implementation of the local search framework, where each local step requires $O(n)$ computation time. Our empirical results indicate that the proposed method, used as post-processing step, can effectively generate a hierarchical clustering with substantial revenue.
• Abstract（参考訳）: 本稿では階層クラスタリングのための局所探索アルゴリズムを提案する。 局所的なステップでは、木階層内で密に位置付けられた2つのサブツリーをスワップする木再配置操作を {\emchange} と呼ぶ。 インターチェンジ操作は、以前は系統樹の文脈で用いられてきた。 得られた階層を客観的に評価する関数として、Moseley and Wang (NIPS 2017) が提案した収益関数を利用する: 主な結果として、任意の局所最適木が少なくとも$\frac{n-2}{3}\sum_{i <j}w(i,j)$の収益を保証していることを示す: [n] \times [n] \rightarrow \mathbb{R}^+$ は、関連した類似性関数である。 この発見は、Moseley と Wang が分析した平均リンクアルゴリズムの既定境界を反映している。 このアライメントは、平均リンクツリーが、インターチェンジ操作に関して局所的に最適である性質を享受しているため、一致しないことを示す。 その結果,本研究では,平均リンクアルゴリズムに対する代替的な知見を提供し,比較的高い収益を得られる幅広い階層の存在を,局所探索アルゴリズムにより明らかにした。 さらに、各ローカルステップが$O(n)$計算時間を必要とするローカル検索フレームワークの実装を提案する。 実験の結果,提案手法は後処理のステップとして利用され,実質的な収益を伴う階層的クラスタリングを効果的に生成できることが示唆された。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• When Does Bottom-up Beat Top-down in Hierarchical Community Detection? [8.097200145973389]
  階層的なネットワークのクラスタリングは、階層の低いレベルがよりきめ細かいコミュニティ構造を明らかにするように、コミュニティのツリーを見つけることで構成される。 Agglomerative ($textitbottom-up$)アルゴリズムは、まず最小のコミュニティ構造を特定し、その後、$textitlinkage$メソッドを使ってコミュニティを何度もマージする。 ボトムアップアルゴリズムにより階層木と階層ブロックモデルのコミュニティ構造を復元するための理論的保証を確立する。
  論文  参考訳（メタデータ） (2023-06-01T15:55:46Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
  階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。 本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
  論文  参考訳（メタデータ） (2021-08-13T03:03:56Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Combinatorial and computational investigations of Neighbor-Joining bias [0.0]
  Neighbor-Joiningアルゴリズムは、生物学的データから生じる相同性マップから木の計量を計算する。 これらの地域についての完全な記述はまだ見つかっていない。 隣り合う集合の異なる配列は、同じ木を生成することができ、したがって複数の幾何学的領域を同じ出力に関連付ける。
  論文  参考訳（メタデータ） (2020-07-18T06:48:45Z)
• DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
  本稿では,ディープ・ニューラル・アーキテクチャーを効果的かつ効率的に探索するためのディバイド・アンド・コンカ(DC)手法を提案する。 ImageNetデータセットで75.1%の精度を達成しており、これは同じ検索空間を使った最先端の手法よりも高い。
  論文  参考訳（メタデータ） (2020-05-29T09:02:16Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。 我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
  論文  参考訳（メタデータ） (2020-02-26T17:43:53Z)
• Scalable Hierarchical Clustering with Tree Grafting [66.68869706310208]
  Grinchは、大規模で非階層的な階層的クラスタリングと一般的なリンク関数のための新しいアルゴリズムである。 Grinchは、リンケージ関数を持つクラスタリングのための分離性という新しい概念によって動機付けられている。
  論文  参考訳（メタデータ） (2019-12-31T20:56:15Z)

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

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