シーケンシャルパターンマイニング

シーケンシャルパターンマイニングは、値が順番に提供されるデータ例間の統計的に関連するパターンを見つけることに関係するデータマイニングのトピックです。 ^{[1] [2]}通常、値は離散的であると想定されるため、時系列マイニングは密接に関連していますが、通常は別のアクティビティと見なされます。シーケンシャルパターンマイニングは、構造化データマイニングの特殊なケースです。

この分野では、いくつかの重要な従来の計算問題が扱われています。これには、シーケンス情報のための効率的なデータベースとインデックスの構築、頻繁に発生するパターンの抽出、シーケンスの類似性の比較、および欠落しているシーケンス メンバーの回復が含まれます。一般に、シーケンス マイニングの問題は、通常、文字列処理アルゴリズムに基づく文字列マイニング と、通常、関連ルール学習に基づくアイテムセット マイニングに分類できます。ローカル プロセス モデル^[3]は、シーケンシャル パターン マイニングを、シーケンシャル順序付け構造に加えて、(排他的) 選択、ループ、および並行性構造を含むことができるより複雑なパターンに拡張します。

文字列マイニングでは通常、シーケンスに現れる項目の限られたアルファベットを扱いますが、シーケンス自体は通常非常に長くなることがあります。アルファベットの例には、自然言語テキストで使用されるASCII文字セットのアルファベット、DNA シーケンスのヌクレオチド塩基「A」、「G」、「C」、「T」、またはタンパク質シーケンスのアミノ酸があります。生物学アプリケーションでは、文字列内のアルファベットの配置の分析を使用して、遺伝子およびタンパク質シーケンスを調べてその特性を判定できます。DNAまたはタンパク質の文字のシーケンスを知ること自体は最終目標ではありません。むしろ、主要なタスクは、その構造と生物学的機能の観点からシーケンスを理解することです。これは通常、最初に各シーケンス内の個々の領域または構造単位を識別し、次に各構造単位に機能を割り当てることによって達成されます。多くの場合、これには特定のシーケンスを以前に研究したものと比較する必要があります。文字列内で 挿入、削除、および突然変異が発生すると、文字列間の比較は複雑になります。

バイオインフォマティクスにおける配列比較のための主要なアルゴリズムの調査と分類は、Abouelhoda & Ghanem (2010) によって発表されており、その中には次のようなものが含まれている: ^[4]

• 繰り返し関連の問題:単一のシーケンスに対する操作を扱い、分散した固定長および最大長の繰り返し、タンデム繰り返し、および一意のサブシーケンスと欠落した (綴られていない) サブシーケンスを見つけるために、正確な文字列マッチングまたは近似文字列マッチング方法に基づくことができます。
• アライメント問題:最初に 1 つ以上の配列をアライメントすることで文字列間の比較を扱います。一般的な方法の例には、データベース内の 1 つの配列を複数の配列と比較するBLASTや、複数のアライメントを行うClustalWなどがあります。アライメント アルゴリズムは、正確な方法または近似方法のいずれかに基づくことができ、グローバル アライメント、セミグローバル アライメント、およびローカル アライメントに分類することもできます。配列アライメントを参照してください。

シーケンス マイニングの問題の中には、頻繁なアイテムセットとその出現順序を発見するのに役立つものがあります。たとえば、「{顧客が車を購入した場合}、1 週間以内に {保険を購入} する可能性が高い」という形式のルールや、株価のコンテキストで「{ノキアが上昇し、エリクソンが上昇した場合}、2 日以内に {モトローラが上昇し、サムスンが上昇する可能性が高い}」という形式のルールを求めています。従来、アイテムセット マイニングは、大規模なトランザクションで頻繁に共起するアイテム間の規則性を発見するためのマーケティング アプリケーションで使用されています。たとえば、スーパーマーケットでの顧客の買い物かごのトランザクションを分析すると、「顧客がタマネギとジャガイモを一緒に購入した場合、同じトランザクションでハンバーグの肉も購入する可能性が高い」というルールを作成できます。

アイテムセットマイニングの主要アルゴリズムの調査と分類は、Han et al. (2007)によって発表されている。^[5]

頻繁なアイテムセットのマイニングのためにシーケンス データベースに適用される 2 つの一般的な手法は、影響力のあるアプリオリ アルゴリズムと、より最近のFP 成長手法です。

製品やユーザーの購買行動は多種多様であるため、製品が陳列されている棚は小売環境において最も重要なリソースの 1 つです。小売業者は棚のスペース割り当てと製品陳列を適切に管理することで、利益を増やすだけでなくコストを削減することもできます。この問題を解決するために、George と Binu (2013) は、PrefixSpan アルゴリズムを使用してユーザーの購買パターンをマイニングし、マイニングされた購買パターンの順序に基づいて製品を棚に配置するアプローチを提案しました。^[6]

一般的に使用されるアルゴリズムは次のとおりです。

• GSPアルゴリズム
• 同値クラスを使用したシーケンシャルパターン検出 (SPADE)
• フリースパン
• プレフィックススパン
• MAPres ^[7]
• Seq2Pat（制約ベースのシーケンシャルパターンマイニング用）^{[8] [9]}

• コロケーション抽出 – 単語のシーケンスを見つける計算技術
• プロセスマイニング - イベントログを使ったデータマイニング技術
• 配列解析 – ゲノム配列の識別と研究
• 社会科学におけるシーケンス分析 – カテゴリシーケンスのセットの分析
• シーケンスクラスタリング – アルゴリズムフォールバックとしてウィキデータの説明を表示するページスペースなしで短い説明を表示するページ
• シーケンスラベリング – パターン認識フォールバックとしてウィキデータの説明を表示するページ

• SPMF には、GSP、PrefixSpan、SPADE、SPAM などのオープンソース実装が含まれています。