論文の概要: 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) ランタイムが最低である。
関連論文リスト
- Discovering Leitmotifs in Multidimensional Time Series [3.6463708995502273]
本稿では,MDTSのための新しい,効率的かつ高効率なリートモチーフ探索アルゴリズムLAMAを提案する。
LAMAは2つの中核主成分に依存している: (a) リートモチーフは、まだ未知の数のサブディメンジョンしか与えられていない ― 少なすぎる、あるいは多すぎる、そして (b) サブディメンジョンの集合は、見つかった最良のパターンから独立していない。
論文 参考訳(メタデータ) (2024-10-16T06:50:45Z) - 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) - Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
大規模言語モデルに対して,多段階推論を行うための課題について検討する。
中心的な疑問は、どの推論例が最も効果的なプロンプトを作るかである。
多段階推論のためのシンプルで効果的な例選択方式である複雑性ベースのプロンプトを提案する。
論文 参考訳(メタデータ) (2022-10-03T05:33:27Z) - Multi-scale Anomaly Detection for Big Time Series of Industrial Sensors [50.6434162489902]
そこで本研究では,自然にスムーズな時系列を復号・符号化する手法であるMissGANを提案する。
MissGANはラベルを必要としないし、通常のインスタンスのラベルだけを必要とするので、広く適用できます。
論文 参考訳(メタデータ) (2022-04-18T04:34:15Z) - OPP-Miner: Order-preserving sequential pattern mining [26.997138010841347]
本稿では時系列データの順序関係に基づいてパターンを表現した順序保存シーケンシャルパターン(OPP)マイニング手法を提案する。
実験により、OPP-Minerは効率的でスケーラブルであるだけでなく、時系列で類似したサブシーケンスを発見できることが示された。
論文 参考訳(メタデータ) (2022-01-09T11:06:26Z) - 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 Liebig's Barrel Meets Facial Landmark Detection: A Practical Model [87.25037167380522]
正確で、堅牢で、効率的で、一般化可能で、エンドツーエンドのトレーニングが可能なモデルを提案する。
精度を向上させるために,2つの軽量モジュールを提案する。
DQInitは、インプットからデコーダのクエリを動的に初期化し、複数のデコーダ層を持つものと同じ精度でモデルを実現する。
QAMemは、共有するクエリではなく、それぞれのクエリに別々のメモリ値を割り当てることで、低解像度のフィーチャーマップ上のクエリの識別能力を高めるように設計されている。
論文 参考訳(メタデータ) (2021-05-27T13:51:42Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。
複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。
これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
論文 参考訳(メタデータ) (2021-03-25T14:35:07Z) - Motif Difference Field: A Simple and Effective Image Representation of
Time Series for Classification [3.419406971620478]
モチーフベースの時系列クラスタリングは、時系列データの高階パターンや構造の発見に使用される。
時系列の画像表現に基づく畳み込みニューラルネットワーク(CNN)分類器にインスパイアされたモチーフ差分場(MDF)を提案する。
論文 参考訳(メタデータ) (2020-01-21T14:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。