파이썬 코딩으로 말하는 데이터 분석 - 4. 연관 (Apriori 알고리즘)

요즘 데이터분석과 관련하여  텐서플로우와 스파크(ML)등의 머신러닝 솔루션들이 굉장히 유행하고 있습니다. 물론 저것들이 삶을 편안하게 만들어주기도 하지만 대부분의 데이터 분석은 저런 거창한 것 말고 평균,편차 같은 기본적인 개념으로 부터 시작되고 있으며 이러한 개념을 조금씩 변경해가며 더 의미있는 가치를 찾기 위해 빠르게 적용해보는 과정을 거쳐야하는데  그러기 위해서는 

1. 직접 코딩해서 기본적인 데이터분석 유틸리티 함수들을 만들어봐야한다. 

2. SQL문을 잘 다루어야한다. 

3. 엑셀을 잘 다루어야 한다. 

이 3가지는 기본이라고 저는 생각합니다. 소규모 데이터를 가지고 이리저리 반복해서 돌려보는 과정은 매우 중요하며 이런 기본적인 것들도 못하면서 하둡,텐서플로우나 깔짝대고, 데이터 분석 한다 라고 칭할 수는 없겠지요. (이것은 논쟁의 여지가 있습니다.) 그래서 이것들 중 1번에 대하여  "밑바닥부터 시작하는 데이터과학" 등의 좋은책의 내용을 통해서 살펴보는 시간을 갖도록 하겠습니다. 

통계,확률,패턴인식 분야의 내용들의 수식은 외우기가 힘듭니다. 외워도 금방 까먹어지는게 통계관련 공식인거 같습니다. (예를들어 정규분포,확률밀도라는 개념은 매우 쉽게 수긍이 가지만 , 그 식을 외우는건 좀 .;;) 또한 체득하고 나면 당연한거 아냐? 라고 느껴지는 알고리즘(수식) 인데 글로 설명하면 매우 산만해지는거 학문인거 같습니다. 하지만  우리들은 소프트웨어 개발자이기 때문에 수많은 기술변화도 따라가야하는 운명에 있는데 쓸때 없이 공식 및 수학을 외우고 있을 수는 없지 않겠습니까? 

제가 초등학교 5학년때 만(10,000) 단위 암산을 했었는데요. 주산,암산을 배워보신분은 아시겠지만 그것이 가능한것은 기억의 매개로 주판을 이용한 것 입니다. 마찬가지로 우리 개발자들은 그 기억의 매개체로 코드를 이용하면 개념과 함정(예를들어 K-Means 를 통해 군집화하면 길이차를 가지고 구분짓는 것이기 때문에 문제가 생기는 도메인 또한 많다) 에 대한 이해가 더 오래갈 것이라 보며 덤으로 가져다 사용도 할 수 있을것입니다.

* 그 상상의 매개체로써의 언어로 "파이썬" 을 선택했으며 정말 좋은 언어라고 생각합니다.

순서 

1. 통계 - 카운팅,min,max,평균,중앙값,산포도,분산,편차,공분산,상관관계 

2. 가설과 추론 (베이지언 - 사후확률,우도) 

3. 군집화 (K-Means)

4. 연관 (Apriori)

5. 함수형으로 데이터 다루기 

6. 경사하강법

7. 회귀분석

8. 은닉 마코프법 (HMM) 

9. k-NN

10. DTW 

 * 참고로 "밑바닥부터 배우는 데이터과학" 서적은 numpy,scikit-learn 등의 외부라이브러리를 활용은 배제되었습니다.

연관 되는 이벤트들이란?

이마트에 가서 장을 보는 것으로 이야기를 풀어나가 본다.
어느 날이 좋은 목요일엔  ("수박"-"기저귀"-"맥주") 를 사고 어느날 안좋은 목요일에도  ("기저귀"-"맥주") 를 샀다고하자. 그런 날이 자주 있었다고 하면 목요일과 "기저귀" 와 "맥주" 는 어떤 연관관계가 있다고 할 수 있다. 나 뿐만 아니라 수많은 남자들이 목요일날 저렇게 함께 사는 확률이 높다는것을 알아차린다면 업주는 무엇을 해야할까? 그렇다 "기저귀" 와 "맥주" 코너를 비슷한 곳에 위치시킴으로써 매출을 늘릴 수 있을 것이다.

이렇게 어떤 데이터 집합속에서 각 데이터간의 관계를 살펴서 연관 되는 분석/규칙을 찾는 알고리즘중에 하나가 Apriori 알고리즘이다. 먼저 관련 용어를 아래 표를 가지고 설명하겠다.  매우 간단하다.

이마트 방문일	상품
1일	두유,상추
5일	상추,기저귀,맥주,삼겹살
10일	두유,기저귀,맥주,오렌지 주스
15일	상추,두유,기저귀,맥주
20일	상추,두유,기저귀,오렌지 주스

지지도 

위의 표로 보면 [두유] 의 지지도는 4/5 인데 이유는 전체 집합군에서 두유가 포함된 집합의 수이다.

전체에서 아이템 집합 (두유) 이 포함된 데이터 집합의 비율로 정의한다. 

[두유,기저귀] 의 지지도는 ? 그렇다. 3/5 이다.  

두유와 기저귀를 모두 포함한 데이터 집합은 3개가 있다.

신뢰도 

[기저귀]를 샀을때 [맥주]도 같이 사는 확률에 관한 이야기이다.

즉 [기저귀] ->[맥주] 로 그 둘간의 연관 규칙을 나타내는데,  

[기저귀] 를 산 모든날이 100일이라고 하면 , [기저귀] 와 [맥주] 를 함께 산 날이 90일이라고 칠때

그 신뢰도는 9/10이다. 즉 신뢰도란 지지도({기저귀,맥주})  / 지지도({기저귀}) 가 된다.

Apriori 알고리즘이란?

위의 그림은 A 가 발생하고 나서 (A,B) (A,C) (A,D) 등이 일어날 수 있고 그 후에 (A,B,C) 가 일어날수 있음에 대한 단순한 트리이다. 이때 AB가 일어날 확률이 적었다면 , AB에서 파생되는 것들도 적을것임은 너무 자명하다. 따라서그것들에 대한 계산을 삭제해가면서 빈발(Frequent) 관계를 찾는 알고리즘이라고 보면된다. 알고리즘의 성능을 높게하기 위해서 말이다. 

소스로 말해요.

이제 알고리즘을 만들기 위해 필요한 함수들을 공부해보도록 하자. 파이썬 공부를 겸하면서~1석2조!!

[[1,3,4], [2,3,5], [1,2,3,5], [2,5]] 이런 데이타가 있다고 하자.

1. createC1 

데이터셋들을 중복되지 않게 유일한 수들로 나열시키는 함수이다.
[1,1,1,2,3,2,2,3,3,4,5,3,4] 의 결과는 [1,2,3,4,5] 로 나올것이다.

def createC1(dataSet):
    C1=[]
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])

    C1.sort()
    return map(frozenset, C1)

[1,2,3,4,5] 이렇게 나온결과를 map 을 사용하여 변경해주고 있다.
map, reduce, filter, folder 과 같은 것들은 함수형 파라다임에서 기본적인 함수들이며, 많은 언어에서 지원하는 추세이다. map 의 경우 두번째 파라미터를 , 첫번째 파라미터이 함수를 적용해서 리스트를 뽑아낸다.

결국 [frozenset([1]), frozenset([2]) .....] 이런식의 최종 결과가 도출된다. 

* frozenset 은 한번 정의하면 이후 add 같은 변경이 불가능한 집합을 의미 하며 나중에 딕셔너리의 키로 사용할 예정이기때문에 굳이 frozenset 을 사용하였다. 

2. scanD 

C1 은 [1,2,3,4,5] 같은 유일한 데이터의 리스트이고 (정확히는 [frozenset([1]), frozenset([2]) .....])
D 는 [set([1,3,4]), set([2,3,5]) .... 이다.

C1 = createC1(dataset)

D = map(set,dataset)  # distinct 수를 뽑아냄. (1,3,3) 이면 (1,3) 

# 전체 그룹중에 Ck 가 있는것.
# Ck 가 1 이라면 1을 포함한 그룹들을 찾음 (지지도 생성) 
# Ck 가 [1,3] 이라면 [1,3] 둘다 포함한 그룹들의 지지도 찾음 
def scanD(D, Ck, minSupport):
  
    # 요소 n 은 몇개의 그룹에 포함되어 있는지 계산한다. (1은 2개) 
    ssCnt = {}
    for tid in D:          # tid 에는 set([1,3,4]) 등이 담긴다.
        for can in Ck:     # can 에는 frozenset([1]) 등이 담긴다.
            if can.issubset(tid):  # 1 이 [1,3,4] 에 있으면 
                if not ssCnt.has_key(can): ssCnt[can] = 1 
                else: ssCnt[can] += 1  # 키 : 1  값 : 1을 가진 그룹의 수 

    
    # 지지도가 0.5보다 높은것들의 리스트를 구함. 
    # 1의 경우 2군데 포함되었으니 2/4 = 0.5 
    # 2의 경우 3/4 , 3의 경우 3/4 , 4의 경우 1/4, 5의 경우 3/4 
    numItems = float(len(D)) # 그룹 갯수
    retList = []
    supportData = {}
    for key , value in ssCnt.iteritems():
        support = value / numItems 
        if support >= minSupport:
            retList.insert(0,key)
        supportData[key] = support

    return retList, supportData

L1 = scanD(D, C1, 0.5) 

는 [frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]  이런 결과가 나온다.

지지도가 0.5 이하인 4 빼고는 다 나오는셈~ 

이마트로 설명해보면 사람들이 장을 보는 아이템들이
도깨비는 [상추,기저귀,맥주,삼겹살] 를 사고
은탁이는 [상추,삼겹살] 
저승사자는 [상추]
써니는 [맥주,삼겹살] 을 샀다면  

50%이상 선택되는 아이템을 찾는 로직이며, 결과는 기저귀 빼고 나머지가 선택될 것이다.
[상추,삼겹살] 짝 또한 지지도가 50%이상 선택되어졌다. 

apriori 알고리즘 (빈발아이템 집합찾기)

# [1,3,2,5] 를 
# [1,3] [2,5] [2,3] [3,5] 를 
# [2,3,5] 이런식으로 만드는 함수 
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])

    return retList

# 특정 지지도 이상의 값들의 쌍을 찾음 
def apriori(dataset, minSupport = 0.5):
    C1 = createC1(dataset)
    D = map(set, dataset)
    L1 , supportData = scanD(D,C1,minSupport)
    L = [L1]
    k=2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2],k)
        Lk,supK = scanD(D,Ck,minSupport) # 후보그룹을 모두 찾는다.
        supportData.update(supK)
        L.append(Lk) #이게 핵심!특정 지지도 이상의 그룹들만 L에 담는다.즉 가지치기
        k += 1
    return L, supportData


if __name__ == "__main__":
   print "apriori 알고리즘"

   dataset = loadDataSet()

   L, suppData = apriori(dataset)
   print "L:"  + str(L)
   print "........................."
   print "suppData:" + str(suppData)

코드에서 retList.append(Lk[i] | Lk[j]) 는 만약 frozenset([2,3]) 과 frozenset([2,5]) 가 있다면 [2,3,5] 로 만들어주는 코드이다.  예를들어 자세히 살펴보자.

Lk = [frozenset([1,2]), frozenset([1,3])]

Lk[0] | Lk[1]  는 frozenset([1,2,3])   # 합집합

Lk[0] - Lk[1]  는 frozenset([2])       # 차집합 

Lk[0] & Lk[1]  는 frozenset([1])       # 교집합 

이왕 하는 김에 set 에 대해서 좀 더 알아보자.

numbers1 = {1, 3, 5, 7}
numbers2 = {1, 3}

# # Is subset.
if numbers2.issubset(numbers1):
    print("Is a subset")

# # Is superset.
if numbers1.issuperset(numbers2):
    print("Is a superset")

# Intersection of the two sets.
   print(numbers1.intersection(numbers2))

결과)

지지도 0.5 이상의 가장 빈번한 조합들 

L:[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]

조합들의 지지율 상세  

suppData:{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([2, 3, 5]): 0.5, frozenset([1, 2]): 0.25, frozenset([1, 5]): 0.25, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([1, 3]): 0.5, frozenset([2]): 0.75}

이마트로 설명해보면  사람들이 장을 보는데 도깨비는 [상추,기저귀,맥주,삼겹살] 를 사고 은탁이는 [상추,맥주,삼겹살] 저승사자는 [상추], 써니는 [맥주,삼겹살] 을 샀다면, 그 중에서  사람들이 50%이상 선택되는 아이템을 찾는다고 할때  결과는 무엇일까? 

단일 아이템 : [상추] [맥주] [삼겹살]

2쌍 아이템: [상추,맥주]  [삼겹살,맥주]

3쌍 아이템: [상추,삼겹살,맥주] 

가 될 것이다.

apriori 알고리즘 (연관규칙찾기)

위의 함수에서는 일단 가장 빈번하게 나타나는 패턴들을 찾아서 묶어놓았다.

L:[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]

이런식으로 말이다.

역시 이해하기 편하게 이마트의 경우로 생각해보자. (몇년지나 다시 읽어보니 그냥 숫자가 더 이해하기 쉬운 함정이..)

[두유, 상추] 라는 빈발집합을 찾았다고 해도  
[두유] 를 살 때 [상추] 를 사는 경우가 매우 많으면 [두유] -> [상추] 는 연관 관계에 있다고 볼 수 있지만 

[상추] 또한 [두유] 와 연관관계가 많다고는 단정 지을 수는 없다.

왜냐면 [상추] 를 샀을때 [두유] 를 같이 사는 경우보다 [갈비살] 을 사는 경우가 훨 씬 많을 수 있기 때문이다.

또한 특정 요일에 [두유,상추] 보다 [두유,빵] 을 사는 비율이 더 높다면 그 요일의 경우는 두유와 연관이 있는것은 상추보다는 빵일 수 도 있다.

소스를 통해 이해해보자. (좀 복잡하니 편집기를 놓고 하나씩 따라가면서 이해하는게 빠를 것이다.) 

def generateRules(L, supportData, minConf=0.7):
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if i>1:
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet,H1,supportData, bigRuleList, minConf)

    return bigRuleList

def calcConf(freqSet, H, supportData, br1, minConf=0.7):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet] / supportData[freqSet-conseq]
        if conf >= minConf:
            print freqSet-conseq, '-->', conseq, 'conf:', conf
            br1.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

def rulesFromConseq(freqSet, H, supportData, br1, minConf=0.7):
    m = len(H[0])
    if (len(freqSet) > (m + 1)):
        Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, br1, minConf)
        if (len(Hmp1) > 1):
            rulesFromConseq(freqSet, Hmp1, supportData, br1, minConf)




if __name__ == "__main__":
   print "apriori 알고리즘"
   dataset = loadDataSet()
   L, suppData = apriori(dataset)
   print "L:"  + str(L)
   print "........................."
   print "suppData:" + str(suppData)

   rules = generateRules(L, suppData, minConf=0.7)

이 코드의 핵심은 conf = supportData[freqSet] / supportData[freqSet-conseq]  코드이다.
이 코드가 말하는 바는   conf =  (기저귀,맥주) 가 함께 나올 지지율 /  기저귀가 포함된 모든것의 지지율이다. 
이 비율이 높을때는 기저귀와 맥주는 함께 따라다닌다고 보면 된다는 것이다. 

데이터 : [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]

빈번조합들 (50%이상 지지도)

L:[ [frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])],
    [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])],
    [frozenset([2, 3, 5])], []]

전체 조합들의 지지율   

suppData:{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([2, 3, 5]): 0.5, frozenset([1, 2]): 0.25, frozenset([1, 5]): 0.25, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([1, 3]): 0.5, frozenset([2]): 0.75}

지지도 0.5 이상의 결과 :  

frozenset([3]) --> frozenset([1]) conf: 0.666666666667

frozenset([1]) --> frozenset([3]) conf: 1.0

frozenset([5]) --> frozenset([2]) conf: 1.0

frozenset([2]) --> frozenset([5]) conf: 1.0

frozenset([3]) --> frozenset([2]) conf: 0.666666666667

frozenset([2]) --> frozenset([3]) conf: 0.666666666667

frozenset([5]) --> frozenset([3]) conf: 0.666666666667

frozenset([3]) --> frozenset([5]) conf: 0.666666666667

frozenset([5]) --> frozenset([2, 3]) conf: 0.666666666667

frozenset([3]) --> frozenset([2, 5]) conf: 0.666666666667

frozenset([2]) --> frozenset([3, 5]) conf: 0.666666666667

지지도 0.7 이상의 결과 : 

frozenset([1]) --> frozenset([3]) conf: 1.0     # 1 을 할때, 3도 같이 할 확률이 100%

frozenset([5]) --> frozenset([2]) conf: 1.0     # 5 를 할때 2를 할 확률도 100%

frozenset([2]) --> frozenset([5]) conf: 1.0     # 2 를  할 때 5를 할 확률도 100%

유심히 봐야할 것은 2와 5는 서로 연관관계가 있지만 
1과 3은  단지 1이 3과 연관관계가 있는것이지 3 은 1과 연관관계가 부족하다는 것.

---

레퍼런스  : 머신러닝 인 액션