論文の概要: An Objective for Hierarchical Clustering in Euclidean Space and its
Connection to Bisecting K-means
- arxiv url: http://arxiv.org/abs/2008.13235v1
- Date: Sun, 30 Aug 2020 18:17:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-23 12:12:20.931247
- Title: An Objective for Hierarchical Clustering in Euclidean Space and its
Connection to Bisecting K-means
- Title(参考訳): ユークリッド空間における階層的クラスタリングの目的と二分的K平均との関係
- Authors: Benjamin Moseley, Yuyan Wang
- Abstract要約: 最近導入された相似スコアを持つ点に対する目的は、距離が距離を形成するとき、すべての木は1/2近似となる。
そこで本研究では,ユークリッド空間における階層的クラスタリングの新たなグローバルな目的について述べる。
本稿は、この目的と二分法k平均アルゴリズムとの理論的関係を構築した。
- 参考スコア(独自算出の注目度): 20.322355919030112
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper explores hierarchical clustering in the case where pairs of points
have dissimilarity scores (e.g. distances) as a part of the input. The recently
introduced objective for points with dissimilarity scores results in every tree
being a 1/2 approximation if the distances form a metric. This shows the
objective does not make a significant distinction between a good and poor
hierarchical clustering in metric spaces. Motivated by this, the paper develops
a new global objective for hierarchical clustering in Euclidean space. The
objective captures the criterion that has motivated the use of divisive
clustering algorithms: that when a split happens, points in the same cluster
should be more similar than points in different clusters. Moreover, this
objective gives reasonable results on ground-truth inputs for hierarchical
clustering. The paper builds a theoretical connection between this objective
and the bisecting k-means algorithm. This paper proves that the optimal 2-means
solution results in a constant approximation for the objective. This is the
first paper to show the bisecting k-means algorithm optimizes a natural global
objective over the entire tree.
- Abstract(参考訳): 本稿では,各点の対が差点(距離など)を入力として持つ場合の階層的クラスタリングについて検討する。
最近導入された異質点の目的により、距離が距離となるとすべての木は1/2近似となる。
これは、目的が計量空間における良好な階層的クラスタリングと貧弱な階層的クラスタリングを区別していないことを示している。
そこで本稿では,ユークリッド空間における階層的クラスタリングのための新たなグローバル目標について述べる。
この目標は、分割クラスタリングアルゴリズムを使用する動機となった基準をキャプチャする: スプリットが発生した場合、同じクラスタ内のポイントは、異なるクラスタ内のポイントよりもよく似ているべきである。
さらに、この目的は階層的クラスタリングの基盤となる入力に対して合理的な結果を与える。
本稿は、この目的と二分法k平均アルゴリズムとの理論的関係を構築する。
本稿では,最適2平均解が目的に対して一定の近似をもたらすことを示す。
二分法k-平均アルゴリズムが木全体の自然な大域的目標を最適化することを示す最初の論文である。
関連論文リスト
- Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。
木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-10-19T14:02:42Z) - Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳(メタデータ) (2024-09-24T08:59:51Z) - ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
それは実用性を目指しており、アイテムはアプリケーション固有の重要な値を持つことができ、クラスタリングがどちらが優れているかを判断するときに人間の判断を使うのは粗悪であり、アイテムの任意のスライスのためのメトリクスを報告できる。
クラスタリング品質の差分を測定するアプローチは、高価な地平を前もって構築し、それに関して各クラスタリングを評価する代わりに、ABCDEはクラスタリング間の実際の差分に基づいて、判定のための質問をサンプリングする。
論文 参考訳(メタデータ) (2024-07-31T08:29:35Z) - Linear time Evidence Accumulation Clustering with KMeans [0.0]
この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。
分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。
k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
論文 参考訳(メタデータ) (2023-11-15T14:12:59Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Fair Clustering Under a Bounded Cost [33.50262066253557]
クラスタリングは、データセットをメトリクス空間内の近くのポイントで構成されるクラスタに分割する、基本的な教師なしの学習問題である。
最近の変種であるフェアクラスタリング(英語版)は、各点とその群のメンバーシップを表す色を関連付け、各色が群フェアネスを満たすために各クラスタに等しい表現(およそ)を持つことを要求する。
我々は,集団の実用的目的と集団の平等的目的,および集団の平等的目的を一般化するグループ・レキシミン的目的の2つの公正性を考察する。
論文 参考訳(メタデータ) (2021-06-14T08:47:36Z) - 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) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳(メタデータ) (2020-05-02T10:39:26Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-02-28T04:21:53Z) - Point-Set Kernel Clustering [11.093960688450602]
本稿では,オブジェクトとオブジェクトの集合との類似性を計算する,ポイントセットカーネルと呼ばれる新しい類似度尺度を提案する。
新たなクラスタリング手法は,大規模データセットを扱えるように,効率的かつ効率的であることを示す。
論文 参考訳(メタデータ) (2020-02-14T00:00:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。