티스토리 뷰
[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 = { {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 코드로 작성하면 다음과 같습니다.
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 ...
'이론 > Data Mining' 카테고리의 다른 글
[Data Mining] 1.1. 연관 법칙 (Association Rule) 소개 (2) | 2014.11.02 |
---|---|
[Data Mining] 0. 데이터 마이닝 소개 (0) | 2014.10.31 |
- Total
- Today
- Yesterday
- 쉘 코드 작성
- 힙 스프레잉
- shellcode writing
- IE 11 UAF
- TenDollar CTF
- Windows Exploit Development
- 윈도우즈 익스플로잇 개발
- data mining
- TenDollar
- 2014 SU CTF Write UP
- IE UAF
- 쉘 코드
- heap spraying
- Use after free
- IE 11 exploit development
- UAF
- IE 10 익스플로잇
- 데이터 마이닝
- School CTF Write up
- School CTF Writeup
- WinDbg
- shellcode
- expdev 번역
- IE 10 God Mode
- IE 10 Exploit Development
- 2015 School CTF
- Mona 2
- IE 11 exploit
- CTF Write up
- IE 10 리버싱
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |