論文の概要: Motiflets -- Fast and Accurate Detection of Motifs in Time Series
- arxiv url: http://arxiv.org/abs/2206.03735v1
- Date: Wed, 8 Jun 2022 08:22:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-09 13:14:53.671208
- Title: Motiflets -- Fast and Accurate Detection of Motifs in Time Series
- Title(参考訳): Motiflets -- 時系列におけるMotifの高速かつ正確な検出
- Authors: Patrick Sch\"afer, Ulf Leser
- Abstract要約: モチーフは直感的には、より大きな時系列の中でほぼ同じことを繰り返す短い時系列である。
モチーフ発見(MD)は、与えられた入力系列においてそのようなモチーフを見つけるタスクである。
そこで我々は,k-Motifletの正確な近似アルゴリズムを提案し,その複雑性を解析する。
- 参考スコア(独自算出の注目度): 6.957232327345943
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A motif intuitively is a short time series that repeats itself approximately
the same within a larger time series. Such motifs often represent concealed
structures, such as heart beats in an ECG recording, or sleep spindles in EEG
sleep data. Motif discovery (MD) is the task of finding such motifs in a given
input series. As there are varying definitions of what exactly a motif is, a
number of algorithms exist. As central parameters they all take the length l of
the motif and the maximal distance r between the motif's occurrences. In
practice, however, suitable values for r are very hard to determine upfront,
and the found motifs show a high variability. Setting the wrong input value
will result in a motif that is not distinguishable from noise. Accordingly,
finding an interesting motif with these methods requires extensive
trial-and-error. We present a different approach to the MD problem. We define
k-Motiflets as the set of exactly k occurrences of a motif of length l, whose
maximum pairwise distance is minimal. This turns the MD problem upside-down:
Our central parameter is not the distance threshold r, but the desired size k
of a motif set, which we show is considerably more intuitive and easier to set.
Based on this definition, we present exact and approximate algorithms for
finding k-Motiflets and analyze their complexity. To further ease the use of
our method, we describe extensions to automatically determine the
right/suitable values for its input parameters. Thus, for the first time,
extracting meaningful motif sets without any a-priori knowledge becomes
feasible. By evaluating real-world use cases and comparison to 4
state-of-the-art MD algorithms, we show that our proposed algorithm is (a)
quantitatively superior, finding larger motif sets at higher similarity, (b)
qualitatively better, leading to clearer and easier to interpret motifs, and
(c) has the lowest runtime.
- Abstract(参考訳): モチーフは直感的には、より大きな時系列の中でほぼ同じことを繰り返す短い時系列である。
このようなモチーフは、心電図記録中の心拍数や脳波睡眠データでの睡眠スピンドルなどの隠れた構造を表現することが多い。
モチーフ発見(MD)は、与えられた入力系列においてそのようなモチーフを見つけるタスクである。
モチーフが何であるかには様々な定義があるため、多くのアルゴリズムが存在する。
中心となるパラメータとして、それらは全てモチーフの長さ l とモチーフの発生の間の最大距離 r を取る。
しかし実際には、r に対する適切な値は事前決定が非常に困難であり、見いだされたモチーフは高い変数を示す。
間違った入力値を設定すると、ノイズと区別できないモチーフが生成される。
したがって、これらの手法で興味深いモチーフを見つけるには、広範な試行錯誤が必要である。
我々はMD問題に対して異なるアプローチを示す。
k-モティフレットを、最大対距離が最小となる長さ l のモチーフの正確な k 発生の集合として定義する。
中心となるパラメータは距離しきい値 r ではなく、モチーフ集合の所望のサイズ k であり、これはかなり直感的で設定が容易である。
この定義に基づいて,k-Motiflet の正確な近似アルゴリズムを提案し,その複雑性を解析する。
提案手法をより簡単にするために,入力パラメータの適切な値を自動的に決定する拡張について述べる。
したがって、初めてアプリオリ知識のない意味のあるモチーフ集合を抽出することは実現可能となる。
実世界のユースケースの評価と4つの最先端MDアルゴリズムとの比較により,提案アルゴリズムが有用であることを示す。
a) 量的に優れ、より類似度の高いより大きなモチーフセットを見つける。
(b)質的に優れ、モチーフの明確化と解釈が容易になる、
(c) ランタイムが最低である。
関連論文リスト
- Representation Learning for Frequent Subgraph Mining [64.32430554934021]
Subgraph Pattern Miner (SPMiner) は、大きなターゲットグラフに頻繁なサブグラフを見つけるための新しいニューラルネットワークである。
5ノードと6ノードのモチーフでは、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できる。
SPMinerは、10ノードの頻繁なモチーフを確実に特定できる。
論文 参考訳(メタデータ) (2024-02-22T08:11:22Z) - LoCoMotif: Discovering time-warped motifs in time series [7.265353600305124]
時系列モチーフディスカバリ(英: Time Series Motif Discovery、TSMD)とは、時系列で何回も発生するパターンを識別するタスクである。
既存のTSMDの手法には以下の制限がある。
制限のないLoCoMotifという新しい方法を提案する。
論文 参考訳(メタデータ) (2023-11-29T12:18:46Z) - Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
本研究では、Boundless DASを用いて、命令に従う間、大規模言語モデルにおける解釈可能な因果構造を効率的に探索する。
私たちの発見は、成長し、最も広くデプロイされている言語モデルの内部構造を忠実に理解するための第一歩です。
論文 参考訳(メタデータ) (2023-05-15T17:15:40Z) - Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
大規模言語モデルに対して,多段階推論を行うための課題について検討する。
中心的な疑問は、どの推論例が最も効果的なプロンプトを作るかである。
多段階推論のためのシンプルで効果的な例選択方式である複雑性ベースのプロンプトを提案する。
論文 参考訳(メタデータ) (2022-10-03T05:33:27Z) - Towards Target High-Utility Itemsets [2.824395407508717]
応用インテリジェンスでは、ユーティリティ駆動型パターン探索アルゴリズムは、データベースの洞察力と有用なパターンを識別することができる。
重要な研究課題として、ターゲットとした高ユーティリティアイテムセットマイニングが登場している。
本稿では,マイニングプロセス中に高ユーティリティなアイテムセットを迅速にマッチングしてターゲットパターンを選択することができるTHUIMを提案する。
論文 参考訳(メタデータ) (2022-06-09T18:42:58Z) - Multi-scale Anomaly Detection for Big Time Series of Industrial Sensors [50.6434162489902]
そこで本研究では,自然にスムーズな時系列を復号・符号化する手法であるMissGANを提案する。
MissGANはラベルを必要としないし、通常のインスタンスのラベルだけを必要とするので、広く適用できます。
論文 参考訳(メタデータ) (2022-04-18T04:34:15Z) - odeN: Simultaneous Approximation of Multiple Motif Counts in Large
Temporal Networks [7.025709586759655]
時間的モチーフを研究する際の主な合併症の1つは、構築できる多くのモチーフである。
そこで我々は,すべてのモチーフを正確に近似したサンプリングベースアルゴリズムodeNを提案する。
論文 参考訳(メタデータ) (2021-08-19T15:06:05Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳(メタデータ) (2021-06-14T13:01:46Z) - When Hearst Is not Enough: Improving Hypernymy Detection from Corpus
with Distributional Models [59.46552488974247]
本稿では,大きなテキストコーパスの助けを借りて,単語 (x, y) 間のis-a関係が存在するかどうかを論じる。
近年の研究では、大規模なハーストペアを抽出して給餌し、目に見えない(x, y)ペアの親和性が緩和された場合、パターンベースのペアの方が優れていることが示唆されている。
本稿では,これらの特定の事例の非無視的存在を初めて定量化し,その場合の分布法がパターンベースの事例を補うのに最適であることを示す。
論文 参考訳(メタデータ) (2020-10-10T08:34:19Z) - Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
動的時間ワープの下で時系列のモチーフを発見するための,最初のスケーラブルな正確な方法を提案する。
我々のアルゴリズムは、DTW計算の99.99%を許容できる。
論文 参考訳(メタデータ) (2020-09-16T19:35:43Z) - Motif Difference Field: A Simple and Effective Image Representation of
Time Series for Classification [3.419406971620478]
モチーフベースの時系列クラスタリングは、時系列データの高階パターンや構造の発見に使用される。
時系列の画像表現に基づく畳み込みニューラルネットワーク(CNN)分類器にインスパイアされたモチーフ差分場(MDF)を提案する。
論文 参考訳(メタデータ) (2020-01-21T14:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。