9 minute read

추천 시스템의 알고리즘을 알아보고, 고전적인 방법 연관 규칙 분석과 컨텐츠 기반 추천에 대해 알아보자.

추천 시스템 2

연관 규칙 분석(Association Rule Analysis, Association Rule Mining)

  • 흔히 장바구니 분석 혹은 서열 분석이라고도 불림
  • 주어진 데이터에 대해서, 하나의 상품이 등장했을때 다른 상품이 같이 등장하는 규칙을 찾는 것.

연관 규칙과 Itemset

  • 규칙 : IF (condition) THEN (result)
    • {condition} -> {result}의 형식으로 표현
  • 연관 규칙 : IF (antecedent) THEN (consequent)
    • 특정 사건이 발생했을 때 함께 빈번하게 발생하는 또 다른 사건의 규칙을 의미
  • Itemset : antecedent와 consequent 각각을 구성하는 상품들의 집합
    • antecedent와 consequent는 disjoint(서로소)를 만족한다.

반발 집합(Frequent Itemset)

itemset

  • Itemset
    • 1개 이상의 item의 집합
    • K-itemset : k개의 item으로 이루어진 itemset
  • support count(\(\sigma\))
    • 전체 transaction data에서 itemset이 등장하는 횟수
    • \[\sigma({빵,우유}) = 3\]
  • support
    • itemset이 전체 transaction data에서 등장하는 비율
    • support({빵, 우유}) = 3/5 = 0.6
  • frequent itemset
    • 유저가 지정한 minimum support 값 이상의 itemset을 의미
    • frequent itemset은 반대로 유저가 지정한 minimum support보다 작은 itemset을 의미

연관 규칙 척도

  • frequent itemset들 사이의 연관규칙을 만들기 위해서는 measurement가 필요!
    • X -> Y 가 존재할 때, (X, Y : itemset, N : 전체 transaction 수)

support

  • 두 itemset X,Y 를 모두 포함하는 transaction의 비율. 즉, 전체 transaction에 대한 itemset의 확률값
  • 좋은(빈도가 높거나, 구성 비율이 좋은)규칙을 찾거나, 불필요한 연산을 줄일 때 사용됨.
  • \(s(X) = \frac{n(X)}{N} = P(X)\), \(s(X\to Y) = \frac{n(X\cup Y)}{N} = P(X\cap Y)\)

confidence

  • X가 포함된 transaction 가운데 Y도 포함하는 transaction 비율(Y의 X에 대한 조건부 확률) confidence가 높을수록 유용한 규칙을 뜻함
  • \[c(X\to Y) = \frac{n(X\cup Y)}{n(X)} = \frac{s(X\to Y)}{s(X)} = \frac{P(X\cap Y)}{P(X)} = P(Y|X)\]

lift

  • [X가 포함된 transaction 가운데 Y가 등장할 확률] / [Y가 등장할 확률]
  • lift = 1 -> X,Y는 독립
  • lift > 1 -> X,Y가 양의 상관관계를 가짐, lift < 1 ->X,Y가 음의 상관관계를 가짐
  • \[l(X\to Y) = \frac{P(Y|X)}{P(Y)} = \frac{P(X\cup Y)}{P(X)P(Y)} = \frac{s(X\to Y)}{s(X)s(Y)} = \frac{x(X\to Y)}{s(Y)}\]

예시

itemset

사용방법

  • Item의 수가 많아질수록, 가능한 itemset에 대한 rule의 수가 기하급수적으로 많아진다.
    • 이 중 유의미한 Rule만 사용해야 함
  • <사용법>
    1. minimum support, minimum confidence로 의미없는 rule을 screen out
      • 전체 transaction중 너무 적게 등장하거나, 조건부 확률이 아주 낮은 rule을 필터링하기 위함
    2. lift값으로 내림차순 정렬을 하여 의미 있는 rule을 평가함.
      • lift가 크다는 것은 rule을 구성하는 antecedent와 consequent가 연관성이 높고 유의미하다는 뜻.

연관 규칙의 탐색

Mining Association Rules

  • 주어진 트랜잭션 가운, 아래 조건을 만족하는 가능한 모든 연관 규칙을 찾는다.
    • support >= minimum support
    • confidence >= minimum confidence

Brute-force approach

  • 가능한 모든 연관 규칙을 나열한다.
  • 모든 연관 규칙에 대해서 개별 support와 confidence를 계산한다.
  • minimum support, confidence를 만족하는 rule만 남기고 모두 Pruning한다.
  • -> 모든 연관 규칙을 찾으려면 엄청난 계산량이 요구된다.
  • Complexity ~ O(NWM), \(M = 2^d\)(d: number of unique items)
  • exponential하게 증가하기 때문에 거의 불가능한 일이다.

효율적인 Association Rule Mining

  1. Frequent Itemset Generation
    • minimum support 이상의 모든 itemset을 생성한다.
  2. Rule Generation
    • minimum confidence 이상의 association rule을 생성한다.
    • 이때 rule을 이루는 antecedent와 consequent는 서로소를 만족해야한다.

1번 task의 computation cost가 가장 크다

Frequent Itemset Generation Strategies

  • Apriori 알고리즘 - 가능한 후보 itemset의 개수를 줄인다(M을 줄임)
  • DHP 알고리즘 - 탐색하는 transaction의 숫자를 줄인다.(N을 줄임)
  • FP-Growth 알고리즘 - 탐색 횟수를 줄인다. (NM을 줄임)

TF-IDF를 활용한 컨텐츠 기반 추천

컨텐츠 기반 추천(Content-based Recommendation)

  • 유저 x가 과거에 선호한 아이템과 비슷한 아이템을 유저 x에게 추천.

itemset by boostcamp

유저가 좋아하는 아이템을 분석해 User Profile을 만들고(위 그림에서 빨강, 삼각형, 원을) 관련된 아이템을 유저에게 추천해준다.

  • 장점
    • 유저에게 추천할 때 다른 유저의 데이터가 필요하지 않는다.
    • 새로운 아이템 혹은 인기도가 낮은 아이템을 추천할 수 있음
    • 추천 아이템에 대한 설명이 가능하다.
  • 단점
    • 아이템의 적합한 피쳐를 찾는 것이 어렵다
    • 한 분야/장르의 추천 결과만 계속 나온다(ocerspecialization)
    • 다른 유저의 데이터를 활용할 수 없다.

Item Profile

  • 추천 대상이 되는 아이템의 feature들로 구성된 item profile을 만들어야 함
    • ex) 영화 : 작가, 제목, 배우, 장르, 감독 등
  • 아이템이 가진 다양한 속성(feature)를 어떻게 표현하면 가장 편할까? -> Vector 형태
    • 하나의 feature가 1개 이상의 vector dimension에 표현됨
    • vector는 이진값(0또는 1) 혹은 실수값을 구성됨.

TF-IDF for Text feature

  • 문서의 경우, 중요한 단어들의 집합으로 표현할 수 있음.
  • 중요한 단어를 선정하는 방법
    • 단어에 대한 중요도를 나타내는 스코어가 필요 -> 가장 많이 쓰는 기본적인 방법 TF-IDF
  • TF-IDF(Term Frequency - Inverse Document Frequency)
    • 단어 d에 등장하는 단어 w에 대해서,
    • 단어 w가 문서 d에 많이 등장하면서(Term Frequency, TF)
    • 단어 w가 전체 문서(D)에서는 적게 등장하는 단어라면(Inverse Document Frequency, IDF)
    • 단어 w는 문서 d를 설명하는 중요한 feature로, TF-IDF 값이 높음!

TF-IDF Formula

TF-IDF(w,d) = TF(w,d)*IDF(w)

  • TF : 단어 w가 문서 d에 등장하는 횟수
    • TF(w,d) = \(freq_{w,d}\)
    • TF(w,d) = \(\frac{freq_{w,d}}{\max_k(freq_{k,d})}\)
  • IDF : 전체 문서 가운데 단어 w가 등장한 비율의 역수
    • IDF(w) = \(\log\frac{N}{n_w}\) (N: 전체 문서 개수, \(n_w\) : w가 등장한 문서의 개수)
    • IDF 값의 변화가 크기 때문에 smoothing을 위해 로그 사용.
  • 예시 itemset by boostcamp
    • 각 word에 대한 IDF를 구하여 TF값을 곱해 TF-IDF를 구하여 채워 놓은 것.
    • 단어의 개수가 6개인 경우 vector는 6차원 값이 된다.

Build User Profile

  • Item Profile을 모두 구축 했으니 User Profile을 구축이 필요

User Profile

  • 유저가 과거에 선호했던 Item List가 있고 개별 Item은 TF-IDF를 통해 벡터로 표현됨
  • 각 유저의 Item List 안에 있는 Item의 Vector들을 통합하면 User Profile이 됨.
  • 앞선 그림에서 유저가 d1,d3를 선호했다면 유저의 프로파일 벡터는 \(\frac{V_{d1}+V_{d3}}{2}\)로 간단하게 나타낼 수 있으며, 문서에 가중치가 주어진다면 vector는 \(\frac{r_{d1}V_{d1}+r_{d1}V_{d3}}{r_{d1}+r_{d2}}\)로 나타낼 수 있다.

Cosine Similarity

주어진 두 벡터 X,Y에 대하여,

  • \[\cos(\theta) = \cos(X,Y) = \frac{X\cdot Y}{\left| X \right|\left| Y \right|} = \frac{\sum_{i=1}^{N}X_i Y_i}{\sqrt{\sum_{i=1}^{N}X_i^2}\sum_{i=1}^{N}Y_i^2}\]
  • 두 차원이 같아야 한다.
  • 직관적으로 두 벡터가 가리키는 방향이 얼마나 유사한지를 의미한다.
    • 비슷할수록 1, 반대일수록 -1에 가깝다.

유저와 아이템 사이의 거리 계산하기

유저 벡터 u와 아이템 벡터 i에 대해서 아래와 같은 거리를 계산

  • \[score(u,i) = cos(u,i) = \frac{u \cdot i}{\left| u \right| \cdot \left| i \right|}\]
    • 둘의 유사도가 클수록 해당 아이템이 유저에게 관련성이 높다
    • score(u,i)가 가장 높은 아이템부터 유저에게 추천함

-> 만약 유저 u가 i에 대해 가질 선호도를 정확하게 예측하고 싶다면.

Rating 예측하기

유저가 선호하는 아이템의 Vector를 활용하여 정확한 평점 예측하기

  • 유저 u가 선호하는 아이템 N개의 벡터와, N개의 item vector가 있을 때 평점이 \(r_{u,i}\)일 때, 새로운 아이템\(i^{\prime}\)에 대하여 평점을 예측해보자.
  • \(i^{\prime}\)와 i의 유사도 :
    • \[sim(i, i^{\prime}) = \cos(v_i, v_i^{\prime})\]
  • \(sim(i, i^{\prime})\) 를 가중치로 사용하여 \(i^{\prime}\)의 평점을 추론:
    • \[prediction(i^{\prime}) = \frac{\sum_{i=1}^{N}sim(i, i^{\prime})\cdot r_{u,i}}{\sum_{i=1}^{N}sim(i, i^{\prime})}\]
  • 예시 itemset by boostcamp

Comments

You May Also Enjoy