論文の概要: An objective function for order preserving hierarchical clustering
- arxiv url: http://arxiv.org/abs/2109.04266v1
- Date: Thu, 9 Sep 2021 13:35:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-10 14:00:23.710023
- Title: An objective function for order preserving hierarchical clustering
- Title（参考訳）: 階層クラスタリングの順序保存のための目的関数
- Authors: Daniel Bakkelund
- Abstract要約: このモデルは、分割階層クラスタリングのためのダスグプタコスト関数の拡張である。
最適解を見つけることはNPハードなので、相対的な性能保証が$O(log3/2n)$である時間近似を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present an objective function for similarity based hierarchical clustering
of partially ordered data that preserves the partial order in the sense that if
$x \leq y$, and if $[x]$ and $[y]$ are the respective clusters of $x$ and $y$,
then there is an order relation $\leq'$ on the clusters for which $[x] \leq'
|y]$. The model distinguishes itself from existing methods and models for
clustering of ordered data in that the order relation and the similarity are
combined to obtain an optimal hierarchical clustering seeking to satisfy both,
and that the order relation is equipped with a pairwise level of comparability
in the range $[0,1]$. In particular, if the similarity and the order relation
are not aligned, then order preservation may have to yield in favor of
clustering. Finding an optimal solution is NP-hard, so we provide a polynomial
time approximation algorithm, with a relative performance guarantee of
$O(\log^{3/2}n)$, based on successive applications of directed sparsest cut.
The model is an extension of the Dasgupta cost function for divisive
hierarchical clustering.
- Abstract（参考訳）: もし$x \leq y$と$[x]$と$[y]$がそれぞれ$x$と$y$のクラスタであるなら、$[x] \leq' |y]$となるクラスタに$\leq'$という順序関係があるという意味で、部分順序を保存する部分順序データの類似性に基づく階層的クラスタリング関数を示す。
このモデルは、順序関係と類似性が組み合わさって両者を満足しようとする最適な階層的クラスタリングを求め、順序関係が$[0,1]$の範囲でペアワイズな比較可能性レベルを備えるという、順序データのクラスタリングのための既存の方法とモデルとを区別する。
特に、類似性と順序関係が一致していない場合、順序保存はクラスタリングに有利である必要がある。
最適解を求めることはnpハードであるため、有向スパルセストカットの逐次応用に基づいて、相対性能保証が$o(\log^{3/2}n)$の多項式時間近似アルゴリズムを提供する。
このモデルは分割階層クラスタリングのためのdasguptaコスト関数の拡張である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。