카테고리 338 [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. Frequent Pattern, Association Rules Frequent Pattern, Association Rules Minimum support를 만족하는 pattern을 frequent pattern이라 한다. Frequent pattern들 간의 관계를 rule이라 한다. Rule 중에서 minimum confidence를 만족하는 rule을 association rule이라 한다. Support Itemset X의 support는 전체 transaction DB에서 X가 얼마나 나타났는지를 의미한다. 비율이 될 수도 있고 카운팅 횟수가 될 수 있다. 이는 정하는 마음이다. Minimum support를 threshold로 삼아서 이보다 큰 support를 가져야만 frequent pattern이 될 수 있다. frquent pattern = $sup.. 2022. 4. 16. 이전 1 ··· 28 29 30 31 32 33 34 ··· 68 다음
