728x90 반응형 Apriori Principle2 [Data Science] Association Rule Mining (3) - Apriori + Hash Tree 이전 포스트(https://trivia-starage.tistory.com/88)에서 Brute-force의 성능을 높일 수 있는 방법 중 3번째에 대해서 설명해본다. Support ContingDB를 scan해서 각 candidate itemset이 support여부를 확인하는 방법이다.그런데 각 transaction이 모든 candidate에 matching여부를 확인하기 위해 모든 candidate를 순회하는 문제가 발생한다.이 때 비교횟수를 줄이기 위해 해시 기반 자료구조를 활용한다.길이가 3인 15개의 candidate itemset이 있다고 하자.{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {.. 2023. 4. 2. [Data Science] Association Rule Mining (2) - Apriori principle Review of Frequent Itemset Mining by Brute-force approachBrute-force에서 우리가 시간을 줄일 수 있는 방법을 살펴보자.(1) $M$ 줄이기pruning을 이용하여 필요없는 후보 itemset을 지워버린다. (2) $N$ 줄이기DHP알고리즘이나 vertical-based mining algorithm으로 해결할 수 있다.그러나 교재에서 다루지 않으므로 생략. (3) $MN$ 줄이기해시테이블과 같은 효율적인 자료구조를 이용하여 candidate나 transaction을 저장한다. 모든 candidate를 모든 transaction과 비교할 이유가 없다. Apriori principle어떤 itemset이 frequent하다면, 그 부분집합 subset도 .. 2023. 4. 1. 이전 1 다음 728x90 반응형
