카테고리 339 [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. Frequent Pattern Mining Frequent Pattern Mining Frequent Pattern이란 Frequent pattern이란 주어진 데이터에서 빈번하게 발생하는 패턴이다. Frequent pattern으로 set of iterms(순서 의미 없음), subsequences(순서가 의미 있는 나열), substructures(그래프의 구조 등)이 될 수 있다. Frequent Pattern Analysis 데이터 속에서 빈번하게 발생하는 패턴을 찾는 테스크이다. 거래 내역(transaction)에서 어떤 상품들이 함께 구매되는가, PC를 산 뒤에 어떤 상품이 다음에 구매되는가 등을 찾는 과정이다. Basket data analysis(장바구니 분석), cross-marketing, catalog design, web l.. 2022. 4. 16. 이전 1 ··· 28 29 30 31 32 33 34 ··· 68 다음
