본문 바로가기
728x90
반응형

Apriori5

[CS246] PCY, Multistage, Multihash Algorithm Recap: A-PrioriA-Priori 알고리즘은 2-pass 알고리즘이다. pass1에서는 아이템을 스캔하여 개수를 저장하고, pass2에서 candidate frequent pairs ($C_2$)를 찾는다. 각 $C_k$로부터 truly frequent itemsets $L_k$를 찾는 과정을 반복한다.이렇게 크기가 $k$인 frequent itemsets $L_k$를 통해 association rule을 찾을 수 있다. 그러나 $C_2$ 역시 너무 커서 main memory에 들어가지 않으면? 이 문제를 해결하는 알고리즘이 PCY, multistage, multihash 이다. PCY AlgorithmA-Priori의 pass1에서 사용되지 않는 main-memory가 너무 많다. 이렇게 사용.. 2023. 9. 14.
[CS246] A-Priori Algorithm: Finding Frequent Itemsets Recap: Frequent Itemsets Mining and Association Rulefrequent itemset, association rule에 대해 이전 포스팅을 참고한다. (frequent itemset이 주어졌을 때, association rule을 만드는 방법이다.) https://trivia-starage.tistory.com/181 [CS26] Frequent Itemsets Mining & Association RulesMarket-Basket Model 우리는 association rule을 찾고 싶다. Amazon과 같은 곳에서 어떤 사람이 $\{ x,y,z \}$를 샀다면, $\{ v,w \}$ 도 사는 경향을 찾고 싶을 것이다. 위 그림을 예시로 할 때, 2개의 rule을.. 2023. 9. 12.
[Data Science] Association Rule Mining - Excercises Transaction Data Setup5개의 거래가 있는 아래 데이터에 대하여, min_sup=60%, min_conf=80%라 하자.전체 transaction data가 5개이므로, min_sup 60% = 3개이다.(1) Apriori먼저 1-frequent itemset을 만들고 min_sup=3이 안되는 아이템을 지워 ($L_1$)을 만들자 $L_1$으로 self-join을 하여(임시 $C_2$)를 구한다. 그리고 $L_1$에 없는 아이템이 있다면(이 경우에는 없다) 그 후보는 pruning하여 $C_2$를 구한다.이렇게 구한 $C_2$ 중에서 min_sup=3 이상이 되는 itemset만 남겨 $L_2$를 만든다.$L_2$를 self-join을 하면 다음과 같다.그런데 {M, O, K}의 경우.. 2023. 4. 17.
[Data Science] Association Rule Mining (7) mlxtend로 association rule을 만들어보자 앞의 포스팅에서 배운 association rule mining 알고리즘을 mlxtend 패키지를 이용하여 활용해보자.pip install mlxtend TransactionEncoder()sklearn의 OneHotEncoder, LabelEncoder 등과 거의 유사한 Encoder 클래스이다.transaction data를 numpy array로 인코딩해준다.import pandas as pdfrom mlxtend.preprocessing import TransactionEncoderdataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'], ['Dill', 'Onion', 'Nutmeg', 'Kidney Be.. 2023. 4. 4.
[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.
728x90
반응형

티스토리툴바