GSP는 Generalized Sequential Patterns의 약자입니다. Srikant와 Agrawal이 1996년에 만든 순차 패턴 마이닝 방법입니다. Apriori라고 하는 일반적인 항목 집합 마이닝을 위한 핵심 알고리즘의 확장입니다. GSP는 순차적 패턴의 하향 폐쇄 특성을 필요로 하며 여러 단계를 거쳐 학생이 만들고 테스트하는 접근 방식을 채택합니다.
알고리즘은 다음과 같습니다. 데이터베이스의 첫 번째 스캔에서 몇 가지 빈번한 항목, 즉 지원이 최소인 항목을 발견할 수 있습니다. 각 항목은 해당 항목을 포함하는 1개의 이벤트 빈도 시퀀스를 생성합니다. 각 후속 패스는 순차적 패턴의 시드 그룹과 이전 패스에서 찾은 순차적 패턴 그룹으로 시작합니다.
이 시드 세트는 후보 시퀀스라고 하는 잠재적으로 자주 발생하는 새로운 패턴을 생성할 수 있습니다. 각 후보 시리즈는 생성된 시드 순차 패턴보다 하나 이상의 항목을 포함합니다(여기서 패턴의 각 이벤트는 하나 이상의 항목을 포함할 수 있음).
시퀀스에 있는 항목의 여러 인스턴스는 시퀀스의 높이입니다. 따라서 주어진 패스의 일부 후보 시퀀스는 동일한 높이를 갖습니다. 길이가 k인 시퀀스를 k 시퀀스로 정의합니다.
Ck 후보 k-시퀀스의 집합을 나타냅니다. 데이터베이스에 대한 전달은 모든 후보 k-시퀀스에 대한 지원을 발견합니다. Ck의 후보자 최소 min_sup 형식 Lk , 모든 빈번한 k-시퀀스의 집합입니다. 이 세트는 다음 패스 k+1에 대한 시드 세트로 발전합니다. 알고리즘은 패스에서 새로운 순차적 패턴이 발견되지 않거나 후보 시퀀스를 생성할 수 없는 경우 제거합니다.
GSP는 Apriori 속성을 사용하여 다음과 같이 후보 집합을 줄입니다. k 번째 패스에서 시리즈는 길이 -(k -1) 서브시퀀스 각각이 (k -1) 번째 패스에서 발견된 순차적 패턴인 경우에만 후보입니다.
데이터베이스의 새로운 스캔은 각 후보 시퀀스에 대한 지원을 수집하고 새로운 순차적 패턴 세트 Lk를 발견했습니다. . 이 세트는 다음 패스의 시드로 발전합니다. 알고리즘은 패스에서 순차 패턴이 발견되지 않거나 후보 시퀀스가 생성되지 않은 경우 제거합니다.
Apriori와 같은 순차 패턴 마이닝 기술(후보 생성 및 테스트 기반)은 서열 데이터베이스를 수직 데이터 형식으로 측정하여 분석할 수도 있습니다. 수직 데이터 형식에서 데이터베이스는 (itemset:(sequence_ID, event_ID)) 형식의 튜플 집합으로 바뀝니다.
이벤트 식별자는 시퀀스 내에서 타임스탬프로 제공됩니다. 시퀀스에서 i번째 항목 집합(또는 이벤트)의 event_ID는 i입니다. 항목 집합은 하나 이상의 순서로 나타날 수 있습니다. (시퀀스 ID, 이벤트 ID) 세트는 주어진 itemset에 대해 결합하여 itemset의 ID_list를 형성합니다.