Today I Learned

오늘 배운 내용은 CBF 방법인 TF-IDF와

컨텐츠 기반 추천 (CBF)

유저가 과거에 선호한 아이템과 비슷한 아이템을 그 유저에게 추천하는 방식
ex) 장르, 주제, 같은 감독, 같은 배우 등..

• 아이템의 특성을 기반으로 추천하기 때문에 아이템의 메타데이터가 중요하다. 아이템간 유사도 계산을 활용한다. 유저와 아이템의 프로파일 생성이 중요하다.

• 다른 유저의 데이터가 필요없고 추천에 대한 설명이 가능하며 새로운 아이템이나 인기가 적은 아이템을 추천할 수 있다.

• 한 장르의 추천 결과만 계속 나올 수 있고(overspecialization), 프로파일 생성에 시간이 오래 걸린다.

TF-IDF

문서 내 단어의 중요도를 수치화하는 방법.
이를통해 아이템(문서) 간 유사도를 측정할 수 있다.
(단어 w, 문서 d, 전체문서 D)

• TF (Term Frequency, 단어 빈도): 특정 문서 내에서 단어가 출현한 빈도. 문서 내의 중요도를 반영한다.
  frequency를 그대로 쓰거나 normalize 해서 사용.

• IDF (Inverse Document Frequency, 역문서 빈도): 전체 문서 집합에서 특정 단어의 희소성. 흔한 단어면 가중치를 감소한다. 아래처럼 log로 smoothing해서 사용한다.
  IDF(w) = log(전체 문서 수/단어가 포함된 문서 수)

• TF-IDF = TF x IDF = 전체 문서에서는 잘 안나오지만 특정 문서에서 많이 나오는 단어 수치화!

• 전체 TF-IDF를 구하면 문서 하나당 단어 vector가 생성된다. 이를 item profile로 본다.

• 유저가 어떤 문서를 선호한다면 그 문서의 단어 vector(item profile)을 이용해서 단순히 평균내거나(simple vector) 가중평균을 내서(variant vector) 벡터 형식의 user profile을 만들 수 있다.

• 코사인 유사도
  두 벡터의 각도를 이용해서 유사도를 측정할 수 있다.
  직관적으로 두 벡터가 가리키는 방향이 얼마나 유사한지 -1~1로 표현한다.

• 유저와 아이템간 score를 측정하려면 코사인 유사도를 이용해서 유저벡터 u와 아이템 벡터 i의 유사도를 측정한다. score(u,i) = cos(u,i)

연관 분석

Association Rule Analysis, 장바구니 분석이나 서열분석이라고도 한다.

• 장바구니에 어떤 물건을 같이 담는지 규칙을 찾는 과정에서 시작.
  연속된 거래들 사이의 규칙을 찾는다.

• A면 B다라는 규칙을 찾는다. A(선행항)->B(결과항) / 여기서 ->는 인과관계는 아니다.
  ex) 햇반 -> 김치

• 규칙중에 빈번하게 발생하는 규칙들을 연관 규칙이라 한다.
  IF (antecedent) THEN (consequent)

• itemset은 한 거래에서 antecedent와 consequent를 각각 구성하는 상품의 집합으로, 두 집합은 서로소를 만족한다.

• 빈발 집합(Frequent itemset)
  유저가 지정한 minimum support 이상의 itemset

척도

• Support(지지도)
  itemset이 전체 거래에 등장하는 비율
  ex) 전체 거래에서 {우유,시리얼}이 등장하는 비율 = support({우유,시리얼}) = 6/10 = 0.6
  support(A->B) = P(AnB) : 규칙의 지지도는 각각의 교집합 확률로 나타낼 수 있다.

• Confidence(신뢰도) : 조건부 확률. 이게 높을수록 유용한 규칙이다.
  Confidence(시리얼→우유) = P(우유|시리얼) : 시리얼을 샀을때 우유를 살 확률
  Confidence(A→B) = P(B|A) = Support(A→B) / Support(A)

• lift(향상도)
  lift=1이면 독립(A,B가 서로 영향 x).
  lift>1이면 A,B가 양의 상관관계, lift<1이면 음의 상관관계.
  lift가 크면 antecent와 consequent가 연관성이 높고 유의미한 관계라는 뜻.

• 척도 사용 방법
  minimum support, minimum confidence를 생성해 의미없는 rule을 걸러낸다.
  그리고, lift로 내림차순 sort해서 의미 있는 rule을 평가한다.

연관 규칙 탐색

• 위의 방법을 적용해 일치하는 연관규칙을 탐색하는 것이 가장 어려운 부분으로 여러 방법이 있다.

• 모든 연관 규칙을 나열해서 support와 confidence를 다 계산하는 brute-force 방식은 계산량이 매우 많다. 시간복잡도는 O(NWM)으로 M이 $2^d$이기 때문에 거의 사실상 불가능하다. 그래서 아래의 알고리즘들로 효율적인 탐색을 한다.

1. Apriori 알고리즘으로 itemset의 후보를 줄인다(M 감소)
2. DHP 알고리즘으로 탐색해야 하는 transaction 감소(N 감소)
3. FP-Growth 알고리즘으로 모든 조합을 탐색하지 않고 탐색 횟수 감소(NM 감소)