GSP（一般化逐次パターン）とは？逐次パターンマイニングの基本を解説

GSP（一般化逐次パターン）とは

GSPは「Generalised Sequential Patterns（一般化逐次パターン）」の略で、1996年にSrikantとAgrawalによって提案された逐次パターンマイニング手法です。両氏が以前に発表した、頻出アイテムセットマイニングの代表的アルゴリズムである「Apriori」を、系列データへと拡張したものにあたります。

GSPは逐次パターンが持つ下向き閉包性（Apriori特性）を利用し、データベースを複数回走査しながら「候補生成→支持度検証」という手順で頻出パターンを段階的に絞り込んでいく方式を採用しています。

GSPアルゴリズムの流れ

第1回目の走査：頻出アイテムの発見

最初のデータベース走査では、最小支持度（min_sup）を満たす頻出アイテムを発見します。各アイテムは、そのアイテムを含む「1イベントの頻出系列」として抽出されます。

第2回目以降の走査：候補系列の生成と検証

2回目以降の各走査では、前回の走査で見つかった逐次パターンの集合（シード集合）を出発点とします。このシード集合から、新たに頻出する可能性のあるパターン、すなわち「候補系列」が生成されます。各候補系列は、生成元となったシードの逐次パターンよりも1つだけ多いアイテムを含みます（パターン内の各イベントは1つまたは複数のアイテムを含み得ます）。

系列の長さとk-系列

系列に含まれるアイテムの総数は「系列の長さ」と呼ばれます。したがって、同一の走査で生成される候補系列の中には、同じ長さを持つものが存在します。長さkの系列は「k-系列」と定義されます。

支持度の計測と終了条件

C_kを候補k-系列の集合とします。データベースを1回走査することで、各候補k-系列の支持度が求められます。C_kの中でmin_sup以上の支持度を持つ候補からなるL_kが「すべての頻出k-系列の集合」であり、この集合が次の走査（k+1回目）のシード集合となります。ある走査で新しい逐次パターンが1つも発見されない場合、または候補系列が1つも生成できない場合に、アルゴリズムは終了します。

Apriori特性による候補の削減

GSPはApriori特性を活用して候補集合を効率的に絞り込みます。具体的には、k回目の走査において、ある系列が候補となるのは、その系列の長さ(k−1)の部分系列がすべて、(k−1)回目の走査で発見済みの逐次パターンである場合に限られます。これにより、支持度計算の対象となる候補数を大幅に削減できます。

その後のデータベース再走査によって各候補系列の支持度が集計され、新たな逐次パターンの集合L_kが得られます。この集合が次の走査のシードとなり、新しいパターンが発見されない、または候補が生成できなくなった時点で処理を終えます。

垂直データ形式による分析

Apriori型の逐次パターンマイニング手法（候補生成・検証ベース）では、系列データベースを「垂直データ形式」に変換して分析することも可能です。垂直データ形式では、データベースは (itemset: (sequence_ID, event_ID)) という形式のタプルの集合として表現されます。

イベント識別子（event_ID）は、系列内におけるタイムスタンプの役割を果たします。系列内のi番目のアイテムセット（イベント）のevent_IDはiとなります。また、1つのアイテムセットは複数の系列に出現することがあり、特定のアイテムセットに対する(sequence_ID, event_ID)ペアの集合は、そのアイテムセットの「IDリスト（ID_list）」と呼ばれます。