ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 42, No. 11, pp. 1380-1385, 2015. 11 http://dx.doi.org/10.5626/jok.2015.42.11.1380 협력필터링기반의추천시스템을위한이웃선정전략 (A Strategy for Neighborhood Selection in Collaborative Filtering-based Recommender Systems) 이수정 (Soojung Lee) 요약협력필터링은가장성공적으로사용되는추천시스템의방법으로서, 서적, 음악등다방면의상업시스템에서활용되어왔다. 이러한방법의핵심은사용자에게가장적합한추천인들을선정하는것인데, 이를위하여다양한유사도측정방법이연구되었다. 본연구에서는추천성능의향상을위하여기존의유사도값에근거한추천인선정의문제점을파악하고이의개선책으로서유사도값과공통평가항목수의비율을기준으로하여가변적으로추천인을결정하는방법을제시한다. 실험을통하여다양한기준값에대해성능변화를관찰한결과, 예측성능과추천성능의두측면모두에서제안방법이매우향상된결과를가져왔으며, 특히주어진기준값을만족하는추천인수가적을때에도향상된성능결과를보였다. 키워드 : 협력필터링, 추천시스템, 유사도공식, 인접이웃 Abstract Collaborative filtering is one of the most successfully used methods for recommender systems and has been utilized in various areas such as books and music. The key point of this method is selecting the most proper recommenders, for which various similarity measures have been studied. To improve recommendation performance, this study analyzes problems of existing recommender selection methods based on similarity and presents a method of dynamically determining recommenders based on the rate of co-rated items as well as similarity. Examination of performance with varying thresholds through experiments revealed that the proposed method yielded greatly improved results in both prediction and recommendation qualities, and that in particular, this method showed performance improvements with only a few recommenders satisfying the given thresholds. Keywords: collaborative filtering, recommender system, similarity measure, nearest neighbor 1. 서론 정회원 : 경인교육대학교컴퓨터교육과교수 (Gyeongin National Univ. of Education) sjlee@gin.ac.kr (Corresponding author 임 ) 논문접수 :2015년 6월 29일 (Received 29 June 2015) 논문수정 :2015년 8월 25일 (Revised 25 August 2015) 심사완료 :2015년 8월 26일 (Accepted 26 August 2015) CopyrightC2015 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지제42권제11호 (2015. 11) 정보홍수시대에인터넷에서원하는정보를신속하게검색하기가어려워짐에따라약 90% 의검색결과가사용자가원치않는불필요한정보로밝혀졌다 [1]. 이문제를경감시키기위해사용자선호도에기반한검색결과를제공하는개인화서비스가주목받고있다. 이중가장유명한예는추천시스템으로서, 주로고객이구매하기원하는상품을찾을수있도록도움을주는데사용된다 [2]. 추천시스템의구현방법은크게협력필터링 (collaborative filtering, CF) 과내용기반필터링 (content-based filtering, CBF) 로나뉜다 [3]. CF 방식은유사흥미를가진다른사용자들의선호항목들로부터추천대상자가아직미구매한상품에대한선호도를예측하고, 가장큰
협력필터링기반의추천시스템을위한이웃선정전략 1381 예측치의항목들을추천한다. 한편 CBF는추천대상자가선호했던항목들의특성이나그의프로필을기초로항목을추천한다. 따라서선호했던특성의항목들과다른특성의항목이추천되기어렵다 (overspecialization). 또한새로운사용자나시스템사용이적은사용자에게는적합한추천이어렵다 (new user problem)[3]. 이러한 CBF 방식의문제를해결할수있는방법으로서, CF 시스템은가장성공적인기법으로알려져있으며음악, 서적, 영화등다양한영역에서사용되었다. 이방법의장점은항목특성등의내용은고려하지않고, 다른사용자들의선호여부만을참조하기때문에, 추천대상자가이제껏선호하지않던특성을가진항목이라할지라도, 추천될수있으므로, 새로운특성의항목들을발견할수있다는점이다. 단, 정확한추천을위해서는추천대상자와다른사용자간의흥미유사도를측정하는것이관건인데, 이를위해다양한측정방식이개발되었다 [4-6]. 사용자기반 CF(user-based CF) 시스템에서는두사용자가평가했던항목들의평가등급들을토대로유사도를산출한다. 따라서, 유사도측정은 CF 시스템의성능을결정하는주요척도라고할수있다. 그러나, 현재까지주로사용되는유사도측정방식은 2.2절에서언급한바와같이특정한조건하에서부적절한값을산출하는문제점을갖고있다 [4,7]. 이에본연구에서는이런문제점들을경감시키고자, 기존에천편일률적으로적용하던방식에서벗어나, 사용자간의공통평가이력의정보량에따라가변적으로추천인범위를정하는방법을제시한다. 논문의구성은다음과같다. 2절에서기존유사도측정방식및관련문제점을기술하고, 3절에서제안방법을설명한후 4절에서성능측정실험결과를제시하고, 5절에서논문의결론을맺는다. 2. 배경 2.1 유사도유사도는사용자기반 CF 시스템에서항목추천에참가할이웃들을결정하는데사용된다. 두명의사용자가유사한기호를갖는다면, 새로운항목에대해서도유사한반응을보일것이라고가정하기때문이다. 사용자들이부여하였던모든등급이력을보관하고, 공통평가항목에대해부여하였던등급들을토대로사용자간유사도를계산하고, 가장높은유사도의사용자들을인접이웃으로정의한다. 새로운항목을추천하기위하여, 그항목에대해현사용자가부여할등급을예측하는절차를진행하는데, 이때 NN에속한사용자가부여한평가등급과그사용자와의유사도값을토대로예측치를결정한다. 만약새로운항목에대한평가이력이없다면, 그러한항목은당연히예측치 를산출할수없고따라서추천이불가능하다. 이는협력필터링의특성으로인해발생되는근본적인문제 (new item problem) 이다 [3]. 모든새로운항목에대해예측치를결정하고, 그들중에서최고값에해당하는항목을추천하게된다. 구체적으로, 사용자 u가항목 x에대해부여할평가예측치, 는대개다음의 Resnick's formula에의해 산출한다 [8]. 이때, 는 u의평균평가치, sim(u, v) 는사용자 u와 v 간의유사도값, r v,x 는사용자 v의항목 x에대한평가치, 는 u의인접이웃집합이다. 위와같이평가예측치를결정하기위해우선유사도값에근거하여인접이웃집합을결정하고, 각이웃의평가치를참조하는데있어서도유사도값크기에비례하는가중치를둔다. 따라서, 시스템성능에유사도는절대적역할을함을알수있다. 현재까지사용되는주요측정방법으로는 Pearson 상관도 (COR), cosine similarity (COS), adjusted cosine, constrained Pearson 상관계수, 스피어만순위상관계수, MSD(Mean Squared Difference) 등이있다. 2.2 유사도산출방식의문제점기존의주요유사도측정방식들의문제점을분석한연구결과에서는주요방식인 COR와 COS 방식을다루었다 [4,7]. 예로서, 두사용자의공통평가항목이단하나일때, COS는 1의값, COR는계산불가가되는문제점이있다. 또한공통항목들이다수일지라도, 사용자가이들에대해각각동일한등급을부여한다면유사한결과를초래한다. 즉, 공통항목들모두에대해서한사용자가 a의값, 또다른사용자가 b의값 (a b) 을부여한다면, COS는가장큰값인 1을산출하게된다. 물론이러한예는매우드물지만, 공통항목개수가적을수록이같은현상의발생가능성은커진다. 따라서새로운사용자나시스템의초기단계에서일어날수있는유사도관련문제점을해결하기위한연구가진행되어왔다 [9]. 3. 제안방법 3.1 유사도와 Jaccard Index 의관계 2.2절에서언급한문제점을조사하기위해공통평가항목수와유사도와의관계를살펴보았다. 공통평가항목수는 Jaccard Index(J) 로서측정하였는데, 를사용자 u 가평가한항목집합이라고할때, 사용자 u와 v간에아래와같이산출한다 [10]. (1)
1382 정보과학회논문지제 42 권제 11 호 (2015. 11) Pearson correlation 표 1 피어슨상관도의각구간별 Jaccard index 평균 Table 1 Average Jaccard index per interval of Pearson correlation [0, 0.1) [0.1, 0.2) [0.2, 0.3) [0.3, 0.4) Average Jaccard index 0.100 0.119 0.121 0.110 0.093 0.070 0.656 0.577 0.049 0.044 0.033 [0.4, 0.5) [0.5, 0.6) [0.6, 0.7) [0.7, 0.8) [0.8, 0.9) [0.9, 1.0) 1.0 그림 1 각유사도구간에속하는사용자쌍의 Jaccard index 분포 Fig. 1 Distribution of Jaccard index of user pairs per similarity interval 일반적으로매우유사한두사용자간에는 J 값이클것으로기대된다. 그림 1은 MovieLens 데이터셋 [11] 을이용한실험결과로서, COR의각구간별로 J 분포를나타냈다. 대개 J<0.05인사용자쌍의비율이가장높고, [0.05, 0.1) 에속하는비율이그다음이었다. COR=1.0인경우, 뜻밖에도 J<0.05인비율이 0.85나되었다. 이는공통평가항목비율이매우낮은데도유사도는더큰경우가더많다는의미로서, COR 값에대한신뢰를저하시키는것이고이런경향은 COS나 MSD에대해서도나타났다. 표 1은각 COR 구간별 J값의평균을제시하였다. 위실험과는반대관점에서또다른실험을하였는데그림 2에각 J 구간별로 COR 분포를나타냈다. 각 J 구간의공통적인특성은유사도가낮아질수록대개그에속한사용자쌍의비율이증가추세를보이다가매우낮은유사도 (<0.2) 일때는다소감소한다는것이다. 대개 J 구간을막론하고 0.4 미만의유사도를가진사용자쌍의비율이가장높았다. 특이한점은 [0, 0.1) 의 J 구간에서는유사도가 1인사용자쌍의비율이 0.1 정도로서다른구간에서보다더욱높다는사실이다. 표 2에각 J 구간별 COR 평균을참고로제시하였다. COS을이용한실험에서도 [0, 0.1) 의 J 구간에서만은유사도가 1인비율이 0.16으로써매우높았고, 다른 J 구간에서는약 0의비율을보이는것과대조적이었다. 이는공통항목개수가매우적을때두사용자가같은평가를부여할확률이높기때문이고, 또다른이유로는 2.2절에서 그림 2 Jaccard index(j) 구간별유사도값의분포 Fig. 2 Distribution of similarity per Jaccard index (J) interval 표 2 Jaccard index 구간별피어슨상관도 (COR) 의평균 Table 2 Average Pearson correlation per Jaccard index interval Jaccard [0, 0.1) [0.1, 0.2) [0.2, 0.3) [0.3, 0.4) [0.4, 0.5) index Average COR 0.444 0.270 0.233 0.256 0.313 언급한바와같이유사도산출공식의본질적문제점때문이라고할수있다. 결론적으로, 공통평가항목비율이낮은데도불구하고매우높은유사도를갖는다면, 기대와는달리그러한인접이웃이평가한새로운항목의등급은현사용자에게부정확할확률이크고, 또한식 (1) 에서높은유사도의인접이웃은큰비중을가지므로, 시스템의추천정확도를저하시킬수있다. 또한그림 2에제시한바와같이이러한경우가 10% 를넘어적지않은비율이므로더욱대책이필요하다. 3.2 예측정확도실험유사도가높은데 J 값이작은것이문제가되는이유는그러한관계를보이는인접이웃의평가예측치가부정확할것이기때문이다. 이를확인하기위해, 유사도종류별로 J 값의변화에따라평균평가등급의차이 (Mdiff) 는어떠한분포를나타내는지알아보았다. 유사도가크고 J도큰사용자간의평가등급차이는작을것으로기대된다. 그림 3은유사도 0.7 이상의사용자쌍의 J값변화에따른 Mdiff 분포를여러유사도구간별로나타냈다. COR, COS, MSD를이용해실험한결과, 예상대로유사도구
협력필터링기반의추천시스템을위한이웃선정전략 1383 그림 3 유사도구간별 Jaccard index 에따른평균평가등급차이의분포 Fig. 3 Distribution of mean rating difference with varying Jaccard index per similarity interval 간에무관하게 J가증가할수록대체로 Mdiff는감소했다. 특히, 유사도 <1.0일때 COR가가장큰감소를보였고, COS=1.0일때 J 값의영향이가장컸다. 그림에서 J 값이특정값이상일때데이터가누락된경우는그에해당하는경우의사용자쌍이없었기때문이다. 결과적으로, 같은유사도값일지라도 J 값이커짐에따라두사용자의평가치가더욱서로근접하게됨을알수있다. 3.3 평가예측치산출방법앞에서설명한사전실험내용을적용하여, 본연구에서는인접이웃의선정에있어서평가예측치의정확도를향상시키는방법을제안한다. 주요아이디어는유사도가크고, J 값또한큰인접이웃들만을예측치결정에이용하는것이다. 그러나, 이러한조건에맞는이웃들숫자가부족할때는기존방법대로유사도값만을기준으로인접이웃을선정한다. 이경우엔일반적인다수의인접이웃의평가치를총괄적으로참조하는것이예측성능향상에이로울것이기때문이다. 다음절에서는주어진두조건을만족하는이웃수의변화에따라성능이어떻게달라지는지, 또한기존방식의성능과어떤차이를보이는지실험을통해알아보았다. 결론적으로, 제안방법은사용자의인접이웃과의유사도및 J 값에따라평가치참조군을결정하는전략이다. 제안방법을구체적으로그림 4에기술하였다. 4. 실험 4.1 실험배경제안방법의성능을알아보기위해, 관련연구에서널리쓰이는 MovieLens 데이터셋 [11] 으로 COR, COS, MSD에대해실험하였다. MovieLens는 943명이 1682 개의영화중 20개이상에대해 1 5까지의점수를부여한집합이다. 평가개수는총 100,000로서희소성수준 1) 은 0.937이다. 높은신뢰도의결과산출을위해 5회 1) sparsity level=1-100,000/(943 1682) 표 3 각유사도종류별 threshold (simt) Table 3 Threshold for each similarity type (simt) COR COS MSD 0.5 0.95 0.9 크로스확인후평균을구하였고, 각회마다훈련과시험데이터비율은 8:2로하였다. 훈련데이터를통해인접이웃들을구하였고, 이들의평가등급으로예측평가등급을산출하였다. 성능평가를위해기존에널리사용되는 MAE (Mean Absolute Error) 와 F1을도입하였다. 전자는예측성능을위한것으로서평가예측치와실제치차이의절대값평균이므로, 작을수록좋다 [3]. 후자는추천성능의척도로서 precision(p) 과 recall(r) 의조화평균, F1(2PR/(P+R)) 로계산된다 [12]. P는시스템의추천항목들중사용자선호항목들의비율을나타내며, R은사용자의전체선호항목들중시스템이추천한항목들의비율이다. 본실험에서는평가등급이 4 이상이면선호항목으로간주하였다. 3.3절에서언급한두 threshold의최적값을알아보기위해, 우선 sim T 만을다양하게변화시켜사전실험한결과표 3에제시한값에대해서가장좋은 MAE 결과를보였다. 따라서, 이후실험에서 sim T 값은표 3의값으로고정하고, J T 값을변화시켜, 기존방식과의성능차이를알아보았다. 4.2 실험결과그림 4의 S 와 J T 값의변화에따른제안방법의성능을평가하였다. 세가지유사도공식을이용하되제안방법을적용한실험결과는각유사도공식이름에 -T 를붙여표기하였다. 그림 5는 J T 값을범례에표시된각각의값으로고정하였을때, S 가증가함에따른 MAE 성능의변화를살펴본것이다. 기존방식의실험에서는 S 와동일한수의인접이웃을유사도가높은순서대로선택하여그들의평가치를참조하여예측치를결정하였다. N_T의변화가아닌 S 변화에따라실험
1384 정보과학회논문지제 42 권제 11 호 (2015. 11) 그림 4 제안된평가치예측방법 Fig. 4 Proposed method for rating prediction 결과를산출한이유는, 특정값 (N_T) 이상의모든 S 에대해서가아닌각 S 에대해서성능비교함으로써그효과를좀더상세히알수있을것이기때문이다. 즉, 실험의목적은적정 N_T 값을결정하는데있지않고 S 에속한인접이웃수에따른성능향상정도를파악하기위함이다. 또한, 그림 4의 4단계인 else 조건에해당하는경우들에대해실험결과를산출하지않았는데, 그이유는 else 조건내용은기존과동일한방법으로인접이웃을구하는것이므로실험결과가기존과동일할것이기때문에, 제안방식의효과가적용되는부분에대해서만결과를산출함으로써그성능효과를면밀히살펴보기위함이다. 그림 5에서유사도종류에관계없이결과패턴이대개유사한데 S 가증가할수록기존방식이나제안방식모두 MAE가감소하는이유는더욱많은인접이웃들을참조함으로써오차가감소되기때문이다. 또한 J T 가증가할수록 MAE는특히 COS-T와 MSD-T에서상대적으로더욱크게감소하는데, 이는공통평가항목비율이높은이웃의참조치가더욱이롭게작용하기때문이다. COR-T의경우에 J T=0.15와 S >20일때 MAE는오히려증가하는데, 이는다른두유사도종류와는다르게, 이경우에해당하는경우수가적어서일반화된결과치를얻을수없었기때문이다. 결론적으로제안방식을따르면 MAE가최대약 10~13% 의감소율을보였다. J T 값이다를때 COR 그래프가동일한결과가나오지않은이유는, 해당조건에부합하는사용자쌍에대해서실험결과를산출하였기때문이다. 즉, J T=0.1인경우그조건을만족하는사용자쌍, J T=0.15인경우도그조건을만족하는사용자쌍을대상으로결과를산출하였기때문이다. 이렇게대상을달리한이유는 COR-T 결과산출대상과동일한사용자쌍을고려함으로써 COR와 COR-T의성능비교를동일한조건에서하기위함이다. 그림 6은 F1 성능결과를나타낸다. S 가증가함에따라 F1 성능은예상대로점차향상되는데, 유사도종류와무관하게 S 값이작을때가장큰 J T 값에대한결과는다른값의 J T 결과와대체로비등한성능을보였다. 그러나, 가장큰 J T 값에대한성능결과는 S 값의증가에따라 (MSD일경우 S =35까지 ) 향상속도가가장큼을주목할수있다. 이는공통평가항목비율이높은인접이웃들이많을때성능이가장크게향상됨을의미한다. 단, J T=0.25에대한 MSD 실험에서 S =40일때성능이하락한것은그처럼높은유사도와 Jaccard 값을만족하는 그림 5 제안방법과기존방법의 MAE 성능비교 Fig. 5 Comparison of MAE performance between the proposed and previous methods
협력필터링기반의추천시스템을위한이웃선정전략 1385 그림 6 제안방법과기존방법의 F1 성능비교 Fig. 6 Comparison of F1 performance between the proposed and previous methods 인접이웃 ( 유사도 0.9, Jaccard 0.25) 의수가 40이되는경우가매우드물어, 일반화된결과를얻기에부족하기때문인것으로파악된다. 결론적으로, S =40일경우에유사도종류에관계없이제안방법은약 7~19% 의향상률을보였고, 가장큰효과는약 11~19% 의향상률을보인 MSD-T에서나타났다. 주목할점은 S =5처럼작은인접이웃수만을참조할때에도 J T=0.1일경우제안방법은기존보다약 7~8% 의성능향상을보인점이다. 5. 결론 본연구에서는협력필터링기반의추천시스템의성능향상을위해기존에유사도값만으로결정한인접이웃선정방식을개선하는방법을제안하였다. 유사도값외에공통평가항목비율을기준으로하여평가치참조에필요한인접이웃군을결정하고, 이들값이주어진기준에미달할경우에는기존대로유사도값만을기준으로하여인접이웃을결정하므로, 제안방법은개인별로다른참조군이결정되도록하는방식이다. 다양한기준값에대해성능변화를실험관찰한결과, 예측성능과추천성능모두에서제안방법이매우향상된결과를가져왔으며, 특히주어진기준값을만족하는인접이웃의수가적을때에도향상된성능결과를보였다. References [1] D. Arotaritei and S. Mitra, "Web Mining: A Survey in the Fuzzy Framework," Fuzzy Sets and Systems, Vol. 148, No. 1, pp. 5-19, 2004. [2] D. Jannach, Z. Karakaya, and F. Gedikli, "Accuracy Improvements for Multi-criteria Recommender Systems," Proc. of the ACM Conf. Electronic Commerce, pp. 674-689, 2012. [3] G. Adomavicius and A. Tuzhilin, "Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-art and Possible Extensions," IEEE Trans. Knowledge & Data Engineering, Vol. 17, No. 6, pp. 734-749, 2005. [4] H. J. Ahn, "A New Similarity Measure for Collaborative Filtering to Alleviate the New User Coldstarting Problem," Information Sciences, Vol. 178, No. 1, pp. 37-51, 2008. [5] B. Jeong, J. Lee, and H. Cho, "Improving Memorybased Collaborative Filtering via Similarity Updating and Prediction Modulation," Information Sciences, Vol. 180, No. 5, pp. 602-612, 2010. [6] H. Liu, et al., "A New User Similarity Model to Improve the Accuracy of Collaborative Filtering," Knowledge-Based Systems, Vol. 56, pp. 156-166, 2014. [7] S. Lee, "A Rank-based Similarity Measure for Collaborative Filtering Systems," Journal of KACE, Vol. 14, No. 5, pp. 97-104, 2011. (in Korean) [8] P. Resnick, et al., "GroupLens: An Open Architecture for Collaborative Filtering of Netnews," Proc. of the ACM Conf. Computer Supported Cooperative Work, pp. 175-186, 1994. [9] J. Bobadilla, F. Ortega, A. Hernando, and J. Bernal, "A Collaborative Filtering Approach to Mitigate the New User Cold Start Problem," Knowledge-Based Systems, Vol. 26, pp. 225-238, 2011. [10] G. Koutrica, B. Bercovitz, and H. Garcia, "FlexRecs: Expresing and Combining Flexible Recommendations," Proc. of the ACM SIGMOD Int'l Conf. on Management of data, pp. 745-758, 2009. [11] MovieLens, [Online]. Available: http://movielens.umn. edu [12] M. Gao, Z. Wu, and F. Jiang, "Userrank for Itembased Collaborative Filtering Recommendation," Information Processing Letters, Vol. 111, No. 9, pp. 440-446, 2011. 이수정 1985년이화여자대학교수학교육과. 1990 년 Texas A&M 대학교컴퓨터과학과 ( 석사 ). 1994년 Texas A&M 대학교컴퓨터과학과 ( 박사 ). 1994년~1998년삼성전자통신개발실선임연구원. 1998년~ 현재경인교육대학교컴퓨터교육과교수관심분야는컴퓨터교육, 추천시스템, 정보필터링