論文の概要: Genie: A new, fast, and outlier-resistant hierarchical clustering
algorithm
- arxiv url: http://arxiv.org/abs/2209.05757v1
- Date: Tue, 13 Sep 2022 06:42:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-14 12:21:56.779525
- Title: Genie: A new, fast, and outlier-resistant hierarchical clustering
algorithm
- Title（参考訳）: Genie: 新しい、高速で、かつ、外れ値耐性の階層的クラスタリングアルゴリズム
- Authors: Marek Gagolewski, Maciej Bartoszuk, Anna Cena
- Abstract要約: 我々はGenieと呼ばれる新しい階層的クラスタリングリンク基準を提案する。
我々のアルゴリズムは、2つのクラスタを、選択された経済不平等尺度が与えられたしきい値を超えないようにリンクする。
このアルゴリズムのリファレンス実装は、Rのためのオープンソースの'genie'パッケージに含まれている。
- 参考スコア（独自算出の注目度）: 3.7491936479803054
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The time needed to apply a hierarchical clustering algorithm is most often
dominated by the number of computations of a pairwise dissimilarity measure.
Such a constraint, for larger data sets, puts at a disadvantage the use of all
the classical linkage criteria but the single linkage one. However, it is known
that the single linkage clustering algorithm is very sensitive to outliers,
produces highly skewed dendrograms, and therefore usually does not reflect the
true underlying data structure -- unless the clusters are well-separated. To
overcome its limitations, we propose a new hierarchical clustering linkage
criterion called Genie. Namely, our algorithm links two clusters in such a way
that a chosen economic inequity measure (e.g., the Gini- or Bonferroni-index)
of the cluster sizes does not drastically increase above a given threshold. The
presented benchmarks indicate a high practical usefulness of the introduced
method: it most often outperforms the Ward or average linkage in terms of the
clustering quality while retaining the single linkage's speed. The Genie
algorithm is easily parallelizable and thus may be run on multiple threads to
speed up its execution even further. Its memory overhead is small: there is no
need to precompute the complete distance matrix to perform the computations in
order to obtain a desired clustering. It can be applied on arbitrary spaces
equipped with a dissimilarity measure, e.g., on real vectors, DNA or protein
sequences, images, rankings, informetric data, etc. A reference implementation
of the algorithm has been included in the open source 'genie' package for R.
See also https://genieclust.gagolewski.com for a new implementation
(genieclust) -- available for both R and Python.
- Abstract（参考訳）: 階層的クラスタリングアルゴリズムを適用するのに必要な時間は、しばしばペアの相似性尺度の計算数によって支配される。
このような制約は、より大きなデータセットに対して、従来のリンケージの基準を1つのリンケージの基準以外は使用しないという不利益をもたらす。
しかし、単一のリンケージクラスタリングアルゴリズムは、外れ値に非常に敏感であり、高度に歪んだデンドログラムを生成するため、クラスタが十分に分離されない限り、通常は真の基盤となるデータ構造を反映しないことが知られている。
その限界を克服するために、Genieと呼ばれる新しい階層的クラスタリングリンク基準を提案する。
すなわち,このアルゴリズムは,クラスタサイズの選択された経済不平等尺度(gini-またはbonferroni-index)が与えられたしきい値を超えないように,二つのクラスターをリンクする。
提案するベンチマークは,導入手法の実用性が高いことを示すもので,単一リンクの速度を保ちながら,クラスタリング品質の点でウォードや平均リンケージを上回っていることが多い。
Genieアルゴリズムは容易に並列化可能であり、複数のスレッド上で実行することで実行をさらに高速化することができる。
そのメモリオーバーヘッドは小さく、所望のクラスタリングを得るために計算を実行するために完全な距離行列を事前に計算する必要はない。
これは、例えば、実ベクトル、DNAまたはタンパク質配列、画像、ランキング、インフォメトリデータなど、相似性尺度を備えた任意の空間に適用することができる。
アルゴリズムのリファレンス実装は、rのためのオープンソースの'genie'パッケージに含まれている。 https://genieclust.gagolewski.com for a new implementation (genieclust) -- available for r and python.comを参照。
関連論文リスト
- Data Aggregation for Hierarchical Clustering [0.3626013617212666]
BETULAは、よく知られたBIRCHデータ集約アルゴリズムの数値的に安定したバージョンである。
これは、クラスタリングの品質に小さな損失しか与えずに、制約のあるリソースを持つシステムでHACを実行可能なものにするために使用できる。
論文 参考訳（メタデータ） (2023-09-05T19:39:43Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - A Restarted Large-Scale Spectral Clustering with Self-Guiding and Block
Diagonal Representation [1.115905690697198]
自己誘導とブロック対角表現を備えた再起動クラスタリングフレームワークを提案する。
この戦略の利点は、以前のサイクルから得られた有用なクラスタリング情報を保存できることである。
スペクトルクラスタリングにおける不正確な計算の合理性を示す理論的結果が確立された。
論文 参考訳（メタデータ） (2023-06-27T01:38:52Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Hard Regularization to Prevent Deep Online Clustering Collapse without
Data Augmentation [65.268245109828]
オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。
オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。
本稿では,データ拡張を必要としない手法を提案する。
論文 参考訳（メタデータ） (2023-03-29T08:23:26Z) - Scalable Clustering: Large Scale Unsupervised Learning of Gaussian
Mixture Models with Outliers [5.478764356647437]
本稿では,損失最小化に基づくロバストなクラスタリングアルゴリズムを提案する。
これはアルゴリズムが高い確率で高い精度を得るという理論的保証を提供する。
実世界の大規模データセットの実験では、アルゴリズムの有効性が示されている。
論文 参考訳（メタデータ） (2023-02-28T14:39:18Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。