데이터 마이닝의 FP (Frequent Pattern) 성장 알고리즘

frequent pattern growth algorithm data mining

FP 트리 형태의 데이터베이스를 나타내는 빈번한 패턴 성장 알고리즘에 대한 자세한 자습서. FP 성장 대 Apriori 비교 포함 :

Apriori 알고리즘 이전 튜토리얼에서 자세히 설명했습니다. 이 튜토리얼에서는 빈번한 패턴 성장에 대해 알아 봅니다. FP 성장은 빈번한 아이템 세트를 채굴하는 방법입니다.

자동화 된 테스트 스크립트 작성 방법

우리 모두 알다시피, Apriori는 항목 집합을 생성하고 가장 빈번한 항목 집합을 발견하는 데 초점을 맞춘 빈번한 패턴 마이닝 알고리즘입니다. 데이터베이스의 항목 집합 크기를 크게 줄이지 만 Apriori에는 자체 단점도 있습니다.

우리를 통해 읽으십시오 전체 데이터 마이닝 교육 시리즈 개념에 대한 완전한 지식을 얻으려면.

학습 내용 :

• Apriori 알고리즘의 단점
• 빈번한 패턴 성장 알고리즘
• FP 트리
• 빈번한 패턴 알고리즘 단계
• FP- 성장 알고리즘의 예
• FP 성장 알고리즘의 장점
• FP-Growth 알고리즘의 단점
• FP 성장 vs Apriori
• 광택
• 결론
• 추천 도서

Apriori 알고리즘의 단점

1. Apriori를 사용하려면 후보 항목 집합을 생성해야합니다. 데이터베이스의 항목 집합이 큰 경우 이러한 항목 집합이 많을 수 있습니다.
2. Apriori는 생성 된 각 항목 세트의 지원을 확인하기 위해 데이터베이스를 여러 번 스캔해야하므로 높은 비용이 발생합니다.

이러한 단점은 FP 성장 알고리즘을 사용하여 극복 할 수 있습니다.

빈번한 패턴 성장 알고리즘

이 알고리즘은 Apriori 방법을 개선 한 것입니다. 후보 생성없이 빈번한 패턴이 생성됩니다. FP 성장 알고리즘은 빈번한 패턴 트리 또는 FP 트리라는 트리 형태의 데이터베이스를 나타냅니다.

이 트리 구조는 항목 집합 간의 연결을 유지합니다. 데이터베이스는 하나의 빈번한 항목을 사용하여 조각화됩니다. 이 조각난 부분을 '패턴 조각'이라고합니다. 이러한 조각난 패턴의 항목 집합이 분석됩니다. 따라서이 방법을 사용하면 빈번한 항목 집합에 대한 검색이 비교적 줄어 듭니다.

FP 트리

Frequent Pattern Tree는 데이터베이스의 초기 항목 집합으로 만들어진 트리와 같은 구조입니다. FP 트리의 목적은 가장 빈번한 패턴을 채굴하는 것입니다. FP 트리의 각 노드는 항목 세트의 항목을 나타냅니다.

루트 노드는 null을 나타내고 하위 노드는 항목 집합을 나타냅니다. 항목 집합 인 하위 노드와 다른 항목 집합과의 연결은 트리를 형성하는 동안 유지됩니다.

빈번한 패턴 알고리즘 단계

빈번한 패턴 성장 방법을 사용하면 후보 생성없이 빈번한 패턴을 찾을 수 있습니다.

빈번한 패턴 성장 알고리즘을 사용하여 빈번한 패턴을 채굴하는 단계를 살펴 보겠습니다.

#1) 첫 번째 단계는 데이터베이스를 스캔하여 데이터베이스에서 항목 세트의 발생을 찾는 것입니다. 이 단계는 Apriori의 첫 번째 단계와 동일합니다. 데이터베이스에있는 1-itemset의 수를 1-itemset의 지원 수 또는 빈도라고합니다.

#두) 두 번째 단계는 FP 트리를 구성하는 것입니다. 이를 위해 나무의 뿌리를 만듭니다. 루트는 널로 표시됩니다.

#삼) 다음 단계는 데이터베이스를 다시 스캔하고 트랜잭션을 검사하는 것입니다. 첫 번째 트랜잭션을 조사하고 항목 세트를 찾으십시오. 최대 개수가있는 항목 집합이 맨 위에 표시되고 다음 항목 집합이 더 낮은 개수로 표시됩니다. 이는 트리의 분기가 개수의 내림차순으로 트랜잭션 항목 집합으로 구성됨을 의미합니다.

# 4) 데이터베이스의 다음 트랜잭션이 검사됩니다. 항목 세트는 개수의 내림차순으로 정렬됩니다. 이 트랜잭션의 항목 집합이 이미 다른 분기 (예 : 첫 번째 트랜잭션)에있는 경우이 트랜잭션 분기는 루트에 대한 공통 접두사를 공유합니다.

이는 공통 항목 세트가이 트랜잭션에서 다른 항목 세트의 새 노드에 연결됨을 의미합니다.

# 5) 또한 항목 집합의 개수는 트랜잭션에서 발생함에 따라 증가합니다. 공통 노드와 새 노드 수는 트랜잭션에 따라 생성되고 연결됨에 따라 1 씩 증가합니다.

# 6) 다음 단계는 생성 된 FP 트리를 채굴하는 것입니다. 이를 위해 가장 낮은 노드의 링크와 함께 가장 낮은 노드를 먼저 검사합니다. 가장 낮은 노드는 주파수 패턴 길이 1을 나타냅니다. 여기에서 FP 트리의 경로를 횡단합니다. 이 경로를 조건부 패턴 기반이라고합니다.

조건부 패턴베이스는 최하위 노드 (접미사)에서 발생하는 FP 트리의 접두사 경로로 구성된 하위 데이터베이스입니다.

# 7) 경로에있는 항목 세트 수로 구성되는 조건부 FP 트리를 구성하십시오. 임계 값 지원을 충족하는 항목 세트는 조건부 FP 트리에서 고려됩니다.

# 8) 조건부 FP 트리에서 빈번한 패턴이 생성됩니다.

FP- 성장 알고리즘의 예

지원 임계 값 = 50 %, 신뢰도 = 60 %

1 번 테이블

해결책:

지원 임계 값 = 50 % => 0.5 * 6 = 3 => min_sup = 3

1. 각 항목의 개수

표 2

최고의 컴퓨터 청소 소프트웨어는 무엇입니까

2. 항목 세트를 내림차순으로 정렬합니다.

Quickbooks POS는 얼마입니까?

표 3

3. FP 트리 구축

1. 루트 노드 널을 고려하십시오.
2. 트랜잭션 T1의 첫 번째 스캔 : I1, I2, I3에는 세 개의 항목 {I1 : 1}, {I2 : 1}, {I3 : 1}이 포함됩니다. 여기서 I2는 하위 항목으로 루트에 연결되고 I1은 I2 및 I3에 연결됩니다. I1에 연결됩니다.
3. T2 : I2, I3, I4에는 I2, I3 및 I4가 포함됩니다. 여기서 I2는 루트에 연결되고 I3은 I2에 연결되고 I4는 I3에 연결됩니다. 그러나이 분기는 이미 T1에서 사용되는 것처럼 공통적으로 I2 노드를 공유합니다.
4. I2의 개수를 1 씩 늘리고 I3은 I2에 자식으로 연결되고 I4는 I3에 자식으로 연결됩니다. 개수는 {I2 : 2}, {I3 : 1}, {I4 : 1}입니다.
5. T3 : I4, I5. 마찬가지로 I5가있는 새 분기는 자식이 만들어 질 때 I4에 연결됩니다.
6. T4 : I1, I2, I4. 시퀀스는 I2, I1 및 I4입니다. I2는 이미 루트 노드에 연결되어 있으므로 1 씩 증가합니다. 마찬가지로 I1은 T1의 I2와 이미 연결되어 있으므로 1 씩 증가하므로 {I2 : 3}, {I1 : 2}, {I4 : 1}.
7. T5 : I1, I2, I3, I5. 시퀀스는 I2, I1, I3 및 I5입니다. 따라서 {I2 : 4}, {I1 : 3}, {I3 : 2}, {I5 : 1}.
8. T6 : I1, I2, I3, I4. 시퀀스는 I2, I1, I3 및 I4입니다. 따라서 {I2 : 5}, {I1 : 4}, {I3 : 3}, {I4 1}.

4. FP-tree 채굴은 다음과 같이 요약됩니다.

1. 최하위 노드 항목 I5는 최소 지원 횟수가 없기 때문에 고려되지 않으므로 삭제됩니다.
2. 다음 하위 노드는 I4입니다. I4는 {I2, I1, I3 :, I41}, {I2, I3, I4 : 1}의 두 가지 분기에서 발생합니다. 따라서 I4를 접미사로 고려하면 접두사 경로는 {I2, I1, I3 : 1}, {I2, I3 : 1}이됩니다. 이것은 조건부 패턴 기반을 형성합니다.
3. 조건부 패턴 기반은 트랜잭션 데이터베이스로 간주되며 FP- 트리가 구성됩니다. 여기에는 {I2 : 2, I3 : 2}이 포함됩니다. I1은 최소 지원 횟수를 충족하지 않으므로 고려되지 않습니다.
4. 이 경로는 {I2, I4 : 2}, {I3, I4 : 2}, {I2, I3, I4 : 2}와 같은 빈번한 패턴의 모든 조합을 생성합니다.
5. I3의 경우 접두사 경로는 {I2, I1 : 3}, {I2 : 1}입니다. 그러면 2 노드 FP- 트리 : {I2 : 4, I1 : 3}이 생성되고 빈번한 패턴이 생성됩니다. {I2 , I3 : 4}, {I1 : I3 : 3}, {I2, I1, I3 : 3}.
6. I1의 경우 접두사 경로는 다음과 같습니다. {I2 : 4} 단일 노드 FP- 트리 : {I2 : 4}가 생성되고 빈번한 패턴이 생성됩니다 : {I2, I1 : 4}.

아래의 다이어그램은 조건부 노드 I3과 관련된 조건부 FP 트리를 보여줍니다.

FP 성장 알고리즘의 장점

1. 이 알고리즘은 각 반복에 대해 트랜잭션을 스캔하는 Apriori와 비교할 때 데이터베이스를 두 번만 스캔하면됩니다.
2. 이 알고리즘에서는 항목 페어링이 수행되지 않으므로 더 빨라집니다.
3. 데이터베이스는 메모리에 압축 버전으로 저장됩니다.
4. 길고 짧은 빈번한 패턴을 모두 채굴하는 데 효율적이고 확장 가능합니다.

FP-Growth 알고리즘의 단점

1. FP Tree는 Apriori보다 더 복잡하고 만들기가 어렵습니다.
2. 비쌀 수 있습니다.
3. 데이터베이스가 크면 알고리즘이 공유 메모리에 맞지 않을 수 있습니다.

FP 성장 vs Apriori

광택

위의 방법 인 Apriori 및 FP 성장은 수평 데이터 형식을 사용하여 빈번한 항목 집합을 채굴합니다. ECLAT는 수직 데이터 형식을 사용하여 빈번한 항목 집합을 마이닝하는 방법입니다. 수평 데이터 형식의 데이터를 수직 형식으로 변환합니다.

예를 들어,Apriori 및 FP 성장 사용 :

ECLAT의 테이블 형식은 다음과 같습니다.

이 메서드는 수직 데이터 형식으로 2-itemsets, 3 itemsets, k itemsets를 형성합니다. k를 사용하는이 프로세스는 후보 항목 세트를 찾을 수 없을 때까지 1 씩 증가합니다. diffset과 같은 일부 최적화 기술은 Apriori와 함께 사용됩니다.

이 방법은 k + 1 항목 집합의 지원을 찾기 위해 데이터베이스를 스캔 할 필요가 없기 때문에 Apriori보다 이점이 있습니다. 이는 트랜잭션 세트가 트랜잭션 (지원)에서 각 항목의 발생 횟수를 전달하기 때문입니다. 병목 현상은 집합을 교차하는 데 막대한 메모리와 계산 시간을 사용하는 트랜잭션이 많을 때 발생합니다.

결론

Apriori 알고리즘은 마이닝 연관 규칙에 사용됩니다. '빈번한 항목 집합의 비어 있지 않은 하위 집합도 빈번해야합니다'라는 원칙에 따라 작동합니다. (k-1) 항목 집합에서 k 항목 집합 후보를 형성하고 데이터베이스를 스캔하여 자주 사용되는 항목 집합을 찾습니다.

Frequent Pattern Growth Algorithm은 후보 생성없이 빈번한 패턴을 찾는 방법입니다. Apriori의 생성 및 테스트 전략을 사용하지 않고 FP 트리를 구성합니다. FP Growth 알고리즘의 초점은 항목의 경로를 분할하고 빈번한 패턴을 마이닝하는 것입니다.

데이터 마이닝 시리즈의 튜토리얼이 데이터 마이닝에 대한 지식을 풍부하게 해주기를 바랍니다 !!

이전 튜토리얼 | FIRST 튜토리얼

추천 도서

• 데이터 마이닝 기술 : 알고리즘, 방법 및 최고의 데이터 마이닝 도구
• 데이터 마이닝의 Apriori 알고리즘 : 예제를 사용한 구현
• 데이터 마이닝의 의사 결정 트리 알고리즘 예제
• 데이터 마이닝 예 : 데이터 마이닝의 가장 일반적인 애플리케이션 2021
• 데이터 마이닝 : 데이터 분석의 프로세스, 기술 및 주요 문제
• 데이터 마이닝 프로세스 : 관련된 모델, 프로세스 단계 및 과제
• CSTE 소프트웨어 테스트 인증 시험 문제 패턴
• 데이터 마이닝 대 기계 학습 대 인공 지능 대 딥 러닝