본문 바로가기
728x90
반응형

frequent itemsets4

[CS246] Frequent Itemsets: SON, Toivonen Algorithm Recap: Frequent Itemsets & Intro.A-Priori, PCY, Multistage, Multihash 알고리즘을 이용하면 결국 크기가 $k$인 frequent itemset을 얻기 위해서 $k$번 반복해야한다. 물론 일부는 frequent pair에 특화되어있지만 결국 $k$번 반복하는 것은 동일하다. 이번 포스팅에서는 pass 수가 2번 이하인 알고리즘을 알아보자. 크게 3가지 방법이 알려져있다.Random sampling (random sampling은 대규모 데이터셋에서 효과적이다. 무시하지 말기)ToivonenSON (Savasere, Omiecinski, Navathe) Random Samplingmarket basket에 대하여 랜덤 샘플링(무작위 표본 추출법)을 적용하.. 2023. 9. 15.
[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.
[CS246] Frequent Itemsets Mining & Association Rules Market-Basket Model우리는 association rule을 찾고 싶다. Amazon과 같은 곳에서 어떤 사람이 $\{ x,y,z \}$를 샀다면, $\{ v,w \}$ 도 사는 경향을 찾고 싶을 것이다. 위 그림을 예시로 할 때, 2개의 rule을 찾을 수 있다. {milk} -> {coke}, {diaper, milk} -> {beer}Applications item과 basket은 반드시 상품과 바구니일 필요가 없다. 추상화된 데이터 형태라고 생각하면 다양한 응용이 가능하다. Supermarketitems=상품, basket=상품 집합 Topic discoveryitems=단어(word), basket=문서(document) Plagiarismitem=문서(documents), bask.. 2023. 9. 11.
728x90
반응형

티스토리툴바