論文の概要: Re-embedding data to strengthen recovery guarantees of clustering
- arxiv url: http://arxiv.org/abs/2301.10901v1
- Date: Thu, 26 Jan 2023 02:15:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 14:39:35.952552
- Title: Re-embedding data to strengthen recovery guarantees of clustering
- Title(参考訳): クラスタリングの回復保証を強化するためのデータ再埋め込み
- Authors: Tao Jiang, Samuel Tan, Stephen Vavasis
- Abstract要約: 4つの既知のテクニックをパイプラインにチェーンするクラスタリングメソッド。4つのコンポーネントのどれよりも強いリカバリ保証を持つアルゴリズムを生成する。
SONクラスタリングは,すでに証明可能な保証を有する十分に検証された手法であるため,再埋め込みにより回復SONクラスタリングが改善されることを確認した。
- 参考スコア(独自算出の注目度): 11.637038729188612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a clustering method that involves chaining four known techniques
into a pipeline yielding an algorithm with stronger recovery guarantees than
any of the four components separately. Given $n$ points in $\mathbb R^d$, the
first component of our pipeline, which we call leapfrog distances, is
reminiscent of density-based clustering, yielding an $n\times n$ distance
matrix. The leapfrog distances are then translated to new embeddings using
multidimensional scaling and spectral methods, two other known techniques,
yielding new embeddings of the $n$ points in $\mathbb R^{d'}$, where $d'$
satisfies $d'\ll d$ in general. Finally, sum-of-norms (SON) clustering is
applied to the re-embedded points. Although the fourth step (SON clustering)
can in principle be replaced by any other clustering method, our focus is on
provable guarantees of recovery of underlying structure. Therefore, we
establish that the re-embedding improves recovery SON clustering, since SON
clustering is a well-studied method that already has provable guarantees.
- Abstract(参考訳): そこで本研究では, 4つの既知手法をパイプラインにチェーンし, 4つのコンポーネントのいずれよりも強い回復保証を持つアルゴリズムを導出するクラスタリング手法を提案する。
私たちがleapfrog distancesと呼ぶパイプラインの最初のコンポーネントである$n$が$\mathbb r^d$で与えられると、密度ベースのクラスタリングを思い起こさせ、$n\times n$ distance matrixになります。
leapfrog距離は、他の2つの既知の手法である多次元スケーリングとスペクトル法を用いて、新しい埋め込みに変換され、$d'$ が $d'\ll d$ を満たす$n$ を$\mathbb r^{d'}$ に新しい埋め込みを与える。
最後に、再埋め込みされた点にSONクラスタリングを適用する。
第4のステップ(SONクラスタリング)は原則として他のクラスタリング手法に置き換えることができますが、我々は基盤となる構造の回復を保証することに注力しています。
したがって,sonクラスタリングは十分に研究されている手法であり,すでに証明可能な保証があるため,再エンベディングによりsonクラスタリングの回復が向上する。
関連論文リスト
- Multiple Kernel Clustering via Local Regression Integration [4.856913393644719]
複数のカーネルメソッドは、複数のカーネルデータの固有の多様体構造をあまり考慮しない。
本稿ではまず,カーネル型局所回帰(CKLR)を用いたクラスタリング手法を提案する。
次に、マルチカーネルローカルレグレッション(CMKLR)を介してクラスタリングを行うように拡張する。
論文 参考訳(メタデータ) (2024-10-20T06:26:29Z) - A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。
私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。
ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文 参考訳(メタデータ) (2024-02-02T10:44:42Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Convergence and Recovery Guarantees of the K-Subspaces Method for
Subspace Clustering [33.1464583756714]
K-部分空間法(K-subspaces, KSS)は、K-means法を一般化した部分空間クラスタリング法である。
KSS法の初期割り当てが真のクラスタリングの近傍にある場合、超線型速度で収束することを示す。
論文 参考訳(メタデータ) (2022-06-11T15:47:21Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳(メタデータ) (2022-02-01T19:31:15Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z) - Dimensionality Reduction for $k$-means Clustering [3.655021726150368]
本稿では,$k$-meansクラスタリング問題の次元を効果的に削減し,精度の高い近似を求める方法を提案する。
4つのアルゴリズムが提示され、2つのtextitfeature selectionと2つのtextitfeature extract based algorithmがランダム化されている。
論文 参考訳(メタデータ) (2020-07-26T17:31:44Z) - Exact Recovery of Mangled Clusters with Same-Cluster Queries [20.03712152278538]
半教師付きアクティブクラスタリングフレームワークにおけるクラスタリカバリ問題について検討する。
我々は、$n$ポイントを$k$クラスタに分割するアルゴリズムを設計し、$O(k3 ln k ln n)$oracleクエリと$tildeO(kn + k3)$でクラスタを非分類エラーで復元する。
論文 参考訳(メタデータ) (2020-06-08T15:27:58Z) - Stable and consistent density-based clustering via multiparameter
persistence [77.34726150561087]
トポロジカルデータ解析による次数-リップス構成について考察する。
我々は,入力データの摂動に対する安定性を,通信間距離を用いて解析する。
私たちはこれらのメソッドを、Persistableと呼ばれる密度ベースのクラスタリングのためのパイプラインに統合します。
論文 参考訳(メタデータ) (2020-05-18T19:45:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。