Computer Science/Data Science 86 [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. [Frequent Pattern Mining] Apriori Algorithm Apriori Algorithm A Candidate Generation-and-Test Approach Candidate를 만들고 테스트하는 과정을 거치며 frequent pattern을 찾는 알고리즘이다. 다만 과정 중에 pruning을 통해 경우의 수를 줄인다. Pruning Principle Downward closure property의 대우를 이용한다. Frequent 하지 않은(infrequent) itemset을 포함하는 superset은 generation/test하지 않는다. 과정 DB를 scan하며 1개짜리 frequent itmeset을 생성한다. k-frequent($L_k$)를 이용하여 (k+1) 길이의 candidate itmesets($C_{k+1}$)을 생성한다. Self-.. 2022. 4. 16. 이전 1 ··· 13 14 15 16 17 18 다음
