論文の概要: Efficient Conformance Checking using Approximate Alignment Computation
with Tandem Repeats
- arxiv url: http://arxiv.org/abs/2004.01781v2
- Date: Sat, 26 Mar 2022 13:28:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-17 13:04:01.715133
- Title: Efficient Conformance Checking using Approximate Alignment Computation
with Tandem Repeats
- Title(参考訳): タンデムリピートを用いた近似アライメント計算による効率よいコンフォーマンスチェック
- Authors: Daniel Rei{\ss}ner, Abel Armas-Cervantes, Marcello La Rosa
- Abstract要約: コンフォーマンスチェックは、期待されるプロセスの振る舞いをキャプチャするプロセスモデルと、観測された振る舞いを記録する対応するイベントログの違いを発見し、記述することを目的としている。
アライメントは、イベントログ内のトレースと、対応するプロセスモデルの最も近い実行トレースの間の距離を計算するための確立されたテクニックである。
本稿では,前処理と後処理を併用してトレースの長さを圧縮し,アライメントコストを再計算する手法を提案する。
- 参考スコア(独自算出の注目度): 0.03222802562733786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conformance checking encompasses a body of process mining techniques which
aim to find and describe the differences between a process model capturing the
expected process behavior and a corresponding event log recording the observed
behavior. Alignments are an established technique to compute the distance
between a trace in the event log and the closest execution trace of a
corresponding process model. Given a cost function, an alignment is optimal
when it contains the least number of mismatches between a log trace and a model
trace. Determining optimal alignments, however, is computationally expensive,
especially in light of the growing size and complexity of event logs from
practice, which can easily exceed one million events with traces of several
hundred activities. A common limitation of existing alignment techniques is the
inability to exploit repetitions in the log. By exploiting a specific form of
sequential pattern in traces, namely tandem repeats, we propose a novel
approximate technique that uses pre- and post-processing steps to compress the
length of a trace and recomputes the alignment cost while guaranteeing that the
cost result never under-approximates the optimal cost. In an extensive
empirical evaluation with 50 real-life model log pairs and against six
state-of-the-art alignment techniques, we show that the proposed compression
approach systematically outperforms the baselines by up to an order of
magnitude in the presence of traces with repetitions, and that the cost
over-approximation, when it occurs, is negligible.
- Abstract(参考訳): コンフォーマンスチェックは、期待されるプロセスの振る舞いをキャプチャするプロセスモデルと、観測された振る舞いを記録する対応するイベントログの違いを見つけ、記述することを目的とした、一連のプロセスマイニング技術を含んでいる。
アライメントは、イベントログ内のトレースと対応するプロセスモデルの最も近い実行トレースの間の距離を計算するための確立されたテクニックである。
コスト関数が与えられた場合、アライメントは、ログトレースとモデルトレースの間のミスマッチ数が最小である場合に最適である。
しかし、最適なアライメントを決定するには計算コストがかかる。特に、数百のアクティビティのトレースを持つ100万件を超えるイベントログの増大と、プラクティスからのイベントログの複雑さを考慮して。
既存のアライメントテクニックの一般的な制限は、ログの繰り返しを利用することができないことだ。
トレースの特定の形態,すなわちタンデム繰り返しを利用して,前処理と後処理を併用してトレースの長さを圧縮し,アライメントコストを再計算し,コストが最適コストを過小評価しないことを保証する,新しい近似手法を提案する。
50個の実生活モデルログ対と6つの最先端アライメント手法を用いた広範な実証評価において,提案手法は,反復を伴うトレースの存在下で,最大1桁の精度でベースラインを体系的に上回っており,その場合のコストオーバー近似は無視できることを示した。
関連論文リスト
- Efficient Online Computation of Business Process State From Trace Prefixes via N-Gram Indexing [0.5141137421503899]
プロセスモデルとプロセスの進行中ケースのトレースプレフィックスを含むイベントログが与えられたら、各ケースをモデル内の対応する状態にマップする。
この状態計算問題に対するアプローチは、モデルに対して各トレースプレフィックスのトークンベースのリプレイを実行することである。
本稿では,現在進行中の事例のトレースプレフィックスが与えられた場合,n-gramとして状態を表わす指標を用いて,その状態を一定時間に計算する手法を提案する。
論文 参考訳(メタデータ) (2024-09-09T14:28:24Z) - A Scalable and Near-Optimal Conformance Checking Approach for Long Traces [3.3170150440851485]
プロセスマイニングにおける重要なタスクであるコンフォーマルティチェックは、最適なアライメントを見つけるという指数関数的な複雑さのため、計算不能になる可能性がある。
本稿では,これらの拡張性に対処する新しいスライディングウインドウ手法を提案する。
トレースを管理可能なサブトレースに分割し,プロセスモデルと反復的に整列することにより,検索空間を大幅に削減する。
論文 参考訳(メタデータ) (2024-06-08T11:04:42Z) - Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳(メタデータ) (2024-05-24T17:11:27Z) - Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
最小ウェイト完全マッチングを用いて表面コードを復号するパイプライン手法について述べる。
独立な非通信可能な並列化処理段階は、潜在的な相関に従ってグラフを再重み付けする。
後続の一般的なステージがマッチングを終了します。
完全にフォールトトレラントなトーリック, 回転しない, 回転する曲面符号に対して, 新たなアルゴリズムの有効性を検証した。
論文 参考訳(メタデータ) (2022-05-19T19:58:02Z) - FineDiving: A Fine-grained Dataset for Procedure-aware Action Quality
Assessment [93.09267863425492]
競争力のあるスポーツビデオにおける行動の高レベル意味論と内部時間構造の両方を理解することが、予測を正確かつ解釈可能なものにする鍵である、と我々は主張する。
本研究では,多様なダイビングイベントに対して,アクションプロシージャに関する詳細なアノテーションを付加した,ファインディビングと呼ばれる詳細なデータセットを構築した。
論文 参考訳(メタデータ) (2022-04-07T17:59:32Z) - Conformance Checking Over Stochastically Known Logs [7.882975068446842]
データログは、例えば、センサ読み取りの不正確さや、処理プログラムによる読み取りの誤った解釈によって不確実になる可能性がある。
この作業では、プロセスモデルとイベントログを比較するコンフォーマンスチェックに重点を置いています。
我々は,ログ内の事象の不確実性を反映したトレースモデル,同期生成物,コスト関数を数学的に定義する。
論文 参考訳(メタデータ) (2022-03-14T21:33:06Z) - CoCoMoT: Conformance Checking of Multi-Perspective Processes via SMT
(Extended Version) [62.96267257163426]
我々はCoCoMoT(Computing Conformance Modulo Theories)フレームワークを紹介する。
まず、純粋な制御フロー設定で研究したSATベースのエンコーディングを、データ認識ケースに持ち上げる方法を示す。
次に,プロパティ保存型クラスタリングの概念に基づく新しい前処理手法を提案する。
論文 参考訳(メタデータ) (2021-03-18T20:22:50Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Process Discovery for Structured Program Synthesis [70.29027202357385]
プロセスマイニングにおける中核的なタスクは、イベントログデータから正確なプロセスモデルを学ぶことを目的としたプロセス発見である。
本稿では,ターゲットプロセスモデルとして(ブロック-)構造化プログラムを直接使用することを提案する。
我々は,このような構造化プログラムプロセスモデルの発見に対して,新たなボトムアップ・アグリメティブ・アプローチを開発する。
論文 参考訳(メタデータ) (2020-08-13T10:33:10Z) - An Entropic Relevance Measure for Stochastic Conformance Checking in
Process Mining [9.302180124254338]
本稿では,各ログのトレースを圧縮するために必要な平均ビット数として計算された適合性チェックのためのエントロピー関連尺度を提案する。
エントロピー関連性はログのサイズで線形に計算可能であることを示し、産業環境における新しい手法の適用可能性を示す評価結果を提供する。
論文 参考訳(メタデータ) (2020-07-18T02:25:33Z) - Partial Order Resolution of Event Logs for Process Conformance Checking [10.58705988536919]
既存の適合性チェック技術の重要な前提は、すべてのイベントがプロセスインスタンス毎のイベントの順序を推測できるタイムスタンプに関連付けられているということです。
本稿では,動作抽象化の異なる概念を取り入れた,この課題に対するいくつかの推定手法を提案する。
実世界のデータと合成データの実験により、我々の手法は最先端の精度を大幅に向上させることが明らかとなった。
論文 参考訳(メタデータ) (2020-07-05T18:43:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。