論文の概要: Objective-Based Hierarchical Clustering of Deep Embedding Vectors
- arxiv url: http://arxiv.org/abs/2012.08466v1
- Date: Tue, 15 Dec 2020 18:08:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-07 09:55:12.189988
- Title: Objective-Based Hierarchical Clustering of Deep Embedding Vectors
- Title（参考訳）: 深層埋め込みベクトルの客観的階層クラスタリング
- Authors: Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin
- Abstract要約: この研究には、最大450万ドルのエントリを持つデータセットが含まれており、埋め込み次元は2048ドルである。
このような大規模データセットへの階層的クラスタリングのスケールアップという課題に対処するため,新たな実用的階層的クラスタリングアルゴリズムB++&Cを提案する。
人気の高いMoseley-Wang (MW) / Cohen-Addad et alでは、平均で5%/20%改善されている。
(CKMM)目的。
- 参考スコア（独自算出の注目度）: 6.78399939455462
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We initiate a comprehensive experimental study of objective-based
hierarchical clustering methods on massive datasets consisting of deep
embedding vectors from computer vision and NLP applications. This includes a
large variety of image embedding (ImageNet, ImageNetV2, NaBirds), word
embedding (Twitter, Wikipedia), and sentence embedding (SST-2) vectors from
several popular recent models (e.g. ResNet, ResNext, Inception V3, SBERT). Our
study includes datasets with up to $4.5$ million entries with embedding
dimensions up to $2048$.
In order to address the challenge of scaling up hierarchical clustering to
such large datasets we propose a new practical hierarchical clustering
algorithm B++&C. It gives a 5%/20% improvement on average for the popular
Moseley-Wang (MW) / Cohen-Addad et al. (CKMM) objectives (normalized) compared
to a wide range of classic methods and recent heuristics. We also introduce a
theoretical algorithm B2SAT&C which achieves a $0.74$-approximation for the
CKMM objective in polynomial time. This is the first substantial improvement
over the trivial $2/3$-approximation achieved by a random binary tree. Prior to
this work, the best poly-time approximation of $\approx 2/3 + 0.0004$ was due
to Charikar et al. (SODA'19).
- Abstract（参考訳）: 我々は,コンピュータビジョンおよびnlpアプリケーションからの深い埋め込みベクトルからなる大規模データセット上での,客観的な階層クラスタリング手法に関する包括的実験を開始する。
これには、ImageNet、ImageNetV2、NaBirds)、ワード埋め込み(Twitter、Wikipedia)、およびいくつかの最近の人気モデルの文埋め込み(SST-2)ベクターが含まれる。
ResNet, ResNext, Inception V3, SBERT)。
私たちの研究には、最大450万ドルのエントリを持つデータセットが含まれており、埋め込み次元は2048ドルです。
このような大規模データセットへの階層的クラスタリングのスケールアップという課題に対処するため、我々は新しい実用的な階層的クラスタリングアルゴリズムb++&cを提案する。
人気の高いMoseley-Wang (MW) / Cohen-Addad et alでは、平均で5%/20%改善されている。
(CKMM)目的(正規化)は、様々な古典的手法や最近のヒューリスティックスと比較される。
また、CKMMの目的を多項式時間で0.74$-近似する理論アルゴリズムB2SAT&Cを導入する。
これは、ランダムなバイナリツリーによって達成された自明な2/3$-近似に対する最初の実質的な改善である。
この研究に先立ち、$\approx 2/3 + 0.0004$の最も優れたポリ時間近似はCharikarらによる。
(SODA'19)。
関連論文リスト
- Multilayer Correlation Clustering [12.492037397168579]
相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。
本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。
目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
論文 参考訳（メタデータ） (2024-04-25T15:25:30Z) - PECANN: Parallel Efficient Clustering with Graph-Based Approximate
Nearest Neighbor Search [8.15681999722805]
本稿では, 点集合の密度に基づくクラスタリングについて検討する。
密度ピークの異なる変種を単一のフレームワークPECANNに統合する。
PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
論文 参考訳（メタデータ） (2023-12-06T22:43:50Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文 参考訳（メタデータ） (2022-10-30T22:58:22Z) - An Information-theoretic Perspective of Hierarchical Clustering [30.896561720088954]
階層クラスタリングのコスト関数はDasgupta citedasgupta 2016 Costによって導入された。
本稿では,階層的クラスタリングをインセンフィス理論の観点から検討し,新たな目的関数を定式化する。
論文 参考訳（メタデータ） (2021-08-13T03:03:56Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed
Bandits [16.1767275655842]
現在の$k$-medoidsクラスタリングアルゴリズム、例えば、PAM(Partitioning Around Medoids)は反復的であり、各イテレーションで$n$のデータセットサイズであり、大規模なデータセットでは極めて高価である。
マルチアームバンディットの技法にインスパイアされたランダム化アルゴリズムであるBanditPAMを提案する。これは、PAMの繰り返しの複雑さを$O(n2)$から$O(n log n)$に減らし、実際に保持されるデータに対する仮定の下で、高い確率で同じ結果を返す。
我々は、コーディングを含むいくつかの大規模な実世界のデータセットで実験的に結果を検証する。
論文 参考訳（メタデータ） (2020-06-11T22:17:16Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。