Fugu-MT 論文翻訳(概要): Near-Optimal Comparison Based Clustering

論文の概要: Near-Optimal Comparison Based Clustering

arxiv url: http://arxiv.org/abs/2010.03918v2
Date: Fri, 9 Oct 2020 12:51:45 GMT
ステータス: 処理完了
システム内更新日: 2022-10-09 11:31:23.208678
Title: Near-Optimal Comparison Based Clustering
Title（参考訳）: 近最適比較に基づくクラスタリング
Authors: Micha\"el Perrot and Pascal Mattia Esser and Debarghya Ghoshdastidar
Abstract要約: 提案手法は, ほぼ最適な比較数を用いて, 植え付けクラスタリングを復元できることを示す。理論的知見を実証的に検証し,実データ上での手法の良好な振る舞いを実証する。
参考スコア（独自算出の注目度）: 7.930242839366938
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The goal of clustering is to group similar objects into meaningful partitions. This process is well understood when an explicit similarity measure between the objects is given. However, far less is known when this information is not readily available and, instead, one only observes ordinal comparisons such as "object i is more similar to j than to k." In this paper, we tackle this problem using a two-step procedure: we estimate a pairwise similarity matrix from the comparisons before using a clustering method based on semi-definite programming (SDP). We theoretically show that our approach can exactly recover a planted clustering using a near-optimal number of passive comparisons. We empirically validate our theoretical findings and demonstrate the good behaviour of our method on real data.
Abstract（参考訳）: クラスタリングの目標は、類似のオブジェクトを意味のあるパーティションにグループ化することです。このプロセスは、オブジェクト間の明示的な類似性測度が与えられるときによく理解される。しかし、この情報が手軽に入手できなければ、その代わりに「対象 i は k よりも j に類似している」といった順序比較のみを観察する。本稿では, 半定値プログラミング(SDP)に基づくクラスタリング手法を使用する前に, 比較からペアワイズ類似度行列を推定する。提案手法は, ほぼ最適数のパッシブ比較を用いて, 植え込みクラスタリングを正確に復元できることを理論的に示す。我々は理論的な知見を実証的に検証し,実データに対する方法のよい振る舞いを示す。

関連論文リスト

Cluster-Aware Similarity Diffusion for Instance Retrieval [64.40171728912702]
拡散に基づく再ランク付け(diffusion-based re-level)は、隣り合うグラフで類似性の伝播を実行することで、インスタンスを検索する一般的な方法である。本稿では,新しいクラスタ・アウェア類似性(CAS)拡散モデルを提案する。
論文参考訳（メタデータ） (2024-06-04T14:19:50Z)
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)
A Revenue Function for Comparison-Based Hierarchical Clustering [5.683072566711975]
比較のみを用いて,デンドログラムの良さを測定できる新たな収益関数を提案する。この関数は、ペアの類似性を用いた階層的クラスタリングにおけるDasguptaのコストと密接に関連していることを示す。理論的には,提案した収益関数を用いて,三重項比較の少ない潜在階層をおよそ復元できるかどうかというオープンな問題を解く。
論文参考訳（メタデータ） (2022-11-29T18:40:02Z)
A sampling-based approach for efficient clustering in large datasets [0.8952229340927184]
本稿では,多数のクラスタを持つ高次元データに対して,簡便かつ効率的なクラスタリング手法を提案する。私たちのコントリビューションは、データポイントとクラスタの完全な比較を必要としないため、k-meansよりもはるかに効率的です。
論文参考訳（メタデータ） (2021-12-29T19:15:20Z)
Shift of Pairwise Similarities for Data Clustering [7.462336024223667]
正規化項がクラスタの2乗サイズの和である場合を考察し、ペアの類似性の適応正規化に一般化する。これは、ペアの類似性を(適切に)シフトさせ、それらのうちのいくつかを負にする可能性がある。そこで我々は,新しいクラスタリング問題を解くために,高速な理論的収束率を持つ効率的な局所探索最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-10-25T16:55:07Z)
Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文参考訳（メタデータ） (2020-10-22T15:58:35Z)
Contrastive Clustering [57.71729650297379]
本稿では,インスタンスレベルのコントラスト学習を明示的に行うContrastive Clustering (CC)を提案する。特にCCは、CIFAR-10(CIFAR-100)データセット上で0.705(0.431)のNMIを達成しており、最高のベースラインと比較して最大19%(39%)のパフォーマンス向上を実現している。
論文参考訳（メタデータ） (2020-09-21T08:54:40Z)
LSD-C: Linearly Separable Deep Clusters [145.89790963544314]
ラベルなしデータセットのクラスタを識別する新しい手法であるLSD-Cを提案する。本手法は,最近の半教師付き学習の実践からインスピレーションを得て,クラスタリングアルゴリズムと自己教師付き事前学習と強力なデータ拡張を組み合わせることを提案する。 CIFAR 10/100, STL 10, MNIST, および文書分類データセットReuters 10Kなど, 一般的な公開画像ベンチマークにおいて, 当社のアプローチが競合より大幅に優れていたことを示す。
論文参考訳（メタデータ） (2020-06-17T17:58:10Z)
Point-Set Kernel Clustering [11.093960688450602]
本稿では,オブジェクトとオブジェクトの集合との類似性を計算する,ポイントセットカーネルと呼ばれる新しい類似度尺度を提案する。新たなクラスタリング手法は,大規模データセットを扱えるように,効率的かつ効率的であることを示す。
論文参考訳（メタデータ） (2020-02-14T00:00:03Z)
Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文参考訳（メタデータ） (2020-01-06T23:33:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。