아프리오리 알고리즘

Apriori는^[1] 관계형 데이터베이스를 통한 빈번한 항목 집합 마이닝 및 연결 규칙 학습을 위한 알고리즘입니다.이러한 항목 집합이 데이터베이스에 자주 나타나면 데이터베이스에서 자주 개별 항목을 식별하고 점점 더 큰 항목 집합으로 확장합니다.Apriori에 의해 결정되는 빈번한 항목 세트는 데이터베이스의 일반적인 경향을 강조하는 관련 규칙을 결정하기 위해 사용할 수 있습니다.이것은 마켓 바스켓 분석 등의 도메인에서 응용 프로그램을 가지고 있습니다.

개요

Apriori 알고리즘은 1994년 Agrawal과 Srikant에 의해 제안되었다.Apriori는 트랜잭션을 포함하는 데이터베이스(예: 고객이 구매한 아이템의 컬렉션, 웹사이트의 빈번한 방문 또는 IP^[2] 주소)에서 작동하도록 설계되었습니다.다른 알고리즘은 트랜잭션(Winepi 및 Minepi)이 없거나 타임스탬프가 없는 데이터(DNA 시퀀스)에서 관련 규칙을 찾기 위해 설계되었습니다.각 트랜잭션은 항목 집합(항목 집합)으로 표시됩니다. $임계값$ C {\ $displaystyle$ C $C$ 가 지정되면 Apriori 알고리즘은 데이터베이스 내의 $최소$ C {\ $displaystyle$ C $}$ 트랜잭션의 $C$ 서브셋인 항목 세트를 식별합니다.

Apriori는 "상향식" 접근방식을 사용합니다.이 접근방식은 빈번한 서브셋을 한 번에 한 항목씩 확장하고(후보 생성으로 알려진 단계), 후보 그룹을 데이터에 대해 테스트합니다.이 알고리즘은 정상적인 확장이 더 이상 발견되지 않으면 종료됩니다.

Apriori는 너비 우선 검색과 해시 트리 구조를 사용하여 후보 항목 세트를 효율적으로 계산합니다. $k-1$ - $k-1$ 의 항목 $집합$ 에서 k $\style$ k $\$ $displaystyle$ k $\$ 의 후보 항목 집합을 생성한 다음 하위 패턴이 자주 없는 후보를 제거합니다.아래 닫힘 보조법에 따르면 후보 세트에는 $\displaystyle$ k $}$ 길이의 $k$ 항목 세트가 모두 포함되어 있습니다.그런 다음 트랜잭션 데이터베이스를 검색하여 후보 간의 빈번한 항목 집합을 결정합니다.

알고리즘의 의사 코드는 트랜잭션 $데이터베이스$ T(\ $displaystyle$ T $T$ 에 대해 다음과 같습니다.지원 $\varepsilon$ 은 $"\displaystyle\varepsilon$ 입니다.다만 $,$ T(\ $displaystyle$ T $)$ 는 멀티셋인 것에 주의해 주세요. $C_{k}$ k $(\$ 는 $C_{k}$ 레벨k(\ $displaystyle$ k $k$ 의 후보 세트입니다.각 단계에서 알고리즘은 이전 레벨의 큰 항목 세트로부터 후보 세트를 생성하는 것으로 간주되며, 하향 닫힘에 대한 설명을 듣습니다. $\mathrm {count} [c]$ $\mathrm {count} [c]$ $\mathrm {count} [c]$ n t $\mathrm {count} [c]$ [ $]{$ $display$ style \ $mathrm { count$ }[ $c$ ]}는 $\mathrm {count} [c]$ 후보 $집합$ c ${$ $displaystyle$ c $c$ }를 나타내는 데이터 구조의 필드에 액세스합니다.이 필드는 처음에는 0으로 간주됩니다.아래에서는 많은 세부사항을 생략합니다.일반적으로 구현에서 가장 중요한 부분은 후보 세트의 저장과 주파수 계산에 사용되는 데이터 구조입니다.

반면 Lk−1 Ck ← Apriori_gen(Lk−1, km그리고 4.9초 만)거래 t동안 TDt←{Ck에 c:c⊆지}에 Dt count[c]에 후보를 c에 ← count[c]+1Lk←{Ck에 c:count[c]≥ ε}k← k+1반환 Union(Lk)Apriori_ 비어 있는 것이 아니Apriori(T, ε)L12←{1-itemsets 큰}k←.gen(L, km그리고 4.9초 만)모든 p ⊆ L, q l L에 대해₂ result ← list(). 여기서₁ p = q₁₂, p = q_k-2, p_k-2 = q_k-1 및_k-1 p < q_k-1 c = p { { q }(L result . add ( c )의 결과를 반환합니다.

예

예 1

각 행이 트랜잭션이고 각 셀이 트랜잭션의 개별 항목인 다음 데이터베이스를 고려합니다.

알파	베타.	엡실론
알파	베타.	세타
알파	베타.	엡실론
알파	베타.	세타

이 데이터베이스에서 판별할 수 있는 관련 규칙은 다음과 같습니다.

알파가 포함된 세트의 100%는 베타도 포함합니다.
알파가 포함된 세트의 50%는 엡실론도 포함합니다.
알파 포함 세트의 50%가 세타 포함

우리는 또한 다양한 예를 통해 이것을 설명할 수 있다.

예 2

한 대형 마트가 각 품목의 재고 관리 단위(SKU)별 매출 데이터를 추적한다고 가정합니다. "버터" 또는 "빵"과 같은 각 품목은 숫자 SKU로 식별됩니다.슈퍼마켓에는 거래 데이터베이스가 있으며, 각 거래는 함께 구입한 SKU 집합입니다.

트랜잭션 데이터베이스가 다음 항목 집합으로 구성되도록 합니다.

아이템 세트
{1,2,3,4}
{1,2,4}
{1,2}
{2,3,4}
{2,3}
{3,4}
{2,4}

Apriori를 사용하여 이 데이터베이스의 빈번한 항목 집합을 결정합니다.이를 위해 데이터베이스의 최소 3개의 트랜잭션에 항목 집합이 나타나는 경우 항목 집합이 자주 발생한다고 가정합니다. 값 3은 지원 임계값입니다.

Apriori의 첫 번째 단계는 각 멤버 항목의 지원이라고 불리는 발생 횟수를 개별적으로 세는 것입니다.데이터베이스를 처음 스캔하여 다음과 같은 결과를 얻을 수 있습니다.

아이템	지지하다
{1}	3
{2}	6
{3}	4
{4}	5

크기가 1인 모든 항목 집합은 최소 3개를 지원하므로 모두 자주 사용됩니다.

다음 단계에서는 자주 사용되는 항목의 모든 쌍 목록을 생성합니다.

예를 들어 쌍 {1,2}과(와) 관련하여 예제 2의 첫 번째 표에는 항목 1과 2가 세 개의 항목 집합에 함께 표시되어 있으므로 항목 {1,2}은(는) 세 개의 항목을 지원합니다.

아이템	지지하다
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

{1,2}, {2,3}, {2,4} 및 {3,4} 쌍이 모두 최소 지원인 3을 충족하거나 초과하므로 자주 사용됩니다.{1,3} 및 {1,4} 쌍이 없습니다.이제 {1,3} 및 {1,4}이(가) 자주 발생하지 않으므로 {1,3} 또는 {1,4}을(를) 포함하는 더 큰 집합은 자주 발생할 수 없습니다.이렇게 하면 세트를 플루닝할 수 있습니다.데이터베이스에서 빈번한 트리플을 찾습니다만, 다음의 2개의 페어 중 하나를 포함한 트리플은 이미 모두 제외할 수 있습니다.

아이템	지지하다
{2,3,4}	2

이 예에서는 자주 세쌍둥이가 없습니다.{2,3,4}이(가) 최소 임계값보다 낮으며, 나머지 세쌍은 이미 임계값보다 낮은 슈퍼 세트이기 때문에 제외되었습니다.

따라서 데이터베이스의 빈번한 항목 집합을 결정하고 일부 항목은 하위 집합 중 하나가 이미 임계값보다 낮은 것으로 알려져 있었기 때문에 어떻게 계산되지 않았는지 설명하였다.

제한 사항

Apriori는 역사적으로 중요하지만, 다른 알고리즘을 양산한 수많은 비효율성 또는 트레이드오프에 시달리고 있습니다.후보 생성은 다수의 서브셋을 생성합니다(알고리즘은 데이터베이스의 각 스캔 전에 가능한 한 많은 서브셋을 사용하여 후보 세트를 로드하려고 시도합니다).상향식 부분 집합 탐색(기본적으로 부분 집합 격자의 너비 우선 통과)은 적절한 부분 집합의 $2^{|S|}-1$ - 1 $(\displaystyle 2$ ^{ S }- $1)$ 후에만 $2^{|S|}-1$ 최대 부분 집합 S를 찾는다.

알고리즘이 데이터베이스를 너무 많이 검색하므로 전체 성능이 저하됩니다.따라서 알고리즘은 데이터베이스가 메모리에 영속적으로 존재하는 것으로 가정합니다.

또한 이 알고리즘은 시간과 공간의 복잡도가 매우 $O\left(2^{|D|}\right)$ ( 2 $O\left(2^{|D|}\right)$ ) \ $displaystyle$ O \ $left$ ( $2$ ^ { D $O\left(2^{|D|}\right)$ } \ $right$ ) $O\left(2^{|D|}\right)$ 。 $|D|$ { $displaystyle$ D $}$ 는 $|D|$ 데이터베이스에 존재하는 수평 폭(항목의 총수)입니다.

Max-Miner와^[3] 같은 이후 알고리즘은 하위 집합을 열거하지 않고 최대 빈도의 항목 집합을 식별하려고 하며, 순전히 상향식 접근 방식이 아닌 검색 공간에서 "점프"를 수행합니다.

레퍼런스

^ Rakesh Agrawal 및 Ramakrishnan Srikant Fast 알고리즘으로 광업 협회 규칙을 정의합니다.제20회 초대규모 데이터베이스 국제회의의 진행, VLDB, 487-499페이지, 칠레 산티아고, 1994년 9월.
^ IP 주소 매칭의 배후에 있는 데이터 과학 2018년 9월 6일 deductive.com에서 2018년 9월 7일을 검색했습니다.
^ Bayardo Jr, Roberto J. (1998). "Efficiently mining long patterns from databases" (PDF). ACM SIGMOD Record. 27 (2).

외부 링크

GUI를 갖춘 GPL Java 어소시에이션 규칙 마이닝 애플리케이션인 ARtool은 빈번한 패턴 검출 및 어소시에이션 규칙 추출을 위한 여러 알고리즘 구현을 제공합니다(Apriori 포함).
SPMF는 Apriori Close, UApriori, Apriori Inverse, Apriori Rare, MSApriori, Apriori 등의 Java 오픈 소스 구현을 제공합니다.TID 및 FPGrowth 및 LCM 등의 보다 효율적인 알고리즘.
Christian Borgelt는 Apriori와 다른 많은 빈번한 패턴 마이닝 알고리즘(Eclat, FPGrowth 등)을 위한 C 구현을 제공합니다.이 코드는 MIT 라이선스에 따라 무료 소프트웨어로 배포됩니다.
R 패키지 규칙에는 Apriori 및 Eclat와 트랜잭션 데이터 및 패턴을 표현, 조작 및 분석하기 위한 인프라가 포함됩니다.
Efficient-Apriori는 원본 문서에서 설명한 대로 알고리즘을 구현한 Python 패키지입니다.

[apriori-1] Rakesh Agrawal 및 Ramakrishnan Srikant Fast 알고리즘으로 광업 협회 규칙을 정의합니다.제20회 초대규모 데이터베이스 국제회의의 진행, VLDB, 487-499페이지, 칠레 산티아고, 1994년 9월.

[2] IP 주소 매칭의 배후에 있는 데이터 과학 2018년 9월 6일 deductive.com에서 2018년 9월 7일을 검색했습니다.

[3] Bayardo Jr, Roberto J. (1998). "Efficiently mining long patterns from databases" (PDF). ACM SIGMOD Record. 27 (2).

[1]

[2]

[3]

Search

아프리오리 알고리즘

네임스페이스

더

목차

개요

예

예 1

예 2

제한 사항

레퍼런스

외부 링크