論文の概要: Refining a $k$-nearest neighbor graph for a computationally efficient
spectral clustering
- arxiv url: http://arxiv.org/abs/2302.11296v1
- Date: Wed, 22 Feb 2023 11:31:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 15:32:40.519986
- Title: Refining a $k$-nearest neighbor graph for a computationally efficient
spectral clustering
- Title（参考訳）: 計算効率の良いスペクトルクラスタリングのための$k$-nearest 近傍グラフの精製
- Authors: Mashaan Alshammari, John Stavrakakis, Masahiro Takatsuka
- Abstract要約: 近似スペクトルクラスタリング(ASC)はサンプリングまたは量子化を使用してデータ代表を選択する。
我々は、データポイントを保持し、エッジ数を積極的に削減する、$k$-nearest 隣のグラフの洗練されたバージョンを提案する。
ASC法と比較して,提案手法はエッジの大幅な削減に拘わらず一貫した性能を示した。
- 参考スコア（独自算出の注目度）: 1.5469452301122175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spectral clustering became a popular choice for data clustering for its
ability of uncovering clusters of different shapes. However, it is not always
preferable over other clustering methods due to its computational demands. One
of the effective ways to bypass these computational demands is to perform
spectral clustering on a subset of points (data representatives) then
generalize the clustering outcome, this is known as approximate spectral
clustering (ASC). ASC uses sampling or quantization to select data
representatives. This makes it vulnerable to 1) performance inconsistency
(since these methods have a random step either in initialization or training),
2) local statistics loss (because the pairwise similarities are extracted from
data representatives instead of data points). We proposed a refined version of
$k$-nearest neighbor graph, in which we keep data points and aggressively
reduce number of edges for computational efficiency. Local statistics were
exploited to keep the edges that do not violate the intra-cluster distances and
nullify all other edges in the $k$-nearest neighbor graph. We also introduced
an optional step to automatically select the number of clusters $C$. The
proposed method was tested on synthetic and real datasets. Compared to ASC
methods, the proposed method delivered a consistent performance despite
significant reduction of edges.
- Abstract（参考訳）: スペクトルクラスタリングは、異なる形状のクラスタを探索する能力を持つため、データクラスタリングの一般的な選択肢となった。
しかし、計算要求のため、他のクラスタリング手法よりも必ずしも好まれるとは限らない。
これらの計算要求を回避する効果的な方法の1つは、点(データ代表者)のサブセット上でスペクトルクラスタリングを行い、クラスタリング結果を一般化することであり、これは近似スペクトルクラスタリング(ASC)として知られている。
ASCはサンプリングまたは量子化を使用してデータ代表を選択する。
これにより脆弱になる。
1) 性能の整合性(初期化又は訓練においてランダムなステップを有するため)
2)局所統計損失(データポイントではなくデータ代表者から対の類似性を抽出するため)。
我々は、データポイントを保持し、計算効率を高めるためにエッジ数を積極的に削減する、$k$-nearest 隣のグラフの洗練されたバージョンを提案した。
ローカル統計は、クラスタ内距離に違反しないエッジを保持し、$k$-nearestの隣グラフの他のエッジをすべて無効にするために利用された。
また、クラスタ数を自動的に選択するオプションのステップも導入しました。
提案手法は, 合成および実データを用いた。
ASC法と比較して,提案手法はエッジの大幅な削減にもかかわらず一貫した性能を示した。
関連論文リスト
- MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳（メタデータ） (2023-12-07T06:19:39Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - 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) - A parameter-free graph reduction for spectral clustering and SpectralNet [1.5469452301122175]
本稿では,パラメータを必要としないグラフ削減手法を提案する。
第一に、各点$p$からその近傍までの距離は、同じ周囲密度を持つ隣人にのみ適応しきい値を用いてフィルタリングされる。
2つのステップを生き残るエッジは、スペクトルクラスタリングであるSpectralNetに渡された構築されたグラフを形成する。
論文 参考訳（メタデータ） (2023-02-25T21:19:30Z) - Approximate spectral clustering with eigenvector selection and
self-tuned $k$ [1.827510863075184]
最近出現したスペクトルクラスタリングは、凸性仮定なしで任意の形状のクラスターを検出することによって、従来のクラスタリング法を超越している。
実際には、$k$のマニュアル設定は主観的あるいは時間を要する可能性がある。
提案アルゴリズムは、ASCの2つの重要なステップにおいて、$k$を推定する2つの関連指標を持つ。
実験では、提案アルゴリズムの効率と、$k$を手動で設定する類似の手法と競合する能力を示す。
論文 参考訳（メタデータ） (2023-02-22T11:32:24Z) - ck-means, a novel unsupervised learning method that combines fuzzy and
crispy clustering methods to extract intersecting data [1.827510863075184]
本稿では,2つの特徴以上の共通点を共有するデータをクラスタリングする手法を提案する。
この手法の主な考え方は、ファジィ C-Means (FCM) アルゴリズムを用いてファジィクラスタを生成することである。
このアルゴリズムはまた、シルエット指数(SI)によって与えられるクラスタの一貫性に従って、FCMとk平均アルゴリズムのための最適なクラスタ数を見つけることができる。
論文 参考訳（メタデータ） (2022-06-17T19:29:50Z) - Determinantal consensus clustering [77.34726150561087]
本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。
DPPは部分集合内の中心点の多様性を好んでいる。
DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
論文 参考訳（メタデータ） (2021-02-07T23:48:24Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。
その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
論文 参考訳（メタデータ） (2020-06-07T09:14:44Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。