728x90 반응형 data science42 [Data Science] Association Rule Mining (6) Interesting Measures Basketball과 Cereal을 각각 $B$, $C$라고 표기하자. 이때 rule의 sup과 conf를 튜플로 표기하면$B \to C$ = [40%, 66.7%] 이다. 그러나 실제 시리얼을 먹는 학생의 비율은 3750/5000=75%로 confidence보다 크다. 심지어 $B$ 없이도 $C$의 비율은 $P(C)=0.75$로 rule $B \to C$는 informative하지 않는다. 심지어 rule $B \to \neg C$ = [20%, 33.3%]는 sup과 conf 모두 낮지만, $P(\neg C | B) = 1750/2000$으로 확률의 측면에서 도 정확하다고 할 수 있다. (more informative) 즉, support와 confidence는 association에는 유용하지만, .. 2023. 4. 3. [Data Science] Association Rule Mining (5) Rule Generation 앞서 Apriori 또는 FP-Growth 알고리즘을 이용하여 Frequent Itemset Mining을 할 수 있다. 이제 mining하여 얻은 pattern들로 rule을 생성할 것이다. Rule Generationfrequent itemset $L$의 모든 (공집합이 아닌) 모든 부분집합 $f$을 찾을 것이다. ($f \to L - f$)위에서 보듯이, $|L|=k$라면 가능한 모든 candidate association은 $2^k -2$개가 있다. ($L \to \varnothing$ 와 $\varnothing \to L$은 제외)보다 효과적으로 rule을 생성할 수 없을까? Anti-monotone property of Confidence일반적으로 서로 다른 rule에 대하여 confidenc.. 2023. 4. 3. [Data Science] Association Rule Mining (4) FP-Growth 이번 글에서는 FP-Tree를 이용한 FP-Growth 알고리즘을 이용하여 frequent itemset mining을 해보자. MotivationApriori principle의 마지막에서 서술했듯이, DB scan을 계속 반복해야하는 단점이 있다. 이는 여전히 비용이 큰 요소이다.게다가 패턴이 긴 경우(long pattern) 은 DB scan을 반복하는것은 물론이고 candidate가 굉장히 많아진다는 문제가 있다. 결국 문제는 candidate generation이다!! Heuristic$P$가 frequent itemset이고, $S$가 $P$를 포함하는 transaction 집합이고 $x$가 item이라 하자. 이때 $x \in S$라면 $\{ x \} \cup P$ 역시 frequent it.. 2023. 4. 2. [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. [Data Science] Association Rule Mining (1) - Introduction Motivation구글이나 네이버같은 검색엔진에 검색어를 입력하면 자동완성이 되는 것도 일종의 association rule(연관 규칙)에 기반한 추천이다. Association Rule Mining아래와 같은 거래 데이터베이스 (transaction data)가 있다고 하자. 여기서 알 수 있는 association rule은 우측 그림과 같다.여기서의 association rule은기저귀를 구매한 사람은 맥주도 구매한다. (아기 아빠는 피곤해서 맥주가 필요한 것일까? 🤣🤣)우유와 빵을 구매한 사람은 달걀과 콜라도 구매한다.맥주와 빵을 구매한 사람은 우유를 구매한다.이렇게 association rule을 찾는 알고리즘은 크게 Apriori, FP-Growth 2가지 알고리즘이 있다. Frequent.. 2023. 4. 1. 이전 1 ··· 3 4 5 6 7 다음 728x90 반응형
