'Apriori algorithm'에 해당되는 글 1건

  1. 2016.05.21 [R 연관규칙(Association Rule) ] Apriori algorithm (14)

지난번 포스팅에서는 연관규칙(association rule)의 평가척도로서 지지도(support), 신뢰도(confidence), 향상도(lift), IS측도(Interest-Support), 교차지지도(cross support) 에 대하여 알아보았습니다.

 

이번 포스팅에서는 연관규칙 (1세대) 알고리즘으로서 Apriori algorithm 에 대해 소개하도록 하겠습니다.  알고리즘을 이해하면 컴퓨터 내부에서 무슨 일이 일어나고 있는지, 컴퓨터가 어떻게 그 많은 연산을 효율적으로 수행하는지 원리를 알 수 있습니다.

 

 

 

1) 왜 효율적인 연관규칙 탐색 알고리즘이 필요한가?

 

거래에서 나타나는 모든 항목들의 집합(item set)을 이라고 할 때, 모든 가능한 부분집합의 개수는 공집합을 제외하고 개 입니다.

 

그리고 모든 가능한 연관규칙의 개수입니다.

 

이를 그래프로 나타내면 아래와 같은데요, 가능한 부분집합의 개수나 연관규칙의 개수가 item 이 증가할 때 마다 지수적으로 증가함을 알 수 있습니다.

 

item이 5개이면 subset 개수가 31개, rule 개수가 180개가 되며, => item이 10개만 되어도 subset 개수가 1023개, rule 개수가 57002 개가 됩니다.  이렇게 지수적으로 증가하는 subset과 rule들을 연필과 종이를 가지고 일일이 계산한다는 것은 미친짓입니다.  그리고 컴퓨터로 계산한다고 해도 계산복잡도와 필요 연산량이 어마무시하게 많아져서 시간이 굉~장히 오래 걸립니다.(심하면 하루를 꼬박 넘기고, 이틀, 사흘....)  이러므로 "빠르고 효율적인 연관규칙 계산 알고리즘"과 "연관규칙 평가 측도(기준)"이 필요한 것입니다.  

 

 

 

 

 

5개의 원소 항목을 가지는 I={A, B, C, D, E} 에 대하여 가능한 모든 항목집합을 예시로 풀어보면 아래와 같습니다. 

 

 

 

 

 

2) 연관규칙 생성 전략 및 Algorithm에는 무엇이 있나?

 

부분집합의 개수가 2^k - 1 개로서 지수적으로 증가하기 때문에 모든 경우의 수에 대해 지지도를 계산하는 것이 연산량이 엄청납니다. 그래서 연산량을 줄이기 위해 아래의 3가지 전략 중의 하나를 사용합니다.

 

1) 모든 가능한 항목집합의 개수(M)를 줄이는 전략 ▶ Apriori algorithm

2) Transaction 개수(N)을 줄이는 전략 ▶ DHP algorithm

3) 비교하는 수(W)를 줄이는 전략 ▶ FP-growth algorithm

 

 

 

3) 빈발항목집합을 추출하는 Apriori algorithm 의 원리, 원칙은 무엇인가?

 

위의 3개의 알고리즘 중에서 1세대 Apriori algorithm에 대해서만 예를 들어서 설명해보겠습니다.

 

최소지지도 이상을 갖는 항목집합을 빈발항목집합(frequent item set)이라고 합니다.  모든 항목집합에 대한 지지도를 계산하는 대신에 최소 지지도 이상의 빈발항목집합만을 찾아내서 연관규칙을 계산하는 것이 Apriori algorithm의 주요 내용입니다. 

 

빈발항목집합 추출의 Apriori Principle

 

1) 한 항목집합이 빈발(frequent)하다면 이 항목집합의 모든 부분집합은 역시 빈발항목집합이다.
(frequent item sets -> next step) 

 

2) 한 항목집합이 비비발(infrequent)하다면 이 항목집합을 포함하는 모든 집합은 비빈발항목집합이다. (superset -> pruning)

 

 

Apriori Pruning Principle


If there is any itemset which is infrequent, its superset should not be generated/tested
(Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94)

 

위의 Apriori Pruning Principal 을 도식화한 예시는 아래와 같습니다.  아래 예시 그림처럼 {A, B} item set이 비빈발항목(infrequent item set)이면 그 및에 {A, B}를 포함해서 줄줄이 딸린 {A, B, C}, {A, B, D}, {A, B, E}, {A, B, C, D}, {A, B, C, E}, {A, B, D, E}, {A, B, C, D, E}도 역시 비빈발항목인, 영양가 없는 superset 일 것이므로 볼 필요도 없으니 (안봐도 비디오...), 아예 처음부터 가지치기(pruning)를 하라는 것입니다. 

 

 

 

{A, B, C, D, E}의 5개 원소 항목을 가지는 4건의 transaction에서 minimum support 2건 (=2건/총4건=0.5) 기준으로 pruning 하는 예를 들어보겠습니다.

 

 

 

위의 예시를 tree 형식으로 색깔로 infrequent item set과 그의 하위 superset을 나타내보면 아래와 같습니다.  색깔 칠해진 superset 들은 가지치기(pruning) 당해서 지지도 계산을 하지 않게 됩니다.

 

 

[그림 1]

 

 

 

위에서 예와 그림으로 소개한 빈발항목집합 추출 Pseudo Aprior algorithm 은 아래와 같습니다.

 

Pseudo Apriori algorithm

 

[Reference] "Fast Algorithms for Mining Association Rules", Rakesh Agrawal, Ramakrishman Srikant, 1994

 

(위의 (3)번 apriori-gen(Lk-1) 에서 (k-1)-항목 빈발항목집합후보를 생성하고, (9)번에서 minimum support  count 보다 큰 빈발항목집합만 추출, 즉 최소지지도 미만은 pruning)

 

 

4) 빈발항목집합의 후보를 생성하고 연관규칙을 도출하는 Apriori algorithm의 원리는?

 

이후에 빈발항목집합의 후보(candidates list)를 생성하고, 연관규칙을 생성한 후에, 최소신뢰도 기준 (minimun confidence criteria)를 적용해서 최소 신뢰도에 미달하는 연관규칙은 제거(pruning)하게 됩니다. 

 

빈발항목집합 후보를 생성하기 위해, (k-1)-항목 빈발항목집합에서 처음 (k-2) 항목이 같은 항목들만 혼합하여 k-항목 빈발항목집합 후보를 생성합니다. 

아래에 2-항목 빈발항목집합 을 가지고 3항목 빈발항목후보 를 생성하는 예를 들어보겠습니다.  2-항목 빈발항목집합에서 (k-1)-항목, 즉 1-항목이 같은 항목은 노란색을 칠한 {B}항목입니다. 따라서 {B}항목이 포함된 {B, C}와 {B, E}를 혼합해서 k-항목 빈발항목집합, 즉 3-항목 빈발항목집합 후보를 만들면 {B, C, E} 가 됩니다. 나머지 {A, B}, {C, E}는 무시하게 됩니다.  실제로 위의 [그림1]에서 살아남은 3-항목 빈발항목집합이 {B, C, E} 입니다 (3-항목 빈발항목의 나머지 항목집합은 superset으로서 pruned 됨).

 

 

[그림2]

 

[Reference] "R, SAS, MS-SQL을 활용한 데이터마이닝", 이정진, 자유아카데미, 2011

 

 

빈발항목집합을 도출했으므로 이제 연관규칙을 생성해보겠습니다.  빈발항목집합 L의 항목들을 공집합이 아닌 두 개의 서로 다른 부분집합 X와 Y로 나누어 하나의 연관규칙 X → Y를 만들었다고 합시다. k-항목 빈발항목집합 L은 최대 개(공집합과 전체집합 제외)의 연관규칙을 만들수가 있으며, 이중에서 최소신뢰도(minimum confidence) 조건을 만족하는 연관규칙을 찾으면 됩니다.

 

연관규칙 생성의 Apriori principle


빈발항목집합 L에 대하여 연관규칙 X → Y 가 최소신뢰도 기준을 만족하지 않으면 X의 어떠한 부분집합 X'에 대한 연관규칙 X' → L - X' 도 최소신뢰도 기준을 만족할 수 없다

 

 

3-항목 빈발항목집합 C3 {B, C, E}를 가지고 6개 (=2^k - 2 = 2^3 -2 = 8 - 2 =6개) 의 연관규칙을 만들어보면 아래 그림과 같습니다.  이때 가령 아래 검정색으로 테두리를 친 {C, E} → {B} 연관규칙이 최소신뢰도 기준에 미달했다고 할 경우, 그 밑에 딸린 {C} → {B, E}, {E} → {B, C} 연관규칙은 제거(pruning)하게 됩니다.

 

[그림3]

 

 

[그림1]에서 처럼 비빈발항목(infrequent)에 대해서 최소지지도(minimum support) 기준 미달 항목을 가지치기(pruning)하고 -> [그림2]에서 처럼 빈발항목후보를 생성한 후에 -> [그림3]에서 처럼 최소신뢰도(minimum confidence) 기준 미달하는 연관규칙을 제거해나가는 반복(iteration) 작업을 새로운 연관규칙이 없을 때까지 하게 됩니다.

 

 

다음번 포스팅에서는 R을 가지고 연관규칙 분석하는 예를 들어보겠습니다.

 

이번 포스팅이 도움이 되었다면 아래의 '공감 ♡'를 꾸욱~ 눌러주세요.

 

Posted by R Friend R_Friend

댓글을 달아 주세요

  1. kjh 2016.08.25 21:53  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 오늘도 어김없이 질문입니다 ㅎㅎ

    1. 최소지지도, 최소신뢰도는 어떻게 구하는지요?
    임의로 정한다는 것을 어디서 본 적이 있는 것 같은데, 일반적으로 정하는 규칙이나 수치가 있나요?

    2. 모든 가능한 연관규칙의 개수 3^k - 2^(k+1) + 1 은 어떻게 구한 수치인가요
    -> 아 이부분은 대강 알겠네요.
    -2^k 는 선행에만 항목집합이 있는 것, -2^k는 후행에만 항목집합이 있는것
    +1은 2번 빼준 공집합을 한번 더해준 것.. 인가보네요

    • R Friend R_Friend 2016.08.26 13:13 신고  댓글주소  수정/삭제

      최소지지도, 최소신뢰도 구하는 법칙은 없습니다. 분석 목적과 대상이 무엇이냐에 따라서 달라지며, 시행착오(trial & error) 시도가 필요합이다.

      최소 기준선이 너무 높으면 아예 rule이 안나올수도 있구요, 기준이 너무 낮으면 허접한 온갖 rule이 튀어나올수 있습니다.

  2. kjh 2016.08.25 22:22  댓글주소  수정/삭제  댓글쓰기

    4) 빈발항목집합의 후보를 생성하고 연관규칙을 도출하는 Apriori algorithm의 원리는?
    이부분 잘 모르겠어요 ㅠㅠ 특히 "2-항목 빈발항목집합에서 (k-1)-항목, 즉 1-항목이 같은 항목은 노란색을 칠한 {B}항목입니다. " 이부분이 무슨말인지 잘 모르겠네요..

    • R Friend R_Friend 2016.08.26 12:45 신고  댓글주소  수정/삭제

      [그림2]를 참고하시기 바랍니다. 처음 2항목에서는 k=2이므로, k-1=1 항목의 첫번째가 같은거를 보면 'B'가 같으므로 (B, C)와 (B, E)를 묶어서 3항목(k=3) 집합 (B, C, E)를 만들고, 나머지는 pruning 했다는 뜻입니다.

      본문이랑 동어반복한거 같네요 ^^;;;

  3. curycu 2017.02.20 16:24  댓글주소  수정/삭제  댓글쓰기

    알찬 포스팅 잘보고 갑니다/ 감사합니다 :)

  4. 8dialshhu 2017.03.02 18:21  댓글주소  수정/삭제  댓글쓰기

    가능한 모든 룰의 개수가 왜 (3^k - 2^(k+1) + 1) 인지 이해가 안되는데요.
    설명해주실수 있나요??

    • R Friend R_Friend 2017.04.30 21:16 신고  댓글주소  수정/삭제

      (1) 거래에서 나타나는 모든 항목들의 집합(item set)을 I={i1, i2, ..., ik} 라고 할 때, 모든 가능한 부분집합의 개수는 공집합을 제외하고 M=2^k - 1 개입니다.

      (2) 항목집합 L의 항목들을 공집합이 아닌 두 개의 서로 다른 부분집합 X와 Y로 나누어 하나의 연관규칙 X -> Y 를 만들었다고 할 때 k-항목 집합 L은 공집합과 전체집합을 제외하고 최대 2^k -2 개의 연관규칙을 만들 수 있습니다.

      (1) 번에서 나온 '모든 가능한 부분집합의 개수 M=2^k - 1 개'에 대해서 => (2)번에서 설명한 'k-항목 집합 L은 공집합과 전체집합을 제외하고 최대 2^k -2 개의 연관규칙'을 적용하면 => '모든 가능한 연관규칙의 개수는 3^k - 2^(k+1) + 1 이 됩니다.

      수식 전개는 저도 따로 안해봤는데요, k 에 4나 5처럼 작은 숫자 적용해서 몇 개 적용해보시면 연관규칙 만드는 경우의 수가 어떻게 되는지 이해하실 수 있을거 같아요.

  5. lcg 2017.03.25 20:38  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. 정말 좋은 글 잘 읽고 있습니다

    앞으로 포스팅 2개씩 인쇄하면서 앞으로 공부하려고 합니다 ㅎㅎ

    알고리즘 관련해서 위엣분과 마찬가지로 모든 룰의 개수 구하는 방법이 궁금합니다.

    수학에 대해 손 놓은지가 좀 오래되서 잘 모르겠습니다 !!

    • R Friend R_Friend 2017.04.30 21:16 신고  댓글주소  수정/삭제

      (1) 거래에서 나타나는 모든 항목들의 집합(item set)을 I={i1, i2, ..., ik} 라고 할 때, 모든 가능한 부분집합의 개수는 공집합을 제외하고 M=2^k - 1 개입니다.

      (2) 항목집합 L의 항목들을 공집합이 아닌 두 개의 서로 다른 부분집합 X와 Y로 나누어 하나의 연관규칙 X -> Y 를 만들었다고 할 때 k-항목 집합 L은 공집합과 전체집합을 제외하고 최대 2^k -2 개의 연관규칙을 만들 수 있습니다.

      (1) 번에서 나온 '모든 가능한 부분집합의 개수 M=2^k - 1 개'에 대해서 => (2)번에서 설명한 'k-항목 집합 L은 공집합과 전체집합을 제외하고 최대 2^k -2 개의 연관규칙'을 적용하면 => '모든 가능한 연관규칙의 개수는 3^k - 2^(k+1) + 1 이 됩니다.

      수식 전개는 저도 따로 안해봤는데요, k 에 4나 5처럼 작은 숫자 적용해서 몇 개 적용해보시면 연관규칙 만드는 경우의 수가 어떻게 되는지 이해하실 수 있을거 같아요.

  6. 도른자 2017.06.28 16:02  댓글주소  수정/삭제  댓글쓰기

    마지막에 {C, E} > {B} Rule은 확률이 100% 아닌가요? 왜 Pruning 되는지 이해가 안되요. 도와주세요.

    --> 자체수정
    아 그냥 예시를 드셨던 것 뿐이었군요
    제 개인적인 생각으로는
    {C, E} > {B}는 100%라서 오해할 가능성이 있는 것 같아요.
    {B,C} > {E}가 66.66%이므로 요걸로 하시고 최소신뢰도가 70%라 한다면 의미가 통할 것 같습니다.

    어쨋든 좋은 글 감사합니다.

  7. HS 2017.12.28 11:41  댓글주소  수정/삭제  댓글쓰기

    매번 눈팅으로 보다가 늦게나마 감사인사를 드립니다.

    알찬 내용 제공해주셔서 정말 감사드립니다. ^^