Simple Recommender

#Simple-Recommender
  • 아이디어:
    '대부분의 사람들이 좋아하면 나도 좋아할 것이다'
  • 인기도에 기반하여 모든 사용자에게 똑같은 추천을 하는 방법
  • 예를 들어 음악이나 영화를 볼 때 사람들은 인기 차트를 참고

목차

#목차
  • 가중치를 통한 평점과 투표 수 반영
1
2
3
4
1) 가중 평균을 통한 보정 방법


2) 신뢰구간을 이용하여 평점과 투표수 반영
  • 최신 글일 수록 상위권에 노출하는 방법
1
2
3
4
1) Hacker News 추천 방식


2) Reddit의 추천 방식
  • 연결성에 초점을 둔 추천 방식
  • Simple Recommender의 한계

1. 가중치를 통한 평점과 투표 수 반영

#1.-가중치를-통한-평점과-투표-수-반영
  • 평점이 높은 상품이 좋은 상품일 것이다
  • 하지만 평점은 단순 평균이기 때문에 많은 사람들이 좋아하는지 반영할 수가 없음

=> 예를들어 1명이 10점을 준 영화보다 1000명이 9점을 준 영화가 더 좋은 영화일 가능성이 높음

  • 또한 영화의 전체적인 평점 역시 고려해야함

=> 전체적인 상품의 평점이 10점만점에 9점이면 높은 점수가 아님

  • 영화나 음악 검색 사이트에서 많이 사용하는 방식

@@0@@

@@1@@: 투표한 사람의 수

@@2@@: 차트에 등재 되기 위한 최소 투표 수

@@3@@: 각 상품에 대한 평점

@@4@@: 전체 평균 투표 수

  • 평균 투표 수와 평균 평점의 가중 평균으로 점수 부여
  • 최소 투표 수 @@5@@을 지정

=> @@6@@이 작을 수록 @@7@@가 낮아져 투표 한 사람이 많을 수록 상품의 평점이 많이 반영

=> @@8@@이 클 수록 @@9@@가 높아짐

데이터 소개

  • Full MovieLens 데이터셋에서 45,000개의 영화에 대한 데이터
  • 영화에 대한 사람들의 평가(평점, 투표수)와 영화에 대한 정보(장르, 개봉일 등)가 있는 데이터
Loading output library...

10점 만점에서 평균 점수는 5.61점

Loading output library...
Loading output library...

상위 10퍼센트의 투표 수를 가진 영화는 160표 이상

@@0@@으로 설정하여 상위 10퍼센트의 영화

Loading output library...

최소 투표 수를 받지 못한 영화는 모두 제거 (90퍼센트가 제거 됨)

Loading output library...
  • 인기 차트에 사람들이 많이 투표한 평점 높은 영화가 추천 됨
  • 쇼생크 탈출, 대부, Dilwale Dulhania Le Jayenge 등의 영화가 최상의 점수를 받음
  • 평점 상으로 Dilwale Dulhania Le Jayenge가 쇼생크 탈출 보다 높지만 투표수가 10분의 1도 안되기 때문에 점수는 더 낮게 책정 됨

=> 단순한 방식이지만 영화 인지도를 봤을 때 어느 정도 그럴듯한 추천 결과가 나옴

  • 미국 커뮤니티 사이트 Reddit에서 인기 댓글을 보여줄 때 Wilson의 Score interval 사용하는 것으로 알려짐
  • 댓글 같은 경우 최신 글 보다는 '좋아요'가 많은 댓글이 이슈를 잘 반영할 수 있음

=> 보통 처음 달린 댓글들에 사람들이 좋아요를 많이 누르고 처음 댓글에 나중에 달리는 댓글이 영향을 많이 받기 때문에 최근 댓글이 중요하지 않을 수 있음

  • 신뢰 구간은 샘플의 크기가 많아질 수록 줄어든 다는 성질을 이용하여 투표 수가 많은 댓글에 점수를 더 주는 방법

Wald test

@@0@@: 각각의 글은 @@1@@의 확률로 좋아요나 싫어요를 받게 됨

@@2@@: 좋아요를 받을 확률

Confidence interval: @@3@@

  • Binomial 분포를 Normal 분포에 근사한 것이기 때문에 sample의 숫자가 많아야 됨
  • 심플하기 때문에 일반적으로 가장 많이 씀
  • 하지만 @@4@@이 1이나 0이 되면 variance 부분이 0이 되서 좋아요만 받은 글이나 싫어요만 받은 글끼리 같은 신뢰구간을 갖게 됨

=> 투표수를 제대로 고려 못하게 됨

Wilson의 Score Interval
Wilson의 방법은 @@0@@를 @@1@@

  • 이 때의 신뢰 구간의 길이는 two sample proportional test보다 짧음

Wilson의 방법의 장점

  • Wilson의 방법은 신뢰 구간의 하한을 통해 정렬하는 방식
  • 신뢰 구간은 샘플이 작아질 수록 줄어들기 때문에 투표를 조금 받은 글은 하한의 값이 작아지게 됨
  • 좋아요의 비중이 높은 글은 평균이 높아지기 때문에 신뢰 구간의 중심이 오른쪽으로 이동

=> 투표의 수와 좋아요의 비중을 동시에 고려할 수 있게 됨

  • two sample proportional test보다 신뢰 구간이 짧아 귀무 가설의 기각을 더 잘하게 됨
  • 두 방법 모두 샘플이 커질 수록 Normal 분포에 수렴한다는 근사적 성질을 이용해야하지만 Wilson의 방법이 더 로버스트함

Wilson과 Wald의 방법 비교

Loading output library...
Loading output library...
  • 좋아요만 10개, 20개,... 1000개 받았을 때 Wald와 Wilson의 방법 비교
  • 파란색은 Wald의 방법으로 샘플 수에 관계없이 획일된 점수를 부여함
  • 주황색은 Wilson의 방법으로 샘플 수가 커질 수록 조금씩 더 큰 점수를 줌
Loading output library...

데이터 소개

  • 인터넷 축구 기사 댓글
  • 해당 사이트에서는 좋아요가 많은 순으로 정렬 후 같은 수의 좋아요를 받은 경우 싫어요가 적은 순으로 위에 노출하는 방식(좋아요가 4개 이하이면 시간순으로 배열)
  • 위 사이트에 Wald와 Wilson의 방법을 적용 하면 댓글 순위가 많이 바뀔까?
Loading output library...

Wald의 방식을 적용했을 때 좋아요만 받은 글은 모두 1점을 받아서 큰 의미가 없음

Loading output library...
  • 좋아요의 비중이 많은 글들이 상위 댓글이 됨
  • 66개의 좋아요를 받으면서 8개의 싫어요를 받은 글이 2등이 됨

=> 원래 2등 글은 4등으로 하락

  • 4개의 좋아요를 받은 글들이 상위 권에 위치하게 됨

=> Sample 사이즈의 크기를 어느정도 반영

  • 투표수에 대한 가중치가 영향을 주기는 하지만 큰 영향을 못 주는 것으로 보임

2. 최신 글일 수록 상위권에 노출하는 방법

#2.-최신-글일-수록-상위권에-노출하는-방법
  • 사람들은 최근에 인기 있는 글에 관심이 많을 수 있음

ex) 위에서 쇼생크 탈출과 같은 고전 영화보다 최근에 인기 있었던 어벤저스 같은 영화를 상위권에 노출하고 싶을 수 있음

  • 특히 커뮤니티 사이트 게시글 같은 경우 최근에 이슈가 되는 글을 인기 글 목록에 추천함
  • 커뮤니티 사이트, 베스트 댓글 등에 이용되는 방법
  • 컴퓨터 사이언스 관련 미국 웹 커뮤니티로 지적 호기심을 충족시켜주는 글이 올라옴
  • 사용자는 글에 댓글 및 좋아요를 누를 수 있지만 싫어요를 누르기 위해서는 어느 정도 포인트가 모여야 됨
  • 게시글 추천 알고리즘

@@0@@

ups: 글에 사람들이 좋아요를 누른 횟 수

downs: 글에 사람들이 싫어요를 누른 횟 수

age: 글을 게시하고 지난 시간=> 글이 오래 될 수록 점수를 낮게 함

gravity: 오래 된 글의 점수가 감소하는 속도 (이 사이트에서는 1.8)로 설정됨

penalty: 관리자가 설정한 규칙에 위반 되면 점수를 낮게함 (예를 들어, 글이 논란이 되거나 자기 자신한테 쓴 글 등), 자세한 내용은 공개 되지 않음

Loading output library...
Loading output library...
  • 게시글은 특성상 대부분의 글이 0~2개의 적은 투표를 받고 극소수의 글이 수 천개의 투표를 받는 양극화 된 분포를 갖음

=> 분자가 linear하게 증가하면 양극화가 심해져 sublinear하게 증가하게 해서 이를 조절

  • 분자의 증가 속도 (0.8)< 분모의 증가 속도(1.8) => 좋아요가 많아도 오래 된 글이면 더 빠르게 점수 감소

=> 최신 글일 수록 더 높은 점수

=> 모든 글의 점수는 시간이 지나면 언젠가는 0이 됨

  • 그림에서 파랑색은 분자에 대한 함수, 주황색은 분모에 대한 함수로 분모에 대한 함수의 증가 속도가 훨씬 빠름을 알 수 있음

데이터 설명

  • 2015년 10월에서 2016년 9월까지 1년 간 Hacker news 게시글
  • 변수

title: 게시글 제목

url: 게시글이 연결된 link

num_points: 좋아요을 받은 수

num_comments: 댓글이 달린 수

author: 게시글 작성자

created_at: 게시글이 작성된 시간

Loading output library...
Loading output library...
Loading output library...
  • 페널티를 적용 안하고 점수를 계산해 본 결과
  • 2시간이 지날 때 마다 페널티 부여
  • '좋아요'를 125개 받은 글이 237개 받은 글이 순위가 더 높음 => 좋아요를 조금 받더라도 최신 글일 수록 훨씬 중요하기 때문

Penalty 적용

  • Hacker's news에서 사용하는 penalty는 미리 운영자가 정해 놓은 rule based 방식을 따름
  • 이중에 알려진 몇몇 방법은 다음과 같음
  • Url 이 없거나 "Ask HN"이라는 항목의 글은 0.4의 페널티
  • Url이 특정 사이트면 0.3의 penalty
  • 댓글이 20개 이상이면서 댓글이 좋아요 보다 많으면 @@0@@로 강한 패널티를 줌 => 논란이 되는 글을 추천하지 않기 위해
Loading output library...
  • 상위 글에서 penalty를 받은 글이 없어 순위가 변하지는 않음

  • 페널티는 점수를 크게 감소시키기 때문에 원하지 않는 글을 노출 시키지 않는데 효과적

  • Ranking의 질을 높일 수 있지만 검열의 목적으로 악용 될 여지가 있음
  • 미국에서 가장 큰 커뮤니티 사이트로 다양한 분야의 정보들이 공유 됨
  • Hacker news는 어느 정도 포인트가 쌓여야 싫어요를 누를 수 있지만 Reddit은 바로 가능
  • 게시글 추천 알고리즘

@@0@@

sign=> 싫어요가 더 많으면 마이너스 점수를 받게 됨

log=> 좋아요와 싫어요의 차이가 클 수록 log 증가하게 됨 (처음 100개의 좋아요가 나중 100개의 좋아요 보다 상승폭이 큼)

age=> 기준점(2005.12.8과의 초 차이) linear하게 증가하기 때문에 앞에 것보다 증가 속도가 빠름

Loading output library...
Loading output library...
  • Hacker News와 마찬가지로 최신글에 점수를 더 많이줌
  • Hacker News에서는 시간이 지나면 모든 글의 점수는 0으로 수렴
  • Reddit은 점수는 변하지 않고 최신 글일 수록 더 높은 점수를 받는 방식
Loading output library...
  • 상위 글에 HN보다 좋아요를 많이 받은 글이 많아짐
  • 시간에 따른 페널티가 HN 알고리즘 보다 약하고 좋아요의 영향력이 훨씬 커짐 (예전 글이 HN보다 많이 노출)
  • HN보다 훨씬 단순

3. 연결성에 초점을 둔 추천 방식

#3.-연결성에-초점을-둔-추천-방식
  • 페이지로 연결 된 링크가 많을 수록 많은 방문자들이 유입될 것이다

=> 많이 연결 된 사이트일 수록 사람들이 관심이 많을 것이다

  • Goolgle의 Page Rank 알고리즘은 페이지에 연결된 링크의 수에 따라 점수화하는 방법

예제 1

Loading output library...
  • 페이지 A,B,C,D가 존재
  • 페이지 B,C,D는 페이지 A로만 연결 돼 있음
  • @@0@@은 A의 page rank로 B, C, D의 페이지 rank의 점수에 의존함
  • @@1@@로 초기의 점수가 동일하다면 다음 단계에서 B,C,D의 방문자는 각각 0.25의 확률로 A로 유입됨
  • @@2@@
  • 따라서 A로 유입될 확률은 0.75 (자기 자신으로 부터의 유입은 무시)

이 과정이 지속 되면

  • @@0@@
  • @@1@@로 두 번째 단계 부터 모든 Page rank가 0이 됨

예제 2

Loading output library...
  • 이제 위와 같이 연결 구조가 더 복잡한 상황에서 보면
  • B는 총 2군데, D는 총 세군데와 연결
  • @@0@@
  • B 페이지와 D 페이지 사용자가 A로 갈 확률이 줄어들어 A의 page rank도 감소함
  • @@1@@
  • @@2@@
  • @@3@@
  • @@0@@
  • @@1@@
  • @@2@@
  • @@3@@

...

점점 모든 값이 0에 가까워짐

일반화

일반화 하면 다음과 같음

@@0@@

Damping Factor

  • 사용자는 언젠가는 클릭을 멈출 것이기 때문에 @@0@@인 damping factor를 도입해서 Page rank가 점차 감소하게 만들음
  • @@1@@
  • damping factor는 솔루션을 unique하게 만드는 기능도 함

Markov Process

  • 결국 이 과정은 이 전 시점의 상태가 다음 시점의 상태에 영향을 주는 형태이기 때문에 Markov process라고 할 수 있음
  • 사이트간의 유입이 영원히 지속되다가 언젠가는 수렴한다는 가정
  • Transition Matrix @@0@@: 홈페이지 j가 홈페이지 i에 연결
  • @@1@@

Updating Rule

Initial value: @@0@@

@@1@@

Stoping rule: @@2@@

예제 3: 구현

Loading output library...
Loading output library...
  • B,C로 직접 연결 된 사이트가 하나씩 밖에 없어 낮음 점수를 받음
  • D,E로 직접 연결된 사이트가 두개 씩이어서 높은 점수
  • A는 직접 하나만 연결 됐지만 E와 연결 돼 있어서 높은 점수를 받은 것으로 보임

4) 실제 데이터에 적용

Loading output library...

데이터 소개

  • Hollins 대학교 홈페이지의 웹사이트 간의 연결 여부
  • 6012개의 웹사이트가 각각 교내 다른 웹사이트에 연결 되어있는지 표시됨
Loading output library...

Outgoing link connection

  • 해당 사이트가 다른 사이트로 향하는 연결이 있는지
  • 1번 사이트는 2,3,4,5, 등의 사이트와 연결
  • 2번 사이트는 26,27,.. 등의 사이트와 연결
Loading output library...
Loading output library...
  • 다른 사이트로의 연결이 가장 많은 사이트는 184개
  • 다른 사이트로의 연결이 없는 사이트가 대부분인 skewed한 분포
Loading output library...

Incoming connection

  • 해당 사이트로 연결하는 사이트의 목록
  • 1번 사이트로 연결하는 사이트는 하나도 없음
  • 2번 사이트로 연결하는 사이트는 1,8,... 등
Loading output library...
Loading output library...
Loading output library...
  • 다른 사이트로 연결이 가장 많았던 1번 사이트가 가장 높은 rank를 받음
  • admission, news, 도서관 관련 사이트가 높은 점수를 받음
  • 점수의 편중이 심함

=> 상위 몇 개 사이트 말고는 사이트끼리 연결이 잘 안 되있음

4. Simple Recommender의 한계

#4.-Simple-Recommender의-한계

단순 인기 기반 추천의 문제점

  • 개인적인 성향을 고려 못함
  • 사람들이 많이 이용한다고 추천할 만한 것은 아님
  • 예를 들어, 해외 여행 중 맛집을 추천해달라고 했는데 맥도날드를 추천
  • 유저 그룹에 따라 성향이 다를 수 있음
  • 예를 들어 10대와 50대가 좋아하는 성향의 음악은 다름