GSPアルゴリズム

GSPアルゴリズム（Generalized Sequential Pattern algorithm）は、シーケンスマイニングに使用されるアルゴリズムです。シーケンスマイニング問題を解決するためのアルゴリズムは、ほとんどがアソシエーションルール（レベル別）アルゴリズムに基づいています。レベル別パラダイムを使用する1つの方法は、まずレベル別にすべての頻出アイテムを発見することです。これは、データベース内のすべてのシングルトン要素の出現回数をカウントすることを意味します。次に、トランザクションから頻出でないアイテムを削除してフィルタリングします。このステップの最後に、各トランザクションは、元々含まれていた頻出要素のみで構成されます。この修正されたデータベースがGSPアルゴリズムへの入力となります。このプロセスでは、データベース全体を1回走査する必要があります。

GSPアルゴリズムは、データベースを複数回走査します。最初の走査では、すべての単一アイテム（1シーケンス）がカウントされます。頻繁に出現するアイテムから、候補となる2シーケンスのセットが作成され、その出現頻度を特定するために別の走査が行われます。頻繁に出現する2シーケンスを使用して候補となる3シーケンスが生成され、このプロセスは、より頻繁に出現するシーケンスが見つからなくなるまで繰り返されます。このアルゴリズムには、主に2つのステップがあります。

• 候補生成。頻繁に出現する(k-1)個のシーケンスの集合Fk _-1が与えられた場合、次のパスの候補はF(k-1)をそれ自身と結合することによって生成されます。剪定フェーズでは、少なくとも1つの部分シーケンスが頻繁に出現しないシーケンスはすべて削除されます。
• サポートカウント。通常、効率的なサポートカウントにはハッシュツリーベースの検索が用いられます。最後に、最大頻度でないシーケンスが削除されます。

 F 1 = 頻繁に出現する 1-シーケンスの集合 k=2、 F k-1 がNull でない間、繰り返す。 候補集合 C k (候補 k 系列の集合) を生成する。 データベースD内のすべての入力シーケンスsについて するsがaをサポートする場合、 C k 内のすべてのaのカウントをインクリメントする 終了Fk = {周波数が閾値を超える a ∈ C k } k = k+1; 終了 結果 = すべての頻出シーケンスの集合は、すべての F kの和集合です

上記のアルゴリズムはAprioriアルゴリズムに似ています。ただし、主な違いは候補セットの生成方法です。ここで、以下のことを仮定します。

A→BとA→C

これらは頻繁に出現する2つの2系列です。これらの系列に含まれる項目はそれぞれ(A, B)と(A, C)です。通常のアソシエーションルールに基づく候補生成では、3項目セットとして(A, B, C)が得られますが、本稿では上記の2系列を結合することで、以下の3系列が得られます。

A → B → C、A → C → B、A → BC

候補生成フェーズでは、この点が考慮されます。GSPアルゴリズムは、シーケンス要素間の最大間隔や最小間隔といった時間制約を考慮しながら、頻繁に出現するシーケンスを検出します。さらに、スライディングウィンドウの概念、つまり、異なるイベントに由来する場合でも、アイテムが同じイベントに属するものとして観測される時間間隔もサポートしています。

• シーケンスマイニング

• R. Srikant および R. Agrawal. 1996.シーケンスパターンのマイニング: 一般化とパフォーマンスの改善. 第 5 回国際データベース技術拡張会議: データベース技術の進歩 (EDBT '96) の議事録、Peter MG Apers、Mokrane Bouzeghoub、および Georges Gardarin (編)。Springer-Verlag、ロンドン、英国、3–17。
• Pujari, Arun K. (2001).データマイニング技術. Universities Press. pp. 256–260 . ISBN  81-7371-380-4。
• Zaki, MJ Machine Learning (2001) 42: 31 .

• SPMFには、GSPアルゴリズムのオープンソース実装に加え、PrefixSpan、SPADE、SPAM、ClaSP、CloSpan、BIDEが含まれています。