論文の概要: Approximate spectral clustering with eigenvector selection and
self-tuned $k$
- arxiv url: http://arxiv.org/abs/2302.11297v1
- Date: Wed, 22 Feb 2023 11:32:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 15:32:56.377294
- Title: Approximate spectral clustering with eigenvector selection and
self-tuned $k$
- Title（参考訳）: 固有ベクトル選択と自己調整$k$を用いた近似スペクトルクラスタリング
- Authors: Mashaan Alshammari, Masahiro Takatsuka
- Abstract要約: 最近出現したスペクトルクラスタリングは、凸性仮定なしで任意の形状のクラスターを検出することによって、従来のクラスタリング法を超越している。
実際には、$k$のマニュアル設定は主観的あるいは時間を要する可能性がある。
提案アルゴリズムは、ASCの2つの重要なステップにおいて、$k$を推定する2つの関連指標を持つ。
実験では、提案アルゴリズムの効率と、$k$を手動で設定する類似の手法と競合する能力を示す。
- 参考スコア（独自算出の注目度）: 1.827510863075184
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The recently emerged spectral clustering surpasses conventional clustering
methods by detecting clusters of any shape without the convexity assumption.
Unfortunately, with a computational complexity of $O(n^3)$, it was infeasible
for multiple real applications, where $n$ could be large. This stimulates
researchers to propose the approximate spectral clustering (ASC). However, most
of ASC methods assumed that the number of clusters $k$ was known. In practice,
manual setting of $k$ could be subjective or time consuming. The proposed
algorithm has two relevance metrics for estimating $k$ in two vital steps of
ASC. One for selecting the eigenvectors spanning the embedding space, and the
other to discover the number of clusters in that space. The algorithm used a
growing neural gas (GNG) approximation, GNG is superior in preserving input
data topology. The experimental setup demonstrates the efficiency of the
proposed algorithm and its ability to compete with similar methods where $k$
was set manually.
- Abstract（参考訳）: 最近出現したスペクトルクラスタリングは、凸性仮定なしで任意の形状のクラスターを検出することによって、従来のクラスタリング法を超える。
残念なことに、$O(n^3)$の計算複雑性では、$n$が大きければ複数の実アプリケーションでは不可能であった。
これにより、研究者は近似スペクトルクラスタリング(ASC)を提案する。
しかし、ASCの手法のほとんどは、$k$のクラスタ数が知られていると仮定した。
実際には、$k$のマニュアル設定は主観的あるいは時間を要する可能性がある。
提案アルゴリズムは、ASCの2つの重要なステップにおいて、$k$を推定する2つの関連指標を持つ。
1つは埋め込み空間にまたがる固有ベクトルを選択し、もう1つはその空間内のクラスタの数を検出する。
アルゴリズムは成長するニューラルガス(GNG)近似を用い、GNGは入力データトポロジーを保存するのに優れている。
実験では、提案アルゴリズムの効率と、$k$が手動で設定された類似の手法と競合する能力を示す。
関連論文リスト
- Are Easy Data Easy (for K-Means) [0.0]
本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。
シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
論文 参考訳（メタデータ） (2023-08-02T09:40:19Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Refining a $k$-nearest neighbor graph for a computationally efficient
spectral clustering [1.5469452301122175]
近似スペクトルクラスタリング(ASC)はサンプリングまたは量子化を使用してデータ代表を選択する。
我々は、データポイントを保持し、エッジ数を積極的に削減する、$k$-nearest 隣のグラフの洗練されたバージョンを提案する。
ASC法と比較して,提案手法はエッジの大幅な削減に拘わらず一貫した性能を示した。
論文 参考訳（メタデータ） (2023-02-22T11:31:32Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Clustering with Penalty for Joint Occurrence of Objects: Computational
Aspects [0.0]
Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。
この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。
本稿では,本手法の計算的側面について考察する。
論文 参考訳（メタデータ） (2021-02-02T10:39:27Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - 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) - Efficient Algorithms for Generating Provably Near-Optimal Cluster
Descriptors for Explainability [36.11663695534294]
本稿では,クラスタに対する簡潔な表現を構築するための最近のアプローチを拡張して,クラスタをより解釈しやすくする問題について検討する。
我々は,その問題に対する性能保証を証明可能な近似アルゴリズムを開発した。
また、異なる脅威レベルを表すゲノム配列のクラスタを含むデータセットからのクラスタを説明するアプリケーションを示す。
論文 参考訳（メタデータ） (2020-02-06T19:49:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。