論文の概要: Bi-Filtration and Stability of TDA Mapper for Point Cloud Data
- arxiv url: http://arxiv.org/abs/2409.17360v1
- Date: Wed, 25 Sep 2024 21:08:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-30 11:54:28.964633
- Title: Bi-Filtration and Stability of TDA Mapper for Point Cloud Data
- Title（参考訳）: ポイントクラウドデータのためのTDAマッパーのバイフィルタと安定性
- Authors: Wako Bungula, Isabel Darcy,
- Abstract要約: カバーサイズとtextbf$epsilon$ を同時に増加させることで安定性を得る方法を示す。
特に,2つのデータセット間のホモロジー群の被覆サイズと$epsilon$はtextbf2$delta$-interleavedであることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Carlsson, Singh and Memoli's TDA mapper takes a point cloud dataset and outputs a graph that depends on several parameter choices. Dey, Memoli, and Wang developed Multiscale Mapper for abstract topological spaces so that parameter choices can be analyzed via persistent homology. However, when applied to actual data, one does not always obtain filtrations of mapper graphs. DBSCAN, one of the most common clustering algorithms used in the TDA mapper software, has two parameters, \textbf{$\epsilon$} and \textbf{MinPts}. If \textbf{MinPts = 1} then DBSCAN is equivalent to single linkage clustering with cutting height \textbf{$\epsilon$}. We show that if DBSCAN clustering is used with \textbf{MinPts $>$ 2}, a filtration of mapper graphs may not exist except in the absence of free-border points; but such filtrations exist if DBSCAN clustering is used with \textbf{MinPts = 1} or \textbf{2} as the cover size increases, \textbf{$\epsilon$} increases, and/or \textbf{MinPts} decreases. However, the 1-dimensional filtration is unstable. If one adds noise to a data set so that each data point has been perturbed by a distance at most \textbf{$\delta$}, the persistent homology of the mapper graph of the perturbed data set can be significantly different from that of the original data set. We show that we can obtain stability by increasing both the cover size and \textbf{$\epsilon$} at the same time. In particular, we show that the bi-filtrations of the homology groups with respect to cover size and $\epsilon$ between these two datasets are \textbf{2$\delta$}-interleaved.
- Abstract（参考訳）: Carlsson、Singh、MemoliのTDAマッパーはポイントクラウドデータセットを取得し、いくつかのパラメータの選択に依存するグラフを出力する。
Dey, Memoli, Wang らは抽象位相空間のためのマルチスケールマッパーを開発し、パラメータ選択を永続ホモロジーで解析できるようにした。
しかし、実際のデータに適用する場合、必ずしもマッパーグラフのフィルターを得るとは限らない。
TDAマッパーソフトウェアで使用される最も一般的なクラスタリングアルゴリズムの1つであるDBSCANは、 \textbf{$\epsilon$} と \textbf{MinPts} の2つのパラメータを持つ。
もし \textbf{MinPts = 1} ならば、DBSCAN は切断高さ \textbf{$\epsilon$} の単一リンククラスタリングと同値である。
DBSCANクラスタリングが \textbf{MinPts $>$ 2} で使用される場合、自由境界点がない場合を除いてマッパーグラフのフィルタリングは存在しないが、カバーサイズが大きくなるにつれて \textbf{MinPts = 1} あるいは \textbf{2} でDBSCANクラスタリングが使用されると、/または \textbf{$\epsilon$} が増加し、/または \textbf{MinPts} が減少する。
しかし、1次元の濾過は不安定である。
データセットにノイズを加えて、各データポイントがほとんどの \textbf{$\delta$} において距離で摂動された場合、摂動データセットのマッパーグラフの永続的ホモロジーは、元のデータセットと大きく異なる。
カバーサイズと \textbf{$\epsilon$} を同時に増加させることで安定性が得られることを示す。
特に、これらの2つのデータセットの間のホモロジー群の被覆サイズと$\epsilon$の2次フィルターは、 \textbf{2$\delta$}-インターリーブドであることが示される。
関連論文リスト
- Conformal Predictions under Markovian Data [50.24983453990065]
マルコフデータに適用した場合の分割等角予測法について検討する。
データ間の相関によって引き起こされる被覆率の差を定量化する。
K$-split CP は鎖の混合特性に適応する手法である。
論文 参考訳（メタデータ） (2024-07-21T22:01:09Z) - Public-data Assisted Private Stochastic Optimization: Power and
Limitations [30.298342283075172]
本稿では,PA-DPアルゴリズムの限界と限界について検討する。
完全な/ラベル付き公開データについては、$tildeOmegabig(minbigfrac1sqrtn+fracsqrtdnepsilon big big)$が過剰なリスクを持つことを示す。
また,PA-DPによる教師あり学習について,テキスト非ラベル公開サンプルを用いて検討した。
論文 参考訳（メタデータ） (2024-03-06T17:06:11Z) - $G$-Mapper: Learning a Cover in the Mapper Construction [0.7852714805965528]
Mapperアルゴリズムは、与えられたデータセットの構造を反映したグラフを出力するトポロジカルデータ解析(TDA)の可視化技術である。
本稿では,正規性に関する統計的テストに従って繰り返し被覆を分割することで,Mapperグラフの被覆を最適化するアルゴリズムを提案する。
我々のアルゴリズムは,アンダーソン・ダーリング試験を反復的に適用することにより,$k$-meansの最適なクラスタ数を探索する$G$-meansクラスタリングに基づいている。
論文 参考訳（メタデータ） (2023-09-12T22:51:16Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction [0.0]
パーシステンスダイアグラム(PD)は、ポイントクラウドデータのシグネチャとして使用される。
PD間のボトルネック距離d_Bを用いて2つの点の雲を比較することができる。
我々は、PD間の新しいスケール不変距離を正規化ボトルネック距離d_Nと定義し、研究する。
論文 参考訳（メタデータ） (2023-06-11T17:17:48Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data [8.55881355051688]
本研究では,高次元空間における重み付きデータを用いたDP-SCOの問題に関する最初の研究を行う。
損失関数が滑らかで、その勾配が第二次モーメントに有界ならば、$epsilon$-DPモデルで$tildeO(fraclog d(nepsilon)frac13)$の(高い確率)誤差境界(過剰な集団リスク)を得ることが可能である。
論文の第2部では,重み付きデータを用いたスパース学習について検討した。
論文 参考訳（メタデータ） (2021-07-23T11:03:21Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Faster DBSCAN via subsampled similarity queries [42.93847281082316]
DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。
本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
論文 参考訳（メタデータ） (2020-06-11T18:57:54Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。