論文の概要: Multi-class Graph Clustering via Approximated Effective $p$-Resistance
- arxiv url: http://arxiv.org/abs/2306.08617v2
- Date: Tue, 18 Jul 2023 23:59:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-20 17:05:54.051175
- Title: Multi-class Graph Clustering via Approximated Effective $p$-Resistance
- Title（参考訳）: 近似有効$p$-Resistanceによるマルチクラスグラフクラスタリング
- Authors: Shota Saito, Mark Herbster
- Abstract要約: 本稿では,$p$-resistanceの近似法を開発し,マルチクラスクラスタリングに適用する。
p$-Laplacian の利点は、パラメータ $p$ がクラスタ構造に制御可能なバイアスをもたらすことである。
- 参考スコア（独自算出の注目度）: 9.272079420574512
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper develops an approximation to the (effective) $p$-resistance and
applies it to multi-class clustering. Spectral methods based on the graph
Laplacian and its generalization to the graph $p$-Laplacian have been a
backbone of non-euclidean clustering techniques. The advantage of the
$p$-Laplacian is that the parameter $p$ induces a controllable bias on cluster
structure. The drawback of $p$-Laplacian eigenvector based methods is that the
third and higher eigenvectors are difficult to compute. Thus, instead, we are
motivated to use the $p$-resistance induced by the $p$-Laplacian for
clustering. For $p$-resistance, small $p$ biases towards clusters with high
internal connectivity while large $p$ biases towards clusters of small
"extent," that is a preference for smaller shortest-path distances between
vertices in the cluster. However, the $p$-resistance is expensive to compute.
We overcome this by developing an approximation to the $p$-resistance. We prove
upper and lower bounds on this approximation and observe that it is exact when
the graph is a tree. We also provide theoretical justification for the use of
$p$-resistance for clustering. Finally, we provide experiments comparing our
approximated $p$-resistance clustering to other $p$-Laplacian based methods.
- Abstract（参考訳）: 本稿では,(有効)$p$-resistanceの近似を開発し,マルチクラスクラスタリングに適用する。
グラフラプラシアンに基づくスペクトル法とそのグラフ $p$-laplacian への一般化は、非ユークリッドクラスタリング技術のバックボーンとなっている。
p$-Laplacian の利点は、パラメータ $p$ がクラスタ構造に制御可能なバイアスをもたらすことである。
p$-Laplacian eigenvector based methodの欠点は、3番目と上位の固有ベクトルの計算が難しいことである。
したがって、我々はクラスタリングに$p$-Laplacianによって誘導される$p$-resistanceを使うことを動機付けている。
p$-resistanceでは、小さな$p$バイアスが内部接続性の高いクラスタに対して、大きな$p$バイアスが小さな"exent"のクラスタに対して、すなわちクラスタ内の頂点間の短パス距離の短さを優先する。
しかし、$p$-resistanceは計算にコストがかかる。
我々は、$p$-resistanceの近似を開発することでこれを克服する。
この近似で上界と下界を証明し、グラフが木であるときにそれが正確であることを観測する。
また、クラスタリングに$p$-resistanceを使用するための理論的正当性も提供する。
最後に、近似した$p$-resistanceクラスタリングと他の$p$-Laplacianベースのメソッドとの比較実験を行う。
関連論文リスト
- Multilayer Correlation Clustering [12.492037397168579]
相関クラスタリング(Bansal et al., FOCS '02)の新たな一般化である多層相関クラスタリングを確立する。
本稿では、共通集合である$V$に対して相関クラスタリング(層と呼ばれる)の一連の入力を与えられる。
目的は、不一致ベクトルの$ell_p$-norm(pgeq 1$)を最小化する$V$のクラスタリングを見つけることである。
論文 参考訳（メタデータ） (2024-04-25T15:25:30Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - New Coresets for Projective Clustering and Applications [34.82221047030618]
点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。
我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
論文 参考訳（メタデータ） (2022-03-08T19:50:27Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Near-Optimal Explainable $k$-Means for All Dimensions [13.673697350508965]
k$-meansのコストは最大$k1 - 2/dmathrmpoly(dlog k)$である。
改良された$k1 - 2/dmathrmpolylog(k)$で、$k,dge 2$から$k$のポリ対数係数までのすべての選択に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-29T16:59:03Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。