GSP là viết tắt của Mẫu tuần tự chung. Đây là một phương pháp khai thác mẫu tuần tự được sản xuất bởi Srikant và Agrawal vào năm 1996. Nó là một bản mở rộng của thuật toán danh nghĩa của họ cho khai thác tập phổ biến, được gọi là Apriori. GSP cần bản chất đóng xuống của các mẫu tuần tự và áp dụng phương pháp tiếp cận tạo và kiểm tra nhiều lần, sinh viên thực hiện.
Thuật toán như sau. Trong lần quét đầu tiên của cơ sở dữ liệu, nó có thể phát hiện ra một số mục thường xuyên, tức là những mục có hỗ trợ tối thiểu. Mỗi mục mang lại một chuỗi thường xuyên 1 sự kiện bao gồm cả mục đó. Mỗi lần vượt qua tiếp theo bắt đầu với một nhóm mầm của các mẫu tuần tự và nhóm các mẫu tuần tự được tìm thấy trong lần vượt qua trước đó.
Tập hợp hạt giống này có thể tạo ra các mẫu mới có khả năng xảy ra thường xuyên, được gọi là chuỗi ứng viên. Mỗi chuỗi ứng viên bao gồm nhiều mục hơn là mẫu tuần tự gốc mà từ đó nó được tạo (trong đó mỗi sự kiện trong mẫu có thể bao gồm một hoặc nhiều mục).
Nhiều trường hợp của các mục trong một chuỗi là chiều cao của chuỗi. Do đó, một số chuỗi ứng cử viên trong một lần vượt qua sẽ có cùng chiều cao. Nó định nghĩa một chuỗi có độ dài k là một chuỗi k.
Hãy để C k chỉ ra tập hợp các trình tự k ứng viên. Một lần chuyển qua cơ sở dữ liệu sẽ khám phá ra sự hỗ trợ cho mọi trình tự k ứng viên. Các ứng cử viên trong C k với biểu mẫu min_sup tối thiểu L k , tập hợp của tất cả các dãy k thường xuyên. Tập hợp này phát triển thành tập hợp hạt giống cho lần vượt qua sau, k + 1. Thuật toán loại bỏ khi không có mẫu tuần tự mới nào được phát hiện trong một lần vượt qua hoặc không có trình tự ứng viên nào có thể được tạo.
GSP sử dụng thuộc tính Apriori để rút ngắn tập hợp các ứng viên như sau. Trong lần vượt qua thứ k, một chuỗi chỉ là ứng cử viên nếu mỗi chuỗi con có độ dài- (k −1) của nó là một mẫu tuần tự được phát hiện ở lần chuyển thứ (k −1).
Một lần quét mới cơ sở dữ liệu sẽ tập hợp hỗ trợ cho từng trình tự ứng viên và phát hiện ra một tập hợp các mẫu tuần tự mới, L k . Tập hợp này phát triển thành hạt giống cho lần vượt qua sau. Thuật toán loại bỏ khi không có mẫu tuần tự nào được phát hiện trong một đường chuyền hoặc khi không có trình tự ứng viên nào được tạo.
Các kỹ thuật khai thác mẫu tuần tự giống như Apriori (dựa trên việc tạo và kiểm tra ứng viên) cũng có thể được phân tích bằng cách đo lường cơ sở dữ liệu trình tự thành định dạng dữ liệu dọc. Ở định dạng dữ liệu dọc, cơ sở dữ liệu biến thành một tập hợp các bộ giá trị của biểu mẫu (itemset:(sequence_ID, event_ID)).
Mã nhận dạng sự kiện cung cấp dưới dạng dấu thời gian bên trong một chuỗi. Sự kiện_ID của tập vật phẩm thứ i (hoặc sự kiện) trong một chuỗi là i. Một tập hợp vật phẩm có thể xuất hiện trong nhiều hơn một chuỗi. Tập hợp (ID trình tự, ID sự kiện) kết hợp cho một tập hợp mục nhất định tạo thành ID_list của tập hợp mục.