論文の概要: Coresets for Time Series Clustering

• arxiv url: http://arxiv.org/abs/2110.15263v1
• Date: Thu, 28 Oct 2021 16:21:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-29 18:56:01.569443
• Title: Coresets for Time Series Clustering
• Title（参考訳）: 時系列クラスタリングのためのコアセット
• Authors: Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi
• Abstract要約: 本稿では,時系列データを用いたクラスタリング問題に対するコアセット構築の問題について検討する。 我々の主な貢献は混合モデルのためのコアセットを構築するアルゴリズムである。 合成データを用いて,コアセットの性能を実証的に評価した。
• 参考スコア（独自算出の注目度）: 33.801060211529354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of constructing coresets for clustering problems with time series data. This problem has gained importance across many fields including biology, medicine, and economics due to the proliferation of sensors facilitating real-time measurement and rapid drop in storage costs. In particular, we consider the setting where the time series data on $N$ entities is generated from a Gaussian mixture model with autocorrelations over $k$ clusters in $\mathbb{R}^d$. Our main contribution is an algorithm to construct coresets for the maximum likelihood objective for this mixture model. Our algorithm is efficient, and under a mild boundedness assumption on the covariance matrices of the underlying Gaussians, the size of the coreset is independent of the number of entities $N$ and the number of observations for each entity, and depends only polynomially on $k$, $d$ and $1/\varepsilon$, where $\varepsilon$ is the error parameter. We empirically assess the performance of our coreset with synthetic data.
• Abstract（参考訳）: 時系列データを用いたクラスタリング問題に対するコアセット構築の問題について検討する。 この問題は、リアルタイム測定やストレージコストの急激な低下を促進するセンサーの急増により、生物学、医学、経済学など多くの分野において重要になっている。 特に、$n$エンティティの時系列データが$k$クラスタ上の自己相関を持つガウス混合モデルから$n$エンティティの時系列データが$\mathbb{r}^d$で生成されるような設定を考える。 我々の主な貢献は、この混合モデルにおける最大確率目的のためにコアセットを構築するアルゴリズムである。 我々のアルゴリズムは効率的であり、基礎となるガウスの共分散行列に対する穏やかな有界性仮定の下では、コアセットのサイズは各エンティティのエンティティ数と観察数とは独立であり、多項式的に$k$, $d$, $1/\varepsilon$に依存し、ここで$\varepsilon$がエラーパラメータである。 我々は合成データを用いてコアセットの性能を実証的に評価する。

関連論文リスト

• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time [6.961946145048321]
  本稿では,クラスタ性が強いグラフに対して,サブ線形時間スペクトルクラスタリングオラクルを設計する問題に対処する。 アルゴリズムは仮定を緩和するが、誤分類比はわずかに高い。 私たちのクラスタリングオラクルは、いくつかのランダムなエッジ削除に対して堅牢です。
  論文  参考訳（メタデータ） (2023-10-27T03:40:37Z)
• New Coresets for Projective Clustering and Applications [34.82221047030618]
  点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。 我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
  論文  参考訳（メタデータ） (2022-03-08T19:50:27Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。