論文の概要: An objective function for order preserving hierarchical clustering

• arxiv url: http://arxiv.org/abs/2109.04266v4
• Date: Tue, 10 Dec 2024 18:31:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:33:08.905864
• Title: An objective function for order preserving hierarchical clustering
• Title（参考訳）: 階層クラスタリングの順序保存のための目的関数
• Authors: Daniel Bakkelund,
• Abstract要約: 確率的部分順序の類似性に基づく階層的クラスタリングの理論と目的関数を提案する。 具体的には、元 $x le y$ が部分順序で与えられ、それぞれのクラスタ $[x]$ と $[y]$ が与えられたとき、その理論はクラスタ上で $[x]le'[y]$ となるような順序関係 $le'$ が得られる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We present a theory and an objective function for similarity-based hierarchical clustering of probabilistic partial orders and directed acyclic graphs (DAGs). Specifically, given elements $x \le y$ in the partial order, and their respective clusters $[x]$ and $[y]$, the theory yields an order relation $\le'$ on the clusters such that $[x]\le'[y]$. The theory provides a concise definition of order-preserving hierarchical clustering, and offers a classification theorem identifying the order-preserving trees (dendrograms). To determine the optimal order-preserving trees, we develop an objective function that frames the problem as a bi-objective optimisation, aiming to satisfy both the order relation and the similarity measure. We prove that the optimal trees under the objective are both order-preserving and exhibit high-quality hierarchical clustering. Since finding an optimal solution is NP-hard, we introduce a polynomial-time approximation algorithm and demonstrate that the method outperforms existing methods for order-preserving hierarchical clustering by a significant margin.
• Abstract（参考訳）: 確率的部分順序と有向非巡回グラフ(DAG)の類似性に基づく階層的クラスタリングの理論と目的関数を提案する。 具体的には、元 $x \le y$ が部分順序で与えられ、それぞれのクラスタ $[x]$ と $[y]$ が与えられたとき、この理論はクラスタ上で $[x]\le'[y]$ となるような順序関係を生じる。 この理論は順序保存的階層的クラスタリングの簡潔な定義を提供し、順序保存的木(デンドログラム)を特定する分類定理を提供する。 最適順序保存木を決定するために,二目的最適化として問題をフレーム化する目的関数を開発し,順序関係と類似度尺度の両方を満たすことを目的とした。 目的とする最適木は順序保存と高品質な階層的クラスタリングの両方であることを示す。 最適解がNP-hardであることから,多項式時間近似アルゴリズムを導入し,階層クラスタリングの順序保存法を有意差で上回ることを示す。

関連論文リスト

• Hierarchical Clustering via Local Search [0.0]
  階層クラスタリングのための局所探索アルゴリズムを提案する。 任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
  論文  参考訳（メタデータ） (2024-05-24T23:46:24Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• 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)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means [20.322355919030112]
  最近導入された相似スコアを持つ点に対する目的は、距離が距離を形成するとき、すべての木は1/2近似となる。 そこで本研究では,ユークリッド空間における階層的クラスタリングの新たなグローバルな目的について述べる。 本稿は、この目的と二分法k平均アルゴリズムとの理論的関係を構築した。
  論文  参考訳（メタデータ） (2020-08-30T18:17:46Z)
• Order preserving hierarchical agglomerative clustering [0.0]
  このような順序データの階層的クラスタリングを順序保存する問題について検討する。 クラスタリングは類似性に基づいており、シングルリンケージや完全リンケージのような標準リンケージ関数を使用する。 最適な階層的クラスタリングは、元の相似度測度に最も近い超測度に対応する部分的デンドログラムとして定義される。
  論文  参考訳（メタデータ） (2020-04-26T21:58:53Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Scalable Hierarchical Clustering with Tree Grafting [66.68869706310208]
  Grinchは、大規模で非階層的な階層的クラスタリングと一般的なリンク関数のための新しいアルゴリズムである。 Grinchは、リンケージ関数を持つクラスタリングのための分離性という新しい概念によって動機付けられている。
  論文  参考訳（メタデータ） (2019-12-31T20:56:15Z)

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

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