GSP 알고리즘

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : 'GSP 알고리즘'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2007년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

GSP 알고리즘(Generalized Sequential Pattern Algorithm)은 시퀀스마이닝에 사용되는 알고리즘입니다.시퀀스 마이닝 문제를 해결하기 위한 알고리즘은 대부분 apriori(레벨 단위) 알고리즘을 기반으로 합니다.수준별 패러다임을 사용하는 한 가지 방법은 먼저 모든 빈번한 항목을 수준별 방식으로 발견하는 것입니다.이는 단순히 데이터베이스에 있는 모든 싱글톤 요소의 발생 횟수를 세는 것을 의미합니다.그런 다음 빈번하지 않은 항목을 제거하여 트랜잭션을 필터링합니다.이 단계가 끝나면 각 트랜잭션은 원래 포함된 빈번한 요소로만 구성됩니다.이 변경된 데이터베이스는 GSP 알고리즘에 대한 입력이 됩니다.이 프로세스를 수행하려면 데이터베이스 전체를 한 번 통과해야 합니다.

GSP 알고리즘은 여러 데이터베이스를 통과시킵니다.첫 번째 패스에서는 모든 단일 항목(1-시퀀스)이 카운트됩니다.빈도의 항목으로부터 후보 2 시퀀스의 세트를 형성해, 그 빈도를 식별하기 위한 다른 패스를 실시한다.빈도가 높은 2-시퀀스는 후보 3-시퀀스를 생성하는 데 사용되며, 더 이상 빈도가 높은 시퀀스가 발견되지 않을 때까지 이 과정이 반복됩니다.알고리즘에는 크게 두 가지 단계가 있습니다.

• 후보 세대빈도(k-1)-빈도_k-1 시퀀스 F의 집합에서 F(k-1)를 결합함으로써 다음 패스 후보가 생성된다.프루닝 단계에서는 적어도 1개의 시퀀스가 빈번하지 않은 시퀀스를 제거합니다.
• 카운팅을 서포트일반적으로 해시 트리 기반 검색은 효율적인 지원 카운트를 위해 사용됩니다.마지막으로 최대가 아닌 빈도의 시퀀스를 제거한다.

알고리즘.

F1 = 빈번한 1-시퀀스 k=2의 집합, F != Null일 때 실행k-1; 후보 집합k C 생성(후보 k-supidate 집합);데이터베이스의 모든 입력 시퀀스에 대해 D는 주파수가 임계값을 초과하도록 End do Fk = {ak ≤ C를 지원하는 경우 C에 있는k 모든 a의 증분 카운트를 수행합니다. k = k+1; End do Result = 모든 빈도 시퀀스의 집합은 모든k F의 합집합입니다.

위의 알고리즘은 Apriori 알고리즘과 비슷합니다.그러나 한 가지 주요 차이점은 후보 집합의 생성입니다.다음과 같이 가정합니다.

A → B 및 A → C

두 가지 빈도가 있습니다.이러한 시퀀스에 관련된 항목은 각각 (A, B)와 (A, C)이다.일반적인 Apriori 스타일의 후보 세대는 (A, B, C)를 3개의 항목으로 제공하지만, 이 맥락에서 우리는 위의 2개의 시퀀스를 결합함으로써 다음과 같은 3개의 시퀀스를 얻는다.

A → B → C, A → C → B 및 A → BC

후보 세대 단계에서는 이를 고려합니다.GSP 알고리즘은 빈번한 시퀀스를 검출하여 시퀀스 요소 간의 최대 간격 및 최소 간격 등의 시간 제약을 허용합니다.또한, 다른 사건에서 발생하더라도 항목이 동일한 사건에 속하는 것으로 관측되는 시간 간격의 슬라이딩 윈도우 개념을 지원한다.

「 」를 참조해 주세요.

• 시퀀스 마이닝

레퍼런스

• R. 스리칸트와 R.아그라왈, 1996년마이닝 시퀀셜 패턴: 일반화와 성능 향상.제5회 데이터베이스 테크놀로지 확장에 관한 국제회의의 속행:데이터베이스 테크놀로지의 진보(EDBT '96) Peter M. G. Apers, Mokrane Bouzeghoub 및 Georges Gardarin(Ed.Springer-Verlag, 런던, 영국, 영국, 3-17.
• .mw-parser-output cite.citation{font-style:상속을 하다;word-wrap:break-word}.mw-parser-output .citation q{인용:")"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output.id-lock-freea,.mw-parser-output .citation .cs1-lock-free{.배경:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9pxno-repeat}.mw-parser-output .id-lock-limiteda,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limiteda,.mw-parser-output .citation .cs1-lock-registration{.배경:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9pxno-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription{.배경:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9pxno-repeat}.mw-parser-output{배경 .cs1-ws-icon:linear-gradient(transparent,transparent),url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1emcenter/12pxno-repeat}.mw.-parser-output .cs1-code{색:상속을 하다;배경:상속을 하다;국경 아무 것도 없고 패딩: 물려받다}.mw-parser-output .cs1-hidden-error{디스플레이:아무도, 색:#d33}.mw-parser-output .cs1-visible-error{색:#d33}.mw-parser-output .cs1-maint{디스플레이:아무도, 색:#3a3, margin-left:0.3em}.mw-parser-output .cs1-format{:95%font-size}.mw-parser-output .cs1-kern-left{.Padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:상속}Pujari, 아룬 K.(2001년).데이터 마이닝 기법. 유니버시티 프레스 ISBN 81-7371-380-4. (256-260페이지), 256페이지, 구글 북스
• 자키, M.J. 머신러닝(2001) 42:31.

외부 링크

• SPMF에는 GSP 알고리즘과 PrefixSpan, SPADE, 스팸, ClaSP, CloSpan 및 BIDE의 오픈소스 구현이 포함됩니다.