데이터 마이닝의 Apriori 알고리즘 : 예제를 사용한 구현

apriori algorithm data mining

데이터 마이닝에서 자주 발생하는 항목 집합을 찾기위한 Apriori 알고리즘에 대한 심층 자습서. 이 튜토리얼은 Apriori의 단계와 작동 방식을 설명합니다.

이것에 데이터 마이닝 튜토리얼 시리즈 , 우리는 의사 결정 트리 알고리즘 이전 튜토리얼에서.

데이터 마이닝에는 연관, 상관, 분류 및 클러스터링과 같은 여러 가지 방법이 있습니다.

경험이 풍부한 웹 서비스 인터뷰 질문

이 튜토리얼은 주로 연관 규칙을 사용한 마이닝에 중점을 둡니다. 연관 규칙에 따라 테이블에서 함께 발생하는 항목 또는 속성 세트를 식별합니다.

학습 내용 :

• 아이템 셋이란?
  • 자주 사용하는 항목 집합은 무엇입니까?
  • FPM (Frequent Pattern Mining)
  • 협회 규칙
• 왜 빈번한 아이템 셋 마이닝인가?
  • Apriori 알고리즘 – 빈번한 패턴 알고리즘
    • Apriori의 단계
    • 장점
    • 단점
• Apriori 효율성을 개선하는 방법
• Apriori 알고리즘의 응용
• 결론
  • 추천 도서

아이템 셋이란?

항목 집합을 함께 항목 집합이라고합니다. 항목 집합에 k- 항목이 있으면이를 k- 항목 집합이라고합니다. 항목 세트는 둘 이상의 항목으로 구성됩니다. 자주 발생하는 항목 집합을 자주 발생하는 항목 집합이라고합니다. 따라서 빈번한 항목 집합 마이닝은 자주 함께 발생하는 항목을 식별하는 데이터 마이닝 기술입니다.

예를 들어 , 빵과 버터, 노트북 및 바이러스 백신 소프트웨어 등

자주 사용하는 항목 집합은 무엇입니까?

지원 및 신뢰에 대한 최소 임계 값을 충족하는 항목 집합을 자주 호출합니다. 지원은 단일 거래로 함께 구매 한 항목의 거래를 보여줍니다. 신뢰도는 항목이 차례로 구매되는 거래를 보여줍니다.

빈번한 항목 집합 마이닝 방법의 경우 최소 임계 값 지원 및 신뢰 요구 사항을 충족하는 트랜잭션 만 고려합니다. 이러한 마이닝 알고리즘의 통찰력은 많은 이점, 비용 절감 및 향상된 경쟁 우위를 제공합니다.

데이터를 마이닝하는 데 걸리는 시간과 빈번한 마이닝을위한 데이터 볼륨이 있습니다. 빈번한 마이닝 알고리즘은 짧은 시간에 적은 메모리 소비로 항목 세트의 숨겨진 패턴을 마이닝하는 효율적인 알고리즘입니다.

FPM (Frequent Pattern Mining)

빈번한 패턴 마이닝 알고리즘은 데이터 세트에서 서로 다른 항목 간의 관계를 발견하기위한 데이터 마이닝의 가장 중요한 기술 중 하나입니다. 이러한 관계는 연관 규칙의 형식으로 표시됩니다. 데이터의 불규칙성을 찾는 데 도움이됩니다.

FPM은 데이터 분석, 소프트웨어 버그, 교차 마케팅, 판매 캠페인 분석, 시장 바구니 분석 등의 분야에서 많은 응용 프로그램을 가지고 있습니다.

Apriori를 통해 발견 된 빈번한 항목 집합은 데이터 마이닝 작업에 많은 응용 프로그램을 가지고 있습니다. 데이터베이스에서 흥미로운 패턴 찾기, 시퀀스 찾기 및 연관 규칙 마이닝과 같은 작업이 가장 중요합니다.

연결 규칙은 슈퍼마켓 거래 데이터, 즉 구매 한 제품에 대한 고객 행동을 조사하기 위해 적용됩니다. 연관 규칙은 항목이 함께 구매되는 빈도를 설명합니다.

협회 규칙

연관 규칙 마이닝은 다음과 같이 정의됩니다.

“I = {…}는 항목이라고하는 'n'이진 속성 집합입니다. D = {….}는 데이터베이스라는 트랜잭션의 집합입니다. D의 각 트랜잭션은 고유 한 트랜잭션 ID를 가지며 I에있는 항목의 하위 집합을 포함합니다. 규칙은 X-> Y 양식의 의미로 정의됩니다. 여기서 X, Y? I 및 X? Y = ?. 항목 X와 Y의 집합은 각각 규칙의 선행 및 결과라고합니다.”

연관 규칙 학습은 대형 데이터베이스에서 속성 간의 관계를 찾는 데 사용됩니다. 연결 규칙, A => B는 일련의 트랜잭션에 대해 '형식이됩니다.'항목 집합 A의 일부 값은 최소 지원 및 신뢰가 충족되는 조건에서 항목 집합 B의 값을 결정합니다.

지원 및 신뢰는 다음 예제로 나타낼 수 있습니다.

위의 문은 연결 규칙의 예입니다. 이는 빵과 버터를 함께 구입 한 거래가 2 %이고 버터와 빵을 구입 한 고객의 60 %가 있음을 의미합니다.

항목 세트 A 및 B에 대한 지원 및 신뢰는 다음 공식으로 표시됩니다.

연관 규칙 마이닝은 2 단계로 구성됩니다.

1. 자주 사용하는 항목 세트를 모두 찾으십시오.
2. 위의 빈번한 항목 집합에서 연결 규칙을 생성합니다.

왜 빈번한 아이템 셋 마이닝인가?

빈번한 항목 집합 또는 패턴 마이닝은 빈번한 패턴, 순차 패턴 및 기타 많은 데이터 마이닝 작업을 기반으로하는 마이닝 연관 규칙, 상관 관계 및 그래프 패턴 제약 조건에서 광범위하게 적용되기 때문에 널리 사용됩니다.

Apriori 알고리즘 – 빈번한 패턴 알고리즘

Apriori 알고리즘은 빈번한 아이템 세트 마이닝을 위해 제안 된 최초의 알고리즘입니다. 나중에 R Agarwal과 R Srikant에 의해 개선되어 Apriori로 알려지게되었습니다. 이 알고리즘은 'join'과 'prune'의 두 단계를 사용하여 검색 공간을 줄입니다. 가장 빈번한 항목 집합을 검색하는 반복적 인 접근 방식입니다.

Apriori 말한다 :

항목 I가 자주 발생하지 않을 확률은 다음과 같습니다.

• 피 (I)
• P (I + A)
• 항목 세트의 값이 최소 지원보다 작은 경우 모든 상위 세트도 최소 지원 아래로 떨어 지므로 무시할 수 있습니다. 이 속성을 Antimonotone 속성이라고합니다.

데이터 마이닝의 Apriori 알고리즘에서 따르는 단계는 다음과 같습니다.

1. 가입 단계 :이 단계는 각 항목을 자신과 결합하여 K-itemsets에서 (K + 1) 항목 집합을 생성합니다.
2. 단계 정리 :이 단계는 데이터베이스의 각 항목 수를 스캔합니다. 후보 항목이 최소 지원을 충족하지 못하는 경우 드물게 간주되어 제거됩니다. 이 단계는 후보 항목 집합의 크기를 줄이기 위해 수행됩니다.

Apriori의 단계

Apriori 알고리즘은 주어진 데이터베이스에서 가장 빈번한 항목 집합을 찾기 위해 따라야 할 일련의 단계입니다. 이 데이터 마이닝 기술은 가장 빈번한 항목 집합이 달성 될 때까지 조인 및 정리 단계를 반복적으로 따릅니다. 최소 지원 임계 값이 문제에 제공되거나 사용자가 가정합니다.

#1) 알고리즘의 첫 번째 반복에서 각 항목은 1-itemsets 후보로 간주됩니다. 알고리즘은 각 항목의 발생 횟수를 계산합니다.

#두) 최소한의 지원, min_sup (예 : 2)이 있어야합니다. 1 세트 – 발생이 최소 한도를 만족하는 항목 세트가 결정됩니다. min_sup보다 크거나 같은 후보 만 다음 반복을 위해 앞당겨지고 나머지는 정리됩니다.

#삼) 다음으로, min_sup이있는 2-itemset 빈번한 항목이 발견됩니다. 이를 위해 조인 단계에서는 항목을 자신과 결합하여 2 개의 그룹을 구성하여 2 개의 항목 집합을 생성합니다.

# 4) 2-itemset 후보는 min-sup 임계 값을 사용하여 정리됩니다. 이제 테이블에는 min-sup 만있는 2 개의 –itemset이 있습니다.

# 5) 다음 반복은 join 및 prune 단계를 사용하여 3 개의 –itemsets를 형성합니다. 이 반복은 3 개 항목 집합의 하위 집합, 즉 각 그룹의 2 개 –itemset 하위 집합이 min_sup에 속하는 안티 모노톤 속성을 따릅니다. 모든 2-itemset 하위 집합이 빈번하면 상위 집합이 빈번하게되고 그렇지 않으면 정리됩니다.

# 6) 다음 단계는 3-itemset을 자신과 결합하여 4-itemset을 만들고 하위 집합이 min_sup 기준을 충족하지 않으면 잘라냅니다. 가장 빈번한 항목 집합이 달성되면 알고리즘이 중지됩니다.

(영상 출처 )

Apriori의 예 :지원 임계 값 = 50 %, 신뢰도 = 60 %

1 번 테이블

해결책:

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

1. 각 항목의 수

스크럼 팀이 제공하는 비즈니스 가치에 대한 책임은 누구에게 있습니까?

표 -2

2. 정리 단계 : 표 -2 I5 항목이 min_sup = 3을 충족하지 않아 삭제되었음을 보여줍니다. I1, I2, I3, I4 만 min_sup 개수를 충족합니다.

표 -3

삼. 가입 단계 : 양식 2-itemset. 에서 1 번 테이블 2-itemset의 발생을 찾으십시오.

표 -4

네. 정리 단계 : 표 -4 항목 세트 {I1, I4} 및 {I3, I4}가 min_sup을 충족하지 않아 삭제되었음을 표시합니다.

표 -5

5. 가입 및 정리 단계 : 양식 3 개 항목 세트. 로부터 1 번 테이블 3-itemset의 발생을 찾으십시오. 에서 표 -5 , min_sup을 지원하는 2-itemset 서브 세트를 찾으십시오.

항목 세트 {I1, I2, I3} 하위 집합, {I1, I2}, {I1, I3}, {I2, I3}이 표 -5 따라서 {I1, I2, I3}이 자주 발생합니다.

항목 세트 {I1, I2, I4} 하위 집합에 대해 볼 수 있습니다. {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4}는 자주 발생하지 않습니다. 표 -5 따라서 {I1, I2, I4}는 빈번하지 않으므로 삭제됩니다.

표 -6

{I1, I2, I3} 만 자주 발생 .

6. 연결 규칙 생성 : 연관성 위에서 발견 된 빈번한 항목 세트에서 다음이 될 수 있습니다.

{I1, I2} => {I3}

신뢰도 = {I1, I2, I3} 지원 / {I1, I2} 지원 = (3/4) * 100 = 75 %

{I1, I3} => {I2}

신뢰도 = {I1, I2, I3} 지원 / {I1, I3} 지원 = (3/3) * 100 = 100 %

{I2, I3} => {I1}

신뢰도 = {I1, I2, I3} 지원 / {I2, I3} 지원 = (3/4) * 100 = 75 %

{I1} => {I2, I3}

신뢰도 = {I1, I2, I3} 지원 / {I1} 지원 = (3/4) * 100 = 75 %

{I2} => {I1, I3}

신뢰 = 지원 {I1, I2, I3} / 지원 {I2 = (3/5) * 100 = 60 %

{I3} => {I1, I2}

신뢰도 = {I1, I2, I3} 지원 / {I3} 지원 = (3/4) * 100 = 75 %

이는 최소 신뢰 임계 값이 60 % 인 경우 위의 모든 연관 규칙이 강력 함을 보여줍니다.

Apriori 알고리즘 : 의사 코드

C : 크기 k의 후보 항목 세트

L : 크기 k의 빈번한 항목 집합

(영상 출처 )

장점

1. 이해하기 쉬운 알고리즘
2. 조인 및 정리 단계는 대규모 데이터베이스의 대규모 항목 집합에서 쉽게 구현할 수 있습니다.

단점

1. 항목 집합이 매우 크고 최소 지원이 매우 낮게 유지되는 경우 높은 계산이 필요합니다.
2. 전체 데이터베이스를 스캔해야합니다.

Apriori 효율성을 개선하는 방법

알고리즘의 효율성을 향상시키기 위해 많은 방법을 사용할 수 있습니다.

1. 해시 기반 기술 : 이 메서드는 k-itemsets 및 해당 개수를 생성하기 위해 해시 테이블이라는 해시 기반 구조를 사용합니다. 테이블 생성을 위해 해시 함수를 사용합니다.
2. 거래 감소 : 이 방법은 반복에서 스캔하는 트랜잭션 수를 줄입니다. 빈번한 항목이없는 거래는 표시되거나 제거됩니다.
3. 분할 : 이 방법은 빈번한 항목 세트를 마이닝하기 위해 두 개의 데이터베이스 스캔 만 필요합니다. 데이터베이스에서 항목 집합이 잠재적으로 자주 발생하려면 데이터베이스의 파티션 중 하나 이상에서 자주 발생해야합니다.
4. 견본 추출: 이 방법은 데이터베이스 D에서 무작위 샘플 S를 선택한 다음 S에서 빈번한 항목 집합을 검색합니다. 전역 빈번한 항목 집합이 손실 될 수 있습니다. 이는 min_sup을 낮추면 줄일 수 있습니다.
5. 동적 항목 세트 계산 : 이 기술은 데이터베이스를 스캔하는 동안 데이터베이스의 표시된 시작 지점에 새 후보 항목 집합을 추가 할 수 있습니다.

Apriori 알고리즘의 응용

Apriori가 사용되는 일부 필드 :

1. 교육 분야에서 : 특성 및 전문성을 통해 입학 한 학생의 데이터 마이닝에서 연관 규칙을 추출합니다.
2. 의료 분야 : 예를 들어 환자의 데이터베이스 분석.
3. 임업 : 산불 데이터를 이용한 산불 발생 확률 및 강도 분석
4. Apriori는 Amazon과 같은 많은 회사에서 추천 시스템 자동 완성 기능을 위해 Google에서 제공합니다.

결론

Apriori 알고리즘은 데이터베이스를 한 번만 스캔하는 효율적인 알고리즘입니다.

데이터베이스의 항목 집합 크기를 상당히 줄여서 좋은 성능을 제공합니다. 따라서 데이터 마이닝은 의사 결정 과정에서 소비자와 산업을 더 잘 지원합니다.

다가오는 튜토리얼을 확인하여 빈번한 패턴 성장 알고리즘에 대해 자세히 알아보세요 !!

이전 튜토리얼 | NEXT 튜토리얼

추천 도서

• 데이터 마이닝 기술 : 알고리즘, 방법 및 최고의 데이터 마이닝 도구
• 데이터 마이닝 : 데이터 분석의 프로세스, 기술 및 주요 문제
• 데이터 마이닝 예 : 데이터 마이닝의 가장 일반적인 애플리케이션 2021
• 데이터 마이닝의 의사 결정 트리 알고리즘 예제
• 데이터 마이닝 프로세스 : 관련된 모델, 프로세스 단계 및 과제
• 데이터 마이닝 대 기계 학습 대 인공 지능 대 딥 러닝
• 최고의 무료 데이터 마이닝 도구 Top 15 : 가장 포괄적 인 목록
• 사용자 정의 변수를 사용한 JMeter 데이터 매개 변수화