論文の概要: Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy
- arxiv url: http://arxiv.org/abs/2608.14215v1
- Date: Fri, 14 Aug 2026 11:45:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 20:14:29.369626
- Title: Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy
- Title（参考訳）: 接続されたサブスペースクラスタリング - 硬さ、スケーラブルなヒューリスティック、および海面測地への応用
- Abstract要約: 制約モデルが一貫性を持つ制約クラスタリング問題を導入する。
ジオデシーにおけるアプリケーションによるモチベーションにより,接続サブスペースクラスタリング問題を導入する。
合併ベースの修復は、73.75%のケースで4つの戦略の中で最強であることを示す。
- 参考スコア（独自算出の注目度）: 3.344416446278979
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.
- Abstract（参考訳）: 制約付き最適化は、サイド情報を統合することで古典的な最適化を拡張し、科学や工学の分野に広く適用することができる。
異なる物理的な場所で変数を計測する設定を考えてみましょう。
これらの測定をグループ化する際には、内部的に類似しており、物理的に一貫性のあるクラスタが望まれます。
したがって、制約モデルがコヒーレンスであるような制約付きクラスタリング問題が存在する。
高次元点と接続グラフが与えられた場合、それらを$k$の連結クラスタに分割し、クラスタの最も適した$m'$2次元アフィン部分空間への全2乗距離を最小化する。
我々は、$m' = 0$と穴のある格子グラフであっても、問題は、$n$が測定数であるすべての$\varepsilon>0$に対して$Ω(n^{1/2-\varepsilon})$で近似するようにNPハードであることを証明している。
次に,接続を強制する反復的なマージ手順で部分空間フィッティングを交互に行う,効率的なロイド式ヒューリスティックを導入する。
私たちのメソッドは、構築によって正確に$k$接続されたリージョンを返しますが、制約のないメソッドは、より高いコストで1{,}966$切断されたフラグメントを残します。
グローバルな海面時系列に関する160のコンフィグレーションの研究において、我々のマージベースの修復は73.75 %のケースで4つの戦略の中で最強であり、テストされた全てのクラスタ数でウォードの手法のような競合よりも一貫して優れています。
その結果得られた地域は、エルニーニョ・南方振動やインド洋双極子のような気候指標に沿った信号を分離した。
ジオデシーのために開発されたが、この手法は気候、リモートセンシング、ニューロイメージング、センサーネットワークなど、他の空間的に埋め込まれた多変量時系列に適用される。
関連論文リスト
- Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification [52.452902154360565]
CARSANNは、局所的な幾何学的複雑さに応じて各地区の空間的支持を適応する幾何学駆動のフレームワークである。
70以上の実世界のOpenMLデータセットの実験は、CARSANNが標準の$k$-NNで一貫して改善されていることを示している。
論文 参考訳（メタデータ） (2026-08-27T19:19:07Z) - Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
我々は、$n$点を$K$群にクラスタリングする根本的な問題を、$mathbbRd$における等方ガウスの混合から引き出された。
我々は、$n leq dK$のクラスタリングの難しさは次元の縮小とスペクトル法によって引き起こされるが、中等次元のレジームはより微妙な現象を伴い、「非最適率」につながることを示した。
我々は、この速度にマッチする新しい非スペクトルアルゴリズムを提案し、中等次元のクラスタリング問題の計算限界に新しい光を当てる。
論文 参考訳（メタデータ） (2026-02-26T14:03:55Z) - Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
ハイパースペクトル画像(HSI)の教師なし解析にサブスペースクラスタリングが広く採用されている。
近年のモデル対応深層空間クラスタリング手法では、O(n2)の複雑性を持つ自己表現行列の計算とスペクトルクラスタリングを含む2段階のフレームワークを用いることが多い。
本稿では,HSIクラスタリングを効率的に行うために,局所構造と非局所構造を協調的にキャプチャする,ベース表現に基づく拡張性のあるコンテキスト保存深層クラスタリング手法を提案する。
論文 参考訳（メタデータ） (2025-06-12T16:43:09Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - GoMVS: Geometrically Consistent Cost Aggregation for Multi-View Stereo [45.5438546016874]
我々は,GoMVSを提案し,幾何学的に一貫したコストを集約し,隣接したジオメトリをよりよく活用する。
提案手法はDTU, Tanks & Temple, ETH3Dデータセット上での最先端性能を実現する。
論文 参考訳（メタデータ） (2024-04-11T17:59:59Z) - Evolution of $K$-means solution landscapes with the addition of dataset
outliers and a robust clustering comparison measure for their analysis [0.0]
我々は、データセットのアウトリージの増加の結果、K$-meansのソリューション空間の変化をマッピングするために、エネルギーランドスケープアプローチを使用します。
速度論的解析により、全てのケースにおいて、全体のファンネルは浅い局所的に燃やされた地域で構成されていることが明らかとなった。
本稿では,速度解析から得られた速度がクラスタリング類似性の新たな尺度となることを提案する。
論文 参考訳（メタデータ） (2023-06-25T21:22:21Z) - STICC: A multivariate spatial clustering method for repeated geographic
pattern discovery with consideration of spatial contiguity [7.376428009531946]
理想的な空間クラスタリングは、空間的連続性と空間的属性の両方を考慮するべきである。
既存の空間クラスタリングアプローチは、空間的連続性を維持した反復的な地理的パターンを発見するための課題に直面する可能性がある。
本研究では,地理的オブジェクトの属性と空間的関係を考慮した空間的Toeplitz Inverse Covariance-Based Clustering (STICC)法を提案する。
論文 参考訳（メタデータ） (2022-03-17T20:58:06Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - $p$-Norm Flow Diffusion for Local Graph Clustering [18.90840167452118]
我々は、p-ノルムネットワークフローとの拡散を$pin (1,infty)$とする凸最適化定式化の族を示す。
局所クラスタリングでは,入力種子の周囲の低コンダクタンスカットの発見に有用であることを示す。
提案手法は,pge 2$の強い局所実行時間で解き,合成グラフと実世界のグラフの両方で実験的な評価を行い,既存の手法とよく比較できることを示す。
論文 参考訳（メタデータ） (2020-05-20T01:08:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。