Apriori 알고리즘이란 무엇인가요?

1994년 라케시 아그라왈과 라마크리슈난 스리칸트(ibm.com 외부 링크)가 소개한 알고리즘의 이름인 'Apriori'는 알고리즘이 계산에 사용하는 빈번한 항목 집합에 대한 사전 지식(prior knowledge)을 나타냅니다. Apriori 알고리즘은 데이터에 대해 반복을 실행하여 k-항목 세트, 즉 자주 함께 발생하는 k 항목을 식별합니다. 그런 다음 k-항목 세트를 사용하여 k+1 항목 세트를 식별합니다. Apriori 알고리즘은 자주 구매되는 그룹에 항목을 추가하면 빈도가 높아지는 것이 아니라 낮아질 뿐이라는 인사이트에 기반합니다. 이 프로세스는 데이터 세트에서 항목 세트가 자주 나타나면 모든 하위 세트도 자주 나타나야 한다는 Apriori 속성에 의존합니다. 반대로, 항목 세트가 자주 나타나지 않는 것으로 확인되면 모든 상위 세트가 자주 나타나지 않는 것으로 간주됩니다.

Apriori 알고리즘은 모든 종류의 데이터 세트, 특히 트랜잭션 데이터베이스에서 생성된 데이터 세트에 적용할 수 있으며 추천 시스템을 지원하기 위한 장바구니 분석에 자주 사용됩니다. 예를 들어, 의류와 신발을 판매하는 이커머스 플랫폼에서 한 쇼핑객이 신발을 검색하고 정장용 검은색 신발을 장바구니에 추가하기로 결정했다고 가정해 보겠습니다. 그러면 쇼핑객은 인터페이스에서 양말과 같은 다른 구매 품목을 추천한다는 사실을 알게 됩니다. 이 추천 시스템이 작동하는 방식 중 하나는 고객의 구매 패턴을 학습하여 함께 구매했을 가능성이 있는 품목을 연관시키는 것입니다.

Apriori 알고리즘 사용의 가장 큰 장점 중 하나는 단순성과 적응성입니다. 그러나 Apriori 알고리즘은 대규모 데이터 세트를 처리할 때 효율적이지 않습니다. 항목 세트 후보를 생성하는 다중 반복 프로세스는 계산 비용이 많이 들고 메모리를 많이 사용할 수 있습니다. 이러한 문제를 완화하기 위해 Apriori는 종종 다른 기술과 결합됩니다.

Apriori 기능은 Python, Java, R 등 널리 사용되는 여러 프로그래밍 언어에 통합되어 있어 빈번한 항목 세트와 함께 양질의 연관 규칙을 생성하여 기존 애플리케이션이나 시스템에 쉽게 통합할 수 있습니다.

Apriori 알고리즘의 각 주요 단계는 연관 규칙을 생성하기 위해 가장 빈번한 항목 세트와 가능한 모든 상위 세트를 식별하는 것입니다.

이 알고리즘은 먼저 데이터 세트에서 빈도와 함께 1-itemsets라고도 하는 고유한 항목을 식별합니다. 그런 다음 지정된 임계값을 초과할 확률과 함께 나타나는 항목을 후보 항목 세트로 결합하고 자주 사용하지 않는 항목 세트를 필터링하여 추가 단계에서 계산 비용을 줄입니다. 빈번한 항목 세트 마이닝이라고 하는 이 프로세스를 통해 의미 있는 빈도를 가진 항목 세트만 찾습니다.

Apriori 알고리즘은 Apriori 속성을 사용하여 빈번한 항목 세트를 더 결합하여 더 큰 항목 세트를 생성합니다. 확률이 낮은 더 큰 항목 세트 조합은 정리됩니다. 이렇게 하면 검색 공간이 더 줄어들고 계산이 더 효율적으로 이루어집니다.

알고리즘은 정의된 임계값 확률을 충족하는 모든 빈번한 항목 세트가 완전히 생성될 때까지 1단계와 2단계를 반복합니다. 각 반복을 통해 항목 세트에 더욱 복잡하고 포괄적인 연관성을 생성합니다.

Apriori가 항목 세트 만든 후에는 생성된 연관성 및 관계의 강도를 조사할 수 있습니다.

Apriori 알고리즘은 지원, 신뢰도, 상승도 메트릭을 사용하여 운영 기준을 정의하고 성능 효율성을 개선합니다.

지원은 총 트랜잭션 수에 대해 트랜잭션에서 항목이 발생한 횟수의 비율로 정의됩니다. 따라서 이 메트릭은 트랜잭션에서 각 개별 항목의 발생 확률을 정의합니다. 동일한 논리를 항목 세트로 확장할 수 있습니다.

$S\left(I_A\right)=\frac{Occ\left(I_A\right)}{ToTalTransacTions}$

여기서 I_A는 A 항목이고, Occ(I_A)는 A 항목의 발생 횟수이며, S(I_A) = A 항목의 지지도입니다.

예를 들어, 소매점에서 하루 동안 2,000건의 거래 중 250건에 사과 구매가 포함될 수 있습니다. 공식을 사용하면 다음과 같습니다.

$S\left(I_{Apples}\right)=\frac{250}{2000}=0.125$

이 결과는 그날 사과를 구매했을 확률이 12.5%라는 것을 의미합니다.

Apriori 알고리즘을 적용할 때 필요한 최소 지원 임계값을 지정할 수 있습니다. 즉, 지정된 최소 지원보다 낮은 지원을 받는 항목 또는 항목 세트는 빈도가 낮은 것으로 간주됩니다.

신뢰도 메트릭은 항목 세트에서 함께 발생하는 항목이나 항목 세트의 확률을 식별합니다. 예를 들어 트랜잭션에 2개 항목이 있는 경우, 한 항목의 존재가 다른 항목으로 이어지는 것으로 간주합니다. 첫 번째 항목 또는 항목 세트는 선행 항목, 두 번째 항목 세트는 결과 항목입니다. 따라서 신뢰도는 선행과 결과 항목을 모두 가진 트랜잭션의 수, 그리고 선행 항목만 가진 트랜잭션의 수의 비율로 정의됩니다. 이 상황을 표현하면 다음과 같습니다.

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

여기서 A는 선행 항목, B는 결과 항목, C(A,B)는 A가 B로 이어질 확률을 나타냅니다.

앞의 예를 확장하여 사과와 바나나를 함께 구매한 거래가 150건 있다고 가정해 보겠습니다. 신뢰도는 다음과 같이 계산됩니다.

$C(Apples,Bananas)=\frac{150}{250}=0.6$

이 결과는 사과 구매가 바나나 구매로 이어질 확률이 60%임을 나타냅니다. 마찬가지로, 바나나에 대한 총 500건의 거래가 있다고 가정하면 바나나 구매가 사과 구매로 이어질 확률은 다음과 같이 계산됩니다.

$C(Bananas,Apples)=\frac{150}{500}=0.3$

여기서 바나나 구매가 사과 구매로 이어질 확률은 30%에 불과합니다.

신뢰도는 가능성을 측정하는 좋은 척도이지만, 항목 간의 명확한 연관성을 보장하는 것은 아닙니다. 다른 이유로 신뢰도의 값이 높을 수도 있습니다. 이러한 이유로, 연관성 규칙으로 마이닝할 때는 가능성이 낮은 연관성을 걸러내기 위해 최소 신뢰도 임계값이 적용됩니다.

상승도는 항목 A가 항목 B로 이어질 가능성이 항목 A의 가능성보다 높은 계수입니다. A와 B 사이의 연관성을 정량화하는 메트릭으로, 항목 세트의 항목 간에 실제 관계가 있는지 아니면 우연에 의해 함께 그룹화되었는지를 나타내는 데 도움이 될 수 있습니다. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


여기서 L_A,B는 항목 A가 항목 B로 연결되는 상승도이고, C_A,B는 항목 A가 항목 B로 연결되는 신뢰도이며, S_A는 항목 A에 대한 지지도를 나타냅니다.

위의 예에서 다음을 확인할 수 있습니다. 

$L(Apples,Bananas)=\frac{0.6}{0.125}=4.8$

높은 상승도 값은 사과와 바나나를 함께 구매할 가능성이 사과만 구매할 가능성보다 4.8배 높다는 것을 나타냅니다. 또한 다음과 같은 사실을 확인할 수 있습니다. 

$L(Bananas,Apples)=\frac{0.3}{0.25}=1.2$

여기서 상승도 값이 낮다는 것은 바나나 구매가 사과 구매로 이어지는 것은 우연의 일치일 수 있음을 나타냅니다.

모든 규칙에 대한 지지도와 신뢰 임계값을 계산한 다음 임계값을 충족하지 않는 규칙을 정리하기 위해 무차별 대입 접근 방식(ibm.com 외부 링크)을 적용하면 연산이 불가능할 수 있습니다. Apriori 알고리즘을 더 효율적으로 적용하기 위해 다른 연관 규칙 마이닝 기술을 함께 사용하기도 합니다. 가장 흔한 두 가지는 FP-growth 알고리즘(ibm.com 외부에 링크 있음), 메모리와 연산 제약을 줄이기 위한 변형형 FP-Max입니다. Apriori 알고리즘은 Decision Trees와 결합될 수도 있으며, 여기서 Apriori 알고리즘은 빈도 높은 항목 세트를 식별하고 Decision Trees 기술은 연관 규칙을 식별하는 데 도움이 됩니다.

Apriori 알고리즘에서 널리 사용되는 또 다른 변형은 모든 트랜잭션이 기록될 때까지 기다리지 않고 잠재적인 항목 세트를 조기에 계산하기 시작하는 동적 항목 세트 계산(DIC)(ibm.com 외부 링크)입니다. DIC는 데이터 세트를 더 작은 세그먼트로 나누고 각 세그먼트를 개별적으로 처리합니다. 이러한 데이터 분할은 알고리즘이 빈번한 항목 세트를 식별할 수 없을 때 조기 중지를 가능하게 할 뿐만 아니라, 컴퓨팅 비용을 크게 절감하는 데도 도움이 됩니다.

데이터가 이를 지원하는 경우 클러스터링 알고리즘 같은 비지도 학습 기반 인공 지능 애플리케이션에서도 Apriori 알고리즘이 유용할 수 있습니다. 이 알고리즘은 서로 별개인 것처럼 보이는 개체들 간의 관계와 연관성을 식별하여 가능한 클러스터들로 그룹화하는 데에도 도움이 됩니다.

항목 세트를 발견하고 그룹화하는 작업은 다양한 분야에서 활용됩니다. 그리고 Apriori 알고리즘은 범용성 때문에 데이터 마이너가 가장 먼저 시도하는 알고리즘으로 꼽히기도 합니다. 다양한 산업에서 흔히 사용되는 몇 가지 사용 사례를 살펴보겠습니다.

Apriori 알고리즘의 가장 일반적인 응용 분야 중 하나는 장바구니 분석을 수행하는 것입니다. 소매업체는 고객의 구매 내역을 분석하고 자주 구매하는 품목을 서로 가까이 또는 동일한 선반에 배치하여 매장 배치 방식을 최적화합니다. 전자 상거래 플랫폼은 Apriori 알고리즘을 사용하여 사용자 선호도를 기반으로 제품 기반 관계를 연구하고 구매 패턴 마이닝 분석을 통해 효율적인 고객 추천 시스템을 만듭니다. 동일한 종류의 분석을 사용하여 카탈로그에서 교육 과정을 선택하거나 보험을 선택할 때 다른 보장을 유형을 권장하는 등 서비스 구매를 최적화할 수 있습니다.

에이프리리 알고리즘은 증상과 질병 사이의 강력한 연관성 규칙을 찾아 진단의 효율성을 높이고 표적 치료 계획을 수립하는 데 사용할 수 있습니다. 예를 들어, 어떤 환자가 당뇨병에 걸릴 가능성이 높은지(ibm.com 외부 링크), 식단이나 생활 방식이 질병에 어떤 역할을 하는지(ibm.com 외부 링크) 등을 파악할 수 있습니다. 또한 약물 부작용과 관련된 요인을 파악하는 데에도 도움이 될 수 있습니다.

Apriori 알고리즘은 비트랜잭션 데이터베이스에도 적용할 수 있습니다. 데이터 분석가들은 웹 사용량 마이닝, 클릭스트림 데이터 분석, 사용자 행동 해석에 Apriori를 사용하는 경우가 많습니다.

Apriori 알고리즘의 또 다른 일반적인 응용 분야는 금융 거래에서 사기 패턴을 식별하는 것입니다. 특정 구매 패턴을 사기 가능성이 있는 것으로 식별하면 금융 기관이 신속하게 거래를 중단하거나 계좌 소유자에게 연락할 수 있습니다.