論文の概要: Sum-of-norms clustering does not separate nearby balls
- arxiv url: http://arxiv.org/abs/2104.13753v1
- Date: Wed, 28 Apr 2021 13:35:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-29 12:37:15.424938
- Title: Sum-of-norms clustering does not separate nearby balls
- Title（参考訳）: sum-of-normsクラスタリングは近くのボールを分離しない
- Authors: Alexander Dunlap and Jean-Christophe Mourrat
- Abstract要約: 我々は,データセットを一般的な尺度に置き換えた,sum-of-normsクラスタリングの連続バージョンを示す。
我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
- 参考スコア（独自算出の注目度）: 77.34726150561087
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sum-of-norms clustering is a popular convexification of $K$-means clustering.
We show that, if the dataset is made of a large number of independent random
variables distributed according to the uniform measure on the union of two
disjoint balls of unit radius, and if the balls are sufficiently close to one
another, then sum-of-norms clustering will typically fail to recover the
decomposition of the dataset into two clusters. As the dimension tends to
infinity, this happens even when the distance between the centers of the two
balls is taken to be as large as $2\sqrt{2}$. In order to show this, we
introduce and analyze a continuous version of sum-of-norms clustering, where
the dataset is replaced by a general measure. In particular, we state and prove
a local-global characterization of the clustering that seems to be new even in
the case of discrete datapoints.
- Abstract（参考訳）: Sum-of-normsクラスタリングは、$K$-meansクラスタリングの一般的な凸化である。
このデータセットが、単位半径の2つの非結合球の結合に関する均一測度に従って分布する多数の独立確率変数からなる場合、ボールが互いに十分に近接している場合、サム・オブ・ノームのクラスタリングは通常、データセットの2つのクラスタへの分解を回復できない。
次元が無限大になる傾向にあるので、2つの球の中心間の距離が2\sqrt{2}$であるとしても、これは成り立つ。
これを示すために,データセットを一般的な尺度に置き換えた,sum-of-normsクラスタリングの連続バージョンを紹介し,分析する。
特に、離散データポイントの場合においても、新しいと思われるクラスタリングの局所的・言語的特徴を記述し、証明する。
関連論文リスト
- UniForCE: The Unimodality Forest Method for Clustering and Estimation of
the Number of Clusters [2.4953699842881605]
我々は,一様性の概念に着目し,局所的一様性クラスタと呼ばれる柔軟なクラスタ定義を提案する。
局所的ユニモーダルクラスタは、データのサブクラスタのペア間で一様性が局所的に保存される限り、拡張される。
局所的な単調クラスタリングのためのUniForCE法を提案する。
論文 参考訳（メタデータ） (2023-12-18T16:19:02Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Anomaly Clustering: Grouping Images into Coherent Clusters of Anomaly
Types [60.45942774425782]
我々は異常クラスタリングを導入し、その目標はデータを異常型の一貫性のあるクラスタにまとめることである。
これは異常検出とは違い、その目標は異常を通常のデータから分割することである。
パッチベースの事前訓練されたディープ埋め込みとオフザシェルフクラスタリング手法を用いた,単純で効果的なクラスタリングフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-21T23:11:33Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Local versions of sum-of-norms clustering [77.34726150561087]
本手法はボールモデルにおいて任意に閉じた球を分離できることを示す。
我々は、不連結連結集合のクラスタリングで発生する誤差に定量的な有界性を証明した。
論文 参考訳（メタデータ） (2021-09-20T14:45:29Z) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳（メタデータ） (2021-03-16T21:14:56Z) - Quantizing Multiple Sources to a Common Cluster Center: An Asymptotic
Analysis [14.048989759890475]
我々は、$Ld$次元のサンプルを$d$次元のベクトルのデータセットから$Ld$次元のクラスタセンターに結合することで得られる$Ld$次元のサンプルを定量化することを検討する。
クラスタセンターの数が多いレジームにおける平均的性能歪みの式を求める。
元の(ノイズのない)データセットへの忠実さに関して、我々のクラスタリングアプローチは、$Ld$次元ノイズ観測ベクトルを$Ld$次元中心に量子化することに依拠する単純アプローチよりも優れています。
論文 参考訳（メタデータ） (2020-10-23T17:14:28Z) - 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) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。