GSP** ย่อมาจาก **Generalised Sequential Patterns** เป็น sequential pattern mining method ที่พัฒนาโดย Srikant และ Agrawal ในปี 1996 เป็นการขยายของ seminal algorithm ของพวกเขาสำหรับ frequent itemset mining ที่เรียกว่า Apriori GSP ใช้ downward-closure property ของ sequential patterns และใช้ multiple-pass, candidate generate-and-test approach
อัลกอริทึมมีดังนี้ ใน first scan ของ database หา frequent items ทุกตัว (มี minimum support) แต่ละ item ให้ 1-event frequent sequence ที่มี item นั้น แต่ละ subsequent pass เริ่มจาก seed set ของ sequential patterns และ set ของ sequential patterns ที่พบใน pass ก่อนหน้า
Seed set นี้ generate candidate sequences ใหม่ที่อาจเป็น frequent แต่ละ candidate sequence มี item มากกว่า seed sequential pattern ที่มันมาจาก 1 item (แต่ละ event ใน pattern อาจมี 1 หรือหลาย items) จำนวน items ใน sequence เรียกว่า length ของ sequence กำหนด sequence ที่มี length k ว่าเป็น k-sequence
ให้ Ck แทน set ของ candidate k-sequences การผ่าน database หนึ่งครั้ง หา support สำหรับทุก candidate k-sequence Candidates ใน Ck ที่มี min_sup ขึ้นไป สร้าง Lk คือ set ของ all frequent k-sequences Set นี้กลายเป็น seed set สำหรับ pass ถัดไป k+1 Algorithm หยุดเมื่อไม่พบ sequential pattern ใหม่ใน pass หรือไม่สามารถ generate candidate sequence ได้
GSP ใช้ Apriori property ลด candidate set ดังนี้ ใน k-th pass sequence เป็น candidate ก็ต่อเมื่อทุก length-(k−1) subsequences ของมันเป็น sequential pattern ที่พบใน (k−1)-th pass
New scan ของ database รวบรวม support สำหรับแต่ละ candidate sequence หา sequential patterns ใหม่ Lk Set นี้กลายเป็น seed สำหรับ pass ถัดไป Algorithm หยุดเมื่อไม่พบ sequential pattern ใน pass หรือไม่มี candidate sequence generate
Apriori-like sequential pattern mining methods (based on candidate generate and test) สามารถ analyze ได้โดยแปลง sequence database เป็น vertical data format ใน vertical format database กลายเป็น set of tuples รูปแบบ (itemset: (sequence_ID, event_ID))
Event identifier เป็น timestamp ภายใน sequence Event_ID ของ i-th itemset (หรือ event) ใน sequence คือ i Itemset อาจปรากฏในหลาย sequences Set ของ (sequence ID, event ID) pairs สำหรับ itemset ที่กำหนด สร้าง ID_list ของ itemset
