論文の概要: 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コスト関数の拡張である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。