論文の概要: Spectral Clustering on Large Datasets: When Does it Work? Theory from
Continuous Clustering and Density Cheeger-Buser
- arxiv url: http://arxiv.org/abs/2305.06541v1
- Date: Thu, 11 May 2023 03:08:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-12 16:06:52.656200
- Title: Spectral Clustering on Large Datasets: When Does it Work? Theory from
Continuous Clustering and Density Cheeger-Buser
- Title（参考訳）: 大規模データセットのスペクトルクラスタリング:いつ動作するのか?
連続クラスタリングと密度シーガーバスターの理論
- Authors: Timothy Chu, Gary Miller, Noel Walkington
- Abstract要約: 現代の機械学習では、多くのデータセットは確率密度関数から引き出された多数の点としてモデル化される。
我々の研究は、ラプラス分布の混合から引き出されたデータに対して、シマリクスペクトルクラスタリングがうまく働くことを示唆している。
私たちのキーとなるツールは、不連続なものを含む全ての確率密度に対する新しいCheeger-Buser不等式です。
- 参考スコア（独自算出の注目度）: 0.17188280334580194
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spectral clustering is one of the most popular clustering algorithms that has
stood the test of time. It is simple to describe, can be implemented using
standard linear algebra, and often finds better clusters than traditional
clustering algorithms like $k$-means and $k$-centers. The foundational
algorithm for two-way spectral clustering, by Shi and Malik, creates a
geometric graph from data and finds a spectral cut of the graph.
In modern machine learning, many data sets are modeled as a large number of
points drawn from a probability density function. Little is known about when
spectral clustering works in this setting -- and when it doesn't. Past
researchers justified spectral clustering by appealing to the graph Cheeger
inequality (which states that the spectral cut of a graph approximates the
``Normalized Cut''), but this justification is known to break down on large
data sets.
We provide theoretically-informed intuition about spectral clustering on
large data sets drawn from probability densities, by proving when a continuous
form of spectral clustering considered by past researchers (the unweighted
spectral cut of a probability density) finds good clusters of the underlying
density itself. Our work suggests that Shi-Malik spectral clustering works well
on data drawn from mixtures of Laplace distributions, and works poorly on data
drawn from certain other densities, such as a density we call the `square-root
trough'.
Our core theorem proves that weighted spectral cuts have low weighted
isoperimetry for all probability densities. Our key tool is a new Cheeger-Buser
inequality for all probability densities, including discontinuous ones.
- Abstract（参考訳）: スペクトルクラスタリングは、時間のテストに耐えた最も人気のあるクラスタリングアルゴリズムの1つである。
記述は簡単で、標準的な線形代数を使って実装でき、しばしば$k$-meansや$k$-centersのような従来のクラスタリングアルゴリズムよりもよいクラスタを見つける。
Shi and Malikによる双方向スペクトルクラスタリングの基礎アルゴリズムは、データから幾何グラフを作成し、そのグラフのスペクトルカットを見つける。
現代の機械学習では、多くのデータセットは確率密度関数から引き出された多数の点としてモデル化される。
この設定でスペクトルクラスタリングがいつ動作するのか、そうでないのかは、ほとんど分かっていない。
過去の研究者は、グラフCheegerの不等式(グラフのスペクトルカットは ``Normalized Cut''' に近似している)に訴えることでスペクトルクラスタリングを正当化したが、この正当化は大きなデータセットで分解することが知られている。
過去の研究者が検討した連続的なスペクトルクラスタリング(確率密度の非重み付けスペクトルカット)が、基礎となる密度自体のよいクラスターを見つけることを証明し、確率密度から導かれる大きなデータセット上のスペクトルクラスタリングに関する理論的に未定の直観を与える。
我々の研究は、シマリクスペクトルクラスタリングがラプラス分布の混合から引き出されたデータに対してうまく機能し、我々は「平方根トラフ」と呼ばれる密度のような特定の密度から引き出されたデータに対してうまく機能することを示唆している。
我々のコア定理は、重み付きスペクトルカットが全ての確率密度に対して低い重み付き等尺性を持つことを証明している。
私たちのキーとなるツールは、不連続なものを含む全ての確率密度に対する新しいCheeger-Buser不等式です。
関連論文リスト
- Datacube segmentation via Deep Spectral Clustering [76.48544221010424]
拡張ビジョン技術は、しばしばその解釈に挑戦する。
データ立方体スペクトルの巨大な次元性は、その統計的解釈において複雑なタスクを生じさせる。
本稿では,符号化空間における教師なしクラスタリング手法の適用の可能性について検討する。
統計的次元削減はアドホック訓練(可変)オートエンコーダで行い、クラスタリング処理は(学習可能な)反復K-Meansクラスタリングアルゴリズムで行う。
論文 参考訳（メタデータ） (2024-01-31T09:31:28Z) - Robustness for Spectral Clustering of General Graphs under Local Differential Privacy [2.4447259440166302]
ソーシャルネットワークはブロックモデル(SBM)から派生していないと我々は主張する。
私たちの主な焦点は、エッジフリップメソッド -- ローカルな差分プライバシーを保護するための一般的なテクニック -- にあります。
クラスタリングの結果は、SBMから生成される密集グラフやクラスタリンググラフに対して安定しているが、一般に、スペクトルクラスタリングは特定の密集グラフやクラスタリンググラフに対して非常に不規則な結果をもたらす可能性があることを示す。
論文 参考訳（メタデータ） (2023-09-13T10:23:29Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Improving Spectral Clustering Using Spectrum-Preserving Node Reduction [1.52292571922932]
我々は、スペクトル保存ノード還元を用いて固有分解を加速し、データセットの簡潔な表現を生成する。
実験の結果,最先端手法と比較してクラスタリング性能が劇的に向上した。
論文 参考訳（メタデータ） (2021-10-24T01:43:12Z) - Higher-Order Spectral Clustering for Geometric Graphs [0.17188280334580194]
我々は、高階スペクトルクラスタリングと呼ばれる効果的な一般化を提案する。
概念的には古典的なスペクトルクラスタリング法に似ているが、高次固有値に付随する固有ベクトルを分割するために用いられる。
本手法は, 極小グラフにおいても, 数値実験に有効であることを示す。
論文 参考訳（メタデータ） (2020-09-23T19:51:55Z) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳（メタデータ） (2020-09-10T05:21:20Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。
その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
論文 参考訳（メタデータ） (2020-06-07T09:14:44Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。
nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文 参考訳（メタデータ） (2020-04-25T17:52:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。