Computer Science 254 [Frequent Pattern Mining] CHARM (using Vertical Data Format) CHARM Vertical data format을 이용하여 mining하는 방법이다. Vertical Format Vertical format이란 $t(AB) = \{T_{11}, T_{25}, ...\}$와 같은 형태이다. $t(AB)$는 itemset AB를 포함하는 모든 transaction의 tid-list를 의미한다. * 지금까지 표현한 transaction DB는 horizontal format이다. 방법 Horizontal format을 vertical format으로 바꾼다. k=1부터 시작해서 frequent k-itemset으로부터 cadidate (k+1)-itemset을 생성한다. TID-sets intersection과 apriori property를 이용한다. A와 B를 가지고 .. 2022. 4. 17. [Closed Pattern Mining] CLOSET CLOSET Closed pattern을 mining하는 방법이다. Closed Pattern 아래 조건을 만족하는 itemset Y가 존재하지 않을 때 X는 closed pattern이다. Y는 X의 superset이다. Y의 support와 X의 support가 같다. Navie한 방법 모든 frequent itemset을 찾고 각 itemset에 대해 그 superset과 같은 support를 가지는 itemset을 제거한다. 그러나 frequent pattern의 수는 많기 때문에 freqent pattern을 찾는 것, 그 superset을 찾고 support를 비교하는 것 등 모든 것에 대해 cost가 비싸다. 방법 FP-tree를 이용하면 낮은 cost로 closed itemset만 recu.. 2022. 4. 17. [Max Pattern Mining] MaxMiner MaxMiner Max pattern을 mining하는 알고리즘이다. Max-pattern 아래 조건을 만족하는 Y가 없을 때 frequent pattern X를 max-pattern이라 한다. Y는 X를 포함하는 superset이다. Y는 frequent하다. (X의 sup보다 작아도 상관없음) MaxMiner 방법 2번의 DB scan으로 max-pattern을 찾을 수 있다. Scan 1 frequent item을 찾고 오름차순으로 정렬한다. (sup 작은 순 → 큰 순) 모든 가능한 2-itemset을 생성하고 potential max-pattern을 찾는다. 생성할 때 내부의 정렬 순서를 지켜야 한다. potential max-pattern 각 item으로 시작할 수 있는 가장 긴 패턴 set-.. 2022. 4. 17. [Frequent Pattern Mining] FP-Growth (using FP-Tree) FP-Growth = Frequent Pattern Growth Candidate genration 과정 없이 frequent pattern mining을 수행한다. FP-Growth는 transaction DB를 FP-Tree로 만들고 통해 이를 이용해서 frequent pattern을 만든다. FP-Tree를 생성해서 frequent pattern을 구하기 때문에 DB scan은 2번만 발생한다. 기본 원리 Local frequent item을 이용해서 짧은 것을 통해 긴 패턴을 생성해낸다. 즉, frequent pattern을 recursion을 통해 점진적으로 증가시키는 원리이다. 기존에 발견된 frequent pattern(A)를 가지고 있는 transaction들 안에서 새로운 frequent.. 2022. 4. 17. [Frequent Data Mining] Reduce DB Scan and Candidates Apriori의 문제점과 해결 Apriori의 문제점 Transaction DB scan 횟수가 너무 많다. → partition, sampling 이용 생성되는 candidate의 수가 너무 많다. → DHP 이용 support counting에 대한 cost가 높다. → DIC 이용 Reduce DB Scan and Candidates Partition : DB scan 횟수 줄이기 $\rightarrow$ 2번만 scan DHP : Candidate 수 줄이기 $\rightarrow$ hash table 이용 Sampling : DB Scan 횟수 줄이기 $\rightarrow$ 1 + 2번 scan DIC : support를 구하는 cost 줄이기 $\rightarrow$ 병렬 scan Parti.. 2022. 4. 16. 이전 1 ··· 22 23 24 25 26 27 28 ··· 51 다음
