티스토리 뷰

이론/Data Mining

[Data Mining] 1.2. Apriori Algorithm - Frequent Itemset

hackability 2014. 11. 3. 22:00

최종 수정: 2014.11.07


안녕하세요. Hackability 입니다.


이 전 포스팅에서는 연관 법칙에 대한 간략한 소개를 하였습니다. 이번 포스팅 내용은 연관 법칙에 사용되는 Apriori 알고리즘에서 (단계 1)인 빈번 집합 생성에 대해 알아보도록 하겠습니다.


# Apriori Algorithm


Apriori 알고리즘은 2 단계로 구성되어 있습니다.


단계 1: min sup을 만족 시키는(빈번한) 모든 아이템 집합 생성

단계 2: 단계 1에서 생성된 집합에서 min conf를 만족 시키는 모든 법칙을 생성


(단계 1) 빈번한 아이템 집합 생성


Apriori 알고리즘은 Downward closure라는 특성을 이용하여 효과적으로 동작하게 됩니다. Downward closure란 어떤 minsup을 만족 시키는 집합이 있다고 가정하면, 해당 하위 집합 역시 minsup을 만족 시킨다는 특징입니다. 밑에서 설명 하겠지만 만약 다음과 같은 집합이 Apriori Algorithm에 의해 선택되었다고 가정합니다.


{1, 4, 5}  (minsup = 30%, minconf = 80%)


그렇다면 위의 하위 집합인 {1}, {4}, {5}, {1, 4}, {1, 5}, {4, 5} 역시 minsup, minconf를 만족한다는 특성입니다.


먼저, pseudocode를 통해 Apriori Algorithm을 살펴 보도록 하겠습니다.





(헉헉... 슈더 코드를 티스토리에서 쓰는건 지옥이군요...)


슈더 코드에 너무 겁먹지 말고 하나씩 따라가 보도록 하겠습니다. 먼저, 알고리즘은 Candidate Generator를 통해 발생 가능한 모든 집합을 생성 합니다. 그 후, 생성된 집합의 하위 집합이 이 전 빈번 집합에 있는지 확인하고 해당 집합이 minsup도 만족 한다면 F 집합에 포함 시킵니다.


위 과정을 슈더 코드로 보면 복잡해 보이지만 아래 예를 보시면 쉽게 이해가 될 것 같습니다. 이번 예는 지난 번과 마찬가지로 Code Red 친구들의 Zero-day 구매 예를 통해 어떤 구매 집합이 가장 빈번하게 발생되는지 살펴 보도록 하겠습니다.


먼저, minsup=30% 그리고 구매 Transaction 을 다음과 같다고 가정합니다.


T1 = [PDF, MS Word, Flash Player]

T2 = [PDF, Gom Player]

T3 = [Gom Player, OpenSSL]

T4 = [PDF, MS Word, Gom Player]

T5 = [PDF, MS Word, Hangul, Gom Player, Flash Player]

T6 = [MS Word, Hangul, Flash Player]

T7 = [MS Word, Flash Player, Hangul]


먼저, 알고리즘에서는 k-th 집합을 생성합니다. 초기에는 아이템이 하나인 집합을 생성하면 다음과 같을 것 입니다.


C1 = {PDF, MS Word, Flash Player, Gom Player, OpenSSL, Hangul}


본 알고리즘에서 이렇게 발생 가능한 모든 아이템 집합을 생성하는데, 사실 더욱 효율적으로 알고리즘을 동작시키기 위해서는 lexicographic order로 집합을 정렬 시켜야 합니다. [Wiki link] 간단히 설명하면, 숫자나 문자 같은 경우에는 자체로 순서가 있지만 그렇지 못한 경우가 있을 수 있습니다. 해당 문자에 대해 의미 부여를 통해 문자간의 의미에 따라 정렬 등이 가능한 형태를 의미합니다.


본 예에서는 C1의 순서를 index 형태로 사용하여 순서를 지정하도록 하겠습니다. 예를들어, 0은 PDF를 의미하며 1는 MS Word를 의미합니다.


Candidate Set인 C1을 추출했으면 이 후, minsup을 만족시키는 아이템인지 확인합니다. 각각의 Frequency를 확인하면 다음과 같습니다.


F1 = {{PDF}:4, {MS Word}:5, {Flash Player}:4, {Gom Player}:4, {OpenSSL}:1, {Hangul}:3}


하지만 OpenSSL의 경우, support = 1/7 < 30% 이기 때문에 빈번 집합에 포함되지 못합니다. 그렇기 때문에 F1 집합에는 결론적으로 다음과 같이 구성 됩니다.


F1 = {{PDF}:4, {MS Word}:5, {Flash Player}:4, {Gom Player}:4, {Hangul}:3}


이렇게 구성된 집합은 candidate-gen을 통해 발생 가능한 모든 집합을 생성하게 됩니다. candidate-gen함수에서 주의하실 부분은 f1, f2의 집합의 마지막 원소가 다름을 주의하시기 바랍니다. 슈더 코드 폰트가 작아서 f2의 마지막 원소에 프라임이 안 보일 수 있습니다 :(


candidate-gen은 입력받은 집합에서 발생 가능한 다음 집합을 생성합니다. F1이 candidate-gen을 통해 발생되는 C2는 다음과 같습니다.


C2 = { {PDF, MS Word}, {PDF, Flash Player}, {PDF, Gom Player}, {PDF, Hangul}, {MS Word, Flash Player}, {MS Word, Gom Player}, {MS Word, Hangul}, {Flash Player, Gom Player}, {Flash Player, Hangul}, {Gom Player, Hangul} }


이제 후보 집합이 생겼습니다. 이제 이 후보 집합에서도 minsup을 만족 시키지 못하는 원소들을 제거해 주어야 합니다. 번거롭지만 C2에서 minsup을 만족시키는 집합을 찾는 것 까지만 자세히 살펴 보도록 하겠습니다. 다시 언급하자면, 아래 원소들이 전체 Database인 T에 몇 개가 존재하는지 카운트 하는 것 입니다.


F2 = { 

{PDF, MS Word}: 3, -> 3/7 >= 30% (만족)

{PDF, Flash Player}: 2, -> 2/7 < 30% (불만족) 

{PDF, Gom Player}: 3, -> 3/7 < 30% (만족)  

{PDF, Hangul}: 1, -> 1/7 < 30% (불만족) 

{MS Word, Flash Player}: 4, -> 4/7 >= 30% (만족) 

{MS Word, Gom Player}: 2, -> 2/7 < 30% (불만족) 

{MS Word, Hangul}: 3, -> 3/7 >= 30% (만족) 

{Flash Player, Gom Player}: 1, -> 1/7 < 30% (불만족) 

{Flash Player, Hangul}: 3, -> 3/7 >= 30% (만족) 

{Gom Player, Hangul}: 1 -> 1/7 < 30% (불만족) 

}


결론적으로 F2는 다음과 같은 빈번 집합을 갖게 됩니다.

F2 = { {PDF, MS Word}, {PDF, Gom Player}, {MS Word, Flash Player}, {MS Word, Hangul}, {Flash Player, Hangul} }


이제 F2을 candidate-gen을 통해 C3을 만들 차례 입니다. candidate-gen은 두 개의 집합을 선택하여 k-1까지 원소가 같고 마지막 원소만 다른 두 개의 집합을 합치는 역할을 합니다. 그러면 다음과 같은 집합이 선택되게 됩니다.


C3 = { {PDF, MS Word, Gom Player}, {MS Word, Flash Player, Hangul} }


하지만, 위에서 {PDF, MS Word, Gom Player} 집합은 선택될 수가 없는데, 그 이유는 {PDF, MS Word, Gom Player}의 하위 집합인 {MS Word, Gom Player}가 F2에서 빈번 집합이 아니였기 때문에 {PDF, MS Word, Gom Player}가 C3에서 선택될 수 없습니다. 따라서, C3는 다음과 같이 됩니다.


C3 = { {MS Word, Flash Player, Hangul} }

 

위 내용에 대해 python 코드로 작성하면 다음과 같습니다. 


Apriori_Algorithm_01.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
def is_sublist(a, b):
    if a == []: return True
    if b == []: return False
    return b[:len(a)] == a or is_sublist(a, b[1:])
 
def candidate_gen(freq, level):
    print "Generate all subsets of %d level item set" % (level)
 
    subset = []
    tmp    = []
    for i in range(0, len(freq)-1):
        for j in range(i+1, len(freq)):
            if level == 1:
                subset.append([[freq[i][0], freq[j][0]], 0])
                continue
 
            if freq[i][0][:-1] != freq[j][0][:-1]:
                continue
 
            tmp = []
            for k in range(0, len(freq[i][0])):
                tmp.append(freq[i][0][k])
            tmp.append(freq[j][0][-1])
            
            if level == 2:
                print "[#] Test subset :" + str(tmp)
                for k in range(0, len(tmp)-1):
                    for l in range(k+1, len(tmp)):
                        found = False
                        tmp2 = [tmp[k], tmp[l]]
                        for m in range(0, len(freq)):
                            if is_sublist(tmp2, freq[m][0]):
                                found = True
                                break
 
                        if found == False:  
                            print str(tmp2) + " is not subset ! (FALSE)"
 
                        if found == False: break
                    if found == False: break
                if found == False: continue
 
            elif level == 3:
                print "[!] Not implemented ..."
 
            subset.append([tmp, level+1])
            print
 
    return subset
 
T = [
    ['PDF', 'MS Word', 'Flash Player'],
    ['PDF', 'Gom Player'],
    ['Gom Player', 'OpenSSL'],
    ['PDF', 'MS Word', 'Gom Player'],
    ['PDF', 'MS Word', 'Hangul', 'Gom Player', 'Flash Player'],
    ['MS Word', 'Hangul', 'Flash Player'],
    ['MS Word', 'Flash Player', 'Hangul']
];
 
minsup = 0.3
n      = len(T) # Not used
 
c      = []
items  = [] # Not used
freq   = []
 
level  = 1
 
# Initialization
 
print "[#] The initial transaction "
for i in range(0, len(T)):
    print T[i]
print
 
for i in range(0, len(T)):
    for j in range(0, len(T[i])):
        found = False
        for k in range(0, len(c)):
            if c[k][0] == T[i][j]:
                c[k][1] = c[k][1] + 1
                found = True
                break
 
        if found == False:
            c.append([T[i][j], 1])
 
while level < 4:
    freq = []
 
    # Find the frequent itemset (>=minsup)
    print "[#] (%d)-level item set" % (level)
    for k in range(0, len(c)):
        print str(c[k][0]) + " => " + str(c[k][1])
 
        if (c[k][1] / (n*1.0)) >= minsup:
            freq.append([c[k][0], c[k][1]])
    print 
 
    print "[#] (%d)-level frequent item set" % (level)
    for k in range(0, len(freq)):
        print str(freq[k][0]) + " => " + str(freq[k][1])
    print 
 
    c = candidate_gen(freq, level)
 
    for i in range(0, len(T)):
        for j in range(0, len(c)):
 
            hit = 0
            for k in range(0, len(c[j])):
                for l in range(0, len(T[i])):
                    if c[j][0][k] == T[i][l]:
                        hit = hit + 1
 
            if hit == level+1:
                c[j][1] = c[j][1] + 1
 
    level = level + 1
 
    if c == []:
        print "[#] Nothing ..."
        break


-_-... 여러분은 이런 저질 코드 작성 안하셨으면 합니다....발 코딩이지만 예제를 꼭 보여주고 싶은 마음에 작성했습니다. 하지만 정말 슬퍼보이는 코드가 나왔네요... 코드에 몇 가지 (사실 상당히 많이) 부족한 부분이 있습니다. 


1. Lexical Order를 가정한다면 필요 없는 루프가 도는 것

2. candidate-gen 에서 if 문으로 level을 나눠서 처리 하는 것

3. is_sublist 함수의 경우, 수백만건의 요청이 오면 재귀 지옥이 발생하는 것


다음 부턴 R 이나 Matlab으로 예제를 보여야 겠다고 다짐해봅니다...


뭐 일단... 돌려보죠... -_-;;


결과 값

------------------------------------------------

[#] The initial transaction 

['PDF', 'MS Word', 'Flash Player']

['PDF', 'Gom Player']

['Gom Player', 'OpenSSL']

['PDF', 'MS Word', 'Gom Player']

['PDF', 'MS Word', 'Hangul', 'Gom Player', 'Flash Player']

['MS Word', 'Hangul', 'Flash Player']

['MS Word', 'Flash Player', 'Hangul']


[#] (1)-level item set

PDF => 4

MS Word => 5

Flash Player => 4

Gom Player => 4

OpenSSL => 1

Hangul => 3


[#] (1)-level frequent item set

PDF => 4

MS Word => 5

Flash Player => 4

Gom Player => 4

Hangul => 3


Generate all subsets of 1 level item set

[#] (2)-level item set

['PDF', 'MS Word'] => 3

['PDF', 'Flash Player'] => 2

['PDF', 'Gom Player'] => 3

['PDF', 'Hangul'] => 1

['MS Word', 'Flash Player'] => 4

['MS Word', 'Gom Player'] => 2

['MS Word', 'Hangul'] => 3

['Flash Player', 'Gom Player'] => 1

['Flash Player', 'Hangul'] => 3

['Gom Player', 'Hangul'] => 1


[#] (2)-level frequent item set

['PDF', 'MS Word'] => 3

['PDF', 'Gom Player'] => 3

['MS Word', 'Flash Player'] => 4

['MS Word', 'Hangul'] => 3

['Flash Player', 'Hangul'] => 3


Generate all subsets of 2 level item set

[#] Test subset :['PDF', 'MS Word', 'Gom Player']

['MS Word', 'Gom Player'] is not subset ! (FALSE)

[#] Test subset :['MS Word', 'Flash Player', 'Hangul']


[#] (3)-level item set

['MS Word', 'Flash Player', 'Hangul'] => 3


[#] (3)-level frequent item set

['MS Word', 'Flash Player', 'Hangul'] => 3


Generate all subsets of 3 level item set

[#] Nothing ...

------------------------------------------------

하하... 결과는 우리가 진행해온 방향으로 잘 동작하는 것 같습니다. 중간에 하이라이트 된 부분이 레벨 2에서 하위 집합이 이 전 집합에 없기 때문에 발생된 로그 입니다. 따라서 해당 집합이 다음 후보군에 포함되지 못하였습니다.

여기 까지 Apriori 알고리즘에서 단계 1에 해당하는 빈번 집합 생성에 대해 알아보았습니다. 단계 1 내용을 마치기 전에 몇 가지 추가적인 내용에 대해 얘기 해보고 마무리 할까 합니다.

* 이론적으로 아이템의 수를 m 이라 가정하면 복잡도는 O(2^m) 이 되어, 지수 알고리즘이 됩니다. 하지만 본 마이닝 알고리즘은 minimum support 측도를 이용하여 굉장히 효과적으로 이용할 수 있습니다. 이러한 특정을 가르켜 sparseness라 하는데 마켓 분석에서의 sparseness의 의미는 마켓에서 많은 물품을 팔지만 실제로 고객은 그 중 몇 개의 물품만 구입한다는 것 입니다.

* 본 알고리즘은 높은 수준의 scale up이 가능합니다. (저 위의 슬퍼 보이는 코드를 쓰지 않는다면요...) Apriori 알고리즘의 특징은 데이터 셋을 메모리에 전부 올리지 않고 살펴볼 가장 큰 집합만 살펴 보기 때문입니다. 일반적으로 10회 미만의 가장 큰 데이터 집합이 선택됩니다. 이러한 특성은 실무에서 굉장히 중요한데 그 이유는 실 시계에서 발생되는 이벤트는 굉장히 양이 많기 때문에 이를 모두 메모리에 올릴 수 업기 때문입니다. 따라서, 본 알고리즘은 굉장히 실용적이라고 할 수 있겠지요.

* 본 알고리즘은 level-wise 탐색을 기반으로 하고 있습니다. 따라서, 모든 level의 탐색이 끝나지 않더라도 원하는 level에서 언제든지 종료 가능하기 때문에 프로그램이 굉장히 유연해 집니다. 실제로 많은 응용 예에서 굉장히 긴 빈번 집합이라던지 룰 등은 사용하기가 까다롭기 때문에 이러한 유연성은 때에 따라서 큰 도움이 됩니다.

* Association rule mining에서의 가장 큰 단점은 수 많은 양의 아이템 집합이나 룰들이 생성되어 사용자로 하여금 의미를 찾기 힘들게 될 수 있다는 점 입니다. 이를 가르켜 interestingness problem 라 하는데, 이를 해결하기 위한 연구들도 진행되고 있습니다.

이제 빈번 집합을 생성했으니 다음 포스팅에서는 연관 법칙 생성에 대해 알아보도록 하겠습니다.


저작자표시

'이론 > Data Mining' 카테고리의 다른 글

[Data Mining] 1.1. 연관 법칙 (Association Rule) 소개  (2) 2014.11.02
[Data Mining] 0. 데이터 마이닝 소개  (0) 2014.10.31
공유하기 링크
댓글