論文の概要: 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であることから,多項式時間近似アルゴリズムを導入し,階層クラスタリングの順序保存法を有意差で上回ることを示す。
関連論文リスト
- Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Hierarchical Clustering: New Bounds and Objective [1.1295032417617457]
異種性に基づくクラスタリングのための新しい目的関数を提案する。
任意のツリー$T$に対して、$H_i,j$を$i$と$j$の共通の祖先の数とする。
論文 参考訳（メタデータ） (2021-11-12T18:32:23Z) - On the Generative Utility of Cyclic Conditionals [103.1624347008042]
2つの条件付きモデル$p(x|z)$を用いて、共同分布$p(x,z)$をモデル化できるかどうか、また、どのようにしてサイクルを形成するかを検討する。
本稿では,周期条件生成モデリングのためのCyGenフレームワークを提案する。
論文 参考訳（メタデータ） (2021-06-30T10:23:45Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - 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) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - 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) - Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-02-26T15:18:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。