연관 분석과 TF-IDF를 활용한 콘텐츠 기반 추천

 

2022년 3월 7일(월)부터 11일(금)까지 네이버 부스트캠프(boostcamp) AI Tech 강의를 들으면서 중요하다고 생각되거나 짚고 넘어가야 할 핵심 내용들만 간단하게 메모한 내용입니다. 틀리거나 설명이 부족한 내용이 있을 수 있으며, 이는 학습을 진행하면서 꾸준히 내용을 수정하거나 추가해나갈 예정입니다. 강의 자료의 저작권은 네이버 커넥트재단 부스트캠프 AI Tech에 있습니다.

 

 

추천 시스템 기법

딥러닝 모델 기반의 추천 시스템을 사용하는 건 CV, NLP 보다는 중요성이 떨어진다.

현업에서는 무거운 딥러닝 모델의 트래픽, latency 등 현실적인 문제로 인해 클래식한 머신러닝 모델도 많이 사용한다.

 

연관 분석

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

흔히 장바구니 분석 또는 서열 분석이라고도 불리며, 상품의 구매, 조회 등 하나의 연속된 거래들 사이의 규칙을 발견하기 위해 적용하는 방법이다.

 

Transaction	Items
1	{Next Level, Savage}
2	{Next Level, 4 walls, INVU, Better}
3	{Savage, 4 walls, INVU, Queendom}
4	{Next Level, Savage, 4 walls, INVU}
5	{Next Level, Savage, 4 walls, Queendom}

 

[연관 규칙 예시]

{4 walls} → {INVU}

{Next Level, Savage} → {Better}

 

주어진 거래(transaction) 데이터에 관하여 하나의 상품이 등장했을 때 다른 상품이 같이 등장하는 규칙을 찾는 것이다.

단, 연관 규칙에서의 화살표는 일종의 annotation이지 인과 관계를 의미하지는 않는다.

 

 

연관 규칙(Association Rule)과 Itemset

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

 

 

빈발 집합

• itemset
  • 1개 이상의 item 집합
  • k-itemset: k개의 item으로 이루어진 itemset
• support count($\sigma$)
  • 전체 transaction data에서 특정 itemset이 등장하는 횟수
• support(지지도)
  • 특정 itemset이 전체 transaction data에서 등장하는 비율
• frequent itemset
  • 유저가 지정한 minimum support 값 이상의 itemset을 의미한다.
• Infrequent itemset
  • 유저가 지정한 minimum support 값보다 작은 itemset을 의미한다.

 

 

연관 규칙의 척도

Frequent itemset들 사이의 연관 규칙을 만들기 위해서는 척도(measurement)가 필요하다.

$X \rightarrow Y$가 존재하는 것을 전제로 한다. ($X$, $Y$: itemset, $N$: 전체 transaction 수)

 

Support(지지도)

두 itemset $X$, $Y$를 모두 포함하는 transaction의 비율을 의미한다.

전체 transaction에 대한 itemset의 확률값이다.

빈도가 높거나 구성 비율이 높은 규칙을 찾거나, 불필요한 연산을 줄일 때 사용한다.

$$ s(X) = \frac{n(X)}{N} = P(X) $$

$$ s(X \rightarrow Y) = \frac{n(X \cup Y)}{N} = P(X \cap Y) $$

전체 transaction 중에서 $X$와 $Y$가 모두 등장하는 transaction의 비율을 의미한다.

 

Confidence(신뢰도)

$X$가 포함된 transaction 가운데 $Y$도 포함하는 transaction의 비율, 즉 $X$에 대한 $Y$의 조건부 확률을 의미한다.

Confidence가 높을수록 유용한 규칙을 뜻한다.

$$ c(X \rightarrow Y) = \frac{n(X \cup Y)}{n(X)} = \frac{s(X \rightarrow Y)}{s(X)} = \frac{P(X \cap Y)}{P(X)} = P(Y|X) $$

Lift(향상도)

$X$가 포함된 transaction 가운데 $Y$가 등장할 확률을 전체에서 $Y$가 등장할 확률로 나눈 것이다.

$$ l(X \rightarrow Y) = \frac{P(Y|X)}{P(Y)} = \frac{P(X \cap Y)}{P(X) P(Y)} = \frac{s(X \rightarrow Y)}{s(X) s(Y)} = \frac{c(X \rightarrow Y)}{s(Y)} $$

Lift는 support와 confidence와는 다르게 0과 1사이의 값만을 가지지는 않는다.

Llift가 1일 때, $X$, $Y$는 독립을 의미하고, Lift가 1보다 크면 $X$, $Y$가 양의 상관관계를, 1보다 작으면 음의 상관관계를 가진다.

 

 

유의미한 itemset의 rule 구하기

Item 수가 많아질수록, 가능한 itemset에 대한 rule의 수가 기하급수적으로 많아진다. 그래서 유의미한 rule만을 사용하는 것이 중요하다.

 

1. Minimum support, minimum confidence로 의미 없는 rule을 없앤다.
2. 전체 transaction 중에서 너무 적게 등장하거나, 조건부 확률이 아주 낮은 rule을 필터링하는 것이다.
3. Lift 값으로 내림차순 정렬하여 의미있는 rule을 평가한다.
4. lift가 크다는 것은 rule을 구성하는 antecedent와 consequent가 연관성이 높고 유의미하다는 것을 의미한다.

 

 

연관 규칙의 탐색

Mining Association Rules

$$ (support) \ge (\text{minimum support})\\ (confidence) \ge (\text{minimum confidence}) $$

주어진 transaction 가운데, minimum support 이상인 support와 minimum confidence 이상인 confidence를 갖는 가능한 모든 연관 규칙을 찾는다.

 

Brute-force 접근법

가능한 모든 연관 규칙을 나열하고, 모든 연관 규칙에 관해 개별 support와 confidence를 계산한 후, 조건을 만족하는 rule만 남기고 모두 pruning(가지치기)하는 것이다.

그러나 모든 연관 규칙을 찾아서 계산하기에는 엄청나게 많은 계산량이 요구되는 단점이 있다.

개별 transaction의 아이템을 풀스캔해서 가능한 모든 itemset의 support를 계산하는 시간복잡도는 $O(NWM), M = 2^{d}$가 된다.

여기서 $N$은 전체 transaction 수, $W$는 각각의 transaction의 아이템 수, M은 가능한 itemset의 개수, $d$는 unique한 아이템 수이다.

개별 transaction의 아이템을 풀스캔하는 데 걸리는 시간복잡도 $O(NW)$, 풀스캔 후 각각의 unique한 item별 아이템 셋을 만드는 경우의 수가 $2^d$(각 아이템 별로 어떤 한 아이템 셋에 들어가느냐 들어가지 않느냐 두 가지의 경우가 존재)이므로 모든 itemset의 support를 계산하는 데 걸리는 시간복잡도는 $O(2^d)$가 된다.

 

효율적인 Association Rule Mining 방법

1. Frequent Itemset Generation
2. Minimum support 이상의 모든 itemset을 생성한다.
3. Rule Generation
4. Minimum confidence 이상의 assocation rule을 생성한다.

여기서 1번 과정의 computation cost(가능한 모든 Itemset의 support를 계산하는 것)가 가장 크다.

 

Frequent Itemset 생성 전략

• 가능한 후보 itemset의 개수를 줄인다.
  • $M$의 크기를 줄이는 것
  • Apriori 알고리즘
    • 가지치기를 활용하여 탐색해야 하는 $M$을 줄인다.
• 탐색하는 transaction의 수를 줄인다.
  • $N$을 줄이는 것
  • itemset의 크기가 커짐에 따라 전체 $N$개 transaction보다 적은 수를 탐색한다.
  • DHP(Direct Hashing & Pruning) 알고리즘
• 탐색 횟수를 줄인다.
  • $NM$을 줄이는 것
  • 효율적인 자료구조를 사용하여 후보 itemset과 transaction을 저장한다.
  • 모든 Itemset과 transaction의 조합에 관하여 탐색할 필요가 없다.
  • FP(Frequent Pattern)-Growth 알고리즘 참고 자료: https://process-mining.tistory.com/92

 

 

 

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

TF-IDF는 텍스트 데이터를 다루는 가장 기본적인 방법이다.

 

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

특정 유저가 과거에 선호한 아이템과 비슷한 아이템을 해당 유저에게 추천하는 것이다.

 

장점

• 유저에게 추천할 때 다른 유저의 데이터가 필요하지 않다.
• 새로운 아이템 또는 인기도가 낮은 아이템을 추천할 수 있다.
• 추천 아이템에 대한 설명이 가능하다.

 

단점

• 아이템의 적합한 특징을 찾는 것이 어렵다.
• 한 분야 ・ 장르의 추천 결과만 계속 나올 수 있다. (Overspecialization)
• 다른 유저의 데이터를 활용할 수 없다.

 

 

Item Profile

추천 대상이 되는 아이템의 특징들로 구성된 Item profile을 만들어야 한다.

가장 쉬운 건 수학적인 vector 형태로 표현하는 것이다.

 

TF-IDF

단어에 대한 중요도를 나타내는 스코어를 TF-IDF로 구할 수 있다.

1. 문서 $d$에 등장하는 단어 $w$에 대해서
2. 단어 $w$가 문서 $d$에 많이 등장하면서 (Term Frequency, TF)
3. 단어 $w$가 전체 문서($D$)에서는 적게 등장하는 단어라면 (Inverse Document Frequency, IDF)
4. 단어 $w$는 문서 $d$를 설명하는 중요한 feature이며, TF-IDF 값이 높음을 의미한다.

 

$$ \text{TF-IDF}(w, d) = TF(w,d) \cdot IDF(w) $$

TF는 단어 $w$가 문서 $d$에 등장하는 횟수

$$ TF(w, d) = freq_{w,d}\\ TF(w, d) = \frac{(freq_{w,d})}{max_{k}(freq_{k,d})} $$

문서 $d$에서 가장 많이 등장한 단어의 등장 횟수로 나눠줘서 정규화해줄 수도 있다.

 

IDF는 전체 문서 가운데에서 단어 $w$가 등장한 비율의 역수이다.

전체 문서에서 많이 등장할수록 해당 단어의 특이성이 감소하고, 적게 등장할수록 해당 단어의 특이성이 증가한다고 보는 것이다.

$$ IDF(w) = \log{\frac{N}{n_{w}}} $$

$N$은 전체 문서의 개수, $n_{w}$는 $w$가 등장한 문서의 개수를 의미한다.

IDF 값은 변화가 크므로 smoothing을 위해 $\log$를 취한다.

TF-IDF에서 단어를 아이템으로 바꾸면 이를 콘텐츠 기반 추천으로 활용할 수 있다.

 

 

User Profile 구축하기

유저가 과거에 선호했던 item list가 있고, 개별 item은 TF-IDF를 통해 vector로 표현된다.

각 유저의 item list 안에 있는 item의 vector들을 통합하면 User Profile이 된다.

 

Simple vector

유저가 선호한 item vector들의 평균값을 사용하는 방법이다.

예를 들어, 유저가 아이템 $d_1$, $d_2$를 선호했으면 해당 유저의 Profile vector는 $\frac{v_{d1} + v_{d2}}{2}$이다.

 

Variant한 방법

유저가 아이템에 내린 선호도로 정규화한 가중치 평균값을 사용하는 방법

예를 들어, 유저가 $d_1$, $d_2$를 선호했으면 해당 유저의 Profile vector는 $\frac{r_{d1}v_{d1} + r_{d2}v_{d2}}{r_{d1} + r_{d2}}$이다.

 

 

Consine Similarity

주어진 같은 차원의 두 벡터 $X$, $Y$에 관하여, 두 벡터 사이의 각을 이용해 구할 수 있는 유사도이다.

두 벡터가 가리키는 방향이 얼마나 유사한지를 의미한다고 볼 수 있다.

$$ \cos(\theta) = \cos(X, Y) = \frac{X \cdot Y}{|X||Y|} $$

유저 벡터 $u$와 아이템 벡터 $i$에 대해서 다음과 같이 거리를 계산한다.

$$ score(u, i) = cos(u, i) = \frac{u \cdot i}{|u| \cdot |i|} $$

둘의 유사도가 클수록 해당 아이템이 유저에게 관련성이 높음을 의미한다.

 

 

Rating(평점) 예측하기

유저 $u$가 선호하는 아이템 $I = \{i_1, \cdots, i_N\}$의 아이템 vector는 $V = \{v_1, \cdots, v_N\}$, 평점은 $r_{u, i}$일 때,

새로운 아이템 $i'$에 대한 평점 예측은 다음과 같이 구한다.

$i'$와 $I$에 속한 아이템 i의 유사도를 구한다.

$$ sim(i, i') = cos(v_i, v_{i'}) $$

$sim(i, i')$를 가중치로 사용하여 $i'$의 평점을 추론한다.