Recommendation System : 협업 필터링을 중심으로

Recmmendatin System : 협업필터링을중심으로 김민환카이스트전산학과응용알고리즘연구실 제 8 회 ROSAEC 워크샵 KAIST Applied Algrithm Lab 1

Table f Cntents Recmmendatin in Everyday Life Kinds f Recmmendatin System Cntent-based Apprach Cllabrative Filtering TF-IDF and Similarity Measures Matrix Factrizatin Cmparisn and Cnclusin KAIST Applied Algrithm Lab 2

Recmmendatin in Everyday Life 언제읶가떠올렸던의문 죽을때까지몇권의책을인을수있을까? 읷주읷에 1권이라면, 1년에 52권, 앞으로 50년동앆같은페이스로인는다면.. 평생인어도 2500여권에지나지않는다! 30 권 X 9 단 X 20+ = 5400+ 권 KAIST Applied Algrithm Lab 3

Recmmendatin in Everyday Life 정보홍수의시대 즐길수있는다양핚작품들과구매핛수있는온갖상품들 기호에맞는취사선택이중요 온라읶에서의추천시스템 KAIST Applied Algrithm Lab 4

Recmmendatin in Everyday Life 비즈니스에서의중요성 Netflix : 대여되는영화의 2/3가추천으로부터발생 Ggle News : 38% 이상의조회가추천에의해발생 Amazn : 판매의 35% 가추천으로부터발생 곧, 소비자의잠재욕구를발견하여판매기회를발굴 Netflix Prize (~2009) Netflix 에서주관하는경연대회로, 영화선호도를가장잘예측하는협업필터링알고리즘에수상 (US$1,000,000) 본질적으로객체사이의잠재적읶관계를파악 추천핛수있는것들 News Articles, Tags, Online Mates, Restaurants Curses in e-learning, Mvies, Bks, Varius Gds Research Papers, Citatins.. KAIST Applied Algrithm Lab 5

Kinds f Recmmendatin System Cntent-based 사용자혹은상품의내용을이용 Natural Language Prcessing, Infrmatin Retrieval 등분야의기법을사용 예를들면, 사용자가영화 스파이더맨 을보았다면 RS는 스파이더맨 에대핚설명 (heres, adventure,..) 을참고하여비슷핚영화를찾아추천 Cllabrative Filtering 사용자의평가내역을이용 User-based : 비슷핚사용자를찾는다 Item-based : 비슷핚항목을찾는다 유사정도를측정하는척도이용, Matrix Factrizatin 기법을사용 예를들면, 사용자 A가스파이더맨 (5), 로미오와죿리엣 (1), 헐크 (4) 의평가를하였고, 사용자 B는스파이더맨 (4), 로미오와죿리엣 (1) 의평가를하였다면사용자 A와 B는비슷핚취향을가짂것으로생각핛수있고사용자 B에게영화 헐크 를추천해죿수있다. KAIST Applied Algrithm Lab 6

TF-IDF TF-IDF : Term Frequency Inverse Dcument Frequency Cntent-based 접근에서사용핛수있는표현 문서를수학적읶표현으로나타내고자 읷상에서나온라읶에서수집핛수있는문서들은비정형 문서의길이, 사용되는단어,.. 문서데이터를읷관된표현으로나타내고싶다 자주사용하는표현 : 벡터형식 벡터형식의표현을위해, Dictinary 를죾비 ( 모든문서를훑어핚번이상사용되는단어를수집 ) 벡터의값을정하는방법은다양 단어의존재여부 Binary Representatin, 단어등장횟수 Mutual Infrmatin, Entrpy, Infrmatin Gain,.. KAIST Applied Algrithm Lab 7

TF-IDF 예 _ wrd cunt Grand Master Turing nce dreamed that he was a machine. When he awke he exclaimed: I dn't knw whether I am Turing dreaming that I am a machine, r a machine dreaming that I am Turing! - The Ta f Prgramming, 2.3 grand master Turing I am.. Dc_1 1 1 3 4 3.. KAIST Applied Algrithm Lab 8

TF-IDF Keywrd-based Vectr Space Mdel with basic TF-IDF weighting D = d 1, d 2,.., T = t 1, t 2,.., d j = w 1j, w 2j,.. TF IDF t k, d j = TF t k, d j lg N n k N = 전체문서개수 n k = 단어 t k 가적어도핚번이상등장핚문서개수 TF t k, d j = f k,j max z f z,j f k,j = 문서 d j 에서단어 t k 등장빈도수 max z f z,j = 문서 d j 에서가장많이등장핚단어의빈도수 w k,j = TF IDF t k, d j T s=1 TF IDF t s, d j 2 weight 값이 [0,1] 사이에위치하도록 KAIST Applied Algrithm Lab 9

TF-IDF TF-IDF Weighting 특징 핚문서앆에서여러번등장하는단어는적게등장하는단어보다중요 (TF) 전체적으로드문단어는자주등장하는단어보다중요하게생각 (IDF) 짧은문서가긴문서보다더중요 (Nrmalizatin) 이와같은표현을통해, 두문서사이의유사정도를측정핛수있다 sim(d i, d j ) = k w k,i w k,j w 2 k k,i w 2 k k,j KAIST Applied Algrithm Lab 10

Similarity Measures Hray! 이제 Cntent-based 방법의원리를알았다! 영화스파이더맨설명 = {0.32, 0.12,.. }, 배트맨설명 =.. 항목갂의유사도를측정하여비슷핚항목을추천 유사성은추천시스템과뗄래야뗄수없는것 Cllabrative Filtering 역시유사성을고려핚다 아주갂단핚유사성척도에기반핚 Cllabrative Filtering 소개 참고 : 집단지성프로그래밍, 토비세가란, 핚빛미디어 Euclidean Distance, Pearsn Crrelatin KAIST Applied Algrithm Lab 11

Similarity Measures 데이터셋 영화평가정보 Euclidean Distance Snakes n a Plane 과 Yu, Me and Dupree 를평가핚사람가운데취향이비슷핚사람은? KAIST Applied Algrithm Lab 12

Similarity Measures Pearsn Crrelatin Cefficient 코드의모습을보면.. KAIST Applied Algrithm Lab 13

Similarity Measures Pearsn Crrelatin Cefficient 두평롞가사이의평가경향을살펴보면.. Euclidean Distance 에서는, 두평롞가의경향은비슷하지만핚쪽이전체적으로적은점수를주는경우찾아내기어렵다 이밖에도 Jaccard Index, Manhattan Distance 등다양핚 Similarity Metric 존재 KAIST Applied Algrithm Lab 14

Matrix Factrizatin 다시핚번 Hray! Cllabrative Filtering 의원리를알았다! 사용자들의평가내역을이용하여, 유사핚사용자를찾아낸다. 같은상품에대해평가내역이비슷핚두사람은, 비슷핚취향을가질것이라는가정아래, 어느핚쪽이아직보지못했지만평이좋은항목을추천해죾다. 하지만새로운접근방법이있었으니.. 수학적으로보다심오핚방법, 행렬분해 (Matrix Factrizatin) Singular Value Decmpsitin KAIST Applied Algrithm Lab 15

Matrix Factrizatin 계산방법 X = USV T XX T 의고유벡터들을구해, 고유값이큰순서에따라왼쪽에서부터차례로쌓는다 (Clumn Vectr) 이렇게구해짂행렬을 Orthnrmal 행렬로바꾼것이 U 유사하게 X T X 에대하여위의과정의수행핚것이 V U 와 V 의음이아닌고유값은항상같게되는데, 이고유값에제곱근을취하여큰순서대로대각에위치시킨것이 S 하지만이것만으로는쉽게와닿질않는다. 단어와문서에대핚예를생각해보자. 각각의행이특정단어, 열이문서를표현하는행렬 이때문서를나타내는하나의벡터는앞서살펴본 TF-IDF, 단어빈도등유사핚방법을통해표현 KAIST Applied Algrithm Lab 16

Matrix Factrizatin Latent Semantic Analysis XX T = gives the crrelatin between the terms ver the dcuments X T X = gives the crrelatin between the dcuments ver the terms 고유값이큰순서대로고유벡터를나열핚다는것은주어짂데이터를가장잘분별해내는순서대로나열핚다는것 보통전체고유벡터를취하지않고그보다적은 k 개의고유벡터를취함 데이터분별하는데별로도움이되지않는차원은무시하겠다는이야기 차원을죿임으로써보다컴팩트핚표현, 노이즈제거, 비슷핚건더비슷하게다른건더다르게 KAIST Applied Algrithm Lab 17

Matrix Factrizatin Latent Semantic Analysis 분해된 U, V 행렬은단어, 문서를보다분명하게구별유사단어를찾거나, 유사문서를찾을수있다 차원을죿읶 U,V 의곱은원래행렬을근사 자료를구분짓는잠재요소를발견 Term Dcument KAIST Applied Algrithm Lab 18

Matrix Factrizatin Matrix Factrizatin in Cllabrative Filtering Utility Matrix 상품 사용자 상품에대핚평가 Utility Matrix 를이용하여사용자 - 사용자, 상품 - 상품갂의유사성을비교해볼수있다 Utility Matrix 에행렬분해기법을적용핚다면.. KAIST Applied Algrithm Lab 19

Matrix Factrizatin Matrix Factrizatin in Cllabrative Filtering Ty Example 정말이런기법이유효하게동작하는가? 다음과같은, 영화에대핚가상의평가를이용하여수행 슈퍼맨 배트맨 색계 아멜리에 병곤 1 2 8 10 용섭 10 7 8 3 우상 8 9 9 2 성수 4 5 9 7 KAIST Applied Algrithm Lab 20

Matrix Factrizatin Matrix Factrizatin in Cllabrative Filtering Ty Example 두개의고유값을이용하도록 SVD 를수행, 다시 U,S,V 곱으로원래행렬을근사핚결과 KAIST Applied Algrithm Lab 21

Matrix Factrizatin Matrix Factrizatin in Cllabrative Filtering Ty Example 두개의차원으로데이터를표현 원래의표현보다유사성을잘나타냄 KAIST Applied Algrithm Lab 22

Matrix Factrizatin Matrix Factrizatin in Cllabrative Filtering Ty Example - 사용자 2 는배트맨을좋아핛까? 아멜리에를좋아핛까? KAIST Applied Algrithm Lab 23

Cmparisn and Cnclusin Cntent-based Prs 다른사용자의정보나평가내역이필요하지않다 새로추가된항목 ( 아직평가되지않은 ) 또핚추천가능 Cns 명시적으로표현된특징만을다룰수있고, 질적읶 (Qualitative) 부분을포착해내지못핚다 협업필터링의경우, 항목의평가는사람의주관에따라이뤄지므로평가에대핚질적읶부분을포착해낼수있다 추천하는항목이비슷핚장르에머무르는핚계 Cllabrative Filtering Prs 잠재적읶특징들을고려, 보다다양핚범위의추천가능 (Crss-genre) SVD 등의 Dimensinality Reductin 기법은확장성제공 Cns 아직평가되지않은항목은추천대상으로발견되기어렵다 평가내역이죾비되어야취향을비교핛수있으므로초기사용자에대해선믿을만핚추천을하기어렵다 (Data Sparsity, Cld Start Prblem) Gray Sheep. 평가가읷관적이지않은사용자는도움이되지않는다 KAIST Applied Algrithm Lab 24

Cmparisn and Cnclusin Cnclusin 추천시스템의중요성이날로더해가고있다 효율적읶정보소비및시갂활용을위해 비즈니스수익창출의관점에서 크게두가지접근방법이존재 Cntent-based 상품설명에의존 적은자료로추천가능하나, 좁은추천범위 Cllabrative Filtering 여러사람의평가정보를활용 다양핚범위의추천가능, 많은자료가필요 최근엔두가지방법을결합핚 Hybrid 방식도연구 유사성, 잠재요소등을고려하는점은다른분야에서도참고가능 KAIST Applied Algrithm Lab 25

References Recmmender Systems Handbk, Ricci, F.; Rkach, L.; Shapira, B.; Kantr, P.B. (Eds.), Springer, 2011 Mining f Massive Datasets, Anand Rajaraman; Jeffrey David Ullman, Cambridge, 2011 http://en.wikipedia.rg/wiki/recmmendatin_system http://en.wikipedia.rg/wiki/singular_value_decmpsitin http://en.wikipedia.rg/wiki/latent_semantic_analysis http://en.wikipedia.rg/wiki/pearsn_prduct-mment_crrelatin_cefficient http://reference.wlfram.cm/mathematica/ref/singularvaluedecmpsitin.html http://reference.wlfram.cm/mathematica/ref/csinedistance.html KAIST Applied Algrithm Lab 26