[3-2] Improving Apriori

Challenges of Frequent Pattern Mining

 

Improving Apriori: general ideas

❑ Reduce the number of DB scans

❑ Reduce the number of candidates

❑ Improve the candidate counting approaches

 

1. DIC: Reduce Number of Scans  : 동적으로 itemset counting을 시작하는 방법

레벨 전체가 끝날 때까지 기다리지 않고, 조건이 맞는 후보부터 counting을 시작

 

2. Partition: Scan Database Only Twice

DB를 쪼개서 각 조각에서 먼저 frequent pattern 후보를 찾고, 전체 DB는 딱 두 번만 스캔하는 방법

 

각 partition은 메인 메모리(main memory)에 올릴 수 있을 정도로 작아야 한다.

 

첫 번째 스캔에서는 각 partition 안에서 local frequent pattern을 찾는다. 즉,

• P1 안에서 자주 나오는 패턴
• P2 안에서 자주 나오는 패턴 등을 구한다..
• 각 partition은 전체 DB보다 작아서 localMinSup is set as (minSup / k)
• 어떤 패턴이 어느 partition 하나에서라도 그 partition 기준 localMinSup보다 support가 크면 그 패턴을 local frequent pattern으로 본다

두 번째 스캔에서는 1차에서 모아둔 local frequent pattern 후보들을 가지고 전체 DB 기준으로 정말 frequent인지 확인한다.

 

 

이방법은.. 진짜 global frequent pattern을 절대 놓치지 않는다는 보장이 있다.

어떤 itemset이 전체 DB에서 frequent라면 적어도 하나의 partition에서는 frequent해야 한다.

 

왜냐하면 전체 support가 크다는 건 그 빈도가 partition들에 나눠져 있다는 뜻인데, 모든 partition에서 localMinSup보다 작을 수는 없기 때문이야...

전체적으로 자주 나오면 반드시 어느 한 local DB에서는 자주 나와야 함..  그래서 1차 스캔에서 후보로 잡힐 수 있어.

 

그리고 어떤 패턴이 P2에서는 자주 나와도 전체 DB로 보면 support가 부족할 수 있다. 그래서 local frequent pattern은 그냥 후보(candidate) 일 뿐이지..곧바로 global frequent pattern이라고 확정할 수는 없어. 그래서 반드시 두 번째 스캔에서 전체 DB 기준으로 다시 검증해야 한다.

 

 

local frequent = global frequent는 아니기 때문에
마지막 전체 검증이 꼭 필요하다.

 

 

다음 내용으로 Sampling 인데.. 원본 DB 전체를 쓰면 너무 크니까 일단 일부 샘플에서 먼저 분석하자!!

샘플은 전체 DB보다 크기가 작으니까 원래 min_sup을 그대로 쓰면 진짜 의미 있는 패턴도 support가 작게 잡혀 놓칠 수 있으니까... 샘플 크기에 맞게 support 기준을 줄여 쓰자

Problems with the simple sampling

1) Some of frequent patterns found in SDB are not really frequent in the original database (similar with the local frequent patterns in Partition)

샘플에서는 자주 보여도 원래 전체 DB에서는 자주 아닐 수 있음 즉, false positive가 생김

 

2) Some of true frequent patterns could be missed if they are not included in SDB (different with Partition)

진짜 원본 DB에서는 frequent한데 샘플에 우연히 잘 안 들어오면 놓칠 수 있음. 즉, false negative 가능성도 생김

 

 

Solutions: two more scanning for verification

 

1. Negative border는 자기 자신은 S에 없지만, 그 모든 부분집합은 S 안에 있는 itemset들이야. 즉, 거의 frequent처럼 보였는데 샘플에서는 threshold를 못 넘겨서 S에 포함되지 않은 경계선 itemset들임..

 

2. negative border 검증은 샘플링 때문에 놓쳤을 수 있는 진짜 frequent pattern을 복구하는 장치야.

 

 

 

DHP: Direct Hashing and Pruning  : 목적은 후보 수 줄이기

 

 

When generating Lk , this algorithm also generates all the size k+1 itemsets for each transaction, and hashes them to a hash table and keeps a count..

 

Lk를 만드는 과정에서 각 transaction 안의 (k+1)-itemset 후보들도 같이 만들어본다는 뜻이야. 즉, 지금 k단계를 하면서 다음 단계 후보 정보를 미리 수집하는 느낌..그리고 만든 (k+1)-itemset들을 해시 테이블에 넣고 그 bucket count를 센다는 거야. 즉, 후보를 직접 다 저장하기보다 해시 버킷 단위로 대략 빈도를 모은다.

 

방금 방법으로 왜 후보를 줄일 수 있는지

 

Lk로부터 Ck+1 후보를 만들 때 그냥 다 만드는 게 아니라 먼저 해시 테이블을 보고 각 후보가 속하는 bucket의 count를 확인한다 ... 그 bucket 전체 count조차 min_sup보다 작으면 그 버킷 안에 있는 어떤 itemset도 support가 min_sup 이상일 수 없기 때문이야. 즉, bucket count < min_sup 이면 그 bucket 소속 후보는 전부 탈락 그래서 후보 개수를 줄이는 데 효과적이다.

 

 

Apriori는 그냥 L1에서 만들 수 있는 2-itemset 후보를 다 만드는데, DHP는 해시 테이블 보고 일부는 안 만든다.

같은 DB라도 Apriori는 가능한 후보를 더 많이 만들고, DHP는 hash pruning으로 불필요한 후보를 미리 제거한다. 즉, DHP의 장점은 candidate explosion 완화이다..

 

힝구... 진짜 아직 배워본적 없는 과목이라 그런지 내용이 좀 어렵네.. (과제도 나왔으니 이번주 데사를 열심히 해볼 예정)

 

교수님 찐으로 설명 잘해주심! 2배속으로 봤는데 (졸고 봤는데도 ㅋㅋ) 바로 다 이해감 ㅋㅋ