연관분석3

 

 

여기에 있는 내용은 인터넷에서 연관분석 검색해서 나온 책의 일부입니다. 책 전체는 없고 연관분석 부분만 있네요. 아래에 첨부합니다. 처음 익플로 잘 다운이 안되서 크롬을 깔라 다운하니까 되네요.

 

 

ch6 (1).pdf

 

 

 

1. 개인적 체험

 

저번 글에서 이 연산분석은 개념은 간단하지만 실제 구현하는데 있어 계산해야 하는 양이 너무 많이 이걸 간단히 하는 방법이 오히려 핵심적인 부분이라 이야기 했죠. 상품수가 100개만 되어도 support와 confidence의 경우의 수가 너무 많이 나온다는 것이죠.

 

그래서 이 연관분석을 하려면 전산을 전공해야 합니다. 특히 자료구조나 트리구조에 대해 해박한 프로그램 능력이 있어야 합니다. 저는 한번 큰 고생을 한 적이 있습니다. 지도교수가 계산기 프로그램을 트리구조로 짜라는 숙제를 줬는데 개념상은 이해가 되는데 이걸 실제로 프로그램으로 구현을 하기 힘들었습니다. 전산과에서 자료구조를 배우지 않아서 그런 것이죠. push하고 pop up 하고 하는데 이걸 list로 어떻게 구현해야 할 지 감이 오지가 않아서요. 그래서 뭐든지 체계적으로 배우는 것이 중요합니다.

 

 

할 수 없어 한국에 와서 전산도사인 전자공학과 출신인 후배에게 도움을 받았죠. 나중에 프로그램 설명을 해주는데도 잘 이해를 못했습니다. 그 친구는 워낙 뛰어난 친구라 나중에 LG에서 핸드폰 개발 팀장을 오래 동안 했습니다.

 

 

 

2. 사전 찾기

 

어렵게 이야기하지 말고 일단 쉬운 예를 한번 들어보죠. 우리가 사전에서 어떤 단어를 찾는다고 하죠. 마트에 있는 품목들의 사전을 랜덤한 순서로 만들었다고 하죠. 이런 경우 어떤 품목을 찾으려면 처음부터 쭉 흩어가야 합니다.

 

그러나 우리는 사전을 이렇게 만들지 않죠. ㄱ ㄴ ㄷ.. 이런 순서에 ㅏ ㅓ ㅗ ...이런 순서로 배열을 하죠.

 

그래서 ‘양파’ 항목을 이 사전에서 찾는다면 ㅅ 까지는 쳐다보지도 않고 그냥 뛰어 넘는다는 것이죠. 그래서 이 찾는 search가 매우 효율적으로 됩니다. 이런 아이디어를 hash라고 합니다. 여러분이 SNS에서 해시태그라는 것을 사용하죠.

 

통상 품목에다 숫자 번호 1, 2, 3, 4, ... 이렇게 쭉 주고 나머지 값이 같은 것을 하나로 덩어리로 만듭니다. 사전에서 ㄱ, ㄴ, ㄷ,.. 이렇게 처음 자음이 같은 것끼리 하나의 덩어리로 만들 듯이요. 수학에서는 module이라 합니다. 그래서 hash 함수를 module 함수라고요 하고요.

 

 

사전의 예는 그리 낯선 것이 아닙니다. 여러분인 한글 작업을 할 때 실시간으로 문법 체크를 하죠. 즉 한글에서 타이핑하는 순간 마다 한글 프로그램에 들어 있는 사전을 search 한다는 것이죠. 친 단어가 사전에 없으면 맞춤법이 틀렸다고 보는 것이죠.

 

통상 사람들은 자기 업무와 관련해서 한글을 많이 사용하죠. 이 이야기는 한글 작업시 쓰는 단어가 매우 한정적이고 또 반면에 그 단어들의 사용빈도가 매우 높다는 것이죠.

 

그럼 단어를 칠 때 일일이 사전을 다 찾는 것이 아니라 자주 사용하는 단어 목록을 따로 만들어서 사용하면 더 좋겠죠. 자주 사용하는 단어 목록은 전체 사전보다 양이 훨씬 적어 메모리를 많이 차지하지 않고 또 search 하는 시간도 훨씬 줄어든다는 것이죠. 이런 개념을 cash라고 하죠. 컴퓨터에 캐시가 하드웨어적으로 들어 있지만 여기서는 소프트웨어적인 개념입니다.

 

 

우리가 하려는 것도 일단 support를 조사하여 자주 사용되는 품목들 목록을 만들어 search하려는 시간을 줄이려고 하는 것입니다.

 

 

왼쪽에는 여러분이 한글에서 치는 단어라고 생각하고 오른쪽에는 사전이라 생각하면 연관분석에서는 왼쪽은 그날 거래된 바구니 모임이 되고 오른쪽은 고빈도의 품목목록이 됩니다. 오른쪽의 품목 목록을 이 책에서는 candidate라고 쓰네요. 아래 그림을 한번 보시죠. 그래서 가능하면 후보목록 수를 줄이고 그리고 왼쪽의 거래 바구니와 비교하는 시간을 줄이는데 목적입니다.

 

 

 

 

여기서 한글에서 search와 차이점은 거래바구니 전체를 비교하는 것이 아니라 거래바구니의 모든 부분집합과 비교를 해야 합니다. 예를 들어 첫 번째 고객의 거래바구니에서는 (빵, 밀크)인데 이 경우 (빵), (밀크), (빵, 밀크) 이 세 가지가 오른쪽의 후보목록에 있는가 찾아야 한다는 것이죠. 그래서 만약 있으면 후보목록에서 빈도 수가 +1이 된다는 것이죠.

 

그래서 실제 마트에서 그날 거래가 만번이면 실제로 비교해야 하는 목록은 수십만번이 될 수 있습니다. 한 달 거래가 수십만번이면 비교해야 하는 목록은 수백만번이 될 수 있습니다. 뭐 슈퍼 컴퓨터의 프러세스가 수십만개 있다면 별 문제가 없겠죠. 각각 프로세스 거래 하나당 맡아서 처리하면 끝나죠. 병렬알고리즘이죠.

 

 

 

 

3. 중요공식

 

앞에서 이야기 했듯이 confidence 값이 높은 것을 찾아야 하는데 , 즉 연관성이 높은 품목의 짝을 찾아야 하는데 그 이전에 support의 값이 낮은 것은 먼저 분석에서 제외를 해야 합니다. support가 낮다는 것은 고객의 바구니 안에 그 품목들이 들어가 있을 확률이 너무 낮다는 것이죠. 그래서 이런 경우 confidence가 높아도 장사에는 별 도움이 안된다는 것이죠.

 

먼저 다음의 점을 유의하기 바랍니다. 연관법칙은 A->B로 쓰지만 support에서는 사실 A와 B를 구별할 필요가 없습니다.

 

support의 공식을 보면 support(A+B)=pr(A+B)이므로 (A+B) 덩어리만 알면 됩니다. 예를 들어 (사과, 배, 딸기)가 있다면 사과->(배, 딸기)나 (사고, 배)->딸기나 (배, 딸기)->사과나 전부 support 값이 같습니다. 그래서 support 이야기할 때는 A, B를 구별하지 않고 그냥 퉁쳐서 A라 표시하겠습니다.

 

 

그리고 일단 support가 구해지면 confidence는 상대적으로 구하기 쉽습니다. 즉 confidence(A->B)=Pr(A+B)/Pr(B)=support(A+B)/Pr(B)

 

로서 Pr(B)만 구해내면 됩니다. 이것도 support할 때 이미 구해져 있죠.

 

그럼 support와 confidence에서 유용한 정리를 먼저 소개하겠습니다. 정리1은 앞에서 이야기한 오른쪽이 후보목록군을 support 값을 이용하여 축약하는데 필요한 정리입니다.

 

 

1) Apriori Principle

 

정리1(support):

 

A가 고빈도 품목들이면 A의 부분집합은 항상 고빈도 품목들입니다. 반대로 A가 저빈도 품목들이면 A보다 큰 품목들은 항상 저빈도 품목들입니다.

 

 

여기서 고빈도 품목과 저빈도 품목은 분석하는 사람이 일정 값을 부여하는 것입니다. 즉 support(A)>0.1이면 고빈도, support(A)<0.1이면 저빈도 이런 식으로 분석하는 사람에 상황에 맞춰 고빈도, 저빈도를 지정한다는 것이죠.

 

예를 들어서 딸기가 저빈도라면, 즉 그날 마트에 와서 딸기를 산 사람이 10% 미만이라면 딸기를 포함하는 모든 품목들 즉 (딸기, 옷), (딸기, 배, 컴퓨터), (딸기, 화장품, 칫솔) 이런 품목들 모두 저빈도입니다. 그냥 조그만 생각하면 당연합니다. 그래서 모든 개별 품목에서 대해 support를 구한 다음 저빈도로 판단되면 이 품목을 포함하는 모든 품목들은 우리가 서치하는 대상에서 제외시킬 수가 있습니다.

 

아래 그림을 한번 보시죠.

 

 

 

 

 

(c,d,e) 항목이 고빈도이면 이것의 부분집합 항목은 전부 다 고빈도라는 것이죠. 오른쪽에 회색으로 표시되어 있죠. 한편

 

 

 

 

 

왼쪽을 한번 보시죠. (a, b)가 저빈도이면 (a, b)를 포함하는 모든 품목군들은 다 저빈도라는 것이죠. 우리는 이 bottom-up 방식을 사용하겠습니다.

 

 

그래서 처음에 모든 품목들에 대해 숫자를 부여합니다. 가나다 순으로 하는 것이 아니고요. 그리고 위 방법을 사용해서 저빈도 품목들을 다 제외한 다음 품목 수가 1인 경우, 2인 경우, 3인 경우 등 이런 순서로 크게 배열을 합니다. 사전에서 ㄱ, ㄴ, ㄷ, ...으로 배열하듯이요.

 

각각 품목 수에 따라 크게 배열 한 다음 그 안에서 모듈 함수, 즉 mod 3이라 하면 나머지가 0, 1, 2 인 경우에 따라 또 세부적으로 배열합니다. ㅏ, ㅑ, ㅓ, ㅕ... 이런 식으로 배열하듯이요. 이건 다음에 더 쓰겠습니다.

 

품목의 한글 순서대로 하지 않고 숫자로 하는 이유가 있습니다. 새로운 상품이 들어 왔을 경우 한글 순서대로 하면 디비 업데이트와 분석 업데이트가 매우 불편합니다. 그러나 숫자로 하면 기존의 숫자 최대값에다가 1만 더하여 밑에다 갖다 붙이면 됩니다. 새 품목의 이름이 무엇이든지 관계가 없다는 것이죠.

 

 

지금 이런 알고리즘을 Apriori 알고리즘이라 하고 연관분석에서 가장 고전적인 분석입니다. 그리고 이렇게 불필요한 것을 잘라내는 것을 support-based pruning 이라고 합니다.

 

 

2)

 

정리2(confidence)

 

만약 X->(Y-X)가 저confidence라면 X의 부분집합인 M은 M->(Y-M) 역시 저confidence이다.

 

아래 그림을 한번 보시죠.

 

 

 

왼쪽에 회색 칠한 부분을 한번 보세요. (bcd)->a는 저신뢰 연관법칙입니다. 여기서 X=(bcd), Y=(abdc)가 되는 것이죠. 그럼 bcd의 부분 집합 목록인 M=(cd), (bd), (bc), (d), (c), (b)에서 Y-M으로 가는 연관법칙은 모두 저신뢰 연관법칙이라는 것이죠.

 

 

그러나 confidence에서 유의할 점이 있습니다. 다음의 (커피, 티)의 교차분석표를 한번 보죠.

 

차->커피의 confidence는 차 산 사람 200명 중 커피를 150명이 샀으니까 0.75, 즉, 75%입니다. 그러나 자세히 보면 전체 1000명 고객 중 800명이 커피를 샀다는 것이죠. 즉 80%가 커피를 샀다는 것이죠. 즉 차 산 사람이 커피를 살 확률이 오히려 줄어든다는 것이죠. 그래서 단순히 차->커피의 confidence가 높다고 해서 좋은 것은 아니라는 것이죠.

 

그래서 또 많은 학자들이 이런 저런 측정치를 만들어 냅니다. 이건 소개한 논문들 참조하시고요. 그러나 위의 경우는 매우 특이한, 매우 희소한 경우가 아닐까 생각이 드네요. 좀 더 생각을 해 봐야 할 것 같습니다.

 

 

다음은 구체적으로 왼쪽의 거래바구니 목록을 해시하고 오른쪽의 후보목록을 해시하여 보다 빨리 search하고 빈도수를 계산하는 방법을 대해 소개하겠습니다.

ch6 (1).pdf

0.6MB