본문 바로가기
728x90
반응형

전체 글266

[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.
공분산과 상관계수, Covariance and Correlation 두 확률변수의 관계를 나타내는 공분산(covariance)에 대해 알아보자.Covariance, 공분산두 확률변수 $X, Y$의 기댓값을 각각 $\mu_X, \mu_Y$라 할 때, 공분산은 다음과 같이 정의한다.\[ Cov(X, Y) = E\left[ (X-\mu_X)(Y-\mu_Y) \right] \]위 식을 전개하여 정리하면, 다음과 동일한 식을 얻을 수 있다.\[ Cov(X, Y) = E(XY) - E(X)E(Y) \]Note: 공분산의 값의 범위는 $(-\infty, \infty)$이다.Note: 공분산은 두 확률변수의 선형 관계(linear relationship)만 파악할 수 있다.Note: $Cov(X, X) = Var(X)$ 이다. Linearlity of covariance, 공분산의 선.. 2023. 3. 31.
728x90
반응형