일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 완전탐색
- 백준
- 재귀
- 세그먼트트리
- acm
- priority_queue
- stack
- 그리디
- DFS
- Greedy
- Algospot
- 유니온파인드
- 누적합
- backtracking
- 알고리즘문제해결전략
- 종만북
- 분리집합
- BOJ
- 다이나믹프로그래밍
- 동적계획법
- 백트래킹
- 이분탐색
- 스택
- 문자열
- 알고스팟
- union-find
- 너비우선탐색
- BFS
- DP
- 분할정복
- Today
- Total
DAMPER's blog
[Data Mining] 2 - Frequent Itemset 본문
연관 규칙 찾기
많은 transaction이 존재한다고 하자.
각 transaction에는 아이템들의 부분집합이 있을 때 연관규칙을 찾아보자.
Q1 : transaction들에서 빈번하게 등장하는 아이템 부분집합을 찾자
Support 란?
부분집합 I를 모두 포함하는 transaction의 수
또는
부분집합 I를 모두 포함하는 transaction의 비율
다음 표는 각 transaction에 해당하는 Item들을 나타낸 표이다.
Transaction ID | Items |
1 | Bread, Coke, Milk |
2 | Beer, Bread |
3 | Beer, Coke, Diaper, Milk |
4 | Beer, Bread, Diaper, Milk |
5 | Coke, Diaper, Milk |
위 표에 따르면 부분집합 {Beer, Bread} 의 Support 는 2이다. (2, 4 transaction에 포함되어있음.)
support threshold s 는 아이템 부분집합의 빈번함 척도이다.
s이상의 support 를 갖는 부분집합은 빈번하게 등장하는 부분집합이라는 뜻이다.
연관 규칙(Association rules) 이란
transaction에 대해 if - then 으로 표현되는 규칙
연관규칙 {i_1, i_2, ... i_k} -> j 의 의미는 "어떤 transaction에서 아이템 부분집합 {i_1, i_2, ... i_k} 을 포함할 때 아이템 j를 포함할 가능성이 높다."이다.
많은 연관 규칙 중에서 significant/interesting 한 규칙을 찾아야 한다.
"포함할 가능성이 높다."에 대한 척도를 정의한 것이 confidence 이다.
confidence
confidence(I->j) = support(I U j) / support(I)
아이템 부분집합 I를 포함하는 transaction들 중에 I와 아이템 j를 모두 포함하는 transaction들의 비율
Interesting 연관 규칙
confidence 가 높은 연관 규칙이라도 interesing 하지 않을 수 있다.
연관 규칙 I->j 에 대한 Interest
Interest(I->j) = |conf(I->j) - Pr[j]|
confidence(I->j)에서 j에 대한 비율을 뺀 값을 의미한다.
Pr[j] = (number of transactions that contain j) / (number of transactions)
모든 transaction들 중 j를 포함하는 transaction들에 대한 비율
보통 0.5 이상의 수를 threshold로 사용.
Transaction ID | Basket |
1 | milk, coke, beer |
2 | milk, pepsi, juice |
3 | milk, beer |
4 | coke, juice |
5 | milk, pepsi, beer |
6 | milk, coke, beer, juice |
7 | coke, beer, juice |
8 | beer, coke |
위 표에 대해 연관 규칙 {milk, beer} -> coke 가 있다고 하자.
support = 2
confidence = 2/4 = 0.5
Interest = 0.5 - 5/8 = -1/8
해당 규칙은 intereting 하지 않음을 알 수 있다.
Q2 : Support >= s 이고 Confidence >= c 인 모든 연관 규칙을 찾아라
s와 c는 사용자에 의해 주어진다.
빈번하게 등장하는 아이템 부분집합(frequent itemsets)을 찾는 것이 어렵다.
연관 규칙 찾기
step 1 : 모든 frequent itemset I를 찾는다.
step 2 : 연관 규칙을 만든다.
2-1 : frequent itemset I의 부분집합 A를 추출한다. (I가 frequent 하기 때문에 부분집합인 A도 frequent 하다.)
2-2 : single pass to compute the rule confidence (confidence(A, B->C, D) = support(A, B, C, D) / support(A, B))
2-3 : 만약 A, B, C -> D의 confidence가 c보다 낮으면, A, B -> C, D의 confidence도 c보다 낮다.
support(A, B, C, D) / support(A, B, C) >= support(A, B, C, D)/support(A, B)
support(A, B, C) 가 support(A, B)보다 작거나 같기 때문.
step 3 : 연관 규칙들 중 조건을 만족하는 (Support >= s and Confidence >= c) 규칙들을 출력한다.
Finding Frequent Itensets
naive way: Frequent Itemsets 을 구하기 위해서는 모든 Itemset을 만들어서 Frequent 한지 계산해야한다.
1. transaction을 1개 읽을 때, 해당 transaction에 포함된 item 수 n만큼 읽어야 한다.
2. 이 때 부분집합 I를 2^n 개 생성해서 카운팅 해야한다.
3. 다시 1로 돌아가서 n중첩 loop를 돌아야한다.
dataset이 너무 커서 memory에 모두 올릴 수 없다.
결국 disk I/O 횟수가 시간에 중요하다.
disk I/O를 줄이는 것이 최선!
메인 메모리 병목현상
많은 frequent-itemset 알고리즘에서 메인 메모리는 critical resource이다.
frequent item pair를 찾는것이 어렵다. (frequent item pair 가 많기 때문...)
frequent item pair를 찾아보자.
접근 1 : matrix를 사용해 모든 pair를 센다.
접근 2 : map[(i, j)] = c 로 저장
접근 1은 pair 당 4byte 저장공간 필요
접근 2는 pair당 12byte 저장공간 필요하지만 count가 1이상인 pair만 저장함.
이 마저도 메모리에 저장할 수 없다면?
다음 글인 A-Priori algorithm에서 메모리를 줄일 수 있는 방법을 제시한다.
'AI | data mining' 카테고리의 다른 글
[Data Mining] 4 - K-means clustering (0) | 2022.11.01 |
---|---|
[Data Mining] 4 - Clustering (0) | 2022.11.01 |
[Data Mining] 3 - Finding Similar Items : Locality Sensitive Hashing (0) | 2022.11.01 |
[Data Mining] 2 - Frequent Items : A-Priori algorithm (0) | 2022.10.31 |